面试题105：
解决方案：
逐一扫描矩阵的每一个格子，如果遇到一个值为1的格子并且它不在已知的岛屿上，那么就到达了一个新的岛屿，于是搜索这个岛屿并且计算它的面积，在比较所有岛屿的面积之后就可以知道最大的岛屿的面积。
源代码（使用广度优先搜索）：
class Solution {
//主函数
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
//用于记录格子是否已经属于已知的岛屿上
boolean[][] visited = new boolean[rows][cols];
int maxArea = 0;
for(int i = 0;i < rows;i++){
for(int j = 0;j < cols;j++){
if(grid[i][j] == 1 && !visited[i][j]){
int area = getArea(grid,visited,i,j);
maxArea = Math.max(area,maxArea);
}
}
}
return maxArea;
}
//广度优先搜索
private int getArea(int[][] grid,boolean[][] visited,int i,int j){
//创建队列。先将起始节点添加到队列中。接下来每步从队列中取出一个节点进行访问。
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{i,j});
visited[i][j] = true;
//四个方向，上、下、左、右。
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int area = 0;
//对于这个题目而言，每访问一个节点，岛屿的面积增加1。接下来从上、下、左、右这4个方向判断相邻的节点是不是还有没有到达过的值为1的节点，如果有，就将其添加到队列中。重复这个过程，直到队列的长度为0。
while(!queue.isEmpty()){
int[] pos = queue.remove();
area++;
for(int[] dir:dirs){
int r = pos[0] + dir[0];
int c = pos[1] + dir[1];
if(r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 1 && !visited[r][c]){
queue.add(new int[]{r,c});
visited[r][c] = true;
}
}
}
return area;
}
}
源代码（使用深度优先搜索）：
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int maxArea = 0;
for(int i = 0;i < rows;i++){
for(int j = 0;j < cols;j++){
if(grid[i][j] == 1 && !visited[i][j]){
int area = getArea(grid,visited,i,j);
maxArea = Math.max(area,maxArea);
}
}
}
return maxArea;
}
//深度优先搜索
private int getArea(int[][] grid,boolean[][] visited,int i,int j){
//将前面代码中的队列替换成栈，由于栈按照“后进先出”的顺序进行压栈、出栈操作，因此图搜索的顺序相应地变成深度优先搜索。
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{i,j});
visited[i][j] = true;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int area = 0;
while(!stack.isEmpty()){
int[] pos = stack.pop();
area++;
for(int[] dir:dirs){
int r = pos[0] + dir[0];
int c = pos[1] + dir[1];
if(r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 1 && !visited[r][c]){
stack.push(new int[]{r,c});
visited[r][c] = true;
}
}
}
return area;
}
}
源代码（使用递归）：
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int maxArea = 0;
for(int i = 0;i < rows;i++){
for(int j = 0;j < cols;j++){
if(grid[i][j] == 1 && !visited[i][j]){
int area = getArea(grid,visited,i,j);
maxArea = Math.max(area,maxArea);
}
}
}
return maxArea;
}
private int getArea(int[][] grid,boolean[][] visited,int i,int j){
visited[i][j] = true;
int area = 1;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for(int[] dir:dirs){
int r = i + dir[0];
int c = j + dir[1];
if(r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 1 && !visited[r][c]){
area += getArea(grid,visited,r,c);
}
}
return area;
}
}
面试题106：
解决方案：
二分图的节点可以分成两种不同的类型，任意一条边的两个节点分别属于两种不同的类型。可以为图中的所有节点着色，两种不同类型的节点分别涂上不同的颜色。如果任意一条边的两个节点都能被涂上不同的颜色，那么整个图就是一个二分图。
源代码（使用广度优先搜索）：
class Solution {
public boolean isBipartite(int[][] graph) {
int size = graph.length;
int[] colors = new int[size];
Arrays.fill(colors,-1);
for(int i = 0;i < size;i++){
if(colors[i] == -1){
if(!setColor(graph,colors,i,0)){
return false;
}
}
}
return true;
}
//给节点着色
private boolean setColor(int[][] graph,int[] colors,int i,int color){
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
colors[i] = color;
while(!queue.isEmpty()){
int v = queue.remove();
for(int neighbor:graph[v]){
if(colors[neighbor] >= 0){
//如果相邻节点颜色相同，则违背了二分图要求，因此返回false
if(colors[neighbor] == colors[v]){
return false;
}
}else{
queue.add(neighbor);
colors[neighbor] = 1 - colors[v];
}
}
}
return true;
}
}
源代码（使用深度优先搜索）：
class Solution {
public boolean isBipartite(int[][] graph) {
int size = graph.length;
int[] colors = new int[size];
Arrays.fill(colors,-1);
for(int i = 0;i < size;i++){
if(colors[i] == -1){
if(!setColor(graph,colors,i,0)){
return false;
}
}
}
return true;
}
private boolean setColor(int[][] graph,int[] colors,int i,int color){
//如果该节点在此之前已经着色，并且它的颜色不是color，那么意味着不能按照二分图的规则对图中的节点进行着色，直接返回false。
if(colors[i] >= 0){
return colors[i] == color;
}
//如果此时节点i还没有着色，则将它的颜色设为color，然后给与它相邻的节点涂上颜色1-color。
colors[i] = color;
for(int neighbor:graph[i]){
if(!setColor(graph,colors,neighbor,1-color)){
return false;
}
}
return true;
}
}
面试题107：
解决方案：
根据题目的要求，上、下、左、右相邻的两个格子的距离为1。可以将图看成一个无权图，图中两个节点的距离是连通它们的路径经过的边的数目。
源代码：
class Solution {
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length;
int cols = mat[0].length;
//定义矩阵D
int[][] result = new int[rows][cols];
Queue<int[]> queue = new LinkedList<>();
for(int i = 0;i < rows;i++){
for(int j = 0;j < cols;j++){
if(mat[i][j] == 0){
queue.add(new int[]{i,j});
result[i][j] = 0;
}else{
result[i][j] = Integer.MAX_VALUE;
}
}
}
//四个方向，上、下、左、右。
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while(!queue.isEmpty()){
int[] pos = queue.remove();
int dist = result[pos[0]][pos[1]];
for(int[] dir:dirs){
int r = pos[0] + dir[0];
int c = pos[1] + dir[1];
if(r >= 0 && r < rows && c >= 0 && c < cols){
//值为1，并且与0的距离大于1时，才需要改变。
if(result[r][c] > dist + 1){
result[r][c] = dist+1;
queue.add(new int[]{r,c});
}
}
}
}
return result;
}
}
面试题108：
解决方案：
这个题目要求计算最短演变序列的长度，即求图中两个节点的最短距离。表示单词演变的图也是一个无权图，按照题目的要求，图中两个节点的距离是连通两个节点的路径经过的节点的数目。
源代码（单向广度优先搜索）：
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//创建两个队列，交替使用queue1和queue2这两个队列由近及远地从起始节点开始搜索所有节点。
Queue<String> queue1 = new LinkedList<>();
Queue<String> queue2 = new LinkedList<>();
Set<String> notvisited = new HashSet<>(wordList);
//因为beginWord与endWord不相同，因此改变长度至少为1.
int length = 1;
queue1.add(beginWord);
while(!queue1.isEmpty()){
String word = queue1.remove();
if(word.equals(endWord)){
return length;
}
//改变一个字符的word的全部情况
List<String> neighbors = getNeighbors(word);
for(String neighbor:neighbors){
//如果单词列表存在该改变一个字符的情况，则添加到queue2中
if(notvisited.contains(neighbor)){
queue2.add(neighbor);
notvisited.remove(neighbor);
}
}
//因为队列queue2全是queue1的中word改变一个字符的情况，故length增加1，queue1遍历完切换到queue2
if(queue1.isEmpty()){
length++;
queue1 = queue2;
queue2 = new LinkedList<>();
}
}
return 0;
}
//改变字符串word的每一个字符，添加到链表中并返回
private List<String> getNeighbors(String word){
List<String> neighbors = new LinkedList<>();
char[] chs = word.toCharArray();
for(int i = 0;i < chs.length;i++){
char old = chs[i];
for(char ch = 'a';ch <= 'z';ch++){
if(old != ch){
chs[i] = ch;
neighbors.add(new String(chs));
}
}
chs[i] = old;
}
return neighbors;
}
}
源代码（双向广度优先搜索）：
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//set1和set2分别存放两个方向上当前需要访问的节点，set3用来存放与当前访问的节点相邻的节点。
Set<String> notVisited = new HashSet<>(wordList);
if(!notVisited.contains(endWord)){
return 0;
}
Set<String> set1 = new HashSet<>();
Set<String> set2 = new HashSet<>();
int length = 2;
set1.add(beginWord);
set2.add(endWord);
notVisited.remove(endWord);
while(!set1.isEmpty() && !set2.isEmpty()){
//每次while循环都是从需要访问的节点数目少的方向搜索，这样做是为了缩小搜索的空间。
if(set2.size() < set1.size()){
Set<String> temp = set1;
set1 = set2;
set2 = temp;
}
Set<String> set3 = new HashSet<>();
for(String word:set1){
List<String> neighbors = getNeighbors(word);
for(String neighbor:neighbors){
if(set2.contains(neighbor)){
return length;
}
if(notVisited.contains(neighbor)){
set3.add(neighbor);
notVisited.remove(neighbor);
}
}
}
length++;
set1 = set3;
}
return 0;
}
private List<String> getNeighbors(String word){
List<String> neighbors = new LinkedList<>();
char[] chs = word.toCharArray();
for(int i = 0;i < chs.length;i++){
char old = chs[i];
for(char ch = 'a';ch <= 'z';ch++){
if(old != ch){
chs[i] = ch;
neighbors.add(new String(chs));
}
}
chs[i] = old;
}
return neighbors;
}
}
面试题109：
解决方案：
- 密码锁4个转轮上的数字定义了密码锁的状态，转动密码锁的转轮可以改变密码锁的状态。一般而言，如果一个问题是关于某事物状态的改变，那么可以考虑把问题转换成图搜索的问题。事物的每个状态是图中的一个节点，如果一个状态能够转变到另一个状态，那么这两个状态对应的节点之间有一条边相连。
- 对于这个问题而言，密码锁的每个状态都对应着图中的一个节点，如状态"0000"是一个节点，"0001"是另一个节点。如果转动某个转轮一次可以让密码锁从一个状态转移到另一个状态，那么这两个状态之间有一条边相连。
源代码：
class Solution {
public int openLock(String[] deadends, String target) {
//存储死锁情况
Set<String> dead = new HashSet<>(Arrays.asList(deadends));
Set<String> visied = new HashSet<>();
String init = "0000";
if(dead.contains(init) || dead.contains(target)){
return -1;
}
Queue<String> queue1 = new LinkedList<>();
Queue<String> queue2 = new LinkedList<>();
int steps = 0;
queue1.offer(init);
visied.add(init);
while(!queue1.isEmpty()){
String cur = queue1.remove();
if(cur.equals(target)){
return steps;
}
List<String> nexts = getNeighbors(cur);
for(String next:nexts){
if(!dead.contains(next) && !visied.contains(next)){
queue2.add(next);
visied.add(next);
}
}
if(queue1.isEmpty()){
steps++;
queue1 = queue2;
queue2 = new LinkedList();
}
}
return -1;
}
//得到转动一次的所有情况
private List<String> getNeighbors(String cur){
List<String> nexts = new LinkedList<>();
for(int i = 0;i < cur.length();i++){
char ch = cur.charAt(i);
char newCh = ch == '0'?'9':(char)(ch-1);
StringBuilder builder = new StringBuilder(cur);
builder.setCharAt(i,newCh);
nexts.add(builder.toString());
newCh = ch == '9'?'0':(char)(ch + 1);
builder.setCharAt(i,newCh);
nexts.add(builder.toString());
}
return nexts;
}
}
面试题110：
解决方案：
使用深度优先搜索，通常用递归实现。从节点0出发开始搜索。每当搜索到节点i时，先将该节点添加到路径中去。如果该节点正好是节点n-1，那么就找到了一条从节点0到节点n-1的路径。如果不是，则从graph[i]找到每个相邻的节点并用同样的方法进行搜索。当从节点i出发能够抵达的所有节点都搜索完毕之后，将回到前一个节点搜索其他与之相邻的节点。
源代码：
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(0,graph,path,result);
return result;
}
//soure用于标记位于节点的位置
private void dfs(int soure,int[][] graph,List<Integer> path,List<List<Integer>> result){
path.add(soure);
if(soure == graph.length-1){
result.add(new ArrayList<>(path));
}else{
for(int next:graph[soure]){
dfs(next,graph,path,result);
}
}
path.remove(path.size() - 1);
}
}
面试题111：
解决方案：
这个问题是关于两个变量之间的除法，因此可以将变量看作图中的节点。如果存在两个变量的除法等式，那么这两个变量对应的节点之间有一条边相连。一个除法等式除了被除数和除数，还有商。被除数和除数都对应图中的节点，商是两个变量的除法的结果，表达的是变量之间的关系，因此商应该是边的属性。可以给图中的每条边定义一个权重，为两个变量的除法的商。
源代码：
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String,Map<String,Double>> graph = getGraph(equations,values);
double[] results = new double[queries.size()];
for(int i = 0;i < queries.size();i++){
String from = queries.get(i).get(0);
String to = queries.get(i).get(1);
if(!graph.containsKey(from) || !graph.containsKey(to)){
results[i] = -1;
}else{
Set<String> visited = new HashSet<>();
results[i] = dfs(graph,from,to,visited);
}
}
return results;
}
//记录两个变量的权重关系到map中
private Map<String,Map<String,Double>> getGraph(List<List<String>> equations,double[] values){
Map<String,Map<String,Double>> graph = new HashMap<>();
for(int i = 0;i < equations.size();i++){
String var1 = equations.get(i).get(0);
String var2 = equations.get(i).get(1);
graph.putIfAbsent(var1,new HashMap<>());
graph.get(var1).put(var2,values[i]);
graph.putIfAbsent(var2,new HashMap<>());
graph.get(var2).put(var1,1.0/values[i]);
}
return graph;
}
//计算字符串from和字符串to的商
private double dfs(Map<String,Map<String,Double>> graph,String from,String to,Set<String> visited){
if(from.equals(to)){
return 1.0;
}
visited.add(from);
for(Map.Entry<String,Double> entry:graph.get(from).entrySet()){
String next = entry.getKey();
if(!visited.contains(next)){
double nextValue = dfs(graph,next,to,visited);
if(nextValue > 0){
return entry.getValue() * nextValue;
}
}
}
visited.remove(from);
return -1.0;
}
}
面试题112：
解决方案：
使用深度优先搜索找出从矩阵的每个数字出发的最长递增路径的长度。
源代码：
class Solution {
public int longestIncreasingPath(int[][] matrix) {
int[][] lengths = new int[matrix.length][matrix[0].length];
int result = 1;
for(int i = 0;i < matrix.length;i++){
for(int j = 0;j < matrix[0].length;j++){
int incrementNum = dfs(matrix,lengths,i,j);
result = Math.max(result,incrementNum);
}
}
return result;
}
private int dfs(int[][] matrix,int[][] lengths,int i,int j){
if(lengths[i][j] != 0){
return lengths[i][j];
}
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
int length = 1;
for(int[] dir:dirs){
int r = i + dir[0];
int c = j + dir[1];
if(r >= 0 && r < rows && c >= 0 && c < cols && matrix[r][c] > matrix[i][j]){
int path = dfs(matrix,lengths,r,c);
length = Math.max(path+1,length);
}
}
lengths[i][j] = length;
return length;
}
}
