“点个赞,看一看,好习惯!本文 GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了 3 个月总结的一线大厂 Java 面试总结,本人已拿腾讯等大厂 offer。 另外,原创文章首发在我的个人博客:blog.ouyangsihai.cn,欢迎访问。
今天介绍一种解决常规的贪心策略或者字典排序的题目的通用解题方法。
第一题,leetcode中等难度题目
先来一道简单的字典序排列的问题,这个题目我这里不会用最优解来解决这个问题,这个是leetcode的中等难度的题目,最优解还是需要再思考一下的,这道题目作为文章开头只是为了介绍我想要介绍的贪心的解题的一种思路而已,大佬请勿喷!!
看到这个题目,我就是想用暴力的方法解决,以便更好的理解这种解题思路。
先给出我的答案,非常暴力,但是非常好理解。
public List<Integer> lexicalOrder(int n) {
List<String> list = new ArrayList<>();
for(int i = 1; i <= n; i++){
list.add(i + "");
}
Collections.sort(list,(o1,o2)->{
return o1.compareTo(o2);
});
List<Integer> iList = new ArrayList<>();
list.stream().forEach((str)->{
iList.add(Integer.parseInt(str));
});
return iList;
}
这个解题方法很简单,用的就是Collections.sort()方法的排序,然后重写一下Comparator类而已,这里用的是lambda表达式,使得代码更加的简洁。
最优解大家可以去leetcode看看哈,自己动手,丰衣足食。
所以,通过这个题目我想给出的信息就是:通常涉及到字符串排序,字典序,数字排序等等的题目,都是可以用这种思路来解决问题的
。
不信,我们再看看其他题目。
第二题,leetcode中等难度题目
这是一道常见的topk问题,最优解也不是我给出的答案,目的只是为了阐述这种解题方法。
我的解题方法:用优先级队列,维护一个大小为k小顶堆,每次堆的元素到达k时,先弹出堆顶元素,这样就堆总是维持着k个最大值,最终可以的到前k高的元素。
下面看看我的解答(注意:我的答案绝对不是最优解,只是为了阐述这种方法)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Queue<Obj> queue = new PriorityQueue<>(k,(o1,o2)->{
return o2.num - o1.num;
});
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
}
for(int key : map.keySet()){
queue.offer(new Obj(key,map.get(key)));
}
int[] ans = new int[k];
int i = 0;
while(i < k){
ans[i] = queue.poll().target;
i++;
}
return ans;
}
class Obj {
public int target;
public int num;
public Obj(int target, int num){
this.target = target;
this.num = num;
}
}
}
这种方法没有维护k的最大的堆。
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap();
for (int n: nums) {
map.put(n, map.getOrDefault(n, 0) + 1);
}
PriorityQueue<Integer> heap =
new PriorityQueue<Integer>((n1, n2) -> map.get(n1) - map.get(n2));
for (int n: map.keySet()) {
heap.add(n);
if (heap.size() > k)
heap.poll();
}
List<Integer> top_k = new LinkedList();
while (!heap.isEmpty())
top_k.add(heap.poll());
Collections.reverse(top_k);
return top_k;
}
}
这种方法维护k的最大的堆。
对比发现:不管维护k的最大堆还是不维护,核心的思想都是
Queue<Obj> queue = new PriorityQueue<>(k,(o1,o2)->{
return o2.num - o1.num;
});
和这段代码
PriorityQueue<Integer> heap =
new PriorityQueue<Integer>((n1, n2) -> map.get(n1) - map.get(n2));
对比第一题中的
Collections.sort(list,(o1,o2)->{
return o1.compareTo(o2);
});
用的都是内部类:Comparator
,然后进行构建符合题意的排序规则。
第三题,更复杂点的
这个题目就更能明白什么是构建符合题意的排序规则。
因为很多题目不止让你根据一个字段进行排序,可能是两个字段进行排序,或者三个字段进行排序,所以就需要进行“构建”。
这个题目的解题思路:先排序再插入
- 排序规则:按照先H高度降序,K个数升序排序
- 遍历排序后的数组,根据K插入到K的位置上
核心思想:高个子先站好位,矮个子插入到K位置上,前面肯定有K个高个子,矮个子再插到前面也满足K的要求。
再看看解答
public int[][] reconstructQueue(int[][] people) {
// [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
// 再一个一个插入过程
// [7,0]
// [7,0], [7,1]
// [7,0], [6,1], [7,1]
// [5,0], [7,0], [6,1], [7,1]
// [5,0], [7,0], [5,2], [6,1], [7,1]
// [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
LinkedList<int[]> list = new LinkedList<>();
for (int[] i : people) {
//在i位置,插入数:i[1]是[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]的第一个数,表示前面有几个比我高的。
list.add(i[1], i);
}
return list.toArray(new int[list.size()][2]);
}
你会发现,核心代码还是跟第一题和第二题一样,只是复杂一点点。
Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
这是什么意思呢:o1和o2是一个类似这样[7,0]
的一位数组,当第一个数相等时,再比较一维数组的第二个数的大小,不相等,当然先比较第一个数了。
这个就是多个字段比较的例子,是不是还是跟前面的思路是一样的。
总结
最后发现,关于排序的,不管是,数组的排序,数字的排序,字符串的排序,还是优先级队列的排序,我们都是可以用Java的Comparator来解决的。
就说这么多,只是思路,不要死磕最优解!!!
最后,再分享我历时三个月总结的 Java 面试 + Java 后端技术学习指南,这是本人这几年及春招的总结,已经拿到了大厂 offer,整理成了一本电子书,拿去不谢,目录如下:
现在免费分享大家,在下面我的公众号 程序员的技术圈子 回复 面试 即可获取。
有收获?希望老铁们来个三连击,给更多的人看到这篇文章
1、老铁们,关注我的原创微信公众号「程序员的技术圈子」,专注于 Java、数据结构和算法、微服务、中间件等技术分享,保证你看完有所收获。
2、给俺点个赞呗,可以让更多的人看到这篇文章,顺便激励下我继续写作,嘻嘻。
3、另外,原创文章首发在我的个人博客:blog.ouyangsihai.cn,欢迎访问。
点赞是对我最大的鼓励 ↓↓↓↓↓↓
相关推荐
LeetCode判断字符串是否循环 leetcode leetcode exercises,algorithms part! TwoSum: 1.key point: unorderd_map(16ms), map(24ms) 2.大概是前50%的样子,并不知道如何进一步提升性能 addTwoNums: 1.新建ListNode...
LeetCode全栈攻略:高效刷题笔记分享 从零开始到技术大牛的必经之路,提升算法能力与编程技巧。 内容概要: 欢迎来到这个全面解析LeetCode刷题心得的世界!这里汇集了我数月来的点滴努力和收获,旨在帮助你在...
leetcode卡 LeetCode Have fun! Progress 2月进度汇总 2021-02-15/2020-02-16/2020-02-17 数组 + 字符串 - 双指针法查询code - 滑动窗口 - 双指针L/R 2021-02-18 - 排列的规律性 2021-02-19 二叉树 - 递归方法 - ...
10. **IO和网络编程**:虽然LeetCode中的大部分问题不涉及网络编程,但了解基本的输入输出和文件操作对实际开发很有帮助。 在“Leetcode-main”这个文件夹中,可能包含每个问题的Java实现文件,每个文件可能对应一...
My_Solutions_to_Leetcode_problems_!__leetcode_算法题源_leetcode-solutions
前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label。 调试 提供了 .vscode 配置文件,在 vscode 中选择「小爬虫」...
⦙⦙⦙⦙⦙⦙⦙ 解决问题的一种非常方法。 问题以减轻离线思维。 编码前的源代码。 通过leetcode.com进行实时测试并提交。 下载您以前的SUBMISSION 。 跟踪您的编码状态。 使用单个帐户在多个座席之间 自动登录。 ...
在编程领域,LeetCode是一个非常受欢迎的在线平台,它提供了大量的算法题目,旨在帮助程序员提升他们的编程技巧和问题解决能力。这个"LeetCode:LeetCode问题已解决!"的主题表明了用户已经成功解决了LeetCode上的...
leetcodebook_leetcode 1~400知识点&题型总结&leetcode对应题表
leetcode 答案LeetCode 和 HackerRank 这个 repo 同步了我在 LeetCode 和 HackerRank 问题中所做的问题。 我主要用C++回答问题。 在极少数情况下,我会用 C 进行编码,当我认为在这些特定问题中不需要 STL 时就会...
JavaLeetCode算法我首先尝试了 C++ 的 LeetCode,并以错误的方式更新了这个 githubi 中的案例(只有 ctrl C 和 ctrl V github 中的文件)。 现在,我知道 github 是如何工作的,然后我想继续尝试 Java 的 leetcode。...
4. **JavaScript代码实现**:在"Javascript-leetcode-master"文件夹中,每个问题的解决方案都以JavaScript代码的形式呈现,通常包括多种方法,如递归、迭代或使用内置库函数等。 5. **测试与调试**:每个解决方案都...
LeetCode 问题的解决方案
《LeetCode刷题笔记》是针对LeetCode这个在线编程挑战平台的个人学习心得与总结,主要涵盖数据结构和算法两大核心领域。LeetCode是一个全球知名的编程训练网站,它提供了丰富的编程题目,帮助开发者提升编程技能,...
LeetCode-Swift, 快速LeetCode解决方案 LeetCodeLeetCode在线判断是一个包含很多收费算法的网站。 them Google Google Google Google LinkedIn this this repo 。 请免费参考并收费STAR以支持这个 repo,
leetcode 567 Leetcode practice makes perfect! 编号 题目 语言 难度 #76 Hard #72 Hard #567 Medium #516 Medium #438 Medium #300 Medium #198 Medium #213 Medium #337 Medium
这个压缩包“lc-all-solutions-master”包含了使用Python语言解决LeetCode所有问题的代码,覆盖了从基础算法到复杂数据结构的广泛领域。以下是对这个资源的详细解析: 一、Python编程基础 Python是解释型、面向对象...
在Visual Studio Code (VSCode) 中解决LeetCode问题是一个高效且便捷的方式,尤其当你使用TypeScript这种强类型、面向对象的编程语言时。这个压缩包文件"vscode-leetcode-master"提供了一整套配置和工具,帮助你在...
本资料集中,我们关注的是使用Python语言来解决LeetCode上的问题。Python以其简洁明了的语法和丰富的库支持,成为了许多程序员首选的工具,特别是在处理算法挑战时。 首先,让我们深入探讨Python在LeetCode中的应用...
本书名为《LeetCode 101 - A LeetCode Grinding Guide (C++ Version)》,是由作者高畅(Chang Gao)撰写的一本面向具有C++编程基础但缺乏刷题经验读者的教科书和工具书。本书的初衷是为了帮助读者系统性地归纳和总结...