LeetCode: Tags-[Array], Difficulty-[Medium]

Tags: Array

Difficulty: Medium

11. Container With Most Water: https://leetcode.com/problems/container-with-most-water/

n条纵线，找出两条线使得容器最大:(题意:假设ai,aj Cmax =min(ai,aj)*(j-i));

暴力解法: (内外for循环; 外循环遍历, 内循环遍历i后的数, 嵌套求最值 max = Math.max(max,min([i],[j]))*(j-i) ps:LeetCode最后大数据TLE,LintCode可以通过)

 1 public class Solution {
 2     public int maxArea(int[] height) {
 3         int max = 0;
 4         for (int i = 0; i < height.length; i++) {
 5             for (int j = i; j < height.length; j++) {
 6                 max = Math.max(max,Math.min(height[j],height[i])*(j - i));
 7             }
 8         }
 9         return max;
10     }
11 }

View Code

解法2：<Two Pointers> (首尾双指针遍历 left,right, 记录max, 保留[left]/[right]中大的一个,另一边指针移动;)

(0.int area; 1.left,right,max; 2.while(<=)max=max(,area); 3.if([left]<)left++); (Q: 可以嵌套for循环的就可以双指针??Todo;)

 1 public class Solution {
 2     /**
 3      * @param heights: an array of integers
 4      * @return: an integer
 5      */
 6     int computeArea(int left, int right,  int[] heights) {
 7         return (right-left)*Math.min(heights[left], heights[right]);
 8     }
 9     
10     public int maxArea(int[] heights) {
11         // write your code here
12         int left = 0, ans=  0 ; 
13         int right = heights.length - 1;
14         while(left <= right) {
15             ans = Math.max(ans,computeArea(left, right, heights));
16             if(heights[left]<=heights[right])
17                 left++;
18             else
19                 right--;
20         }
21         return ans;
22     }
23 }

View Code

15. 3Sum: https://leetcode.com/problems/3sum/

找出数组中所有3数之和为零的数：

解法：(遍历,第一个数的相反数作为后两个数的和,二分遍历后两个数 1.排序 2.for(0,n-2)遍历 3.if(i=0 || [i]=[i-1]) 跳过重复元素 4.lo,high,sum 5.while(<)if等sum则add,while(<&&=)lo++,while(<&&=)hi--跳过重复元素; lo++ hi-- 搜索下一对2SUM; 6.if(<sum)那么lo++,else()hi--; )

(1.sort,rst; 2.for(n-2)if(0||!=); 3.lo=i+1,hi,sum; 4.while() if(=)tmp,add,while(<&=)++while(>&=)--; 5.if(<)++(>)-- 6.return;)

 1 public class Solution {
 2     public List<List<Integer>> threeSum(int[] nums) {
 3         Arrays.sort(nums);
 4         List<List<Integer>> rst = new ArrayList<List<Integer>>();
 5         for (int i = 0; i < nums.length - 2; i++) {
 6             if (i == 0 || (i > 0 && nums[i] != nums[i - 1])){
 7                 int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
 8                 while (lo < hi) {
 9                     if (nums[lo] + nums[hi] == sum) {
10                         List<Integer> tmp = new ArrayList<Integer>();
11                         tmp.add(nums[i]);
12                         tmp.add(nums[lo]);
13                         tmp.add(nums[hi]);
14                         rst.add(tmp);
15                         while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
16                         while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
17                         lo++; hi--;
18                     } else if (nums[lo] + nums[hi] < sum) lo++;
19                     else hi--;
20                 }
21             }
22         }
23         return rst;
24     }
25 }

View Code

 1 public List<List<Integer>> threeSum(int[] num) {
 2     Arrays.sort(num);
 3     List<List<Integer>> res = new LinkedList<>(); 
 4     for (int i = 0; i < num.length-2; i++) {
 5         if (i == 0 || (i > 0 && num[i] != num[i-1])) {
 6             int lo = i+1, hi = num.length-1, sum = 0 - num[i];
 7             while (lo < hi) {
 8                 if (num[lo] + num[hi] == sum) {
 9                     res.add(Arrays.asList(num[i], num[lo], num[hi]));
10                     while (lo < hi && num[lo] == num[lo+1]) lo++;
11                     while (lo < hi && num[hi] == num[hi-1]) hi--;
12                     lo++; hi--;
13                 } else if (num[lo] + num[hi] < sum) lo++;
14                 else hi--;
15            }
16         }
17     }
18     return res;
19 }

View Code

16.3Sum Closest: https://leetcode.com/problems/3sum-closest/

找出数组中三数之和最接近target，返回三数之和:

解法：(遍历第一个数，后两个数二分遍历，比较rst和遍历出的sum的与tar的差值大小；根据sum和tar的差值决定lo和hi的变化)(和我自己思路类似，但是我卡在了lo和hi的变化上，不能用lo++hi——，这样会导致有的组合被跳过 [a,b,c,d]->[a]+[d]->[b]+[c] 漏掉了ab,ac,bd,cd 所以应该根据sum和tar的大小关系确定lo和hi的变化；)(用到方法：Math.abs()取绝对值)

(1.if()-1; 2.sort,rst; 3.for(n-2) if()lo,hi; 4.while()sum if(Math.abs<)rst=sum; 5.if()lo++;if()hi-- 6.return;) (ps:while里的语句跳过重复，也可以不用)

 1 public class Solution {
 2     public int threeSumClosest(int[] nums, int target) {
 3         if (nums == null || nums.length < 3) {
 4             return -1;
 5         }
 6         Arrays.sort(nums);
 7         int rst = nums[0] + nums[1] + nums[2];
 8         for (int i = 0; i < nums.length - 2; i++) {
 9             if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
10                 int lo = i + 1, hi = nums.length - 1;
11                 while (lo < hi){
12                     int sum = nums[lo] + nums[hi] + nums[i];
13                     if (Math.abs(rst - target) > Math.abs(sum - target))
14                         rst = sum;
15                     if (sum < target)
16                         lo++;
17                     else hi--;
18                 }
19             }
20         }
21         return rst;
22     }
23 }

