算法集锦（NO.5）

高频习题

岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

方法一：
递归，使用辅助数组boolean，当遍历原数组时，碰到值为1的时候，就对其周边相连元素的辅助数组变为true。在进行传参遍历时还需要对该点的辅助空间进行判定，即只有当该坐标下的原数组为1，并且其辅助数组为false（未到达）时才可以进行传参，count才能++。

class Solution {
    public int numIslands(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int count=0;
        //辅助数组boolean，来判定某个值为1的点是否已经被遍历过
        boolean [][]treak=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
            //当满足该点未遍历并且该点值为1时，才能进行后续遍历
                if(!treak[i][j]&&grid[i][j]=='1'){
                    check(treak,i,j,grid,m,n);
                    //在遍历完该点相连的符合条件的点后，进行片区count++
                    count++;
                }
            }
        }
        return count;
    }
    public void check(boolean[][]treak,int h,int l,char[][] grid,int m,int n){
    //当满足下标不超过界限，并且点的值为1和未经过该点时，可以进行递归操作
        if(h+1<m&&grid[h+1][l]=='1'&&!treak[h+1][l]){
            treak[h+1][l]=true;
            check(treak,h+1,l,grid,m,n);
        }
        if(h-1>=0&&grid[h-1][l]=='1'&&!treak[h-1][l]){
            treak[h-1][l]=true;
            check(treak,h-1,l,grid,m,n);
        }
        if(l+1<n&&grid[h][l+1]=='1'&&!treak[h][l+1]){
            treak[h][l+1]=true;
            check(treak,h,l+1,grid,m,n);
        }
        if(l-1>=0&&grid[h][l-1]=='1'&&!treak[h][l-1]){
            treak[h][l-1]=true;
            check(treak,h,l-1,grid,m,n);
        }
    }
}

代码优化：取消了boolean辅助判定栈，在给定数组上进行数值更新。

class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;
//当超过边界，且该点不为1时候，跳出。
        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }
//将相连板块的1，更新为0
        grid[r][c] = '0';
        //上下左右的递归遍历
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
    //当grid不存在的时候直接返回0
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
            //当发现某点为1的时候，调用dfs函数，将该点周边的1全部变成0
                if (grid[r][c] == '1') {
                //片区增加
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

方法二：
广度优先遍历，将搜索到为1的时候，将其加入队列，对队列里的值周边相连的点进行遍历，如果满足值为1的时候，就将其更新为0。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
//进行行遍历
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
            //当该点值为1的时候，将其相连附近的值修改为0，并且块数+1
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    //使用queue进行每个值为1的点存放
                    Queue<Integer> neighbors = new LinkedList<>();
                    //因为该为二维链表，所以需要对其点的下标进行某种加密操作
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                    //取出，将下标进行分解
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        //下面就是在边界范围内，如果该点为1，将其存入queue，并且将点更新为0
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }
//返回得到的总岛屿板块
        return num_islands;
    }
}

方法三：
并查集，将相连的板块进行合并

class Solution {
//合并集的编写
    class UnionFind {
        int count;
        int[] parent;
        int[] rank;
//将每个1的下标进行存放至parent中，并且值和数组下标相同
        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        //值为1的总数。
                        ++count;
                    }
                    //将每个节点的rank都赋为0
                    rank[i * n + j] = 0;
                }
            }
        }
//当parent的下标不等于值的时候，这说明该点为0，将其值返回0
        public int find(int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }

        public void union(int x, int y) {
        //rootx为该点为1，rooty为rootx的相连点为1的情况
            int rootx = find(x);
            int rooty = find(y);
            //当这两个点不同时为0时
            if (rootx != rooty) {
            //遍历完后的点，将其rootx和rooty相连接
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                //相连板块的值，则--
                --count;
            }
        }
