leetCode解题报告5道题(十一)

比眉伴天荒 2022-08-27 07:51 165阅读 0赞

### **题目一：Subsets** ###

Given a set of distinct integers, S, return all possible subsets.

Note:

*  Elements in a subset must be in non-descending order.
 *  The solution set must not contain duplicate subsets.

For example,  
If S = `[1,2,3]`, a solution is:

[
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

**分析：**

题目的题意挺简单的，我就不做说明，主要这道题目可以用递归的方法来做，也可以直接用迭代来取代，我们用迭代的方式来做这道题目，没有什么特别的算法，直接上代码，代码里有注释哈！

**AC代码：**

public class Solution {
        private ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        public ArrayList<ArrayList<Integer>> subsets(int[] S) {
            int len = S.length;
            results.add(new ArrayList<Integer>()); //先增加一个 [] 空集
            int size = results.size();
            int nowDealCount = 0; //表示当前要处理的长度
            while (nowDealCount != len){
                for (int i=0; i<size; ++i){
                    ArrayList<Integer> nowList = (ArrayList<Integer>)results.get(i);
                    if (nowDealCount == 0){//如果处理的长度为0,表示是最开始只有一个 空集 的时候
                        for (int j=0; j<len; ++j){
                            ArrayList<Integer> addList = new ArrayList<Integer>();
                            addList.add(S[j]);
                            results.add(addList);
                        }
                    }else if (nowList != null && nowList.size() == nowDealCount){
                        int maxNum = (int)nowList.get(nowDealCount-1);
                        for (int j=0; j<len; ++j){
                            if (maxNum < S[j]){//如果值大于list中的最后一个(max)则表示是呈升序的，这样加入到List中
                                ArrayList<Integer> copyList = new ArrayList<Integer>(nowList);
                                copyList.add(S[j]);
                                results.add(copyList);
                            }
                        }
                    }
                }
                size = results.size();
                nowDealCount++;
            }
            
            return results;
        }
    }

### **题****目二：Subsets II** ###

**Given a collection of integers that might contain duplicates, S, return all possible subsets.**

**Note:**

*  **Elements in a subset must be in non-descending order.**
 *  **The solution set must not contain duplicate subsets.**

**For example,  
If S = `[1,2,2]`, a solution is:**

[
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]

**分析：**

这道题目跟上面那道基本上思路是类似的，只是这道题目多了可能重复的元素，这时候我们就要考虑重复的元素不能有相同集合的问题了，先把Num\[\]数组进行排序，然后跟题目一一样的解法， 只是在此过程中我们需要知道每个添加到results中的集合的最后一个元素(即最大元素)的下标，我们用一个indexList来存储。

这样的话每次要再添加新元素组成新的集合，就只要从下标位置+1开始，到len结束来搜索就行了。但要注意的是，如果当前要添加到集合中的元素和前一个元素相等，那么就不添加，如 ： \[1, 2, 2\], 当我们处理到nowDealCount==1时

要往 \[1\] 中添加元素，我们会添加一个 \[2\]， 组成\[1, 2\]但是当到第二个\[2\]的时候，我们不能再添加一个\[1, 2\]了，否则就重复出现了！

**AC代码：**

### **题目三：Unique Paths** ###

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Note: m and n will be at most 100.

**分析：**

题目的意思从一个矩阵的左上角的位置开始走，只能向右走或者向下走，最后要走到矩阵的右下角，求解出一共有多少种不同的走法.

我们拿一个示例来分析下，当m=3, n=7的时候

一个3 \* 7的矩阵

![Image 1][]

比如现在我们要求从 start(0,0)开始走到finish的方法数，但是start的位置的走法只有两种向右或者向下，这样的话相当于问题被转换成了求解 (0+1, 0)位置达到终点的走法 + (0, 0+1)位置达到终点的走法 \[其实就是一个递归的过程\]。明白了这样之后，我们用递归来求解一下，发现直接TLE了。这样很明显我们需要自底向上，从 (m-2, n-2)的位置开始往前推，最后推到 (0, 0)的时候，就是我们要的结果值了。

设ways\[row\]\[col\]表示 位置(row, col)到达终点(m-1, n-1) 的不同路径的条数，那么很容易得到下面的式子

**ways\[m-1\]\[col\] = 1; ( 0 <= col < n)**

**ways\[row\]\[n-1\] = 1; (0 <= row < m)**

**ways\[row\]\[col\] = ways\[row+1\]\[col\] + ways\[row\]\[col+1\]  (0<= row <=m-2, 0<= col <=n-2)**

通过这样的分析，我们再来看看代码，理解下哈！

**AC代码：**

public class Solution {
        public int uniquePaths(int m, int n) {
            if (m == 0 || n == 0)
                return 0;
            if (m == 1){
                return 1;
            }
            if (n == 1){
                return 1;
            }
            int[][] ways = new int[m][n];
            //最后一列所有的位置的走法都只有1种
            for (int i=0; i<m; ++i){
                ways[i][n-1] = 1;
            }
            //最后一行所有的位置的走法都只有1种
            for (int j=0; j<n; ++j){
                ways[m-1][j] = 1;
            }
            //update
            for (int row=m-2; row>=0; --row){
                for (int col=n-2; col>=0; --col){
                    ways[row][col] = ways[row+1][col] + ways[row][col+1];
                }
            }
            return ways[0][0];
        }
    }

### **题目四：Unique Paths II** ###

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as `1` and `0` respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
      [0,0,0],
      [0,1,0],
      [0,0,0]
    ]

