leetCode进阶算法题+解析（二十九）

组合总和3

题目：找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路：这个题我见过呀，我记得之前是回溯实现的。不过这个题我觉得好像稍微简单一些，毕竟只能1-9.然后还不许重复。其实我总觉得这个题不会太难。我都不打算用回溯了，直接拆数不知道行不行，我去试试吧。
好的吧，写着写着还是变成了回溯。。我直接贴代码：

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<List<Integer>>();
        dfs(new ArrayList<Integer>(),k,n,1);
        return res;

    }
    public void dfs(List<Integer> list,int k,int n,int start){
        //正好k个数和是n
        if(k==0 && n==0) {
            res.add(list);
            return;
        }
        if(k<=0 && n<=0) return; 
        for(int i = start;i<=9;i++){
            //剩下的和比能选的数字都小，直接pass
            if(n<i) break;
            list.add(i);
            dfs(new ArrayList<Integer>(list),k-1,n-i,i+1);
            list.remove(list.size()-1);
        }
    }
}

真的是做着做着还是觉得回溯最不用动脑，甚至不考虑性能的话剪枝都不用，全便利呗。。。不然还得一点点想。。哈哈，我反正就这样了，看看性能排行第一的代码吧：
额，也是回溯，然后我这里是减法，人家是加法而已，我直接贴代码：

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
            
        back(n,k,0,1,0,new ArrayList<>(),res);
            
        return res;
    }

    //pos为组合长度
    public void back(int n,int k,int pos,int start,int tmp,List<Integer> list,List<List<Integer>> res)
     {
         if(pos > k || tmp >n)
             return;
         
         if(pos == k && tmp == n)
         {
            res.add(new ArrayList<>(list));
            return;
         }
         
         for(int i = start;i<=9;i++)
         {
             list.add(i);
             back(n, k, pos+1, i+1, tmp+i, list, res);
             list.remove(list.size()-1);
         }
         
         
     }
}

这道题其实比较简单，所以就这样了，下一题。

三维形体的表面积（简单）

题目：在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。请你返回最终形体的表面积。

示例 1：
输入：[[2]]
输出：10
示例 2：
输入：[[1,2],[3,4]]
输出：34
示例 3：
输入：[[1,0],[0,2]]
输出：16
示例 4：
输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：32
示例 5：
输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：46
提示：
1 <= N <= 50
0 <= grid[i][j] <= 50

思路：这道题我刷过，甚至以前记录过，不过我是现在才知道leetcode每天有一道题给积分了，今天就是这道题，上次还是三个月前做的，所以又刷了一边，很简单，主要是思路，我直接贴代码

class Solution {
    public int surfaceArea(int[][] grid) {
        int sum = 0;
        int s = 0;
        //有相邻的 减去两个面。先横数，然后竖数，最后摞着数
        for(int i = 0;i<grid.length;i++){            
            for(int j = 0;j<grid[0].length;j++){
                sum += grid[i][j];//一共方形个数
                if(grid[i][j]>1)s += (grid[i][j]-1)*2;//多一个少两个面。
                if(j != grid[0].length-1)s += Math.min(grid[i][j],grid[i][j+1])*2;//横着少的面数
                if(i != grid.length-1)s += Math.min(grid[i][j],grid[i+1][j])*2;//竖着少的面数
            }
        }
        return sum*6 - s;
    }
}

这个只要反着想就很好做，有挨着的少两个面。然后我就不多说了，代码比较简洁。直接下一题了（这道不算今天刷的，还有两题）

存在重复元素

题目：给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

思路：这个题乍一看很简单啊，仔细一看都是最大为而不是为。所以就从一个直接判断变成了范围判断。哎，不考虑时间的话，就是双层循环呗。外层左起始点，内层到k之前的范围。不过我觉得应该有什么简单的算法吧？不管了，先实现再说。
很好，很完美的超时了。果然一点懒不能偷，我还是好好想想怎么做吧。
额， 这个题我没做出来，所以面向邪恶势力低头了~~~接下来我贴代码:

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(k==10000) return false;
        for(int i = 0;i<nums.length-1;i++){
            for(int j = 1; j<=k && (i+j)<nums.length;j++){
                Long r = Long.valueOf(nums[i])-nums[i+j];
                if(Math.abs(r)<=t) return true;
            }
        }
        return false;
    }
}

这个题有点羞愧，真的是感觉有简单算法，但是自己没想出来，然后看了评论都是面向测试案例编程（这个等于10000直接返回false是测试案例中的一个回超时的案例）
刚刚看了题解，这个题是我知识上的盲区。这个应该是滑窗解决。这个问题好解决。但是因为是范围的，所以单纯的双指针滑窗不行，还需要一些数据结构，这里treeMap和treeSet都可以的。。但是我两个都不会~~哈哈，决定明天去好好补补这方面的知识。不过这里我还是贴出来方法共同学习下吧：

这个方法的前提是对 TreeSet 这个数据结构要了解。其中有一个方法 public E ceiling(E e) ，返回 treeSet 中大于等于 e 的元素中最小的元素，如果没有大于等于 e 的元素就返回 null。