//返回总数
        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r-1][c] == '1') {
                        uf.union(r * nc + c, (r-1) * nc + c);
                    }
                    if (r + 1 < nr && grid[r+1][c] == '1') {
                        uf.union(r * nc + c, (r+1) * nc + c);
                    }
                    if (c - 1 >= 0 && grid[r][c-1] == '1') {
                        uf.union(r * nc + c, r * nc + c - 1);
                    }
                    if (c + 1 < nc && grid[r][c+1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                }
            }
        }

        return uf.getCount();
    }
}

无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:

输入: s = “”
输出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

方法：
滑动窗口，设置一个窗口初始节点指针-1，将其向右进行滑动，期间需要有一个hashset进行字符的存储，当遇到set中包含的字符时，进行指针右移动。通过fori的i的遍历节点下标和，滑动窗口左指针下标的相减，即可得到无重复的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
    //set进行字符的存储
        Set<Character>occ = new HashSet<>();
        //设置滑动窗口的右边界下标，和滑动窗口大小ans初始化
        int rk = -1; int ans=0;
        //对字符串进行遍历，其中i为滑动窗口的左边界
        for(int i =0 ;i<s.length();++i){
            if(i!=0){
                occ.remove(s.charAt(i-1));
            }
            //将rk++，此时rk为右边界
            while(rk+1<s.length()&&!occ.contains(s.charAt(rk+1))){
                occ.add(s.charAt(rk+1));
                rk++;

            }ans=Math.max(ans,rk-i+1);
        }return ans;
    }
}

类似方法：

class Solution {
    public int lengthOfLongestSubstring(String s) {
    //使用hashset进行不同字符串的存储
        Set<Character>occ = new HashSet<>();
        //滑动窗口左边界
        int rk = -1; int ans=0;
        for(int i =0 ;i<s.length();++i){
        //当occ内不存在该字符时，就将其投入，并且更新ans的最大值
            if(!occ.contains(s.charAt(i))){
                occ.add(s.charAt(i));  
                ans=Math.max(ans,i-rk);
            }else{
            //当存在时就将occ内部的重复值抛出，滑动边界左指针收缩。
                while(occ.contains(s.charAt(i))){
                    occ.remove(s.charAt(rk+1));
                    rk++;
                }
                occ.add(s.charAt(i));
            }
        }return ans;
    }
}

每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

方法：
使用单调递减栈来存储数组下标，遍历数组，如果遇到节点值大于栈顶节点所对应的下标时，就弹出栈顶元素，将其作为下标存到结果数组中，该下标所对应的值为当前遍历的节点序减去栈弹出的节点下标。

class Solution {
    public int[] dailyTemperatures(int[] T) {   
        int []num = new int [T.length];
        Deque<Integer>stack =new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
        //当栈为空或者值递减情况下直接存放入栈中
            if(stack.isEmpty()||T[stack.peek()]>=T[i]){
                stack.push(i);
            }else{
            //当碰到栈非空并且遍历值大于栈顶元素时，存入辅助数组中
                while(!stack.isEmpty()&&T[stack.peek()]<T[i]){
                    num[stack.peek()]=i-stack.pop();
                }
                stack.push(i);
            }
        }
        return num;
    }
}

方法优化：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
        //去除了栈为空和递减栈的判定过程
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}

森林中的兔子
森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 “1” 的兔子可能有相同的颜色，设为红色。
之后回答了 “2” 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 “2” 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0
说明:

answers 的长度最大为1000。
answers[i] 是在 [0, 999] 范围内的整数。
方法：
使用hashmap进行统计，此时需要考虑3种情况，第一种为0的时候，此时表示该颜色独一无二，此时就count直接加上key==0的时候的value就行。第二种情况，当key+1大于等于对应的value时，此时用贪心思想假设这些兔子所描述的颜色为同一种的情况下。第三种情况，当key+1小于对应的value时，此时也用贪心思想，假设颜色相同且数量达到key+1的兔子都描述了自身的情况，此时就需要对其余值进行考虑，如果无余数则直接加上商就行，如果有余数则商➕1。