View Code

18. 4Sum：https://leetcode.com/problems/4sum/

我的解法：(与3SUM解法相同，两趟for循环遍历第一个值和第二个值，注意每趟遍历依然要去重！且每趟for循环的首位要保留；[00000] i=0,j=1去重时不能把j=1也去了)

(1.rst,sort; 2.for(n-3)if(||&&); for(i+!,n-2)if(||&&); 3.lo,hi while(); 4.if(=)tmp,add,while(&); 5.else if(<) else(>) 6.return;)

 1 public class Solution {
 2     public List<List<Integer>> fourSum(int[] nums, int target) {
 3         List<List<Integer>> rst = new ArrayList<List<Integer>>();
 4         Arrays.sort(nums);
 5         for (int i = 0; i < nums.length - 3; i++) {
 6             if (i == 0 || (i !=0 && nums[i] != nums[i - 1])){
 7                 for (int j = i + 1; j < nums.length - 2; j++) {
 8                     if (j == i + 1 || (j != i + 1 && nums[j] != nums[j - 1])){
 9                         int lo = j + 1, hi = nums.length - 1;
10                         while (lo < hi) {
11                             if (nums[lo] + nums[hi] + nums[i] + nums[j] == target) {
12                                 List<Integer> tmp = new ArrayList<Integer>();
13                                 tmp.add(nums[i]); tmp.add(nums[j]);
14                                 tmp.add(nums[lo]); tmp.add(nums[hi]);
15                                 rst.add(tmp);
16                                 while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
17                                 while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
18                                 lo++; hi--;
19                             } else if (nums[i] + nums[j] + nums[lo] + nums[hi] < target)
20                                 lo++;
21                             else hi --;
22                         }
23                     }
24                 }
25             }
26         }
27         return rst;
28     }
29 }

View Code

if也可以有其他写法：(continue)

 1 public class Solution {
 2     public List<List<Integer>> fourSum(int[] num, int target) {
 3         ArrayList<List<Integer>> ans = new ArrayList<>();
 4         if(num.length<4)return ans;
 5         Arrays.sort(num);
 6         for(int i=0; i<num.length-3; i++){
 7             if(i>0&&num[i]==num[i-1])continue;
 8             for(int j=i+1; j<num.length-2; j++){
 9                 if(j>i+1&&num[j]==num[j-1])continue;
10                 int low=j+1, high=num.length-1;
11                 while(low<high){
12                     int sum=num[i]+num[j]+num[low]+num[high];
13                     if(sum==target){
14                         ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
15                         while(low<high&&num[low]==num[low+1])low++;
16                         while(low<high&&num[high]==num[high-1])high--;
17                         low++;
18                         high--;
19                     }
20                     else if(sum<target)low++;
21                     else high--;
22                 }
23             }
24         }
25         return ans;
26     }
27 }

View Code

31. Next Permutation: https://leetcode.com/problems/next-permutation/

找出下一个排列：[1,2,3,1]->[1,3,1,2]; [1,3,5,4,3,2,1]->[1,4,1,2,3,3,5]

解法：(1.从后往前遍历,找到第一个不满足降序的i; 2.从后往前遍历找出i后第一个比i大的数并swap; 3.将i后的数(已经是倒序)reverse反转; 这样能保证变化范围最小)

(我的代码，有问题。。暂时没找到原因……)

错！误！代！码！：原因swap(i,j)是按值传递,swap(nums[i],nums[j])后对数组没有变化；swap(int[] nums, int i, int j)是引用传递，将数组作为方法的参数，可以改变数组

 1 public class Solution {
 2     public void nextPermutation(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return;
 5         }
 6         int i = nums.length - 1;
 7         for (; i >= 1; i--) {
 8             if (nums[i] > nums[i - 1]) {
 9                 break;
10             }
11         }
12         if (i != 0) {
13             int j = nums.length - 1;
14             for (; j >= i; j--) {
15                 if (nums[j] > nums[i - 1]) {
16                     swap(nums[i - 1],nums[j]);
17                     break;
18                 }
19             }
20         }
21         reverse(nums,i);
22     }
23     void swap(int i,int j) {
24         int tmp = i;
25         i = j;
26         j = tmp;
27     }
28     void reverse(int[] nums, int start) {
29         int end = nums.length - 1;
30         for (; start < end; start++,end--) {
31             swap(nums[start],nums[end]);
32         }
33     }
34 }

View Code

正确代码：(利用break记录指针最后的位置)

(1.if; 2.i for(0)if()break; 3.if(!=)j,for(>=) if(i-1)swap break; 4.reverse(i); 5.swap([]),reverse([],start))

 1 public class Solution {
 2     public void nextPermutation(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return;
 5         }
 6         int i = nums.length - 1;
 7         for (; i > 0; i--) {
 8             if (nums[i] > nums[i - 1]) {
 9                 break;
10             }
11         }
12         if (i != 0) {
13             int j = nums.length - 1;
14             for (; j >= i; j--) {
15                 if (nums[j] > nums[i - 1]) {
16                     swap(nums, i - 1, j);
17                     break;
18                 }
19             }
20         }
21         reverse(nums, i);
22     }
23     void swap(int[] nums, int i, int j) {
24         int tmp = nums[i];
25         nums[i] = nums[j];
26         nums[j] = tmp;
27     }
28     void reverse(int[] nums, int start) {
29         int end = nums.length - 1;
30         for (; start < end; start++,end--) {
31             swap(nums,start,end);
32         }
33     }
34 }

View Code

