【持续更新】leetcode算法-数组篇

会在近期陆续地完成数组篇的整理，希望对找工作的小伙伴有所帮助。

1、Two Sum：两数相加为一固定值，求其下标。一次遍历数组，用一个hash表存储已经访问过的数及其下标，对于新访问的数value，查hash表中是否有target-value的值，如果有，程序输出，如果没有，继续访问下一个数直到访问完。

 1 public int[] twoSum(int[] nums, int target) {
 2     Map<Integer, Integer> hash = new HashMap<>();
 3     for (int i=0; i<nums.length; i++){
 4         if(hash.containsKey(target-nums[i])){
 5             return new int[]{hash.get(target-nums[i]),i};
 6         }else{
 7             hash.put(nums[i],i);
 8         }
 9     }
10     return new int[]{0,0};
11 }

2、Median of Two Sorted Arrays：求两个有序数组的中位数。其实就是求第k大的数。首先比较两数组k/2处的数的大小，若a[k/2]<b[k/2]，则a[0,...k/2]可以省去，则求剩余数组k-k/2大的数，依次下去，知道k=1，求第1大的数，即比较两数组的第一个元素，取小的那个。

3、Container With Most Water：给一个数组，每一个元素表示一个高度，找两个元素和x轴围城的容器装下水的最大量。直接的做法是暴力求解，O（n2）复杂度。优化做法是，从两头向中间靠，比较两头元素的大小，大的不动，小的往中间移动。

 1 public int maxArea(int[] height) {
 2     int max = 0;
 3     int left = 0;
 4     int right = height.length - 1;
 5     int curArea = 0;
 6     while (left < right) {
 7         curArea = (right - left) * (height[right] < height[left] ? height[right--] : height[left++]);
 8         if (curArea > max)
 9             max = curArea;
10     }
11     return max;
12 }

4、3Sum：在数组中求三个数相加等于0。先排序，然后遍历数组，两重循环。3个指针，外层循环遍历数组，内层循环遍历外层循环后面的数，如果和大于0，则指针往左移动，如果小于0，则往右移动。

 1 public List<List<Integer>> threeSum(int[] nums) {
 2     List<List<Integer>> list = new ArrayList<List<Integer>>();
 3     Set<List<Integer>> set = new HashSet<>();
 4     sort(nums);
 5     int j = 0;
 6     int k = 0;
 7     for (int i = 0; i < nums.length - 2; i++) {
 8         j = i + 1;
 9         k = nums.length - 1;
10         while (j < k) {
11             int x = nums[i] + nums[j] + nums[k];
12             if (x == 0) {
13                 List<Integer> innerList = new ArrayList<>();
14                 innerList.add(nums[i]);
15                 innerList.add(nums[j]);
16                 innerList.add(nums[k]);
17                 if (!set.contains(innerList)) {
18                     set.add(innerList);
19                     list.add(innerList);   
20                 }
21                 j = j + 1;
22                 k = k - 1;
23             } else if (x > 0) {
24                 k = k - 1;
25             } else {
26                 j = j + 1;
27             }
28         }
29     }
30     return list;
31 }

5、3Sum Closest：类似3Sum

6、4Sum：类似3Sum

7、Remove Duplicates from Sorted Array：有序数组去重，返回剩余数的个数

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

8、Remove Element：数组中移除给定的数，返回剩余数的个数

1 public int removeElement(int[] nums, int val) {
2     int index=0;
3     for(int i =0; i<nums.length; i++){
4         if(nums[i] != val) nums[index++]=nums[i];
5     }
6     return index;
7 }

9、Next Permutation：数组表示一个整数，返回下一个排列数，如果没有比原数组大的排列数，则返回最小的排列数

 1 public void nextPermutation(int[] nums) {
 2     if(nums==null || nums.length<2) return;
 3     int len = nums.length;
 4     // 从右向左遍历，找到第一个前一个数小于后一个的数（升序对），记value=nums[i-1]
 5     int i = len - 1;
 6     while (i>0 && nums[i-1]>=nums[i]){
 7         i--;
 8     }
 9     if(i==0){
10         reverse(nums, 0, len-1);     // 反转数组
11     }else{
12         // 从右向左遍历，找到第一个大于value的数
13         int j = i-1;
14         int k = len -1;
15         while(nums[j]>=nums[k]){
16             k--;
17         }
18         int temp = nums[j];
19         nums[j] = nums[k];
20         nums[k] = temp;
21         reverse(nums, i, len-1);
22     }
23 }

