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;
}
}