类似的：

 1 public class Solution {
 2     public void nextPermutation(int[] nums) {
 3         // find two adjacent elements, n[i-1] < n[i]
 4         int i = nums.length - 1;
 5         for (; i > 0; i --) {
 6             if (nums[i] > nums[i-1]) {
 7                 break;
 8             }
 9         }
10         if (i != 0) {
11             // swap (i-1, x), where x is index of the smallest number in [i, n)
12             int x = nums.length - 1;
13             for (; x >= i; x --) {
14                 if (nums[x] > nums[i-1]) {
15                     break;
16                 }
17             }
18             swap(nums, i - 1, x);
19         }
20         reverse(nums, i, nums.length - 1);
21     }
22     
23     void swap(int[] a, int i, int j) {
24         int t = a[i];
25         a[i] = a[j];
26         a[j] = t;
27     }
28     // reverse a[i, j]
29     void reverse(int[] a, int i, int j) {
30         for (; i < j; i ++, j --) {
31             swap(a, i, j);
32         }
33     }
34 }

View Code

 1 public class Solution {
 2     public void nextPermutation(int[] nums) {
 3       if(nums.length<=1){
 4           return;
 5       }
 6       
 7       int i= nums.length-1;
 8       
 9       for(;i>=1;i--){
10          
11          if(nums[i]>nums[i-1]){ //find first number which is smaller than it's after number
12              break;
13          }
14       }
15       
16       if(i!=0){
17           swap(nums,i-1); //if the number exist,which means that the nums not like{5,4,3,2,1}
18       }
19       
20       reverse(nums,i);    
21     }
22     
23     private void swap(int[] a,int i){
24         for(int j = a.length-1;j>i;j--){
25             if(a[j]>a[i]){
26                 int t = a[j];
27                 a[j] = a[i];
28                 a[i] = t;
29                 break;
30             }
31         }
32     }
33     
34     private void reverse(int[] a,int i){//reverse the number after the number we have found
35         int first = i;
36         int last = a.length-1;
37         while(first<last){
38             int t = a[first];
39             a[first] = a[last];
40             a[last] = t;
41             first ++;
42             last --;
43         }
44     }
45     
46 }

View Code

34. Search for a Range: https://leetcode.com/problems/search-for-a-range/

找出有序数组中tar的首尾位置：

九章解法：(两次二分查找，注意while循环条件是start+1<end; 一般涉及范围问题、有重复值问题都应该用这个条件；对应的，下面的mid=start,end;并且要在最后判断边界值start和end。这样可以模板化，避免判断最终边界值start、mid、end混乱、错误的问题)

(start,end,while(+1<)mid,mid if([]=)else if([]=))

 1 public class Solution {
 2     public int[] searchRange(int[] A, int target) {
 3         if (A.length == 0) {
 4             return new int[]{-1, -1};
 5         }
 6         
 7         int start, end, mid;
 8         int[] bound = new int[2]; 
 9         
10         // search for left bound
11         start = 0; 
12         end = A.length - 1;
13         while (start + 1 < end) {
14             mid = start + (end - start) / 2;
15             if (A[mid] == target) {
16                 end = mid;
17             } else if (A[mid] < target) {
18                 start = mid;
19             } else {
20                 end = mid;
21             }
22         }
23         if (A[start] == target) {
24             bound[0] = start;
25         } else if (A[end] == target) {
26             bound[0] = end;
27         } else {
28             bound[0] = bound[1] = -1;
29             return bound;
30         }
31         
32         // search for right bound
33         start = 0;
34         end = A.length - 1;
35         while (start + 1 < end) {
36             mid = start + (end - start) / 2;
37             if (A[mid] == target) {
38                 start = mid;
39             } else if (A[mid] < target) {
40                 start = mid;
41             } else {
42                 end = mid;
43             }
44         }
45         if (A[end] == target) {
46             bound[1] = end;
47         } else if (A[start] == target) {
48             bound[1] = start;
49         } else {
50             bound[0] = bound[1] = -1;
51             return bound;
52         }
53         
54         return bound;
55     }
56 }

View Code

我的解法：(第二次搜索从rst[0]开始,循环一直继续直到start和end都指向第一个tar)

(1.rst if(0); 2.lo,hi,while(<=)mid,if(>=)mid-1,else mid+1;if(=)mid; 3.if(-1)return; 4.lo,hi,while()mid,if(<=)mid+1,else mid-1;if(=)mid; 5.return)

 1 public class Solution {
 2     public int[] searchRange(int[] A, int target) {
 3         int[] rst = new int[]{-1,-1};
 4         if (A.length == 0) {
 5             return rst;
 6         }
 7         int lo = 0, hi = A.length - 1;
 8         while (lo <= hi) {
 9             int mid = lo + (hi - lo) / 2;
10             if (A[mid] >= target) {
11                 hi = mid - 1;
12             } else {
13                 lo = mid + 1;
14             }
15             if (A[mid] == target) rst[0] = mid;
16         }
17         if (rst[0] == -1) {
18             return rst;
19         }
20         lo = rst[0]; 
21         hi = A.length - 1;
22         while (lo <= hi) {
23             int mid = lo + (hi - lo) / 2;
24             if (A[mid] <= target) {
25                 lo = mid + 1;
26             } else {
27                 hi = mid - 1;
28             }
29             if (A[mid] == target) rst[1] = mid;
30         }
31         return rst;
32     }
33 }

View Code

类似：

 1 public int[] searchRange(int[] nums, int target) {
 2     int[] result = new int[2];
 3     result[0] = findFirst(nums, target);
 4     result[1] = findLast(nums, target);
 5     return result;
 6 }
 7 
 8 private int findFirst(int[] nums, int target){
 9     int idx = -1;
10     int start = 0;
11     int end = nums.length - 1;
12     while(start <= end){
13         int mid = (start + end) / 2;
14         if(nums[mid] >= target){
15             end = mid - 1;
16         }else{
17             start = mid + 1;
18         }
19         if(nums[mid] == target) idx = mid;
20     }
21     return idx;
22 }
23 
24 private int findLast(int[] nums, int target){
25     int idx = -1;
26     int start = 0;
27     int end = nums.length - 1;
28     while(start <= end){
29         int mid = (start + end) / 2;
30         if(nums[mid] <= target){
31             start = mid + 1;
32         }else{
33             end = mid - 1;
34         }
35         if(nums[mid] == target) idx = mid;
36     }
37     return idx;
38 }

View Code

35. Search Insert Position: https://leetcode.com/problems/search-insert-position/

