[关闭]
@adamhand 2019-02-23T22:38:21.000000Z 字数 9138 阅读 805

LeetCode笔记之数组(一)

1. Sum

1.1 Two Sum



  1. public int[] twoSum(int[] nums, int target) {
  2.         for(int i = 0; i < nums.length; i++)
  3.         {
  4.             for(int j = i + 1; j < nums.length; j++)
  5.             {
  6.                 if(nums[i] + nums[j] == target)
  7.                 {
  8.                     return new int[] {i, j};
  9.                 }
  10.             }
  11.         }
  12.         throw new IllegalArgumentException("No two sum solution");
  13.     }
  1. public int[] twoSum(int[] nums, int target) {
  2.     Map<Integer, Integer> map = new HashMap<>();
  3.     for(int i = 0; i < nums.length; i++){
  4.         int component = target - nums[i];    //需要构造一个A+B=target的关系
  5.         if(!map.containsKey(component)){
  6.             map.put(nums[i], i);
  7.         }else{
  8.             return new int[] {map.get(component), i};
  9.         }
  10.     }
  11.     throw new IllegalArgumentException("no solution");
  12. }
  1. //这里要求返回位置而不是数，所以这种方法不能用，因为排了序，位置改变了
  2. public int[] twoSum(int[] nums, int target) {
  3.     Arrays.sort(nums);
  4.     int lo = 0, hi = nums.length - 1;
  5.     while(lo < hi){
  6.         if(nums[lo] + nums[hi] == target){
  7.             //return new int[]{nums[lo], nums[hi]};
  8.             return new int[] {lo, hi};
  9.         }else if(nums[lo] + nums[hi] < target){
  10.             while(lo < hi && nums[lo] == nums[lo+1]) lo++;  //如果有重复元素就跳过
  11.             lo++;
  12.         }else{
  13.             while(lo < hi && nums[hi] == nums[hi-1]) hi--;
  14.             hi--;
  15.         }
  16.     }
  17.     throw new IllegalArgumentException("no solution");
  18. }

1.2 ThreeSum



  1. public List<List<Integer>> threeSum(int[] nums) {
  2.     Arrays.sort(nums);
  3.     List<List<Integer>> res = new LinkedList<>();
  4.     for(int i = 0; i < nums.length - 2; i++){
  5.         if(i == 0 || (i > 0 && nums[i] != nums[i-1])){
  6.             int lo = i+1, hi = nums.length-1, sum = 0-nums[i];
  7.             while(lo < hi){
  8.                 if(nums[lo] +nums[hi] == sum){
  9.                     res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
  10.                     while(lo < hi && nums[lo] == nums[lo+1]) lo++;  //题目要求，元素不能重复
  11.                     while(lo < hi && nums[hi] == nums[hi-1]) hi--;
  12.                     lo++;
  13.                     hi--;
  14.                 }else if(nums[lo] + nums[hi] < sum){
  15.                     lo++;
  16.                 }else{
  17.                     hi--;
  18.                 }
  19.             }
  20.         }
  21.     }
  22.     return res;
  23. }