10、Search in Rotated Sorted Array：在循环有序的数组（数没有重复）中查询一个数，返回这个数的下标，没有则返回-1

 1 public int search(int[] nums, int target) {
 2     if(nums==null || nums.length==0) return -1;
 3     // 找到最小值，即旋转中心
 4     int n=nums.length;
 5     int lo=0, hi=n-1;
 6     while(lo<hi){
 7         int mid=(hi-lo)/2+lo;
 8         if(nums[mid]>nums[hi]) lo=mid+1;
 9         else hi=mid;
10     }
11     int pivot=lo;
12     lo=0;
13     hi=n-1;
14     while(lo<=hi){
15         int mid=(hi-lo)/2+lo;
16         int realmid=(mid+pivot)%n;
17         if(nums[realmid]==target) return realmid;
18         else if(nums[realmid]>target) hi=mid-1;
19         else lo=mid+1;
20     }
21     return -1;
22 }

11、Search for a Range：找到给定的数在有序数组中的下标区间，两次二分搜索，一次找左边界，一次找右边界

 1 public int[] searchRange(int[] nums, int target) {
 2     int[] ret = {-1,-1};
 3     if(nums==null || nums.length==0) return nums;
 4     int n=nums.length;
 5     int lo=0, hi=n-1;
 6     while(lo<hi){
 7         int mid=(hi-lo)/2+lo;
 8         if(nums[mid]<target) lo=mid+1;
 9         else hi=mid;
10     }
11     if(nums[lo]!=target) return ret;
12     ret[0]=lo;
13  
14     lo=0;
15     hi=n-1;
16     while(lo<hi){
17         int mid=(hi-lo)/2+lo+1;     // 保证偏向右边
18         if(nums[mid]>target) hi=mid-1;
19         else lo=mid;
20     }
21     ret[1]=lo;
22     return ret;
23 }

12、Search Insert Position：二分查找

13、Combination Sum：求数组中元素等于给定的数的集合，允许重复，回溯法

 1 public List<List<Integer>> combinationSum(int[] candidates, int target) {
 2     List<List<Integer>> res = new ArrayList<List<Integer>>();
 3     if(candidates == null || candidates.length == 0)
 4         return res;
 5     List<Integer> list = new ArrayList<>();
 6     helper(candidates, target, 0, list, res);
 7     return res;
 8 }
 9 public void helper(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> res) {
10     if(target == 0){
11         res.add(new ArrayList<>(temp));
12         return;
13     }
14     if(target < 0) return;
15     for (int i = start; i < candidates.length; i++){
16         temp.add(candidates[i]);
17         helper(candidates, target-candidates[i], i, temp, res);
18         temp.remove(temp.size() - 1);
19     }
20 }

14、Combination Sum II：求数组中元素等于给定的数的集合，数组中的元素只能用一次，回溯法

 1 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 2     List<List<Integer>> res = new ArrayList<List<Integer>>();
 3     if(candidates.length == 0 || candidates == null)
 4         return res;
 5     List<Integer> list = new ArrayList<>();
 6     Arrays.sort(candidates);
 7     helper(candidates, target, 0, list, res);
 8     return res;
 9 }
10 public void helper(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> res) {
11     if(target == 0){
12         res.add(new ArrayList<>(temp));
13         return;
14     }
15     else if(target < 0)
16         return;
17     else {
18         for (int i = start; i < candidates.length; i++){
19             // 跳过重复元素
20             if(i>start && candidates[i]==candidates[i-1])
21                 continue;
22             temp.add(candidates[i]);
23             helper(candidates, target-candidates[i], i+1, temp, res);
24             temp.remove(temp.size() - 1);
25         }
26     }
27 }

15、First Missing Positive：无序数组，找到第一个缺失的正数，主要思想是将正确的数放到正确的位置上

 1 public int firstMissingPositive(int[] nums) {
 2     if(nums == null || nums.length == 0) return 1;
 3     int n = nums.length;
 4     for (int i=0; i<n; i++){
 5         while(nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1]) swap(nums, i, nums[i]-1);
 6     }
 7     for(int i=0; i<n; i++){
 8         if(nums[i]!=i+1) return i+1;
 9     }
