力扣爆刷第150天之TOP100五连刷(几数之和、堆排、合并链表)

2024-06-13 15:20

本文主要是介绍力扣爆刷第150天之TOP100五连刷(几数之和、堆排、合并链表),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣爆刷第150天之TOP100五连刷(几数之和、堆排、合并链表)

文章目录

      • 力扣爆刷第150天之TOP100五连刷(几数之和、堆排、合并链表)
      • 一、15. 三数之和
      • 二、53. 最大子数组和
      • 三、912. 排序数组
      • 四、21. 合并两个有序链表
      • 五、1. 两数之和

一、15. 三数之和

题目链接:https://leetcode.cn/problems/3sum/description/
思路:经典的两数之和、三数之和,两数之和使用map,三数之和需要考虑的是去重和早停。
三数之和,三个数,第一个数单独拿出来,然后剩下的两个数在一块,这就又形成了两数之和了。首先给整个数组排序,第一个数固定不动,看看剩下两个数加一块的三数之和,如果大于0说第三个数大了,要左移,如果小于0说明第二哥数小了,要右移。对于后两个数的去重,相同的数要抛弃。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length-2; i++) {if(nums[i] > 0) break;if(i > 0 && nums[i] == nums[i-1]) continue;int j = i+1, k = nums.length-1;while(j < k) {int t = nums[i] + nums[j] + nums[k];if(t == 0) {List<Integer> list = new ArrayList();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);result.add(list);while(j < k && nums[j] == nums[j+1]) j++;while(j < k && nums[k] == nums[k-1]) k--;j++;k--;}else if(t > 0) {k--;}else{j++;}}}return result;}
}

二、53. 最大子数组和

题目链接:https://leetcode.cn/problems/maximum-subarray/description/
思路:本题可以用贪心,也可以用动规,如果使用贪心的话,因为求的是最大连续子数组的和,所以只要子数组的和大于0我们就不停的记录最大值,如果子数组的和小于0了,那么就重新开始。

class Solution {public int maxSubArray(int[] nums) {int sum = 0, max = nums[0];for(int i : nums) {sum += i;max = Math.max(max, sum);if(sum < 0) sum = 0;}return max;}
}

三、912. 排序数组

题目链接:https://leetcode.cn/problems/sort-an-array/description/
思路:排序算法嘛,经典题目,一般不是快排就是堆排、归并,如果测试用例有有序的存在,你还不太会写变体的快排的话,写堆排就可以。
思路就是先构建大顶堆,层于层之间有序,层内无序,然后每次把堆顶元素替换到尾部,由此即可排序。

class Solution {public int[] sortArray(int[] nums) {heapSort(nums);return nums;}void heapSort(int[] nums) {for(int i = nums.length/2-1; i >= 0; i--) {builHeap(nums, i, nums.length);}for(int i = nums.length-1; i > 0; i--) {int t = nums[0];nums[0] = nums[i];nums[i] = t;builHeap(nums, 0, i);} }void builHeap(int[] nums, int start, int end) {int t = nums[start], k = start;for(int i = start * 2 + 1; i < end; i = i * 2 + 1) {if(i+1 < end && nums[i] < nums[i+1]) i++;if(nums[i] > t) {nums[k] = nums[i];k = i;}else break;}nums[k] = t;}
}

四、21. 合并两个有序链表

题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/
思路:合并两个有序链表,经典归并排序,没啥好说的,比较然后合并即可。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode root = new ListNode(), p = root;while(list1 != null && list2 != null) {if(list1.val < list2.val) {p.next = list1;list1 = list1.next;}else{p.next = list2;list2 = list2.next;}p = p.next;}if(list1 != null) p.next = list1;if(list2 != null) p.next = list2;return root.next;}
}

五、1. 两数之和

题目链接:https://leetcode.cn/problems/two-sum/description/
思路:经典两数之和,使用map记录每一个数与target的差值,然后如果当前数出现在map中,就说明找到两数之和了。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++) {if(map.containsKey(nums[i])) {return new int[] {map.get(nums[i]), i};}map.put(target - nums[i], i);}return new int[] {-1, -1};}
}

这篇关于力扣爆刷第150天之TOP100五连刷(几数之和、堆排、合并链表)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1057677

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【Python从入门到进阶】64、Pandas如何实现数据的Concat合并

接上篇《63.Pandas如何实现数据的Merge》 上一篇我们学习了Pandas如何实现数据的Merge,本篇我们来继续学习Pandas如何实现数据的Concat合并。 一、引言 在数据处理过程中,经常需要将多个数据集合并为一个统一的数据集,以便进行进一步的分析或建模。这种需求在多种场景下都非常常见,比如合并不同来源的数据集以获取更全面的信息、将时间序列数据按时间顺序拼接起来以观察长期趋势等