The total number of unique paths is `2`.

**分析：**

这道题目跟上面的非常像，只是在判断的时候需要先判断当前自身这个位置是否是1，如果是1表示当前位置是障碍，这样子到达终点的不同路径数就为0，如果不是障碍物的话，那么判断它的右边元素是否是1，不是1的话，加上右边元素对应的路径数，然后再判断它的下面元素是否是1，不是1的话，加上下边元素对应的路径数。

还有要注意的是当开始start元素(0,0)就为1（障碍物）的话 或者 end元素(m-1, n-1)为1(障碍物)那么这样直接返回0，表示没有路径数可以到达终点。

最终ways\[0\]\[0\]即是我们所要求解的最后结果。

**AC代码：**

public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            if (m == 0)
                return 0;
            int n = obstacleGrid[0].length;
            if (n == 0)
                return 0;
            if (m == 1 || n == 1){
                return (obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1) ? 0 : 1;
            }
            //终点或者起点为1，表示为障碍物，直接返回0
            if (obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1){
                return 0;
            }
            //存储路径数
            int[][] ways = new int[m][n];
            //处理最后一列
            for (int i=m-2; i>=0; --i){
                if(obstacleGrid[i+1][n-1] != 1 && obstacleGrid[i][n-1] != 1){
                    ways[i][n-1] = 1;
                }else{
                    ways[i][n-1] = 0;
                    obstacleGrid[i][n-1] = 1;
                }
            }
            //处理最后一行
            for (int j=n-2; j>=0; --j){
                if(obstacleGrid[m-1][j+1] != 1 && obstacleGrid[m-1][j] != 1){
                    ways[m-1][j] = 1;
                }else{
                    ways[m-1][j] = 0;
                    obstacleGrid[m-1][j] = 1;
                }
            }
            //update
            for (int row=m-2; row>=0; --row){
                for (int col=n-2; col>=0; --col){
                    if (obstacleGrid[row][col] == 1){
                        continue;
                    }
                    ways[row][col] = 0;
                    if (obstacleGrid[row+1][col] != 1){
                        ways[row][col] += ways[row+1][col];
                    }
                    if (obstacleGrid[row][col+1] != 1){
                        ways[row][col] += ways[row][col+1];
                    }
                    if (ways[row][col] == 0){
                        obstacleGrid[row][col] = 1;
                    }
                }
            }
            return ways[0][0];
        }
    }

###    **题目五：** ###

### Trapping Rain Water ###

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,   
Given `[0,1,0,2,1,0,1,3,2,1,2,1]`, return `6`.

![rainwatertrap.png][]

The above elevation map is represented by array \[0,1,0,2,1,0,1,3,2,1,2,1\]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

**分析：**

找到最长的那块木板，假设其下标为maxValueIndex。

分别从左侧和右侧向最长的木板靠近。

左侧逼近过程：（i  :  0 ~~  maxValueIndex）

用一个max来记录现在已经遍历到的木板中最长的那个的长度。

1、如果一个木板的长度A\[i\] < max，该木板的下标 i < maxValueIndex 并且 A\[i\] < max (max这个值的下标位置在这块木板的前面)，所以这块木板的左右两侧各有一个木板长于它。则在这块木板上能存的水量为：max - 该木板的长度。

2、如果一个木板的长度A\[i\]  >max，max对应的位置< 该木板的位置 < maxValueIndex 并且A\[i\]  >max, 所以在该木板左右两侧只有一个木板（maxIdx）长于它。则这块木板上不能存水，则更新max值等于A\[i\]。

右侧逼近过程与左侧相似：（i  :  len - 1 ~~ maxValueIndex）

**AC代码：**

public class Solution {
        public int trap(int[] A) {
    
            int len = A.length;
            if (len == 0 || len == 1){
                return 0;
            }
            int sum = 0;
            //找最大的木板的下标哈
            int maxValueIndex = 0;
            int max = 0;
            for (int i=0; i<len; ++i){
                if (max < A[i]){
                    max = A[i];
                    maxValueIndex = i;
                }
            }
            //从左向最大值逼近
            max = A[0];
            for (int i=1; i<maxValueIndex; ++i){
                if (A[i] > max){
                    max = A[i];
                }else{
                    sum += (max - A[i]);
                }
            }
            //从右向最大值逼近
            max = A[len-1];
            for (int i=len-2; i>maxValueIndex; --i){
                if (A[i] > max){
                    max = A[i];
                }else{
                    sum += (max - A[i]);
                }
            }
            
            return sum;
        }
    }

[Image 1]: 
[rainwatertrap.png]: http://www.leetcode.com/wp-content/uploads/2012/08/rainwatertrap.png