10     return n+1;
11 }

16、Trapping Rain Water：求最大的积水量。解法：先找到最大高度的下标，然后分别从两边往最大高度靠，同时维护一个当前最大值变量，积水量就是当前最大值减去当前高度。

 1 public int trap(int[] height) {
 2     if (height==null || height.length <= 2) return 0;
 3     // 找最大高度
 4     int maxIndex=0;
 5     int max=0;
 6     for(int i=0; i<height.length; i++){
 7         if(height[i]>max){
 8             max=height[i];
 9             maxIndex=i;
10         }
11     }
12     int result=0;
13     int curMax=0;
14     for(int i=0; i<maxIndex; i++){
15         if(height[i]<curMax){
16             result += curMax-height[i];
17         }else{curMax=height[i];}
18     }
19     curMax=0;
20     for(int i=height.length-1; i>maxIndex; i--){
21         if(height[i]<curMax) result += curMax-height[i];
22         else curMax=height[i];
23     }
24     return result;
25 }

17、Jump Game II：给定一个数组，求数组头到数组尾的最少的步数。贪心法。

 1 public int jump(int[] nums) {
 2     if(nums==null || nums.length==0) return 0;
 3     int dis=0;
 4     int edge=0;
 5     int steps=0;
 6     for(int i=0; i<nums.length-1 && i<=dis; i++){
 7         dis=Math.max(dis, i+nums[i]);
 8         if(dis>=nums.length-1) return steps+1;
 9         // 判断是否在一次跳转之内，只有等于最大边界时才会步数加1
10         if(edge == i){
11             edge = dis;
12             steps++;
13         }
14     }
15     return 0;
16 }

18、Rotate Image：顺时针旋转n*n矩阵。先转置，再左右翻转。

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

19、Maximum Subarray：求数组的最大子串和。

 1 public int maxSubArray(int[] nums) {
 2     if(nums==null || nums.length==0) return 0;
 3     int max=nums[0];
 4     int curSum=0;
 5     for(int i=0; i<nums.length; i++){
 6         curSum=Math.max(nums[i], curSum+nums[i]);
 7         max=Math.max(max, curSum);
 8     }
 9     return max;
10 }

20、Spiral Matrix：螺旋输出矩阵的元素

 1 public List<Integer> spiralOrder(int[][] matrix) {
 2     List<Integer> res = new ArrayList<>();
 3     int m = matrix.length;
 4     if (m < 1) return res;
 5     int n = matrix[0].length;
 6     int left = 0;
 7     int right = n-1;
 8     int up = 0;
 9     int down = m-1;
10     while (left <= right && up <= down) {
11         // traverse right
12         for (int i = left; i <= right; i++) {
13             res.add(matrix[up][i]);
14         }
15         up++;
16         // traverse down
17         for (int i = up; i <= down; i++) {
18             res.add(matrix[i][right]);
19         }
20         right--;
21         // traverse left
22         if (up <= down) {
23             for (int i = right; i >= left; i--) {
24                 res.add(matrix[down][i]);
25             }
26         }
27         down--;
28         // traverse up
29         if (left <= right) {
30             for (int i = down; i >= up; i--) {
31                 res.add(matrix[i][left]);
32             }
33         }
34         left++;
35     }
36 
37     return res;
38 }

21、Jump Game：给定一个数组，判断能否从数组头到达数组尾。贪心法。维护一个变量，记录当前位置能到达的最远的距离，当最远距离超出数组长度，即可判断能到达数组尾。

1 public boolean canJump(int[] nums) {
2     if(nums==null || nums.length==0) return false;
3     int dis=0;
4     for(int i=0; i<nums.length && i<=dis; i++){
5         dis = Math.max(dis, i+nums[i]);
6         if(dis >= nums.length-1) return true;
7     }
8     return false;
9 }

22、Merge Intervals：合并区间。先按照区间的前端进行排序操作，再查看是否出现覆盖的情况。

 1 public List<Interval> merge(List<Interval> intervals) {
 2     List<Interval> res = new ArrayList<>();
 3     int n = intervals.size();
 4     if (n < 1) return res;
 5     // Sort by ascending starting point using an anonymous Comparator
 6     Collections.sort(intervals, new Comparator<Interval>() {
 7         @Override
 8         public int compare(Interval i1, Interval i2) {
 9             return Integer.compare(i1.start, i2.start);
10         }
11     });
12     int start = intervals.get(0).start;
13     int end = intervals.get(0).end;
14     for(int i=1; i<n; i++){
15         Interval curInteval = intervals.get(i);
16         if(curInteval.start <= end){
17             end = Math.max(end, curInteval.end);
18         }
19         else{
20             res.add(new Interval(start, end));
21             start = curInteval.start;
22             end = curInteval.end;
23         }
24     }
25 }