class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer,Integer>mapCount = new HashMap<>();
        int count=0;
        //map进行遍历存储键值对
        for(int num:answers){
            mapCount.put(num,mapCount.getOrDefault(num, 0)+1);
        }
        //对map的进行遍历
        for(Map.Entry<Integer,Integer>entry :mapCount.entrySet()){
        //当其key为0时直接加上他的value
            if(entry.getKey()==0){
                count+=entry.getValue();
                //当key+1大于等于value时候，表示其为一种颜色，即直接加上key+1
            }else if(entry.getKey()+1>=entry.getValue()){
                count+=entry.getKey()+1;
            }else{
            //当key+1<value时候，表示此时需要打包若干颜色相同的兔子对
                count+=(entry.getKey()+1)*((entry.getValue()/(entry.getKey()+1))+(entry.getValue()%(entry.getKey()+1)==0?0:1));
            }
        }
        return count;
    }
}

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

示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4
示例 2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1
示例 3：

输入：matrix = [[“0”]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

方法一：
动态规划
采用对角线相加法则。比如该节点的值为1时候，通过对其左上，上，左这个方向的节点进行值的筛选，选出最小的值➕1就是该坐标的值，如果该节点的值为0，则直接将该坐标赋值为0即可。

class Solution {
    public int maximalSquare(char[][] matrix) {
    //最大正方形边长值
        int maxSide = 0;
        //当该矩阵为空，并且矩阵的边长为0或者矩阵的列为0时候，直接返回0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        //统计矩阵的长和宽
        int rows = matrix.length, columns = matrix[0].length;
        //创建辅助dp矩阵
        int[][] dp = new int[rows][columns];
        //遍历原有矩阵进行统计其内在值
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
            //当节点值为1时
                if (matrix[i][j] == '1') {
                //当其为边界点时，不存在前置正方形，直接赋1即可
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                    //考虑到前置正方形，则直接对其左，上，左上三个方向进行取最小值来进行最小正方形的读取
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    //更新最大边
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        //通过最大边来得到最大面积
        int maxSquare = maxSide * maxSide;
        //输出最大面积
        return maxSquare;
    }
}

方法二：
暴力法剪枝优化，保存当前最大正方形的边max，当遍历节点的下标行列加上max都超过边界，则不用考虑，直接break。如果在边界内并且该节点值为1，则需要一个辅助函数将该节点，当前最大边界传过去进行验证。

class Solution {
    public int maximalSquare(char[][] matrix) {
    //得到行列值，初始化最大边
        int length = matrix.length;
        int width = matrix[0].length;
        int max = 0;
     	//遍历正方形
        for(int i=0;i<length;i++){
        //当遇到该点行+最大边超出边界时，则直接跳出循环
            if(i+max>=length){
                break;
            }
            for(int j=0;j<width;j++){
           //当遇到该点列+最大边超出边界时，则直接跳出循环
                if(j+max>=width){
                        break;
                    }
                    //当该点为1时
                if(matrix[i][j]=='1'){
                //进行粗略检查
                    if(matrix[i][j+max]=='0'){
                        j=j+max;
                    }else if(i+max<length&&matrix[i+max][j]=='1'){
                    //考虑到max为0时，考虑到最大正方形左上顶点情况
                        if(max==0){
                            max=1;
                        }
                        //进行最大边的判定
                        max = maximalSquareDemo(i,j,matrix,max);
                    }
                }
            }
        }
        return max*max;
    }
    public int maximalSquareDemo(int i,int j,char[][] matrix,int max){
    //通过check去检查是否满足已有的最大边正方形
        if(!check(matrix,i,j,max)){
            return max;
        }
        //如果满足则进行正方形的扩张。
        int m=matrix.length;
        int n=matrix[0].length;
        while(i+max<m&&j+max<n){
            if(check(matrix,i,j,max+1)){
                max++;
            }else{
                break;
            }
        }
        return max;
    }
    //检查该最大边是否满足
    public boolean check(char[][] matrix,int i,int j,int add){
        for(int start=i;start<i+add;start++){
            for(int end=j;end<j+add;end++){
                if(matrix[start][end]=='0'){
                    return false;
                }
            }
        }
        return true;
    }
}

优化后实际平均时间优于方法一，时间复杂度O（N^ 2），空间复杂度O（N）

单词的压缩编码
单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

words.length == indices.length
助记字符串 s 以 ‘#’ 字符结尾
对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 ‘#’ 字符结束（但不包括 ‘#’）的 子字符串 恰好与 words[i] 相等
给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

示例 1：

输入：words = [“time”, “me”, “bell”]
输出：10
解释：一组有效编码为 s = “time#bell#” 和 indices = [0, 2, 5] 。
words[0] = “time” ，s 开始于 indices[0] = 0 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”
words[1] = “me” ，s 开始于 indices[1] = 2 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”
words[2] = “bell” ，s 开始于 indices[2] = 5 到下一个 ‘#’ 结束的子字符串，如加粗部分所示 “time#bell#”
示例 2：

输入：words = [“t”]
输出：2
解释：一组有效编码为 s = “t#” 和 indices = [0] 。

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 7
words[i] 仅由小写字母组成

方法：
创建一个Set的进行字符串数组的存储，然后对其每个字符串的子字符串进行检查，当某个字符串的子字符串在set内，则将其删除，因为可以通过该字符串，直接得到子字符串，少去冗余操作。

class Solution {
    public int minimumLengthEncoding(String[] words) {
    //创建存储空间hashset，并且将字符串数组words化成list存入hashset中
        Set<String>wordsSet=new HashSet<>(Arrays.asList(words));
        //设置总数
        int count=0;
        //对words内部的每个字符进行遍历，如果该字符的子字符串存在于wordSet中，则直接删除。避免冗余操作
        for(String str:words){
            for(int i=1;i<str.length();i++){
                wordsSet.remove(str.substring(i));
            }
        }
        for(String str:wordsSet){
        //每个单词后都需要加上#
            count+=str.length()+1;
        }
        return count;
    }
}

方法二：
字典树
参考甜姨的算法思想

class Solution {
    public int minimumLengthEncoding(String[] words) {
        TrieNode trie = new TrieNode();
        Map<TrieNode, Integer> nodes = new HashMap<TrieNode, Integer>();

        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            TrieNode cur = trie;
            for (int j = word.length() - 1; j >= 0; --j) {
                cur = cur.get(word.charAt(j));
            }
            nodes.put(cur, i);
        }

        int ans = 0;
        for (TrieNode node: nodes.keySet()) {
            if (node.count == 0) {
                ans += words[nodes.get(node)].length() + 1;
            }
        }
        return ans;

    }
}

class TrieNode {
    TrieNode[] children;
    int count;

    TrieNode() {
        children = new TrieNode[26];
        count = 0;
    }

    public TrieNode get(char c) {
        if (children[c - 'a'] == null) {
            children[c - 'a'] = new TrieNode();
            count++;
        }
        return children[c - 'a'];
    }
}

有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

方法：
使用map进行括号的对接。)->(,{->},[->]。

class Solution {
    public boolean isValid(String s) {
    //先进行字符串的长度奇偶判定，若为奇数则直接判定为错误，因为括号必为偶数
        if(s.length()%2!=0)
            return false;
            //使用map进行括号的对接
        Map<Character,Character>map =new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        //使用stack来保存之前未找到右括号的左括号
        Deque<Character>stack =new LinkedList<Character>();
        char []car =s.toCharArray();
        for(int i=0;i<s.length();i++){
        //如果当前为右括号时
            if(map.containsKey(car[i])){
                //当左括号不为相对应的右括号，或者stack为空的时候，此时不符合题意，直接抛出错误。
                if(stack.isEmpty()||stack.peek()!=map.get(car[i])){
                    return false;
                }
                //抛出栈顶，表示配对成功
                stack.pop();
            }else{
            //当不存在时，则表示此为左括号，直接存入栈中
                stack.push(car[i]);
            }
        }
        return stack.isEmpty();
    }
}