- 浏览: 16460 次
- 性别:
- 来自: 上海
文章分类
最新评论
接触到一个经典的面试题:类似于背包最优解的问题, 原题如下
其实就是一个最优拼单的问题
我的解决思路就是尽量的让一个订单金额趋向于1000,比较简单粗暴
具体思路
1.按照不同卖家进行分组
2.核心原则:通过凑单的方式,将每个订单的总金额趋向1000
将卖家下的商品列表按照价格排序 拆分为一个低价商品列表(升序) 高价商品列表(降序),
3.最高价商品+最低价商品,如果大于1000,将最商品单独高价 作为一个订单,移除列表,最低价商品放回列表,重复上述操作
4.最高价商品+最低价商品,如果小于1000,循环获取低价列表,与之前结果相加,大于1000则终止,小于1000则继续,
每次获取列表的商品都会通过remove方法,如果商品拼单失败就会原位置放回列表
具体代码如下
// 按照卖家进行分组
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; }
发表评论
-
知识点
2017-11-13 18:16 0happen befor: 线程 star before 线程 ... -
ConcurrentHashMap 精髓
2017-11-02 15:13 0ConcurrentHashMap 精髓: 1.s ... -
java condition await() 与object wait()的区别
2017-09-07 14:42 2763java condition await() 与object ... -
一致性HASH
2016-11-10 15:54 0在我们做分布式的时候,难免会有一个路由的过程,比如说redis ... -
JVM stop the world
2016-11-09 23:03 444JVM 在进行GC的时候,需要做两个事情,一个是GC root ... -
java Thread 解析
2016-10-27 21:31 0/* * Copyright (c) 1994, 20 ... -
悲观锁 乐观锁,公平锁,非公平锁
2016-10-27 13:55 0悲观锁 乐观锁,公平锁,非公平锁 d 他们的区别 悲观锁与乐 ... -
java LockSupport
2016-10-26 20:33 0/* * ORACLE PROPRIETARY/CONFI ... -
AbstractQueuedSynchronizer 的 CLH
2016-10-26 09:19 0/** * Wait queue node ... -
java 中的wait 与 await
2016-10-25 20:16 0java中wait() 与 await() wait() 方 ... -
java中内存泄漏
2016-09-01 07:43 551内存泄漏(memory leak):该被回收的对象没有被回收, ... -
线程性能与可伸缩性
2016-08-25 23:06 0对性能的思考 性能与可伸缩性 评估各种性能的权衡因素 am ... -
怎么平衡线程并发中的活跃性和安全性
2016-08-25 23:02 0线程的活跃性 活跃性:线程的处理速度 安全性:加锁保证数据的正 ... -
java线程的取消和关闭
2016-08-25 22:55 0java的线程取消和关闭 在正常的业务操作中,碰到进行中的任 ... -
Java 线程池
2016-08-25 09:24 0线程池工作原理 线程池的原理解析 线程池代码解析 -
研发分级
2016-07-27 11:54 0研发分级 今天老大问了一个问题:怎么区分 -
java并发详解
2016-08-31 07:34 577线程安全 1.什么是并发? 2.什么是线程安全 3.如何保证线 ... -
编程建议(持续更新)
2016-07-18 11:01 3671.UML的重要性,推荐plant ... -
java学习路线图
2016-07-14 22:56 640这么长的时间,么有好好总结过自己的学习路线,今天和大家一起分享 ... -
threadLocal的使用场景--事务下的日志记录
2016-07-02 16:04 2864threadLocal在系统中的使 ...
相关推荐
### Java经典面试题知识点 #### Java数据结构容器 - **核心知识点**:Java集合框架,包括List、Set、Map等接口及其实现类。List接口代表有序的集合,例如ArrayList和LinkedList;Set接口代表不允许重复元素的集合,...
"嵌入式经典面试题" 本文总结了嵌入式系统开发中经典的面试题,涵盖了预处理指令、宏定义、条件编译、错误处理、死循环、数据声明等知识点。 1. 用预处理指令#define声明一个常数 预处理指令#define可以用来声明...
以下是一些基于标题和描述中提到的Java经典面试题及对应的知识点详解: 1. **Java基础** - **数据类型**:Java有8种基本数据类型,了解它们的存储大小和范围,以及如何进行类型转换。 - **变量与常量**:理解变量...
### 各公司经典面试题选取知识点总结 #### 一、面试题目的背景及意义 面试题目不仅是考察应聘者的基础知识掌握程度,更重要的是通过这些问题来评估求职者的逻辑思维能力、解决问题的能力以及团队合作精神。本篇...
下面,我们就来详细探讨一下C++经典面试题所涵盖的知识点。 首先,C++的基础部分通常包括以下几个方面: 1. **变量与数据类型**:理解不同类型的变量(如int, float, double, char等)以及它们的存储需求和运算...
Vue经典面试题汇总 本文总结了 Vue 中的经典面试题,涵盖了 Vue 生命周期、Vue Router 导航钩子、SCSS/LESS 预编译、Vuex 状态管理、导航钩子、组件传值、父子组件调用方法等多方面的知识点。 1. Vue 生命周期 在...
Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...
java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java工程师社招经典面试题java...
"前端75道经典面试题.rar"这个压缩包提供了互联网大厂常问的75道前端面试题,覆盖了基础到进阶的多个层面,是提升你面试能力的理想资料。以下是一些可能包含在这些面试题中的关键知识点: 1. **HTML与CSS**: - ...
SQL经典面试题及答案 从给定的文件信息中,我们可以总结出四个重要的SQL知识点: 一、使用GROUP BY语句来统计分类结果 在给定的部分内容中,我们可以看到一个经典的SQL面试题,即如何使用GROUP BY语句来统计分类...
【SQLServer经典面试题详解】 在SQLServer面试中,掌握基本的SQL语法和高级查询技巧是至关重要的。以下是一些常见的面试重点: 1. **DDL(数据定义语言)**:包括CREATE, ALTER, DROP和DECLARE等命令,用于创建、...
这份10万字的PDF文档包含了208道Java经典面试题,旨在帮助开发者们系统地复习和提升自己的技能,以应对包括阿里、腾讯、字节跳动、京东等知名互联网公司的面试。以下是部分题目及其涉及的知识点: 1. **JDK和JRE的...
### C语言经典面试题知识点解析 #### 预处理器(Preprocessor) **1. 定义一年中的秒数常量** - **知识点**: 使用`#define`声明常量、理解预处理器行为、处理整型溢出问题。 - **解析**: 本题主要考察应聘者对`#...
本资源“经典sql语句”聚焦于SQL的经典面试题及其解答,旨在帮助求职者特别是针对SQL Server岗位的应聘者准备面试。以下将详细解析SQL的一些核心知识点,并结合可能的面试问题进行阐述。 1. **选择查询(SELECT)**...
【C&C++经典面试题】涉及的知识点广泛,主要涵盖了C和C++语言的基础、操作系统原理、并发编程、面向对象编程、数据结构、调试工具、数据库理论和网络编程等多个方面。下面将对这些知识点进行详细解释: 1. **进程间...
vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典...
《C#经典面试题及答案解析》 在IT行业的面试中,C#作为.NET框架的核心语言,其相关的知识和技能常常是面试官考察的重点。本文将围绕C#的几个关键概念——委托、事件、控件遍历以及排序算法进行深入探讨,并提供相应...