1.3 ThreeSumClosest



  1. public int threeSumClosest(int[] nums, int target) {
  2.     int sum = 0;
  3.     //int ans = Integer.MAX_VALUE;
  4.     int ans = nums[0] + nums[1] + nums[nums.length-1];
  5.     Arrays.sort(nums);
  6.     for(int i = 0; i < nums.length-2; i++){
  7.         int lo = i+1, hi = nums.length-1;
  8.         // sum = nums[i] + nums[lo] + nums[hi];
  9.         while(lo < hi){
  10.             sum = nums[i] + nums[lo] + nums[hi];
  11.             ans = (Math.abs(target-sum) > Math.abs(target-ans)) ? ans : sum;
  12.             if(sum == target){
  13.                 return target;
  14.             }else if(sum < target){
  15.                 while(lo < hi && nums[lo] == nums[lo+1]) lo++;
  16.                 lo++;
  17.             }else{
  18.                 while(lo < hi && nums[hi] == nums[hi-1]) hi--;
  19.                 hi--;
  20.             }
  21.         }
  22.     }
  23.     return ans;
  24. }
  1. public int threeSumClosest(int[] num, int target) {
  2.     int result = num[0] + num[1] + num[num.length - 1];
  3.     Arrays.sort(num);
  4.     for (int i = 0; i < num.length - 2; i++) {
  5.         int start = i + 1, end = num.length - 1;
  6.         while (start < end) {
  7.             int sum = num[i] + num[start] + num[end];
  8.             if (sum > target) {
  9.                 end--;
  10.             } else {
  11.                 start++;
  12.             }
  13.             if (Math.abs(sum - target) < Math.abs(result - target)) {
  14.                 result = sum;
  15.             }
  16.         }
  17.     }
  18.     return result;
  19. }

1.4 FourSum



  1. public class Solution {
  2.     int len = 0;
  3.     public List<List<Integer>> fourSum(int[] nums, int target) {
  4.         len = nums.length;
  5.         Arrays.sort(nums);
  6.         return kSum(nums, target, 4, 0);
  7.     }
  8.    private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
  9.         ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
  10.         if(index >= len) {
  11.             return res;
  12.         }
  13.         if(k == 2) {
  14.             int i = index, j = len - 1;
  15.             while(i < j) {
  16.                 //find a pair
  17.                 if(target - nums[i] == nums[j]) {
  18.                     List<Integer> temp = new ArrayList<>();
  19.                     temp.add(nums[i]);
  20.                     temp.add(target-nums[i]);
  21.                     res.add(temp);
  22.                     //skip duplication
  23.                     while(i<j && nums[i]==nums[i+1]) i++;
  24.                     while(i<j && nums[j-1]==nums[j]) j--;
  25.                     i++;
  26.                     j--;
  27.                 //move left bound
  28.                 } else if (target - nums[i] > nums[j]) {
  29.                     i++;
  30.                 //move right bound
  31.                 } else {
  32.                     j--;
  33.                 }
  34.             }
  35.         } else{
  36.             for (int i = index; i < len - k + 1; i++) {
  37.                 //use current number to reduce ksum into k-1sum
  38.                 ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k-1, i+1);
  39.                 if(temp != null){
  40.                     //add previous results
  41.                     for (List<Integer> t : temp) {
  42.                         t.add(0, nums[i]);
  43.                     }
  44.                     res.addAll(temp);
  45.                 }
  46.                 while (i < len-1 && nums[i] == nums[i+1]) {
  47.                     //skip duplicated numbers
  48.                     i++;
  49.                 }
  50.             }
  51.         }
  52.         return res;
  53.     }
  54. }

1.5 FourSum II