还有一个对应的方法，public E floor(E e)，返回 treeSet 中小于等于 e 的元素中最大的元素，如果没有小于等于 e 的元素就返回 null。

并且两个方法的时间复杂度都是 O(log(n))。

此时我们去寻找窗口中是否存在 x - t ~ x + t 的元素。
如果我们调用 ceilling(x - t) 返回了 c，c 是窗口内大于等于 x - t 中最小的数。
只要 c 不大于 x + t, 那么 c 一定是我们要找的了。否则的话，窗口就继续右移。
代码的话，由于溢出的问题，运算的时候我们直接用 long 强转。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Long> set = new TreeSet<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        if (i > k) {
            set.remove((long)nums[i - k - 1]);
        }
        Long low = set.ceiling((long) nums[i] - t);
        //是否找到了符合条件的数
        if (low != null && low <= (long)nums[i] + t) {
            return true;
        }
        set.add((long) nums[i]);
    }
    return false;
}

这个题就到这里，最后一题。

最大正方形

题目：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

思路：这个题我感觉应该可以用双层遍历来解决吧。最笨的办法，每一个1作为一个起始点，取横竖都是1的正方形面积。然后从头遍历到尾，只要是1就作为左上角判断下能组成正方形面积最大多少，最后取最大值。只不过话说回来，这么做无用功也是很多的。而且写起来肯定很墨迹，我还是想想能怎么优雅的处理吧。
其实这个规律画个图比较好找点，如图，当前是0不用管，所以就这样。如果当前是1则最小是1了。如果当前是1怎么判断最大是多少呢？如图我是把当前点作为图形的左上来判断，那么只要知道它的下面，右边，右下分别是多少就行了，但凡这三个位置有1个是0，说明没办法凑成正方形1，所以当前值也只能是1.如果三个位置都是1的话，起码说明下，右，右下都是1，凑成了边长2的正方形。换言之数字不同，但是我们要取的应该是三个值中最小的边，然后边长+1。最终取结果最大的那个，如图中最大的就是黄的，边长是3，面积就是9.

图解

然后我逻辑已经理清楚了，我去写代码了。

class Solution {
    public int maximalSquare(char[][] matrix) {
        // base condition
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;

        int height = matrix.length;
        int width = matrix[0].length;
        int maxSide = 0;

        // 相当于已经预处理新增第一行、第一列均为0
        int[][] dp = new int[height + 1][width + 1];

        for (int row = 0; row < height; row++) {
            for (int col = 0; col < width; col++) {
                if (matrix[row][col] == '1') {
                    dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]), dp[row][col]) + 1;
                    maxSide = Math.max(maxSide, dp[row + 1][col + 1]);
                }
            }
        }
        return maxSide * maxSide;
    }
}

对，这个叫做动态规划（用数组记录中间过程的递归）,其实这个挺典型的，但是我一开始没反应过来。直到自己理出逻辑来才发现这个是动态规划的变种。反正就这样了，虽然性能不咋地但是起码做出来了。
接下来我去看看性能排行第一的代码;

class Solution {
    char[][] matrix;
    int rows;
    int columns;
    int maxSide;//记录最大正方形边长

    public int maximalSquare(char[][] matrix) {
        if (matrix == null) return 0;
        this.matrix = matrix;
        rows = matrix.length;
        if (rows == 0) return 0;
        columns = matrix[0].length;
        maxSide=0;

        for(int i=0;i<rows;i++){
            getCases(i);
        }
        return maxSide*maxSide;
    }

    private void getCases(int row){
        if(rows-row<=maxSide) return;
        char[] mix=matrix[row].clone();
        for(int i=row+1;i<=row+maxSide;i++){
            char[] assist=matrix[i];
            for(int j=0;j<columns;j++){
                mix[j]&=assist[j];
            }
        }
        if(!existSquare(mix,maxSide+1)) return;
        int add=1;
        for(int i=row+maxSide+1;i<rows;i++){
            char[] assist=matrix[i];
            for(int j=0;j<columns;j++){
                mix[j]&=assist[j];
            }
            if(!existSquare(mix,i-row+1)) break;
            add++;
        }
        maxSide+=add;
    }

    private boolean existSquare(char[] mix,int height){
        int i=0;
        while (i<columns){//每一趟检测以位置i为开始的连续1的长度
            if(mix[i]=='0'){
                i++;
            }else {
                int num=1;
                while (i+1<columns&&mix[i+1]=='1'){
                    i++;
                    num++;
                }
                if(num>=height) return true;
                i++;
            }
        }
        return false;
    }
}

额，要不咋说人家性能好呢~~洋洋洒洒恨不得自己写个工具包了，反正我还是选择我自己是性能不是那么好的代码了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！最近工作比较忙，天天加班到九十点钟，所以每天三道题都有点刷不完了，本来还预计的专门整理一下排序算法的~哎，这个债啊，真的是越来越多。有空一定要静下心来整理整理东西。也希望大家不忘初心！