一站式网站建设服务商,做推广的网站微信号,两学一做是什么网站,wordpress++pdf力扣爆刷第104天之CodeTop100五连刷6-10 文章目录 力扣爆刷第104天之CodeTop100五连刷6-10一、15. 三数之和二、53. 最大子数组和三、912. 排序数组四、21. 合并两个有序链表五、1. 两数之和 一、15. 三数之和
题目链接#xff1a;https://leetcode.cn/problems/3sum/descrip…力扣爆刷第104天之CodeTop100五连刷6-10 文章目录 力扣爆刷第104天之CodeTop100五连刷6-10一、15. 三数之和二、53. 最大子数组和三、912. 排序数组四、21. 合并两个有序链表五、1. 两数之和 一、15. 三数之和
题目链接https://leetcode.cn/problems/3sum/description/ 思路求三数之和需要外层一个for内层一个for内层的还要双指针。另外就是要注意去重操作。
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger arrayList 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 i1, k nums.length-1;while(j k) {int temp nums[i] nums[j] nums[k];if(temp 0) {ListInteger list new ArrayList();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);arrayList.add(list);while(j k nums[j] nums[j1]) j;while(j k nums[k] nums[k-1]) k--;j;k--;}else if(temp 0) {j;}else{k--;}}}return arrayList;}
}
二、53. 最大子数组和
题目链接https://leetcode.cn/problems/maximum-subarray/description/ 思路可以使用动态规划和贪心来做动态规划就是状态与选择贪心就是局部最优到全局最优。 动态规划定义dp[i]表示在区间nums[0, i]中以nums[i]为结尾的最大子数组的和那么对于每一个dp[i]来说它都可以选择把nums[i]是否追加到子数组的结尾这个就是状态与选择选择的条件是最大子数组的和这一句话就把动态规划讲透了。 贪心贪心更简单只要子数组的和大于0我就一直加只要小于0就离开开启一个新的子数组。
class Solution {public int maxSubArray(int[] nums) {int[] dp new int[nums.length];dp[0] nums[0];int max nums[0];for(int i 1; i nums.length; i) {dp[i] Math.max(dp[i-1]nums[i], nums[i]);max Math.max(max, dp[i]);}return max;}
}三、912. 排序数组
题目链接https://leetcode.cn/problems/sort-an-array/description/ 思路使用归并排序时间复杂度为O(nlogn)空间复杂度为O(n)。
class Solution {int[] temp;public int[] sortArray(int[] nums) {temp new int[nums.length];mergeSort(nums, 0, nums.length-1);return nums;}void mergeSort(int[] nums, int left, int right) {if(left right) return;int mid left (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid1, right);int i left, j mid 1;int k left;while(i mid j right) {if(nums[i] nums[j]) {temp[k] nums[i]; }else{temp[k] nums[j];}}while(i mid) {temp[k] nums[i]; }while(j right) {temp[k] nums[j];}k left;while(k right) {nums[k] temp[k];k;}}
}
四、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();ListNode p1 list1, p2 list2, p root;while(p1 ! null p2 ! null) {if(p1.val p2.val) {p.next p1;p1 p1.next;}else{p.next p2;p2 p2.next;}p p.next;p.next null;}if(p1 ! null) {p.next p1;}if(p2 ! null) {p.next p2;}return root.next;}
}五、1. 两数之和
题目链接https://leetcode.cn/problems/two-sum/description/ 思路两数之和利用map从map里找target - nums[i]找到了就找到了。
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer map new HashMap();for(int i 0; i nums.length; i) {int t target - nums[i];if(map.containsKey(t)) {return new int[] {i, map.get(t)};}else{map.put(nums[i], i);}}return new int[] {-1, -1};}
}