23、Insert Interval：给定一个按前端排好序的区间数组，现有另外一个区间，求插入并合并后的区间。

 1 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
 2     int i=0;
 3     while(i < intervals.size() && intervals.get(i).end < newInterval.start) i++;          // 是否可以用二分找到这个i？
 4     while(i<intervals.size() && intervals.get(i).start <= newInterval.end){
 5         newInterval = new Interval(Math.min(intervals.get(i).start, newInterval.start), Math.max(intervals.get(i).end, newInterval.end));
 6         intervals.remove(i);
 7     }
 8     intervals.add(i,newInterval);
 9     return intervals;
10 }

24、Spiral Matrix II：生成螺旋的矩阵

 1 public int[][] generateMatrix(int n) {
 2     int[][] matrix = new int[n][n];
 3     if (n < 1)
 4         return matrix;
 5     int count = 1;
 6     int left = 0;
 7     int right = n-1;
 8     int up = 0;
 9     int down = n-1;
10     while (left <= right && up <= down) {
11         for (int i = left; i <= right; i++) {
12             matrix[up][i] = count;
13             count++;
14         }
15         up++;
16         for (int i = up; i <= down; i++) {
17             matrix[i][right] = count;
18             count++;
19         }
20         right--;
21         if (up <= down) {
22             for (int i = right; i >= left; i--) {
23                 matrix[down][i] = count;
24                 count++;
25             }
26             down--;
27         }
28         if (left <= right) {
29             for (int i = down; i >= up; i--) {
30                 matrix[i][left] = count;
31                 count++;
32             }
33             left++;
34         }
35     }
36     return matrix;
37 }

25、Unique Paths：求从左上到右下的路径数。

public int uniquePaths(int m, int n) {
    int[] paths = new int[n+1];
    Arrays.fill(paths, 1);
    paths[0] = 0;
    for(int i=0; i<m-1; i++){
        for(int j=0; j<n; j++){
            paths[j+1] = paths[j+1] + paths[j];
        }
    }
    return paths[n];
}

26、Unique Paths II：存在障碍的情况下，求从左上到右下的路径数。

 1 public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 2     int n = obstacleGrid.length;
 3     int m = obstacleGrid[0].length;
 4     int[][] p = new int[n][m];
 5     // 初始化第一行
 6     for (int i = 0; i < m; i++){
 7         p[0][i] = 1 - obstacleGrid[0][i];
 8         if (p[0][i] == 0)   break;
 9     }
10     // 初始化第一列
11     for (int j = 0; j < n; j++){
12         p[j][0] = 1 - obstacleGrid[j][0];
13         if (p[j][0] == 0) break;
14     }
15     for ( int i = 1; i < n; i++){
16         for (int j = 1; j < m; j++) {
17             if(obstacleGrid[i][j] == 1)
18                 p[i][j] = 0;
19             else p[i][j] = p[i-1][j] + p[i][j-1];
20         }
21     }
22     return p[n-1][m-1];
23 }

27、Minimum Path Sum：求从左上到右下的最小的路径的长度，只能向右或向下走。

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

28、Plus One：数组加1

public int[] plusOne(int[] digits) {
    int carry = 1;
    for(int i=digits.length-1; i>=0; i--){
        carry += digits[i];
        digits[i] = carry % 10;
        carry /= 10;
    }
    if(carry==0) return digits;
    else{
        int[] newdigits = new int[digits.length+1];
        newdigits[0]=1;
        for(int i=1; i<newdigits.length; i++){
            newdigits[i]=digits[i-1];
        }
        return newdigits;
    }
}

