力扣-Hot100-图论【算法学习day.38】
前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！
习题
1.岛屿数量
题面:
分析:定义一个递归函数，用于将从某一点开始的四周相邻的1全部标记，然后我们遍历这个二阶数组，如果grid[i][j]==1&&flag[i][j]==0(flag表示标记该点是否属于其他岛屿)，就将该点传入递归函数，将同属于该岛屿的所有点打上标记，ans++，最后返回ans即可
代码:
class Solution {
int[][] flag;
char[][] grid;
int n;
int m;
int ans = 0;
public int numIslands(char[][] grid) {
n = grid.length;
m = grid[0].length;
flag = new int[n][m];
this.grid = grid;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(flag[i][j]==0&&grid[i][j]=='1'){
ans++;
recursion(i,j);
}
}
}
return ans;
}
public void recursion(int i,int j){
if(grid[i][j]!='1'||flag[i][j]==1)return;
flag[i][j] = 1;
//上
if(i-1>=0&&flag[i-1][j]==0)recursion(i-1,j);
//下
if(i+1<n&&flag[i+1][j]==0)recursion(i+1,j);
//左
if(j-1>=0&&flag[i][j-1]==0)recursion(i,j-1);
//右
if(j+1<m&&flag[i][j+1]==0)recursion(i,j+1);
}
}2.腐烂的橘子
题目链接:994. 腐烂的橘子 - 力扣（LeetCode）
题面:
分析:模拟题，我们可以先遍历二维数组，定义两个队列，来存放下一分钟开始向四周腐烂的橘子的行纵坐标， 在额外定义一个遍历来表示新鲜橘子的剩余数量，然后每分钟开始时，我们从队列中取烂橘子，定义一个函数，用来表示一个橘子向四周腐烂的过程，如果将好橘子变成了坏橘子，就将这个新的坏橘子存入队列，并让新鲜橘子减一，当队列中不存在坏橘子时，循环结束，如果仍有好橘子存在，就返回-1，否则返回时间记录变量ans，详细看代码：
代码:
class Solution {
public int orangesRotting(int[][] grid) {
Queue<Integer> qi = new LinkedList<>();
Queue<Integer> qj = new LinkedList<>();
int ans = 0;
int n = grid.length;
int m = grid[0].length;
int freshOrange = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(grid[i][j]==2){
qi.offer(i);
qj.offer(j);
}
else if(grid[i][j]==1){
freshOrange++;
}
}
}
if(freshOrange==0)return 0;
// System.out.println(freshOrange);
// System.out.println(qi.size());
while(!qi.isEmpty()){
ans++;
// System.out.println(freshOrange+" "+qi.size());
int flag = qi.size();
for(int k = 0;k<flag;k++){
int i = qi.poll();
int j = qj.poll();
//上
if(i-1>=0&&grid[i-1][j]==1){
grid[i-1][j]=2;
qi.offer(i-1);
qj.offer(j);
freshOrange--;
}
//下
if(i+1<n&&grid[i+1][j]==1){
grid[i+1][j]=2;
qi.offer(i+1);
qj.offer(j);
freshOrange--;
}
//左
if(j-1>=0&&grid[i][j-1]==1){
grid[i][j-1]=2;
qi.offer(i);
qj.offer(j-1);
freshOrange--;
}
//右
if(j+1<m&&grid[i][j+1]==1){
grid[i][j+1]=2;
qi.offer(i);
qj.offer(j+1);
freshOrange--;
}
}
}
if(freshOrange>0)return -1;
return ans-1;
}
}3.课程表
题面:
分析:主要是看有没有成环
代码:
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] g = new ArrayList[numCourses];
Arrays.setAll(g, i -> new ArrayList<>());
for (int[] p : prerequisites) {
g[p[1]].add(p[0]);
}
int[] colors = new int[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 正在访问中
for (int y : g[x]) {
if (colors[y] == 1 || colors[y] == 0 && dfs(y, g, colors)) {
return true; // 找到了环
}
}
colors[x] = 2; // x 完全访问完毕
return false; // 没有找到环
}
}
4.实现前缀Trie
题目链接:208. 实现 Trie (前缀树) - 力扣（LeetCode）
题面:
分析:
1.暴力做法就是把字符串存数组里，判断字符串是否存在就是遍历数组，判断是否以某一字符串作为开头，就是使用startWith函数
2.我们可以定义一个内部类Node，表示节点，他有两个属性，分别是子节点数组和是否是end（为某个单词的最后一个字母），当添加一个单词时，我们从root出发，遍历这个单词，如果某个子节点不存在，就创建这个子节点，查某个单词时，就看遍历时是不是都存在以及是否最后一个节点的end值为true，而查前缀就只需看是否都存在，具体请看下图
代码:
class Node{
Node[] son = new Node[26];
boolean end;
}
class Trie {
Node root;
public Trie() {
root = new Node();
}
public void insert(String word) {
char[] chars = word.toCharArray();
int n = chars.length;
Node node = root;
for(int i = 0;i<n;i++){
int flag = chars[i]-'a';
if(node.son[flag]==null){
node.son[flag] = new Node();
}
node = node.son[flag];
}
node.end = true;
}
public boolean search(String word) {
char[] chars = word.toCharArray();
int n = chars.length;
Node node = root;
for(int i = 0;i<n;i++){
int flag = chars[i]-'a';
if(node.son[flag]==null){
return false;
}
node = node.son[flag];
}
if(node.end)return true;
return false;
}
public boolean startsWith(String prefix) {
char[] chars = prefix.toCharArray();
int n = chars.length;
Node node = root;
for(int i = 0;i<n;i++){
int flag = chars[i]-'a';
if(node.son[flag]==null){
return false;
}
node = node.son[flag];
}
return true;
}
}
/**
* 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);
*/后言
上面是力扣Hot100的图论专题，下一篇是其他专题的习题，希望有所帮助，一同进步，共勉！
原文地址：https://blog.csdn.net/2301_79232523/article/details/143891992
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！