1-课程表
题目链接：题目链接戳这里！！！
思路：将所有的点构成一个有向图，对该图的每个顶点进行搜索，使用vis数组进行标记，如果该顶点为被搜索过，则vis为0，如果被以其他顶点启动的搜索过，则vis为-1，如果被当前顶点为启动点搜索过，vis为1，则说明有环。
AC代码如下：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List> edge = new ArrayList<>() ;
for(int i=0; i()) ;
}
int [] vis = new int [numCourses] ;
for(int [] courses : prerequisites){
edge.get(courses[1]).add(courses[0]) ;
}
for(int i=0; i> edge, int i, int []vis){
if(vis[i]==1){
return false ;
}
if(vis[i]==-1){
return true ;
}
vis[i] = 1 ;
for(int j : edge.get(i)){
if(!dfs(edge,j,vis)){
return false ;
}
}
vis[i] = -1 ;
return true ;
}
}
2-课程表II
题目链接：题目链接戳这里！！！
思路：dfs+栈+有向图
构建有向图，vis数组标记三种状态，vis=0,节点未被访问，vis=1,节点在当前dfs中被访问，vis=-1，节点被之前的dfs所访问，dfs判断每个节点，是否有环，有环则返回空数组，否则需要使用stack记录。
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List> edge = new ArrayList<>() ;
Stack stack = new Stack<>() ;
for(int i=0; i()) ;
}
int [] vis = new int [numCourses] ;
for(int [] courses : prerequisites){
edge.get(courses[1]).add(courses[0]) ;
}
for(int i=0; i> edge, int i, int []vis, Stackstack){
if(vis[i]==1){
return false ;
}
if(vis[i]==-1){
return true ;
}
vis[i] = 1 ;
for(int j : edge.get(i)){
if(!dfs(edge,j,vis,stack)){
return false ;
}
}
vis[i] = -1 ;
stack.push(i) ;
return true ;
}
}
3-水壶问题
题目链接：题目链接戳这里！！！
思路1：数学法，贝祖定理。
class Solution {
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
if(jug1Capacity+jug2Capacity
思路2：DFS，用栈模拟
4-字典序排数
题目链接：题目链接戳这里！！！
思路1：用set集合去重和自动排序的功能，当然可以AC，不过效率较低，而且并不是题目要考察的知识点。
class Solution {
public List lexicalOrder(int n) {
Set set = new TreeSet<>() ;
List list = new ArrayList<>() ;
for(int i=1; i<=n; i++){
set.add(String.valueOf(i)) ;
}
for(String s : set){
list.add(Integer.parseInt(s)) ;
}
return list ;
}
}
思路2：把这些数字看成一个字典树，然后通过dfs进行先序遍历就可以了。
class Solution {
public List lexicalOrder(int n) {
List list = new ArrayList<>() ;
for(int i=1; i<=9; i++){
dfs(i,n,list) ;
}
return list ;
}
public void dfs(int i, int n, List list){
if(i>n){
return ;
}
list.add(i) ;
for(int j=0; j<=9; j++){
dfs(i*10+j,n,list) ;
}
}
}
5-岛屿的周长
题目链接：题目链接戳这里！！！
思路1：只要该位置是陆地就沿着四个方向搜索，如果是边界或者是水域则贡献1，如果当前位置已经搜索过，则贡献0.
class Solution {
int [] offsetX = {1,-1,0,0} ;
int [] offsetY = {0,0,-1,1} ;
public int islandPerimeter(int[][] grid) {
int cnt = 0 ;
for(int i=0; igrid.length-1 || y>grid[0].length-1 || grid[x][y]==0){
return 1 ;
}
if(grid[x][y]==2){
return 0 ;
}
grid[x][y] = 2 ;
int ans = 0 ;
for(int i=0; i<4; i++){
int nx = x + offsetX[i] ;
int ny = y + offsetY[i] ;
ans += dfs(grid,nx,ny) ;
}
return ans ;
}
}
思路2：直接用循环也可以的。如果当前位置是陆地，则当前位置的前后左右四个方向进行判断，如果是边界或者是水域，则当前位置贡献值加1.
class Solution {
int [] offsetX = {1,-1,0,0} ;
int [] offsetY = {0,0,-1,1} ;
public int islandPerimeter(int[][] grid) {
int ans = 0 ;
for(int i=0; igrid.length-1 || ny>grid[0].length-1 || grid[nx][ny]==0){
cnt ++ ;
}
}
ans += cnt ;
}
}
}
return ans ;
}
}
6-甲板上的战舰
题目链接：题目链接戳这里！！！
思路：就是沿着四个方向搜索，判断连通块的数量即可。
每一轮搜索，都把战舰标记为空白，代表搜索过了。
AC代码如下：
class Solution {
int [] offsetX = {-1,1,0,0} ;
int [] offsetY = {0,0,-1,1} ;
public int countBattleships(char[][] board) {
int cnt = 0 ;
for(int i=0; iboard.length-1 || ty>board[0].length-1){
continue ;
}
if(board[tx][ty]=='X'){
dfs(board,tx,ty) ;
}
}
}
}
7-数组嵌套
题目链接：题目链接戳这里！！！
思路：每一次只要当前值不等于Integer.MAX_VALUE，则循环让下一个下标等于当前值，同时计数加1，同时将Integer.MAX_VALUE赋值给当前值，每轮循环找出最大值即可。
AC代码如下：
class Solution {
public int arrayNesting(int[] nums) {
int ans = 0 ;
for(int i=0; i
8-图像渲染
题目链接：题目链接戳这里！！！
思路：如果当前要修改的位置颜色与newColor相同，则不需要修改，否则，将所有与当前位置联通的都修改为新颜色。
class Solution {
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if(image[sr][sc]==newColor){
return image ;
}
int n = image[sr][sc] ;
dfs(image,sr,sc,n,newColor) ;
return image ;
}
public void dfs(int [][]image, int x, int y, int n, int newColor){
image[x][y] = newColor ;
for(int i=0; i<4; i++){
int tx = x + dx[i] ;
int ty = y + dy[i] ;
if(tx<0 || ty<0 || tx>image.length-1 || ty>image[0].length-1){
continue ;
}
if(image[tx][ty]==n){
dfs(image,tx,ty,n,newColor) ;
}
}
}
}
9-钥匙和房间
题目链接：题目链接戳这里！！！
思路：初始化所有房间为false，即未被访问，dfs搜索每个房间，并已该房间的钥匙为房间号继续搜索，如果出现重复搜索则终止当前搜索，直至搜索完成，判断是否所有房间都被标记为true即可。
class Solution {
public boolean canVisitAllRooms(List> rooms) {
List vis = new ArrayList<>() ;
for(int i=0; i> rooms, List vis, int i){
if(vis.get(i)){
return ;
}
vis.set(i, true) ;
for(Integer j : rooms.get(i)){
dfs(rooms,vis,j) ;
}
}
}
10-边界着色
题目链接：题目链接戳这里！！！
思路：就是dfs判断联通块，如果联通则确当是否是边界，边界则染色，注意搜索过的不能再次搜索。
另外边界的判断有两种，一种是第一行/第一列/最后一行/最后一列；另一种则是判断当前的值与原始数组的同样位置的上下左右对比，如果有一个不一样的，也认为是边界。
class Solution {
int [] dx = {-1,1,0,0} ;
int [] dy = {0,0,-1,1} ;
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
int n = grid[row][col] ;
if(n==color){
return grid ;
}
boolean [][]vis = new boolean[grid.length][grid[0].length] ;
int [][] temp = new int[grid.length][grid[0].length] ;
for(int i=0; igrid.length-1 || ty>grid[0].length-1){
continue ;
}else if(!vis[tx][ty] && grid[tx][ty]==n){
vis[tx][ty] = true ;
dfs(grid,tx,ty,n,color,vis,temp) ;
}
}
}
}
志存高远，责任为先，加油吧，少年！！！