找出插入位置：

我的解法：(二分查找，=的时候作为pos即为mid，>的时候-1，< +1，最后的mid 如果大于等于tar，那么pos就是mid，小于tar，pos就是mid+1)

(1.lo,hi,rst,mid; 2.while(<=)if(=)return,if(>)-,if(<)+; 3.if([mid]>=)mid. else mid+1; 4.return)

 1 public class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         int lo = 0, hi = nums.length - 1;
 4         int rst = 0;
 5         int mid = 0;
 6         while (lo <= hi) {
 7             mid = lo + (hi - lo) / 2;
 8             if (nums[mid] == target) {
 9                 return mid;
10             } else if (nums[mid] > target) {
11                 hi = mid - 1;
12             } else {
13                 lo = mid + 1;
14             }
15         }
16         if (nums[mid] >= target) {
17             rst = mid;
18         } else {
19             rst = mid + 1;
20         }
21         return rst;
22     }
23 }

View Code

类似：(return low; low=mid/low=mid+1)

 1     public int searchInsert(int[] A, int target) {
 2         int low = 0, high = A.length-1;
 3         while(low<=high){
 4             int mid = (low+high)/2;
 5             if(A[mid] == target) return mid;
 6             else if(A[mid] > target) high = mid-1;
 7             else low = mid+1;
 8         }
 9         return low;
10     }

View Code

39. Combination Sum: https://leetcode.com/problems/combination-sum/

找出数组中所有相加可得到tar的组合(个数不限、使用次数不限)：

解法：(回溯法; target-index作为新的target从i处继续判断; 判断语句放在for外,则是target和0比较;注意递归参数是(tar-[i]和i))(PS:逻辑简单,刚开始参数搞错,结果就一直不对;要学会根据错误结果推断原因)

(1.helper(nums,tar,rst,tmp,index) 2.if(0)rst.add,if(<)return; 3.for(index)add,helper(,tar-[i],rst,tmp,i),remove; 4.conbSum:sort,rst,tmp,helper,return)

 1 public class Solution {
 2     public List<List<Integer>> combinationSum(int[] candidates, int target) {
 3         List<List<Integer>> rst = new ArrayList<List<Integer>>();
 4         Arrays.sort(candidates);
 5         List<Integer> tmp = new ArrayList<Integer>();
 6         helper(candidates, target, rst, tmp, 0);
 7         return rst;
 8     }
 9     public void helper(int[] nums, int target, List<List<Integer>> rst, List<Integer> tmp, int index){
10         if (target == 0) {
11             rst.add(new ArrayList<Integer>(tmp));
12             return;
13         }
14         if (target < 0) {
15             return;
16         }
17         for (int i = index; i < nums.length; i++) {
18             tmp.add(nums[i]);
19             helper(nums, target - nums[i], rst, tmp, i);
20             tmp.remove(tmp.size() - 1);
21         }
22     }
23 }

View Code

40. Combination Sum II: https://leetcode.com/problems/combination-sum-ii/

含重复数组找出和为tar的组合(个数不限，只能使用一次):

我的解法：(与Combination Sum的解法相同; 区别：1.回溯时要把指针后移一位i+1; 2.遍历时要跳重,只能使用每轮遍历重复数字的第一个(i=index || [i]!=[i-1])

(1.helper(nums,tar,rst,tmp,index) 2.if(0)rst.add,if(<)return; 3.for(index) if(||&&),add helper(,tar-[i],rst,tmp,i+1),remove; 4.cSum:sort,rst,tmp,help,retu)

 1 public class Solution {
 2     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 3         Arrays.sort(candidates);
 4         List<List<Integer>> rst = new ArrayList<>();
 5         List<Integer> tmp = new ArrayList<>();
 6         helper(candidates, target, rst, tmp, 0);
 7         return rst;
 8     }
 9     public void helper(int[] nums, int target, List<List<Integer>> rst, List<Integer> tmp, int index) {
10         if (target == 0) {
11             rst.add(new ArrayList<Integer>(tmp));
12             return;
13         }
14         if (target < 0) {
15             return;
16         }
17         for (int i = index; i < nums.length; i++) {
18             if (i == index || (i != index && nums[i] != nums[i - 1])) {
19                 tmp.add(nums[i]);
20                 helper(nums, target - nums[i], rst, tmp, i + 1);
21                 tmp.remove(tmp.size() - 1);
22             }
23         }
24     }
25 }

View Code

48. Rotate Image: https://leetcode.com/problems/rotate-image/

顺时针九十度旋转二维矩阵: (todo)

 1 public class Solution {
 2     public void rotate(int[][] matrix) {
 3         for(int i = 0; i<matrix.length; i++){
 4             for(int j = i; j<matrix[0].length; j++){
 5                 int temp = 0;
 6                 temp = matrix[i][j];
 7                 matrix[i][j] = matrix[j][i];
 8                 matrix[j][i] = temp;
 9             }
10         }
11         for(int i =0 ; i<matrix.length; i++){
12             for(int j = 0; j<matrix.length/2; j++){
13                 int temp = 0;
14                 temp = matrix[i][j];
15                 matrix[i][j] = matrix[i][matrix.length-1-j];
16                 matrix[i][matrix.length-1-j] = temp;
17             }
18         }
19     }
20 }

View Code

 1 public class Solution {
 2     public void rotate(int[][] matrix) {
 3         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 4             return;
 5         }
 6 
 7         int length = matrix.length;
 8 
 9         for (int i = 0; i < length / 2; i++) {
10             for (int j = 0; j < (length + 1) / 2; j++){
11                 int tmp = matrix[i][j];
12                 matrix[i][j] = matrix[length - j - 1][i];
13                 matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
14                 matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
15                 matrix[j][length - i - 1] = tmp;
16             }
17         }   
18     }
19 }

View Code

53. Maximum Subarray: https://leetcode.com/problems/maximum-subarray/

连续子数组的最大和:

解法：(动态规划?)(A[i]前的 Sum<0, 那么就从A[i]作为新的起始点; Sum>0, 那么比较Sum+A[i]和max的大小)(很乱……)

