`

经典面试题

    博客分类:
  • java
阅读更多
接触到一个经典的面试题:类似于背包最优解的问题, 原题如下
import java.util.List;


public class SplitOrders {
    

    public class Item{
        
        /**
         * 卖家用户id
         */
        long sellerId;
        
        /**
         * 商品价格,单位分
         */
        long price;
    }
    
    public class Order{
        
        /**
         * 该订单对应的商品
         */
        List<Item> orderItems;
        
        /**
         * 该订单金额,单位分
         */
        long totalPrice;
        
        /**
         * 该订单对应的卖家userId
         */
        long sellerId;
    }
    
    
    /**
     * 根据购物车的商品,生成相应的交易订单,根据如下规则
     * 1.每笔交易订单可以有多个商品
     * 2.每笔交易订单的商品只能是同一个卖家
     * 3.每笔交易商品的总价格不能超过1000元 
     * 4.生成的交易订单数量最小
     * @param items:购物车所有商品
     */
    public List<Order> packageItemsToOrders(List<Item> items){
        
        return null;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

}


其实就是一个最优拼单的问题
我的解决思路就是尽量的让一个订单金额趋向于1000,比较简单粗暴
具体思路
1.按照不同卖家进行分组
2.核心原则:通过凑单的方式,将每个订单的总金额趋向1000
将卖家下的商品列表按照价格排序 拆分为一个低价商品列表(升序) 高价商品列表(降序),
3.最高价商品+最低价商品,如果大于1000,将最商品单独高价 作为一个订单,移除列表,最低价商品放回列表,重复上述操作
4.最高价商品+最低价商品,如果小于1000,循环获取低价列表,与之前结果相加,大于1000则终止,小于1000则继续,
每次获取列表的商品都会通过remove方法,如果商品拼单失败就会原位置放回列表


具体代码如下
// 按照卖家进行分组
 public List<Order> separationItems(List<Item> items) {
        Map<Long, List<Item>> map = new HashMap<>();
        /**
         * 按照卖家进行分组,
         */
        for (Item item : items) {
            Long sellId = item.sellerId;
            List<Item> sellerList = map.get(sellId);
            if (sellerList == null || sellerList.size() == 0) {
                sellerList = new ArrayList<>();
            }
            sellerList.add(item);
            map.put(sellId, sellerList);
        }
        List<Order> res = new ArrayList<>();
        /**
         * 以卖家为单位,合并订单
         */
        for (Long sellId : map.keySet()) {
            List<Order> orderMergeRes = mergeItems(sellId,map.get(sellId));
            res.addAll(orderMergeRes);
        }
        return res;
    }


    /**
     * 商品列表合并操作
     * 尽量保证每个订单的总额无限接近1000,将最高价格商品与最低价格相加,如果大于1000
     * 则任务最高价格商品智能
     * 以下面为例
     * 12,34,45,67,222,555,777,888,999
     * 1.999+12,大于1000,则 999 独立为一个订单
     * 2.继续将888+12,小于1000,则继续+34,大于1000,将888 34 合并作为一个订单
     *
     * @param lessThenT
     * @return
     */
        public List<Order> mergeItems(Long sellId, List<Item> lessThenT) {
             Collections.sort(lessThenT);
            int len = lessThenT.size();
            int flag = len % 2 == 0 ? len / 2 : len / 2 + 1;
            // 保存低价商品列表 从小到大排序
            List<Item> minList = new ArrayList<>();
            // 保存高价商品列表 从大到小
            List<Item> maxList = new ArrayList<>(lessThenT);
            for (int i = 0; i < flag; i++) {
                minList.add(lessThenT.get(i));
                maxList.remove(0);
            }
            Collections.reverse(maxList);
            List<Order> orderList = new ArrayList<>();
            redo:
            while (maxList.size() > 0) {
                Item max = maxList.remove(0);
                Item min = minList.size()==0?null:minList.remove(0);

                /**
                 * 最高价格商品 无法与其他商品合并为一单
                 * 或当前低价格已经被消耗完了
                 */
                if ((min == null || max.price + min.price > 1000)) {
                    /**
                     * 合并失败,将商品还回到原处
                     */
                    if(min != null){
                        minList.add(0, min);
                    }
                    List<Item> tmp = new ArrayList<>();
                    tmp.add(max);
                    Order order = new Order();
                    order.orderItems = tmp;
                    order.totalPrice = max.price;
                    order.sellerId = sellId;
                    orderList.add(order);
                    continue;
                } else {
                    /**
                     * 如果当前最高价格可以与最低价格合并,则再尝试 与次低价格商品合并
                     */
                    List<Item> tmp = new ArrayList<>();
                    tmp.add(max);
                    tmp.add(min);
                    Long total = max.price + min.price;
                    redoLow:
                    while (minList.size() > 0) {
                        Item minSecond = minList.remove(0);
                        if ((total + minSecond.price) > 1000) {
                            minList.add(0, minSecond);
                            Order order = new Order();
                            order.orderItems = tmp;
                            order.totalPrice = total;
                            order.sellerId = sellId;
                            orderList.add(order);
                            // 高价商品提前消耗完了 將低价商品列表 拆分 重复上一步
                            if (maxList.size() == 0 && minList.size() > 0) {
                                maxList.add(0, minList.remove(minList.size() - 1));
                            }
                            continue redo;
                        } else {
                            tmp.add(minSecond);
                            total = total + minSecond.price;
                        }
                        // 低价商品提前被消耗完,将最小的 高价格商品移除到低价格中
                        if (minList.size() == 0 && maxList.size() > 0) {
                            minList.add(0, maxList.remove(maxList.size() - 1));
                            continue redoLow;
                        }
                    }
                    Order order = new Order();
                    order.orderItems = tmp;
                    order.totalPrice = total;
                    order.sellerId = sellId;
                    orderList.add(order);
                }
            }
            return orderList;
        }



分享到:
评论

相关推荐

    java经典面试题

    ### Java经典面试题知识点 #### Java数据结构容器 - **核心知识点**:Java集合框架,包括List、Set、Map等接口及其实现类。List接口代表有序的集合,例如ArrayList和LinkedList;Set接口代表不允许重复元素的集合,...

    嵌入式经典面试题嵌入式经典面试题

    "嵌入式经典面试题" 本文总结了嵌入式系统开发中经典的面试题,涵盖了预处理指令、宏定义、条件编译、错误处理、死循环、数据声明等知识点。 1. 用预处理指令#define声明一个常数 预处理指令#define可以用来声明...

    120个Java经典面试题和答案

    以下是一些基于标题和描述中提到的Java经典面试题及对应的知识点详解: 1. **Java基础** - **数据类型**:Java有8种基本数据类型,了解它们的存储大小和范围,以及如何进行类型转换。 - **变量与常量**:理解变量...

    各公司经典面试题选取

    ### 各公司经典面试题选取知识点总结 #### 一、面试题目的背景及意义 面试题目不仅是考察应聘者的基础知识掌握程度,更重要的是通过这些问题来评估求职者的逻辑思维能力、解决问题的能力以及团队合作精神。本篇...

    C ++经典面试题,C ++经典面试题

    下面,我们就来详细探讨一下C++经典面试题所涵盖的知识点。 首先,C++的基础部分通常包括以下几个方面: 1. **变量与数据类型**:理解不同类型的变量(如int, float, double, char等)以及它们的存储需求和运算...

    vue20道经典面试题,由初级到中高级

    Vue经典面试题汇总 本文总结了 Vue 中的经典面试题,涵盖了 Vue 生命周期、Vue Router 导航钩子、SCSS/LESS 预编译、Vuex 状态管理、导航钩子、组件传值、父子组件调用方法等多方面的知识点。 1. Vue 生命周期 在...

    Python经典面试题-总结

    Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...

    java工程师社招经典面试题

    java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java...

    前端75道经典面试题.rar

    "前端75道经典面试题.rar"这个压缩包提供了互联网大厂常问的75道前端面试题,覆盖了基础到进阶的多个层面,是提升你面试能力的理想资料。以下是一些可能包含在这些面试题中的关键知识点: 1. **HTML与CSS**: - ...

    SQL经典面试题及答案SQL经典面试题及答案

    SQL经典面试题及答案 从给定的文件信息中,我们可以总结出四个重要的SQL知识点: 一、使用GROUP BY语句来统计分类结果 在给定的部分内容中,我们可以看到一个经典的SQL面试题,即如何使用GROUP BY语句来统计分类...

    sqlserver 经典面试题

    【SQLServer经典面试题详解】 在SQLServer面试中,掌握基本的SQL语法和高级查询技巧是至关重要的。以下是一些常见的面试重点: 1. **DDL(数据定义语言)**:包括CREATE, ALTER, DROP和DECLARE等命令,用于创建、...

    10万字208道Java经典面试题总结(附答案).pdf

    这份10万字的PDF文档包含了208道Java经典面试题,旨在帮助开发者们系统地复习和提升自己的技能,以应对包括阿里、腾讯、字节跳动、京东等知名互联网公司的面试。以下是部分题目及其涉及的知识点: 1. **JDK和JRE的...

    c语言经典面试题

    ### C语言经典面试题知识点解析 #### 预处理器(Preprocessor) **1. 定义一年中的秒数常量** - **知识点**: 使用`#define`声明常量、理解预处理器行为、处理整型溢出问题。 - **解析**: 本题主要考察应聘者对`#...

    经典sql语句(SQL经典面试题及答案,某外企SQL Server面试题L)

    本资源“经典sql语句”聚焦于SQL的经典面试题及其解答,旨在帮助求职者特别是针对SQL Server岗位的应聘者准备面试。以下将详细解析SQL的一些核心知识点,并结合可能的面试问题进行阐述。 1. **选择查询(SELECT)**...

    C&C++经典面试题

    【C&C++经典面试题】涉及的知识点广泛,主要涵盖了C和C++语言的基础、操作系统原理、并发编程、面向对象编程、数据结构、调试工具、数据库理论和网络编程等多个方面。下面将对这些知识点进行详细解释: 1. **进程间...

    vue经典面试题及答案.rar

    vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典...

    C_经典面试题及答案

    《C#经典面试题及答案解析》 在IT行业的面试中,C#作为.NET框架的核心语言,其相关的知识和技能常常是面试官考察的重点。本文将围绕C#的几个关键概念——委托、事件、控件遍历以及排序算法进行深入探讨,并提供相应...

Global site tag (gtag.js) - Google Analytics