算法面试——深度优先搜索：全排列、组合总和、岛屿数量

一、全排列

publicList<List<Integer>>permute(int[]nums){List<List<Integer>>result=newArrayList<>();backtrack(nums,newboolean[nums.length],newArrayList<>(),result);returnresult;}privatevoidbacktrack(int[]nums,boolean[]used,List<Integer>path,List<List<Integer>>result){if(path.size()==nums.length){result.add(newArrayList<>(path));return;}for(inti=0;i<nums.length;i++){if(used[i])continue;used[i]=true;path.add(nums[i]);backtrack(nums,used,path,result);path.remove(path.size()-1);used[i]=false;}}

二、组合总和

publicList<List<Integer>>combinationSum(int[]nums,inttarget){List<List<Integer>>result=newArrayList<>();backtrack(nums,target,0,newArrayList<>(),result);returnresult;}privatevoidbacktrack(int[]nums,intremain,intstart,List<Integer>path,List<List<Integer>>result){if(remain==0){result.add(newArrayList<>(path));return;}if(remain<0)return;for(inti=start;i<nums.length;i++){path.add(nums[i]);backtrack(nums,remain-nums[i],i,path,result);path.remove(path.size()-1);}}

三、岛屿数量

publicintnumIslands(char[][]grid){intcount=0;for(inti=0;i<grid.length;i++)for(intj=0;j<grid[0].length;j++)if(grid[i][j]=='1'){dfs(grid,i,j);count++;}returncount;}privatevoiddfs(char[][]g,intr,intc){if(r<0||c<0||r>=g.length||c>=g[0].length||g[r][c]!='1')return;g[r][c]='0';dfs(g,r+1,c);dfs(g,r-1,c);dfs(g,r,c+1);dfs(g,r,c-1);}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！