29、Set Matrix Zeroes：当(i,j)=0是，把第i行和第j列置为0

 1 public void setZeroes(int[][] matrix) {
 2     boolean col0 = false;
 3     for (int i = 0; i < matrix.length; i++) {
 4         if(matrix[i][0]==0) col0=true;
 5         for (int j = 1; j < matrix[0].length; j++) {
 6             if (matrix[i][j] == 0) {
 7                 matrix[0][j] = 0;
 8                 matrix[i][0] = 0;
 9             }
10         }
11     }
12     for (int i = matrix.length-1; i>=0; i--) {
13         for (int j = matrix[0].length-1; j>=1; j--) {
14             if (matrix[0][j] == 0 || matrix[i][0] == 0) {
15                 matrix[i][j] = 0;
16             }
17         }
18         if(col0) matrix[i][0]=0;
19     }
20 }

30、Search a 2D Matrix：在矩阵里查找数。二分查找

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

31、Sort Colors：给定一个数组，元素只有0,1,2，给它排序。可以用计数排序，也可以用交换。

 1 public void sortColors(int[] nums) {
 2     if(nums==null || nums.length==0) return;
 3     int lo=0;
 4     int hi=nums.length-1;
 5     int i=0;
 6     while(i<=hi){
 7         if(nums[i]==0) swap(nums, i++, lo++);
 8         else if(nums[i]==2) swap(nums, i, hi--);
 9         else{i++;}
10     }
11 }

32、Subsets：求一个集合的所有子集

 1 public List<List<Integer>> subsets(int[] nums) {
 2     List<List<Integer>> res = new ArrayList<>();
 3     List<Integer> list = new ArrayList<>();
 4     res.add(list);
 5     for(int i=0; i<nums.length; i++){
 6         int size = res.size();
 7         for(int k=0; k<size; k++){
 8             List<Integer> newList = new ArrayList<>(res.get(k));
 9             newList.add(nums[i]);
10             res.add(newList);
11         }
12     }
13     return res;
14 }

 1 public List<List<Integer>> subsets(int[] nums) {
 2     Arrays.sort(nums);
 3     List<List<Integer>> res = new ArrayList<>();
 4     int totalNumber = 1 << nums.length;
 5     for(int i=0; i<totalNumber; i++){
 6         List<Integer> set = new ArrayList<>();
 7         for(int j=0; j<nums.length; j++){
 8             if(((i>>>j) & 0x1) == 1) set.add(nums[j]);
 9         }
10         res.add(set);
11     }
12     return res;
13 }

33、Word Search：在二维字符数组中，查找单词，回溯法

 1 public boolean exist(char[][] board, String word) {
 2     for(int i = 0; i < board.length; i++)
 3         for(int j = 0; j < board[0].length; j++){
 4             if(exist(board, i, j, word, 0)) return true;
 5         }
 6     return false;
 7 }
 8 private boolean exist(char[][] board, int i, int j, String word, int ind){
 9     if(ind == word.length()) return true;
10     if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind)) return false;
11     char ch=board[i][j];
12     board[i][j]='*';
13     boolean result =    exist(board, i-1, j, word, ind+1) ||
14                         exist(board, i, j-1, word, ind+1) ||
15                         exist(board, i, j+1, word, ind+1) ||
16                         exist(board, i+1, j, word, ind+1);
17     board[i][j] = ch;
18     return result;
19 }

34、Remove Duplicates from Sorted Array II：数组已排序，去除数组中重复的元素，允许出现两次

 1 public int removeDuplicates(int[] nums) {
 2     if(nums.length <= 2) return nums.length;
 3     int index=0;
 4     int p=1;
 5     int counter=1;
 6     while(p<nums.length){
 7         if(nums[p] == nums[index]){
 8             if(counter == 2){
 9                 p++;
10             }
11             else{
12                 nums[++index] = nums[p];
13                 p++;
14                 counter = 2;
15             }
16         }
17         else {
18             nums[++index] = nums[p];
19             p++;
20             counter = 1;
21         }
22     }
23     return index+1;
24 }

35、Search in Rotated Sorted Array II：在循环有序数组中查找，数组中有重复的数

 1 public class Solution {
 2     public boolean search(int[] nums, int target) {
 3         if (nums.length < 1)
 4             return false;
 5         int start = 0;
 6         int end = nums.length - 1;
 7         while (start < end) {
 8             int mid = start + (end-start)/2;
 9             if (nums[mid] == target) return true;
10 
11             if (nums[start] < nums[mid]) {
12                 if (target < nums[mid] && target >= nums[start])
13                     end = mid - 1;
14                 else start = mid + 1;
15             }
16             else if (nums[start] > nums[mid]){
17                 if (target > nums[mid] && target <= nums[end])
18                     start = mid + 1;
19                 else end = mid - 1;
20             }
21             else {
22                 start++;
23             }
24         }
25         return target == nums[start];
26     }
27 }

