Leetcode刷题笔记

Posted by DeepBlue on 12-05,2020

leetcode刷题笔记

计数二进制子串

题目描述

给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例1:

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。

请注意,一些重复出现的子串要计算它们出现的次数。

另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。

示例2:

输入: "10101"
输出: 4
解释: 有4个子串:“10”,“01”,“10”,“01”,它们具有相同数量的连续1和0。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-binary-substrings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

按照题意,我们可以先将字符串整体的进行一遍扫描,例如00110011 ,我们可以将其拆分成为00 11 00 11(这里我们的分组依据是如果碰到两个不相同的二进制字符)

将拆分后的字符串进行计数即int[] a=[2,2,2,2];那么从位置中建立一个滑动窗口,提取a[0]和a[1]中的计数值,其中a[0]=2且a[1]=2,那么这两个相邻的分组中就可以使用Math.min(a[0],a[1])中找出两个不相同的字符之间较短的长度,如例子所示,其中a[0]与a[1]都为2,那么其最小值也为2,就可以组成[01],[0011]两个解。同理a[1],a[2]中Math.min(a[1],a[2])也为2,将其相加,且重复上述过程,既可以得到最终的答案,即:2+2+2=6,可以通过例子2进行检验。

解题代码

class Solotion {
    public int countBinarySubstrings(String s) {
        //边界判断
        if (s == null) {
            return 0;
        }
        //当前位置
        int now = 0;
        //当前位置即count=1
        int count = 1;
        //存储count的list
        List<Integer> counts = new ArrayList<>();
        //结束条件
        while (now < s.length()) {
            //判断是否越界 当前元素与下一个元素是否相等
            if (now + 1 < s.length() && s.charAt(now) == s.charAt(now + 1)) {
                count++;
            } else {
                //如果不相等的话,就需要将该count值进行存储
                counts.add(count);
                count = 1;
            }
            now++;
        }
        int res = 0;
        //获取结果
        for (int i = 0; i < counts.size() - 1; i++) {
            res += Math.min(counts.get(i), counts.get(i + 1));
        }
        return res;
    }
}

被围绕的区域

题目描述

给定一个二维的矩阵,包含 'X''O'字母 O)。

找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X

运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

通过题目描述我们首先差不多确定了这就是一个图的DFS或者BFS的题目,可以使用DFS或者使用BFS进行解答,解题思路是相同的。我们的目标是将其中的被X包围的O转换成为'X'将同时保持不连通的O不变,那么我们就可以从边界中的O出发进行DFS,然后将扫描出来的与外界连通的O转换成其他的字符,然后我们在通过一次遍历找到其中的被替换成特殊字符的元素,以及O元素,将O元素转换成为X,将特殊字符转换成为O,即得到解,如图所示。

X X X X X             X X X X X          X X X X X       X X X X X
X O O O X             X O O O X          X O O O X       X X X X X
X O O X X     =>      X O O X X      =>  X O O X X   =>  X X X X X
X X X O O             X X X # #          X X X O O       X X X O O

解题代码

package com.kklll.leetcode.algorithm;

/**
 * @Author DeepBlue
 * @Date 2020/8/11 15:52
 */
public class Solotion {
    public void solve(char[][] board) {
        //边界条件判断
        if (board == null || board.length == 0) {
            return;
        }
        int line = board.length;
        int column = board[0].length;
        //从四个边进行考虑,找出其中为O的节点,进行DFS
        for (int i = 0; i < line; i++) {
            for (int j = 0; j < column; j++) {
                boolean edge = i == 0 || i == line - 1 || j == 0 || j == column - 1;
                if (edge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        //进行扫描,查找其中的,此时被更改为#的即为原来连通的O,
        //那么应该被修改为O,否则的话原先的O即为被包围的元素,应该被替换为X
        //然后得到的答案就是答案
        for (int i = 0; i < line; i++) {
            for (int j = 0; j < column; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    /**
     * DFS中的内容就是将与边界连通的O找出来,并且将找出来的O使用其他的字符进行一个替换,
     * 那么替换后的字符表示的内容即应该是题目中所要的没有包围的O的部分,然后我们就可以把这个数组进行遍历了
     * @param board
     * @param x
     * @param y
     */
    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 'X' || board[x][y] == '#') {
            return;
        }
        board[x][y] = '#';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

200. 岛屿数量

题目描述

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

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

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

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

这道题的解题思路与上题是类似的,都可以使用BFS或者DFS进行解答,我们可以现在二维数组中找到一个岛屿的一部分,然后对岛屿的数量进行加1,然后进行BFS,将这个岛屿的所有陆地变成海洋(即将岛屿内的'1'赋值为'0'),然后重复上述过程到所有的元素都被遍历一遍,那么得到的结果即为岛屿的数量。

解题代码

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null)
            return 0;
        int count=0;
        //遍历数组找到岛屿的一部分
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                //确认为岛屿的一部分,则从该坐标进行DFS
                if(grid[i][j]=='1'){
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }
    //寻找本岛屿内的其他元素,并将其变成海洋
    public void dfs(char[][] grid,int i, int j){
        if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}

133. 克隆图

题目描述

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式:

简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

例子:

输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/clone-graph
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想

这道题看起来很难懂,但是仔细读题发现就做了一件事,就是将元素进行深拷贝,所谓深拷贝就是被拷贝后的对象内的元素是独立在内存中的,而不是其他对象的引用,那我们就要使用new关键字创建各个节点,并把他们保存,这样的话,就可以得到最终的答案,这道题可以使用BFS或者DFS进行解答,我们获得节点后将该节点的克隆对象存储到map集合里面,然后通过源对象的neighbors元素创建新neighbors节点,重复上述过程,直到所有的对象都被遍历完成一遍即终止。

解题代码

class Solution {
    public Node cloneGraph(Node node) {
        Map<Node,Node> map=new HashMap();
        return dfs(node,map);
    }

    public Node dfs(Node node,Map<Node,Node> map){
        if(node==null){
            return null;
        }
        if(map.containsKey(node)){
            return map.get(node);
        }
        Node clone=new Node(node.val,new ArrayList<Node>());
        map.put(node,clone);
        for(Node n: node.neighbors){
            clone.neighbors.add(dfs(n,map));
        }
        return clone;
    }
}