看到这个问题时，最先想到的方法就是暴力法，四个for循环嵌套，但可想而知算法的速度是多么慢解决这种复杂问题的一个思路就是分治，把复杂问题分解成几个比较简单的问题。

  1. class Solution {
  2.     public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
  3.         Map<Integer, Integer> sums = new HashMap<>();
  4.         int count = 0;
  5.         for(int i = 0; i < A.length; i++){
  6.             for(int j = 0; j < B.length; j++){
  7.                 int sum = A[i] + B[j];
  8.                 if(sums.containsKey(sum)){
  9.                     sums.put(sum, sums.get(sum)+1);
  10.                 }else{
  11.                     sums.put(sum, 1);
  12.                 }
  13.             }
  14.         }
  16.         for(int k = 0; k < C.length; k++){
  17.             for(int v = 0; v < D.length; v++){
  18.                 int sum = -(C[k] + D[v]);
  19.                 if(sums.containsKey(sum)){
  20.                     count += sums.get(sum);
  21.                 }
  22.             }
  23.         }
  24.         return count;
  25.     }
  26. }
  1. public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
  2.     Map<Integer, Integer> sums = new HashMap<>();
  3.     int count = 0;
  4.     for(int i = 0; i < A.length; i++){
  5.         for(int j = 0; j < B.length; j++){
  6.             int sum = A[i] + B[j];
  7.             sums.put(sum, sums.getOrDefault(sum, 0)+1);
  8.         }
  9.     }
  11.     for(int k = 0; k < C.length; k++){
  12.         for(int v = 0; v < D.length; v++){
  13.             count += sums.getOrDefault(-1 * (C[k]+D[v]), 0);
  14.         }
  15.     }
  16.     return count;
  17. }
  1. public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
  2.     int nAB = A.length * B.length;
  3.     int[] sumAB = new int[nAB];
  4.     int i = 0;
  5.     for(int a : A){
  6.         for(int b : B){
  7.             sumAB[i++] = a +b;
  8.         }
  9.     }
  11.     int nCD = C.length * D.length;
  12.     int[] negSumCD = new int[nCD];
  13.     i = 0;
  14.     for(int c : C){
  15.         for(int d : D){
  16.             negSumCD[i++] = -(c + d);
  17.         }
  18.     }
  20.     Arrays.sort(sumAB);
  21.     Arrays.sort(negSumCD);
  23.     i = 0;
  24.     int j = 0, count = 0;
  25.     while(i < nAB && j < nCD){
  26.         if(sumAB[i] == negSumCD[j]){
  27.             int countAB = 1, countCD = 1;
  28.             while(++i < nAB && sumAB[i]==sumAB[i-1]) countAB += 1;
  29.             while(++j < nCD && negSumCD[j]==negSumCD[j-1]) countCD += 1;
  30.             count += countAB * countCD;
  31.         }else if(sumAB[i] < negSumCD[j]){
  32.             i++;
  33.         }else{
  34.             j++;
  35.         }
  36.     }
  37.     return count;
  38. }

2. Trapping Water(盛水问题)

2.1 Trapping Rain Water



  1. class Solution{
  2.     public int trap(int[] height){
  3.         int left = 0, right = height.length-1;
  4.         int left_max = 0, right_max = 0;
  5.         int ans = 0;
  6.         while(left < right){
  7.             if(height[left] < height[right]){
  8.                 if(height[left] >= left_max){
  9.                     left_max = height[left];
  10.                 }else{
  11.                     ans += left_max - height[left];
  12.                 }
  13.                 left++;
  14.             }else{
  15.                 if(height[right] >= right_max){
  16.                     right_max = height[right];
  17.                 }else{
  18.                     ans += right_max - height[right];
  19.                 }
  20.                 right--;
  21.             }
  22.         }
  23.         return ans;
  24.     }
  25. }

2.2 Container With Most Water



假设现在有一个容器，则容器的盛水量取决于容器的底和容器较短的那条高。则我们可以从最大的底长入手，即当容器的底等于数组的长度时，则容器的盛水量为较短边的长乘底

可见 只有较短边会对盛水量造成影响，因此移动较短边的指针，并比较当前盛水量和当前最大盛水量。直至左右指针相遇。主要的困惑在于如何移动双指针才能保证最大的盛水量被遍历到

假设有左指针left和右指针right，且left指向的值小于right的值，假如我们将右指针左移，则右指针左移后的值和左指针指向的值相比有三种情况：

（1）右指针指向的值大于左指针
这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小
（2）右指针指向的值等于左指针
这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小
（3）右指针指向的值小于左指针
这种情况下，容器的高取决于右指针，但是右指针小于左指针，且底也变短了，所以容量盛水量一定变小了

综上所述，容器高度较大的一侧的移动只会造成容器盛水量减小。所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇。