(maxSoFar,maxEndingHere)

1 public static int maxSubArray(int[] A) {
2     int maxSoFar=A[0], maxEndingHere=A[0];
3     for (int i=1;i<A.length;++i){
4         maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
5         maxSoFar=Math.max(maxSoFar, maxEndingHere);    
6     }
7     return maxSoFar;
8 }

View Code

 1 public class Solution {
 2     public int maxSubArray(int[] A) {
 3         if (A == null || A.length == 0){
 4             return 0;
 5         }
 6         
 7         int max = Integer.MIN_VALUE, sum = 0;
 8         for (int i = 0; i < A.length; i++) {
 9             sum += A[i];
10             max = Math.max(max, sum);
11             sum = Math.max(sum, 0);
12         }
13 
14         return max;
15     }
16 }

View Code

54.Spiral Matrix: https://leetcode.com/problems/spiral-matrix/

返回矩阵的螺旋顺序：

解法：(画出矩阵图, 第一趟为[00]-[0n], [1n]-[mn], [m,n-1]-[m0], [m-1,0]-[1,0]; 第二趟,左右边界各加1,用count计数; 判断只剩一行或一列的break)

(1.rst,if(); 2.rows,cols,count; 3.while(*2<) for for if(==1) for for, count++; 4.return rst;)

 1 public class Solution {
 2     public List<Integer> spiralOrder(int[][] matrix) {
 3         List<Integer> rst = new ArrayList<>();
 4         if (matrix == null || matrix.length == 0)
 5             return rst;
 6         int rows = matrix.length;
 7         int cols = matrix[0].length;
 8         int count = 0;
 9         while (count * 2 < rows && count * 2 < cols) {
10             for (int i = count; i < cols - count; i++) {
11                 rst.add(matrix[count][i]);
12             }
13             for (int i = count + 1; i < rows - count; i++) {
14                 rst.add(matrix[i][cols - count - 1]);
15             }
16             
17             if (rows - 2 * count == 1 || cols - 2 * count == 1)
18                 break;
19             
20             for (int i = cols - count - 2; i >= count; i--) {
21                 rst.add(matrix[rows - count - 1][i]);
22             }
23             for (int i = rows - count - 2; i >= count + 1; i--) {
24                 rst.add(matrix[i][count]);
25             }
26             count++;
27         }
28         return rst;
29     }
30 }

View Code

55. Jump Game：https://leetcode.com/problems/jump-game/

步数不大于值从开始跳到结尾：

解法1：DP动态规划 (定义数组boolean[] can, 对于数组中任意i,true的条件是存在j<i满足can[j]=true且j+a[j]<=i;所以需要遍历i之前的所有值; O(n^2))(大数据TLE)

(1.if(); 2.[]can,[0]; 3.for(0,n-1)for(0,i) if(&&)[i]; 4.return [n-1];)

 1 public class Solution {
 2     public boolean canJump(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return true;
 5         }
 6         boolean[] can = new boolean[nums.length];
 7         can[0] = true;
 8         for (int i = 0; i < nums.length; i++) {
 9             for (int j = 0; j < i; j++) {
10                 if (can[j] && j + nums[j] >= i) {
11                     can[i] = true;
12                 }
13             }
14         }
15         return can[nums.length - 1];
16     }
17 }

View Code

解法2：Greedy--根据已知条件得出局部最优解 (0-farthest-a[0];遍历数组,如果i在far范围内,那么far=max(far,a[i]+i); 最后判断far和n-1;)

 1 public class Solution {
 2     public boolean canJump(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return true;
 5         }
 6         int farthest = nums[0];
 7         for (int i = 1; i < nums.length; i++) {
 8             if (farthest >= i ) 
 9                 farthest = Math.max(farthest, i + nums[i]);
10         }
11         return farthest >= nums.length - 1;
12     }
13 }

View Code

 1 public class Solution {
 2     public boolean canJump(int[] A) {
 3         // think it as merging n intervals
 4         if (A == null || A.length == 0) {
 5             return false;
 6         }
 7         int farthest = A[0];
 8         for (int i = 1; i < A.length; i++) {
 9             if (i <= farthest && A[i] + i >= farthest) {
10                 farthest = A[i] + i;
11             }
12         }
13         return farthest >= A.length - 1;
14     }
15 }

View Code

59. Spiral Matrix II: https://leetcode.com/problems/spiral-matrix-ii/

平方螺旋矩阵：

我的解法：(与Spiral Matrix解法相同, 区别是rows和cols都是n, 定义count计数四边已经铺了数字的边框,定义num++;对四边分别for循环赋值, 内部与最外圈的区别就是多了一个count,包括起始条件+/-count, 终止条件+/-count; 前两个for顺序遍历, 中间插入判断条件break, 后两个for倒序;)

(1.int[][],num,count; 2.while(*2<) for for if() for for; 3.return)

 1 public class Solution {
 2     public int[][] generateMatrix(int n) {
 3         int[][] Matrix = new int[n][n];
 4         int count = 0;
 5         int num = 1;
 6         while (count * 2 < n) {
 7             for (int i = count; i < n - count; i++) {
 8                 Matrix[count][i] = num++;
 9             }
10             for (int i = count + 1; i < n - count; i++) {
11                 Matrix[i][n - count - 1] = num++;
12             }
13             
14             if (count * 2 == n - 1) break;
15             
16             for (int i = n - count - 2; i >= count; i--) {
17                 Matrix[n - count - 1][i] = num++;
18             }
19             for (int i = n - count - 2; i >= count + 1; i--) {
20                 Matrix[i][count] = num++;
21             }
22             count++;
23         }
24         return Matrix;
25     }
26 }

View Code

