200岛屿数量
题目
思路解析
把访问过的格子插上棋子
思想是先污染再治理，我们有一个inArea（）函数，是判断是否出界了
我们先dfs（）放各个方向遍历，然后我们再把这个位置标为0
我们岛屿是连着的1，所以我们遍历完后，我们要把遍历完的位置置为0，防止结果重复
代码
class Solution {public int numIslands(char[][] grid) {int count=0;for(int r=0;r<grid.length;r++)
{for(int c=0;c<grid[0].length;c++){if(grid[r][c]=='1'){dfs(r,c,grid);count++;}}
}
return count;}private void dfs(int startindex1,int startindex2,char[][] grid)
{if(!inArea(grid,startindex1,startindex2))return ;if(grid[startindex1][startindex2]=='0')return ;grid[startindex1][startindex2]='0';dfs( startindex1- 1, startindex2,grid);dfs(startindex1 + 1, startindex2,grid);dfs( startindex1, startindex2 - 1,grid);dfs( startindex1, startindex2 + 1,grid);}boolean inArea(char[][] grid,int row,int cline)
{return row>=0&&row<grid.length&&cline>=0&&cline<grid[0].length;
}}994腐烂的橘子
题目
思路解析
我们一开始要统计腐烂的橘子的位置和fresh变量统计有几个新鲜的橘子
我们每腐烂一个新鲜橘子fresh就--
要是最后腐烂完还有新鲜橘子就返回-1，表示不能全部腐烂完
解题思路：我们腐烂的橘子放四个方向腐烂
为了防止重复腐烂，我们每遍历一次旧腐烂橘子就结束，然后把新腐烂橘子加入到List<int[]>里面
然后下次从新腐烂橘子开始腐烂
例如我们for循环的遍历的tmp就是我们的旧腐烂橘子，我们开始腐烂，腐烂的同时往q收集我们的新腐烂橘子
方便我们下次4个方向遍历腐烂橘子
for循环的条件：fresh > 0 && !q.isEmpty()，新鲜橘子>0并且还有能继续遍历的腐烂橘子
while (fresh > 0 && !q.isEmpty()) {ans++; // 经过一分钟List<int[]> tmp = q;q = new ArrayList<>();for (int[] pos : tmp) { // 已经腐烂的橘子往四个方向腐烂for (int[] d : DIRECTIONS) { // 四方向int i = pos[0] + d[0];int j = pos[1] + d[1];if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子fresh--;grid[i][j] = 2; // 变成腐烂橘子q.add(new int[]{i, j});}}}}代码
class Solution {//为了判断是否有永远不会腐烂的橘子（如示例 2），我们可以统计初始新鲜橘子的个数 fresh。//在 BFS 中，每有一个新鲜橘子被腐烂，就把 fresh 减一，这样最后如果发现 fresh>0，就意味着有橘子永远不会腐烂，返回 −1//新鲜橘子腐烂的时候我们要把1变成2private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向public int orangesRotting(int[][] grid) {int m = grid.length;int n = grid[0].length;int fresh = 0;List<int[]> q = new ArrayList<>();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1) {fresh++; // 统计新鲜橘子个数} else if (grid[i][j] == 2) {q.add(new int[]{i, j}); // 一开始就腐烂的橘子的下标}}}int ans = 0;while (fresh > 0 && !q.isEmpty()) {ans++; // 经过一分钟List<int[]> tmp = q;q = new ArrayList<>();for (int[] pos : tmp) { // 已经腐烂的橘子往四个方向腐烂for (int[] d : DIRECTIONS) { // 四方向int i = pos[0] + d[0];int j = pos[1] + d[1];if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子fresh--;grid[i][j] = 2; // 变成腐烂橘子q.add(new int[]{i, j});}}}}return fresh > 0 ? -1 : ans;}
}207课程表
题目
思路解析
判断是否有环
例如【0,1】【1,0】
在学课程0之前要学课程1
在学课程1之前要学课程0
这就是不可能的，用图来说就是有环
访问过不代表找到了环
所以我们要有三种状态
未访问 0
正在访问 1
访问完毕 2
我们最多有numCourses个课程，所以我们遍历numCourses次
for (int i = 0; i < numCourses; i++) {if (colors[i] == 0 && dfs(i, g, colors)) {return false; // 有环}}我们一个节点可能对应多个学习顺序
例如0->1,0->2我们学习1，2之前一个要学习0，所以我们可以顺便把1，2两个节点都dfs完
我们把节点都遍历完后我们都没找到环，就说明我们的该节点x已经访问完毕，我们标记为2
private boolean dfs(int x, List<Integer>[] g, int[] colors) {colors[x] = 1; // x 正在访问中//开始遍历该节点//例如0->1,0->2，我们这个节点是0节点，我们就要遍历1,2for (int y : g[x]) {if (colors[y] == 1 || colors[y] == 0 && dfs(y, g, colors)) {return true; // 找到了环}}colors[x] = 2; // x 完全访问完毕return false; // 没有找到环}代码
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] g = new ArrayList[numCourses];Arrays.setAll(g, i -> new ArrayList<>());//初始化课程,也就是0->1,0->2,1->3这样子学习课程顺序初始化for (int[] p : prerequisites) {g[p[1]].add(p[0]);}//标记染色的数组int[] colors = new int[numCourses];//因为最多有numCourses个课程，所以我们最多遍历numCourses次for (int i = 0; i < numCourses; i++) {if (colors[i] == 0 && dfs(i, g, colors)) {return false; // 有环}}return true; // 没有环}private boolean dfs(int x, List<Integer>[] g, int[] colors) {colors[x] = 1; // x 正在访问中//开始遍历该节点//例如0->1,0->2，我们这个节点是-节点，我们就要遍历1,2for (int y : g[x]) {if (colors[y] == 1 || colors[y] == 0 && dfs(y, g, colors)) {return true; // 找到了环}}colors[x] = 2; // x 完全访问完毕return false; // 没有找到环}
}208实现前缀树
题目
思路解析
26叉树结构
首先我们是26个字母，所以我们应该是26叉树
我们定义一个Node结构来实现这个26叉树
然后我们还有个end标志位，标志这个位置是否是一个一个完整的单词
class Node{Node[] son=new Node[26];boolean end;
}例如下面
我们的apple是一个完整的单词
我们的app是一个完整的单词
但我们是一个遍历顺序，所以我们这个end标志位是必要的
前缀树的初始化
我们有个root节点，保证所有的字符串都从root开始
private Node root;public Trie() {root=new Node();}插入
相当于我们不断构建树
我们Node结构中有一个Node数组 Node[] son=new Node[26]
我们用0,1,2,3表示a,b,c,d......
然后我们移动到遍历的字符的位置
最后单词遍历完毕我们有个end标志位，标志结束
public void insert(String word) {Node cur = root; // 从根节点开始for (char c : word.toCharArray()) {c -= 'a'; // 将字符转换为索引（'a' -> 0, 'b' -> 1, ..., 'z' -> 25）if (cur.son[c] == null) { // 如果当前字符对应的子节点不存在cur.son[c] = new Node(); // 创建新节点}cur = cur.son[c]; // 移动到子节点}cur.end = true; // 标记单词的结尾}find找单词
也就是从root节点开始找单词
private int find(String word) {Node cur = root; // 从根节点开始for (char c : word.toCharArray()) {c -= 'a'; // 将字符转换为索引if (cur.son[c] == null) { // 如果当前字符对应的子节点不存在return 0; // 返回 0，表示未找到}cur = cur.son[c]; // 移动到子节点}return cur.end ? 2 : 1; // 如果当前节点是单词结尾，返回 2；否则返回 1
}search和startsWith
search：如果等于2说明前缀树中有这个单词
find：如果等于1或2说明我们前缀树中有这个单词前缀
public boolean search(String word) {return find(word)==2;//检查是否是完整单词}public boolean startsWith(String prefix) {return find(prefix) != 0;}代码
class Node{Node[] son=new Node[26];boolean end;
}class Trie {private Node root;public Trie() {root=new Node();}public void insert(String word) {Node cur = root; // 从根节点开始for (char c : word.toCharArray()) {c -= 'a'; // 将字符转换为索引（'a' -> 0, 'b' -> 1, ..., 'z' -> 25）if (cur.son[c] == null) { // 如果当前字符对应的子节点不存在cur.son[c] = new Node(); // 创建新节点}cur = cur.son[c]; // 移动到子节点}cur.end = true; // 标记单词的结尾}private int find(String word) {Node cur = root; // 从根节点开始for (char c : word.toCharArray()) {c -= 'a'; // 将字符转换为索引if (cur.son[c] == null) { // 如果当前字符对应的子节点不存在return 0; // 返回 0，表示未找到}cur = cur.son[c]; // 移动到子节点}return cur.end ? 2 : 1; // 如果当前节点是单词结尾，返回 2；否则返回 1
}public boolean search(String word) {return find(word)==2;//检查是否是完整单词}public boolean startsWith(String prefix) {return find(prefix) != 0;}}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/