更严谨的证明：反证法
  之前证明的只是在左指针不改变的情况下，左移右指针只会造成容器的容量减小。但是一旦紧接着左指针发生变化，就无法证明以该左指针为一侧高，右指针右侧的值生成的容器的容量比当前值小。
  以下补充一个简单的反证法证明算法的合理性
  当前的算法为：使用两个指针分别指向数组的头和尾。指向的值较小的那个指针移动，即左指针右移，右指针左移。当左右指针相遇时，
  假设：该算法并没有遍历到容量最大的情况
  我们令容量最大时的指针为p_left和p_right。根据题设，我们可以假设遍历时左指针先到达p_left，但是当左指针为p_left时，右指针还没有经过p_right左指针就移动了。
  已知当左指针停留在p_left时，它只有在两种场景下会发生改变:

  1. class Solution {
  2.     public int maxArea(int[] height){
  3.         int max = 0, l = 0, r = height.length-1;
  5.         while(l < r){
  6.             max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
  7.             if(height[l] < height[r]){
  8.                 l++;
  9.             }else{
  10.                 r--;
  11.             }
  12.         }
  13.         return max;
  14.     }
  15. }

3. Best Time to Buy and Sell(利润最大问题)

3.1 Best Time to Buy and Sell Stock


注意：题目中要求，只能进行一次交易。
- 解法1：暴力循环。因为只能进行一次交易，只需找到满足条件(这里的条件值的是小值要在大值之前)的“最大值”和“最小值”即可。外层就是一个冒泡排序法的嵌套循环。

  1. public class Solution {
  2.     public int maxProfit(int prices[]) {
  3.         int maxprofit = 0;
  4.         for (int i = 0; i < prices.length - 1; i++) {
  5.             for (int j = i + 1; j < prices.length; j++) {
  6.                 int profit = prices[j] - prices[i];
  7.                 if (profit > maxprofit)
  8.                     maxprofit = profit;
  9.             }
  10.         }
  11.         return maxprofit;
  12.     }
  13. }

只需要找到“波峰”和“波谷”就行。可以定义两个变量minprice和maxprofit来解决这个问题。

  1. public class Solution {
  2.     public int maxProfit(int prices[]) {
  3.         int minprice = Integer.MAX_VALUE;
  4.         int maxprofit = 0;
  5.         for (int i = 0; i < prices.length; i++) {
  6.             if (prices[i] < minprice)
  7.                 minprice = prices[i];
  8.             else if (prices[i] - minprice > maxprofit)
  9.                 maxprofit = prices[i] - minprice;
  10.         }
  11.         return maxprofit;
  12.     }
  13. }

3.2 Best Time to Buy and Sell Stock II


注意：和上一个题目的不同之处在于可以进行多次买卖。

334. Increasing Triplet Subsequence

描述：

  1. Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
  3. Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

  1. Input: [1,2,3,4,5]
  2. Output: true

Example 2:

  1. Input: [5,4,3,2,1]
  2. Output: false

前面说到了双指针法，即使用两个指针指向数组的两个位置，然后比较两个指针指向元素的大小，可以看到，“指针”在动而数组不动。

这里如果用这种方法比较复杂，但是受它启发，可以使用一种变形的“双指针”。让数组的元素挨个和指针元素进行比较，“指针”不动而数组在动。具体思路是：

定义一个small指针和一个big指针，将数组元素挨个和这两个指针比较，如果小于small，就将数组元素值赋值给small；如果比small大但比big小，就将元素赋值给big；如果这两个条件都不满足，说明当前元素比big大，而big又比small大，满足提议的情况就出现了，返回true。如果遍历完数组还没有出现上述情况，返回false。

  1. class Solution {
  2.     public boolean increasingTriplet(int[] nums) {
  3.         if(nums.length < 3)
  4.             return false;
  6.         int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
  7.         for(int n : nums){
  8.             if(n <= small)
  9.                 small = n;
  10.             else if(n <= big)
  11.                 big = n;
  12.             else 
  13.                 return true;
  14.         }
  15.         return false;
  16.     }
  17. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注