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变成2
private 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,2
for (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,2
for (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);
*/