类似：(不定义count, 直接用n-2作为变化, 判断条件为n>0; 不过重复定义了xStart,yStart; 其实方法一样……)

 1 public class Solution {
 2     public int[][] generateMatrix(int n) {
 3         if (n < 0) {
 4             return null;
 5         }
 6 
 7         int[][] result = new int[n][n];
 8 
 9         int xStart = 0;
10         int yStart = 0;
11         int num = 1;
12 
13         while (n > 0) {
14             if (n == 1) {
15                 result[yStart][xStart] = num++;
16                 break;
17             }
18 
19             for (int i = 0; i < n - 1; i++) {
20                 result[yStart][xStart + i] = num++;
21             }
22 
23             for (int i = 0; i < n - 1; i++) {
24                 result[yStart + i][xStart + n - 1] = num++;
25             }
26 
27             for (int i = 0; i < n - 1; i++) {
28                 result[yStart + n - 1][xStart + n - 1 - i] = num++;
29             }
30 
31             for (int i = 0; i < n - 1; i++) {
32                 result[yStart + n - 1 - i][xStart] = num++;
33             }
34 
35             xStart++;
36             yStart++;
37             n = n - 2;
38         }
39 
40         return result;
41     }
42 }

View Code

62. Unique Paths: https://leetcode.com/problems/unique-paths/

网格首尾的所有可能路径：

Wrong!典型TLE解法：递归

1 public class Solution {
2     public int uniquePaths(int m, int n) {
3         if (m == 1 || n == 1) return 1;
4         return (uniquePaths(m - 1, n) + uniquePaths(m, n - 1));
5     }
6 }

View Code

解法：(for循环;第一列和第一行上的所有数sum为1,对于[i][j], 有递推关系sum=[i-1][j]+[i][j-1], return[m-1][n-1]) (Q: 所有递归均能改成for循环遍历+递推?)

(1.sum[][]; 2.for[i][0] for[0][i]; 3.for()for()[i][j]; 4.return[-1][-1])

 1 public class Solution {
 2     public int uniquePaths(int m, int n) {
 3         int[][] sum = new int[m][n];
 4         for (int i = 0; i < m ; i++) {
 5             sum[i][0] = 1;
 6         }
 7         for (int i = 0; i < n; i++) {
 8             sum[0][i] = 1;
 9         }
10         for (int i = 1; i < m; i++) {
11             for (int j = 1; j < n; j++) {
12                 sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
13             }
14         }
15         return sum[m - 1][n - 1];
16     }
17 }

View Code

63. Unique Paths II: https://leetcode.com/problems/unique-paths-ii/

有障碍的网格的所有可能路径：

我的解法: (类似U Paths, 区别:对于第一行和第一列,如果在[i][0]出现1,那么i上的sum为1,i下的sum为零;用递推关系sum[i][0] = sum[i-1][0]来表示, 当存在a[i][0]为1时,则sum[i][0]=0,后面依然用递推关系……(这段似乎可以用指针优化,一旦发现第一个1,就把后面的sum都置零?); 其次对于[i][j]区别就是多一个判断条件,如果a[i][j]=1,那么sum[i][j]=0)

(1.m,n,int,if,sum; 2.for(1,m)if(0)[i][0]=[i-1][0] else[i][0]=0; for(1,n); 3.for(1,m)(1,n)if(1)0 else[i][j]=[i-1][j]+[i][j-1]; 4.return)

 1 public class Solution {
 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3         int m = obstacleGrid.length;
 4         int n = obstacleGrid[0].length;
 5         int[][] sum = new int [m][n];
 6         if (obstacleGrid[0][0] == 1) return 0;
 7         sum[0][0] = 1;
 8         for (int i = 1; i < m; i++) {
 9             if (obstacleGrid[i][0] == 0) 
10                 sum[i][0] = sum[i - 1][0];
11             else sum[i][0] = 0;
12         }
13         for (int i = 1; i < n; i++) {
14             if (obstacleGrid[0][i] == 0)
15                 sum[0][i] = sum[0][i - 1];
16             else sum[0][i] = 0;
17         }
18         for (int i = 1; i < m; i++) {
19             for (int j = 1; j < n; j++) {
20                 if (obstacleGrid[i][j] == 1)
21                     sum[i][j] = 0;
22                 else
23                     sum[i][j] = sum[i -1][j] + sum[i][j - 1];
24             }
25         }
26         return sum[m - 1][n - 1];
27     }
28 }

View Code

类似: (第一行第一列遇到1后就break,其他基本相同)

 1 public class Solution {
 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3         if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
 4             return 0;
 5         }
 6         
 7         int n = obstacleGrid.length;
 8         int m = obstacleGrid[0].length;
 9         int[][] paths = new int[n][m];
10         
11         for (int i = 0; i < n; i++) {
12             if (obstacleGrid[i][0] != 1) {
13                 paths[i][0] = 1;
14             } else {
15                 break;
16             }
17         }
18         
19         for (int i = 0; i < m; i++) {
20             if (obstacleGrid[0][i] != 1) {
21                 paths[0][i] = 1; 
22             } else {
23                 break;
24             }
25         }
26         
27         for (int i = 1; i < n; i++) {
28             for (int j = 1; j < m; j++) {
29                 if (obstacleGrid[i][j] != 1) {
30                     paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
31                 } else {
32                     paths[i][j] = 0;
33                 }
34             }
35         }
36         
37         return paths[n - 1][m - 1];
38     }
39 }

View Code

64. Minimum Path Sum：https://leetcode.com/problems/minimum-path-sum/

网格路径上元素和的最小值：

我的解法：(类似U Paths 和UP II, 方法是动态规划/递推关系。对于grid[i][j], sum的值为sum[i-1][j]和sum[i][j-1]的小的值加上grid[i][j]; 其次对于第一行和第一列,sum就是[0][i-1]+grid[0][i]) (PS:Bug Free!! 一次AC!!)

 1 public class Solution {
 2     public int minPathSum(int[][] grid) {
 3         int m = grid.length;
 4         int n = grid[0].length;
 5         int[][] sum = new int[m][n];
 6         sum[0][0] = grid[0][0];
 7         for (int i = 1; i < m; i++) {
 8             sum[i][0] = sum[i - 1][0] + grid[i][0];
 9         }
10         for (int i = 1; i < n; i++) {
11             sum[0][i] = sum[0][i - 1] + grid[0][i];
12         }
13         for (int i = 1; i < m; i++) {
14             for (int j = 1; j < n; j++) {
15                 sum[i][j] = Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
16             }
17         }
18         return sum[m - 1][n - 1];
19     }
20 }