36、Largest Rectangle in Histogram：求最大的长方形面积

 1 public int largestRectangleArea(int[] heights) {
 2     int maxArea = 0;
 3     Stack<Integer> stack = new Stack<>();
 4     int i=0;
 5     int height = 0;
 6     int area = 0;
 7     while(i <= heights.length){
 8         if(i < heights.length) height = heights[i];
 9         else height = 0;
10         if(stack.isEmpty() || height >= heights[stack.peek()]){
11             stack.push(i++);
12         }
13         else{
14             int index = stack.pop();
15             if(stack.isEmpty()) area = i * heights[index];
16             else {
17                 area = (i-stack.peek()-1) * heights[index];
18             }
19             maxArea = Math.max(area, maxArea);
20         }
21     }
22     return maxArea;
23 }

37、Maximal Rectangle：利用36题结论

 1 public int maximalRectangle(char[][] matrix) {
 2     int m = matrix.length;
 3     if (m < 1){
 4         return 0;
 5     }
 6     int n = matrix[0].length;
 7     int[][] heights = new int[m][n+1];
 8     for(int i = 0; i < m; i++){
 9         for(int j = 0; j < n; j++) {
10             if(matrix[i][j] == '0'){
11                 heights[i][j] = 0;
12             }else {
13                 heights[i][j] = i == 0 ? 1 : heights[i - 1][j] + 1;
14             }
15         }
16     }
17     int maxArea=0;
18     for(int i = 0; i < m; i++){
19         int area = maxAreaInHist(heights[i]);
20         if(area > maxArea){
21             maxArea=area;
22         }
23     }
24     return maxArea;
25 }

38、Merge Sorted Array：类似于插入排序

39、Subsets II：数组子集，数组中有重复的元素

 1 public List<List<Integer>> subsetsWithDup(int[] nums) {
 2     int length = nums.length;
 3     Arrays.sort(nums);
 4 
 5     List<List<Integer>> res = new ArrayList<>();
 6     List<Integer> emptyList = new ArrayList<>();
 7     res.add(emptyList);
 8 
 9     for (int i = 0; i < length; i++) {
10         int count = 1;
11         while (i+1< length && nums[i] == nums[i+1]) {
12             count++;
13             i++;
14         }
15         int size = res.size();
16         for (int j = 0; j < size; j++) {
17             for (int k = 0; k < count; k++) {
18                 List<Integer> newList = new ArrayList<>(res.get(j));
19                 for (int p = 0; p <= k; p++)
20                     newList.add(nums[i]);
21                 res.add(newList);
22             }
23         }
24     }
25     return res;
26 }

40、Construct Binary Tree from Preorder and Inorder Traversal：根据先序和中序遍历构建树

构建过程，在中序遍历中找根节点的下标可以用hashmap加速

41、Construct Binary Tree from Inorder and Postorder Traversal：根据中序和后序遍历构建树

构建过程，在中序遍历中找根节点的下标可以用hashmap加速

42、Pascal's Triangle：生成杨辉三角

 1 public List<List<Integer>> generate(int numRows) {
 2     List<List<Integer>> res = new ArrayList<>();
 3 
 4     if (numRows < 1) return res;
 5     List<Integer> first = new ArrayList<>();
 6     first.add(1);
 7     res.add(first);
 8     for (int i = 2; i <= numRows; i++)
 9     {
10         List<Integer> list = new ArrayList<>();
11         List<Integer> preList = res.get(i-2);
12         for (int j = 0; j < i; j++)
13         {
14             if (j == 0)
15                 list.add(1);
16             else if (j == i-1)
17                 list.add(1);
18             else
19             {
20                 list.add(preList.get(j-1)+preList.get(j));
21             }
22         }
23         res.add(list);
24     }
25     return res;
26 }

