200. 岛屿数量
题意
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
题解
简单来看，只要每一个与1上下左右相互连接的就是同一块陆地，那么我们遍历整张图，加入当前点的状态为1，就是有一块陆地了，那么把与他相连的全部赋值为0就可以了，也就是没有价值了
代码
import java.util.*;
public class Solution {
public static void main(String[] args) {
char arr[][]={{'A','B','C','E'},{'S','F','C','S'},
{'A','D','E','E'}
};
}
public int numIslands(char[][] grid) {
int sum=0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length;j++){
if(grid[i][j]=='1'){
sum++;
dfs(grid,i,j);
}
}
}
return sum;
}
static int []zou1={0,0,0,1,-1};
static int []zou2={0,-1,1,0,0};
public static void dfs(char [][] arr,int x,int y){
for(int i=1;i<=4;i++){
int x1=zou1[i]+x;
int y1=zou2[i]+y;
if(x1<0||y1<0||x1>=arr.length||y1>=arr[0].length||arr[x1][y1]=='0'){
continue;
}
arr[x1][y1]='0';
dfs(arr,x1,y1);
}
}
}994. 腐烂的橘子
题意
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
题解
我们这题跟上一题实际上差不多，但是当前题需要求的是最小的分钟数，我们假设当前为3*3，表格为211 111 112 也就是表格边缘有两个的话，实际上对于当前而言，我们应当遍历当前的两个，将与他相连的都赋值为2，也就是被感染了，然后这就是1次，下一次就变成了221 212 122 ，这一次也是同理，遍历所有的2，将他相连的1感染即可
代码
import java.util.*;
public class Solution {
public static void main(String[] args) {
char arr[][]={{'A','B','C','E'},{'S','F','C','S'},
{'A','D','E','E'}
};
}
static int []zou1={0,0,0,1,-1};
static int []zou2={0,1,-1,0,0};
public int orangesRotting(int[][] grid) {
Queue<node>dp =new ArrayDeque<>();
int sum=0;
int ans=0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[i].length ;j++){
if(grid[i][j]==1){
sum++;
}
else if(grid[i][j]==2){
dp.add(new node(i,j));
}
}
}
if(sum!=0&&dp.isEmpty()){
return -1;
}
if(sum==0){
return 0;
}
while(dp.size()>=1&&sum!=0){
ans++;
int f=dp.size();
while(f>=1){
f--;
node now=dp.peek();
dp.poll();
for(int i=1;i<=4;i++){
int x= now.x+zou1[i];
int y=now.y+zou2[i];
if(x<0||y<0||x>=grid.length||y>=grid[x].length||grid[x][y]!=1){
continue;
}
grid[x][y]=2;
dp.add(new node(x,y));
sum--;
}
}
}
if(sum==0){
return ans;
}else{
return -1;
}
}
public static class node{
int x,y;
node(int a,int b){
x=a;
y=b;
}
}
}207. 课程表
题意
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
题解
简单来看，我们将课程视为一张图，也就是遍历图上面有没有环，这个就比较简单，每一次找一个节点进行dfs，看看会不会再一次遍历到当前节点即可
代码
import java.util.*;
public class Solution {
public static void main(String[] args) {
int arr[][]={{0,1}
};
}
static List<List<Integer>> ways = new ArrayList<>(3000);
static int[]mark =new int[3000];
static boolean ans=true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
ans=true;
ways = new ArrayList<>(numCourses+10);
mark = new int[numCourses+10];
for (int i = 0; i < numCourses; i++) {
mark[i]=0;
ways.add(new ArrayList<>());
}
for(int i=0;i<prerequisites.length;i++){
ways.get(prerequisites[i][0]).add(prerequisites[i][1]);
}
for(int i=0;i<numCourses;i++){
if(!ans){
return ans;
}
if(mark[i]==0){
dfs(i);
}
}
return ans;
}
static void dfs(int u){
if (mark[u] == 1) {
ans = false;
return;
}
if (mark[u] == 2) {
return;
}
mark[u] = 1;
for (Integer now : ways.get(u)) {
dfs(now);
}
mark[u] = 2;
}
}208. 实现 Trie (前缀树)
题意
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
题解
简单写一个字典树的题解我们令a=1,b=2等等，画图可得
这实际上就是一ke字典树的抽象模型，令a为根部节点，该图中就会存在abc,abde,abdd，也就是说，在我们进行插入操作的时候，插入的点与点之间的路径关系，但是如果有abd，那么怎么跟abde区分呢，实际上我们把结尾的坐标设置一个结束的按钮即可
代码
class Trie {
boolean check;
Trie[]child;
public Trie() {
check=false;
child =new Trie[28];
}
public void insert(String word) {
Trie node=this;
char []arr=word.toCharArray();
for(int i=0;i<arr.length;i++){
char f=arr[i];
int x=f-'a'+1;
if(node.child[x]==null){
node.child[x]=new Trie();
}
node=node.child[x];
}
node.check=true;
}
public boolean search(String word) {
Trie node=find(word);
if(node==null){
return false;
}
if(node.check==false){
return false;
}
return true;
}
public boolean startsWith(String prefix) {
Trie node=find(prefix);
if(node==null){
return false;
}
return true;
}
public Trie find(String word){
Trie node=this;
char[]arr=word.toCharArray();
for(int i=0;i<arr.length;i++){
int f=arr[i]-'a'+1;
if(node.child[f]==null){
return null;
}
node=node.child[f];
}
return node;
}
}