View Code

73. Set Matrix Zeroes：https://leetcode.com/problems/set-matrix-zeroes/

零所在的行和列都置零：

解法1：(O(m+n)space, 初始化row[]和col[], if(matrix[i][j])等于零, 就将row[i]和col[j]置一; 遍历row,将为1的i行置零; 同理col;)

(1.m,n,row,col; 2.for()for()if(=)1; 3.for()if()for()0; for()if()for()0; )

 1 public class Solution {
 2     public void setZeroes(int[][] matrix) {
 3         int m = matrix.length;
 4         int n = matrix[0].length;
 5         int[] row = new int[m];
 6         int[] col = new int[n];
 7         for (int i = 0; i < m; i++) {
 8             for (int j = 0; j < n; j++) {
 9                 if (matrix[i][j] == 0) {
10                     row[i] = 1;
11                     col[j] = 1;
12                 }
13             }
14         }
15         for (int i = 0; i < m; i++) {
16             if (row[i] == 1) {
17                 for (int j = 0; j < n; j++) {
18                     matrix[i][j] = 0;
19                 }
20             }
21         }
22         for (int j = 0; j < n; j++) {
23             if (col[j] == 1) {
24                 for (int i = 0; i < m; i++) {
25                     matrix[i][j] = 0;
26                 }
27             }
28         }
29 
30     }
31 }

View Code

解法2：(In place 用第一行和第一列作为标记; 从[1][1]后遍历, 如果[i][j]=0, 那么就标记对应的[i][0]和[0][j]=0; 但需要单独考虑row0和col0; 如果存在i=0或j=0时[i][j]=0,需要先暂时用fr和fc标记, 最后额外将first row或者first col置零)

(1.m,n,fr,fc; 2.for()for()if(=) if()if() 0 0; 3.for(1)for(1)if(||)0; 4.if(fr) if(fc);)

 1 public class Solution {
 2     public void setZeroes(int[][] matrix) {
 3         int m = matrix.length;
 4         int n = matrix[0].length;
 5         boolean fr = false;
 6         boolean fc = false;
 7         for (int i = 0; i < m; i++) {
 8             for (int j = 0; j < n; j++) {
 9                 if (matrix[i][j] == 0) {
10                     if (i == 0) fr = true;
11                     if (j == 0) fc = true;
12                     matrix[i][0] = 0;
13                     matrix[0][j] = 0;
14                 }
15             }
16         }
17         for (int i = 1; i < m; i++) {
18             for (int j = 1; j < n; j++) {
19                 if (matrix[i][0] == 0 || matrix[0][j] == 0) {
20                     matrix[i][j] = 0;
21                 }
22             }
23         }
24         if (fr) {
25             for (int i = 0; i < n; i++) {
26                 matrix[0][i] = 0;
27             }
28         }
29         if (fc) {
30             for (int i = 0; i < m; i++) {
31                 matrix[i][0] = 0;
32             }
33         }
34     }
35 }

View Code

74. Search a 2D Matrix: https://leetcode.com/problems/search-a-2d-matrix/

查找二维矩阵: (参考LintCode 1-30 里的T28)

解法1：暴力解法 (for)

 1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         int row = matrix.length;
 4         int col = matrix[0].length;
 5         for (int i = 0; i < row; i++) {
 6             for (int j = 0; j < col; j++) {
 7                 if (matrix[i][j] == target)
 8                     return true;
 9             }
10         }
11         return false;
12     }
13 }

View Code

解法2：两次二分(第一次找到tarRow,防止遗漏while(+1<)+mid+if判断; 第二次while(<=)+ mid+1/-1;)

(1.ifif; 2.start,end,row; 3.while(+1<)mid if(=)if(</>)mid; 4.if(<=)elseif(<=)else false; 5.while(<=)if eif e; 6.return false;)

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix == null || matrix.length == 0){
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0){
            return false;
        }
        int start = 0;
        int end = matrix.length - 1;
        int row ;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (matrix[mid][0] == target){
                return true;
            } else if (matrix[mid][0] < target) {
                start = mid ;
            } else {
                end = mid ;
            }
        }
        if (matrix[end][0] <= target){
            row = end;
        } else if (matrix[start][0] <= target){
            row = start;
        } else {
            return false;
        }
     
        start = 0;
        end = matrix[0].length - 1;
        while (start <= end) {
            int mid = start + (end - start)/2;
            if (matrix[row][mid] == target){
                return true;
            } else if (matrix[row][mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
    }
}

View Code

解法3：一次二分(把matrix看成数组, m*n-1; row=mid/col, col=mid%col;)

(1.ifif; 2.row,col,start,end; 3.while(<=)mid num=[/][%], if()e if() e; 4.return false; )

 1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         if (matrix ==  null ||  matrix.length == 0) 
 4             return false;
 5         if (matrix[0] == null || matrix[0].length == 0) 
 6             return false;
 7         int row = matrix.length;
 8         int col = matrix[0].length;
 9         
10         int start = 0, end = row * col - 1;
11         while (start <= end) {
12             int mid = start + (end - start) / 2;
13             if (matrix[mid / col][mid % col] == target) {
14                 return true;
15             } else if (matrix[mid / col][mid % col] > target) {
16                 end = mid - 1;
17             } else
18                 start = mid + 1;
19         }
20         return false;
21     }
22 }

View Code

75. Sort Colors: https://leetcode.com/problems/sort-colors/

只含0,1,2的数组排序:

