力扣爆刷第104天之CodeTop100五连刷6-10
一、15. 三数之和
题目链接:https://leetcode.cn/problems/3sum/description/
思路:求三数之和,需要外层一个for,内层一个for,内层的还要双指针。另外就是要注意去重操作。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> 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 = i+1, k = nums.length-1;
while(j < k) {
int temp = nums[i] + nums[j] + nums[k];
if(temp == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
arrayList.add(list);
while(j < k && nums[j] == nums[j+1]) 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, mid+1, 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) {
Map<Integer, 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};
}
}