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