解法1：计数两趟for循环:

 1 public class Solution {
 2     public void sortColors(int[] nums) {
 3         int cnt0 = 0, cnt1 = 0;
 4         for (int i = 0; i < nums.length; i++) {
 5             if (nums[i] == 0)
 6                 cnt0++;
 7             else if (nums[i] == 1)
 8                 cnt1++;
 9         }
10         for (int i = 0; i < nums.length; i++) {
11             if (i < cnt0) 
12                 nums[i] = 0;
13             else if (i < cnt0 + cnt1)
14                 nums[i] = 1;
15             else nums[i] = 2;
16         }
17     }
18 }

View Code

解法2：Two Pointers (左指针指向0的后一位, 右指针指向2的前一位, i遍历l; 如果遍历到[i]为0,交换pl和i,pr++,i++; 如果遍历到2,交换pr和i,pr--; 遍历到1,i++;)(注意：循环条件i<=pr; [i]=2时,swap后i不增;)

(1.pl,pr,i; 2.for(<=)if()swap(++,++), if()++, if()swap(--); 3.swap)

 1 public class Solution {
 2     public void sortColors(int[] nums) {
 3         int pl = 0, pr = nums.length - 1;
 4         for (int i = 0; i <= pr;) {
 5             if (nums[i] == 0)
 6                 swap(nums, i++, pl++);
 7             else if (nums[i] == 1)
 8                 i++;
 9             else
10                 swap(nums, i, pr--);
11         }
12     }
13     public void swap (int[]a, int i, int j) {
14         int tmp = a[i];
15         a[i] = a[j];
16         a[j] = tmp;
17     }
18 }

View Code

78. Subsets: https://leetcode.com/problems/subsets/

数组的子集数组：(参考LintCode 1-30: T17)

解法1：(1.rst,if(); 2.tmp,helper,return; 3.helper(nums,rst,tmp,index), add, for(index) add,help(i+1),remove)

 1 public class Solution {
 2     public List<List<Integer>> subsets(int[] nums) {
 3         ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>();
 4         if (nums.length == 0) {
 5             rst.add(new ArrayList<Integer>());
 6             return rst;
 7         }
 8         List<Integer> tmp = new ArrayList<Integer>();
 9         helper(nums, rst, tmp, 0);
10         return rst;
11     }
12     public void helper(int[] nums, List<List<Integer>> rst, List<Integer> tmp, int index){
13         rst.add(new ArrayList<Integer>(tmp));
14         
15         for (int i = index; i < nums.length; i++) {
16             tmp.add(nums[i]);
17             helper(nums, rst, tmp, i + 1);
18             tmp.remove(tmp.size() - 1);
19         }
20     }
21 }

View Code

解法2：位运算(用bit位来表示这一位的number要不要取，第一位有1，0即取和不取2种可能性。所以只要把0到N种可能都用bit位表示，再把它转化为数字集合，就可以了)

 1 class Solution {
 2     /**
 3      * @param S: A set of numbers.
 4      * @return: A list of lists. All valid subsets.
 5      */
 6     public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
 7         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 8         int n = nums.length;
 9         Arrays.sort(nums);
10         
11         // 1 << n is 2^n
12         // each subset equals to an binary integer between 0 .. 2^n - 1
13         // 0 -> 000 -> []
14         // 1 -> 001 -> [1]
15         // 2 -> 010 -> [2]
16         // ..
17         // 7 -> 111 -> [1,2,3]
18         for (int i = 0; i < (1 << n); i++) {
19             ArrayList<Integer> subset = new ArrayList<Integer>();
20             for (int j = 0; j < n; j++) {
21                 // check whether the jth digit in i's binary representation is 1
22                 if ((i & (1 << j)) != 0) {
23                     subset.add(nums[j]);
24                 }
25             }
26             result.add(subset);
27         }
28         
29         return result;
30     }
31 }

View Code

79. Word Search：https://leetcode.com/problems/word-search/

二维矩阵查找字符串(todo)

80. Remove Duplicates from Sorted Array II: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

解法：<Two Pointers> (index指向"新"数组的后一位, i指向原数组; 如果i所指的数num和index-2所指的数相同, 表面new Array里已经包含两个数了, 那么就跳过这个数;)

(1.index; 2.for() if(<2||!=[index-2])= 3.return index;)

 1 public class Solution {
 2     public int removeDuplicates(int[] nums) {
 3         int index = 0;
 4         for (int i = 0; i < nums.length; i++) {
 5             if (i < 2 || nums[i] != nums[index - 2]) {
 6                 nums[index++] = nums[i];
 7             }
 8         }
 9         return index;
10     }
11 }

View Code

 1 Remove Duplicates from Sorted Array(no duplicates) :
 2 
 3 public int removeDuplicates(int[] nums) {
 4     int i = 0;
 5     for(int n : nums)
 6         if(i < 1 || n > nums[i - 1]) 
 7             nums[i++] = n;
 8     return i;
 9 }
10 Remove Duplicates from Sorted Array II (allow duplicates up to 2):
11 
12 public int removeDuplicates(int[] nums) {
13    int i = 0;
14    for (int n : nums)
15       if (i < 2 || n > nums[i - 2])
16          nums[i++] = n;
17    return i;
18 }

View Code

81. Search in Rotated Sorted Array II: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

(todo)

90. Subsets II: https://leetcode.com/problems/subsets-ii/

含重复元素的子集：

 1 public class Solution {
 2     public List<List<Integer>> subsetsWithDup(int[] nums) {
 3         List<List<Integer>> rst = new ArrayList<>();
 4         if (nums.length == 0) {
 5             rst.add(new ArrayList<Integer>());
 6             return rst;
 7         }
 8         Arrays.sort(nums);
 9         List<Integer> tmp = new ArrayList<Integer>();
10         helper(nums, rst, tmp, 0);
11         return rst;
12     }
13     public void helper(int[] nums, List<List<Integer>> rst, List<Integer> tmp, int index) {
14         rst.add(new ArrayList<Integer>(tmp));
15         for (int i = index; i < nums.length; i++) {
16             if (i == index || (i > index && nums[i] != nums[i - 1])){
17                 tmp.add(nums[i]);
18                 helper(nums, rst, tmp, i + 1);
19                 tmp.remove(tmp.size() - 1);
20             }
21             
22         }
23     }
24 }

View Code