43、Pascal's Triangle II：生成第k个杨辉三角

 1 public List<Integer> getRow(int rowIndex) {
 2     List<Integer> res = new ArrayList<>();
 3     if (rowIndex < 0)
 4         return res;
 5 
 6     for (int i = 0; i <= rowIndex; i++)
 7     {
 8         res.add(0, 1);
 9         for (int j = 1; j < res.size()-1; j++)
10         {
11             res.set(j, res.get(j)+res.get(j+1));
12         }
13     }
14     return res;
15 }

44、Triangle：求最短路径

 1 public int minimumTotal(List<List<Integer>> triangle) {
 2     if (triangle == null || triangle.size() == 0)
 3         return 0;
 4 
 5     int [] sum = new int[triangle.size()];
 6     for (int i = 0; i < triangle.size(); i++)
 7         sum[i] = triangle.get(triangle.size()-1).get(i);
 8 
 9     for (int i = triangle.size()-2; i >= 0; i--)
10     {
11         for (int j = 0; j <= i; j++)
12             sum[j] = Math.min(sum[j], sum[j+1]) + triangle.get(i).get(j);
13     }
14     return sum[0];
15 
16 }

45、Best Time to Buy and Sell Stock：

46、Best Time to Buy and Sell Stock II：

47、Best Time to Buy and Sell Stock III：

48、Word Ladder II：

49、Longest Consecutive Sequence：

50、Maximum Product Subarray：

51、Find Minimum in Rotated Sorted Array：

52、Find Minimum in Rotated Sorted Array II：

53、Find Peak Element：

54、Missing Ranges：

55、Two Sum II - Input array is sorted：

56、Majority Element：

57、Rotate Array：

58、Minimum Size Subarray Sum：

59、Combination Sum III：给定数k和n，求所有的k个数之和等于n的集合，其中k个数中不允许重复的数，并且数字大小为1到9。回溯法

 1 public List<List<Integer>> combinationSum3(int k, int n)
 2 {
 3     List<List<Integer>> result = new ArrayList<>();
 4     List<Integer> temp = new ArrayList<>();
 5     boolean[] visited = new boolean[10];
 6     helper(k, n, 1, 0, visited, temp, result);
 7     return result;
 8 }
 9 public void helper(int k, int n, int start, int sum, boolean[] visited, List<Integer> temp, List<List<Integer>> res)
10 {
11     if (sum == n && temp.size() == k){
12         res.add(new ArrayList<>(temp));
13         return;
14     }
15     if (sum > n || temp.size() > k) return;
16     for (int i = start; i < 10; i++){
17         if (visited[i])
18             continue;
19         if (temp.size() > 0 && temp.get(temp.size()-1) > i)
20             continue;
21         temp.add(i);
22         visited[i] = true;
23         helper(k, n, start+1, sum+i, visited, temp, res);
24         temp.remove(temp.size()-1);
25         visited[i] = false;
26     }
27 }

60、Contains Duplicate：

61、Contains Duplicate II：

62、Summary Ranges：

63、Majority Element II：

64、Product of Array Except Self：

65、Shortest Word Distance：

66、Shortest Word Distance III：

67、3Sum Smaller：

68、Missing Number：

69、Find the Celebrity：

70、Wiggle Sort：

71、Move Zeroes：

72、Find the Duplicate Number：

73、Game of Life：

74、Range Addition：

75、Patching Array：给出一个从小到大排好序的整数数组nums和一个整数n，在数组中添加若干个补丁（元素）使得[1,n]的区间内的所有数都可以表示成nums中若干个数的和。返回最少需要添加的补丁个数。

 1 public class Solution {
 2     /**
 3     定义一个当前数字i之前的数组合能到达的最小上界minUpper，如表示的数范围是1-m，则定义上界为minUpper=m+1
 4     循环如下：
 5     上界minUpper <= N：
 6         如果当前数字i <= minUpper：
 7             更新上界：minUpper = minUpper + i
 8         如果当前数字i > minUpper：说明需要添加补丁数字minUpper，并且更新此时的上界minUpper=minUpper+minUpper;
 9     */
10     public int minPatches(int[] nums, int n) {
11         int minUpper = 1;
12         int index = 0;
13         int missingCounter = 0;
14         while (minUpper <= n) {
15             if(index < nums.length && nums[index] <= minUpper) {
16                 minUpper += nums[index];
17                 index++;
18             }
19             else {
20                 //System.out.println(minUpper);
21                 minUpper += minUpper;
22                 missingCounter ++;
23             }
24         }
25         return missingCounter;
26     }
27 }