Android学习总结之算法篇七（图和矩阵）

有向图的深度优先搜索（DFS）和广度优先搜索（BFS）的示例，以此来模拟遍历 GC Root 引用链这种有向图结构：

一、深度优先搜索（DFS）

import java.util.*;public class GraphDFS {private final int V; // 顶点数量private final LinkedList<Integer>[] adj; // 邻接表// 构造函数GraphDFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList<>();}// 添加边void addEdge(int v, int w) {adj[v].add(w);}// 深度优先搜索辅助函数void DFSUtil(int v, boolean[] visited) {// 标记当前节点为已访问并打印visited[v] = true;System.out.print(v + " ");// 递归访问所有邻接节点Iterator<Integer> i = adj[v].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n])DFSUtil(n, visited);}}// 深度优先搜索void DFS(int v) {// 标记所有节点为未访问boolean[] visited = new boolean[V];DFSUtil(v, visited);}public static void main(String[] args) {GraphDFS g = new GraphDFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("从顶点 2 开始的深度优先搜索结果:");g.DFS(2);}
}

二、广度优先搜索（BFS）

import java.util.*;public class GraphBFS {private final int V; // 顶点数量private final LinkedList<Integer>[] adj; // 邻接表// 构造函数GraphBFS(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; ++i)adj[i] = new LinkedList<>();}// 添加边void addEdge(int v, int w) {adj[v].add(w);}// 广度优先搜索void BFS(int s) {// 标记所有节点为未访问boolean[] visited = new boolean[V];// 创建一个队列用于 BFSLinkedList<Integer> queue = new LinkedList<>();// 标记当前节点为已访问并加入队列visited[s] = true;queue.add(s);while (queue.size() != 0) {// 出队并打印s = queue.poll();System.out.print(s + " ");// 获取所有邻接节点Iterator<Integer> i = adj[s].listIterator();while (i.hasNext()) {int n = i.next();if (!visited[n]) {visited[n] = true;queue.add(n);}}}}public static void main(String[] args) {GraphBFS g = new GraphBFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println("从顶点 2 开始的广度优先搜索结果:");g.BFS(2);}
}

代码解释

• 深度优先搜索（DFS）：通过递归的方式，尽可能深地访问图中的节点。在访问一个节点后，标记其为已访问，然后递归地访问其未被访问的邻接节点。
• 广度优先搜索（BFS）：使用队列来实现，从起始节点开始，将其标记为已访问并加入队列。然后不断从队列中取出节点，访问其未被访问的邻接节点，并将这些邻接节点加入队列。

三、蛇形打印矩阵 

import java.util.ArrayList;
import java.util.List;public class ZigzagMatrixPrinter {/*** 以蛇形顺序打印矩阵元素* @param matrix 输入的二维矩阵* @return 包含蛇形顺序元素的列表*/public static List<Integer> zigzagOrder(int[][] matrix) {// 用于存储最终蛇形打印结果的列表List<Integer> result = new ArrayList<>();// 检查输入的矩阵是否为空或无效// 如果矩阵为空，或者矩阵没有行，或者矩阵的第一行没有元素，直接返回空列表if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return result;}// 获取矩阵的行数int rows = matrix.length;// 获取矩阵的列数int cols = matrix[0].length;// 遍历矩阵的每一行for (int i = 0; i < rows; i++) {// 判断当前行是否为偶数行（行索引从 0 开始，所以索引为偶数的行是偶数行）if (i % 2 == 0) {// 偶数行从左到右打印// 遍历当前行的每一列for (int j = 0; j < cols; j++) {// 将当前元素添加到结果列表中result.add(matrix[i][j]);}} else {// 奇数行从右到左打印// 从当前行的最后一列开始，逆序遍历到第一列for (int j = cols - 1; j >= 0; j--) {// 将当前元素添加到结果列表中result.add(matrix[i][j]);}}}// 返回存储蛇形打印结果的列表return result;}public static void main(String[] args) {// 定义一个示例矩阵int[][] matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};// 调用 zigzagOrder 方法进行蛇形打印，并将结果存储在 result 列表中List<Integer> result = zigzagOrder(matrix);// 打印蛇形打印的结果System.out.println(result);}
}

四、顺时针打印矩阵（螺旋打印） 

import java.util.ArrayList;
import java.util.List;public class SpiralPrintMatrix {public static void main(String[] args) {// 定义一个二维数组表示矩阵int[][] matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};// 调用螺旋打印矩阵的方法，得到打印结果列表List<Integer> result = spiralOrder(matrix);// 遍历结果列表，打印每个元素for (int num : result) {System.out.print(num + " ");}}/*** 以螺旋顺序（顺时针）遍历矩阵的方法* @param matrix 要遍历的矩阵* @return 包含螺旋遍历结果的列表*/public static List<Integer> spiralOrder(int[][] matrix) {// 用于存储螺旋遍历结果的列表List<Integer> result = new ArrayList<>();// 检查矩阵是否为空或无效，如果是则直接返回空列表if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return result;}// 获取矩阵的行数int rows = matrix.length;// 获取矩阵的列数int cols = matrix[0].length;// 初始化左边界为 0int left = 0;// 初始化右边界为列数减 1int right = cols - 1;// 初始化上边界为 0int top = 0;// 初始化下边界为行数减 1int bottom = rows - 1;// 当左边界小于等于右边界且上边界小于等于下边界时，继续循环while (left <= right && top <= bottom) {// 从左到右打印上边界的元素for (int j = left; j <= right; j++) {result.add(matrix[top][j]);}// 上边界向下移动一行top++;// 从上到下打印右边界的元素for (int i = top; i <= bottom; i++) {result.add(matrix[i][right]);}// 右边界向左移动一列right--;// 检查上边界是否仍然小于等于下边界if (top <= bottom) {// 从右到左打印下边界的元素for (int j = right; j >= left; j--) {result.add(matrix[bottom][j]);}// 下边界向上移动一行bottom--;}// 检查左边界是否仍然小于等于右边界if (left <= right) {// 从下到上打印左边界的元素for (int i = bottom; i >= top; i--) {result.add(matrix[i][left]);}// 左边界向右移动一列left++;}}// 返回包含螺旋遍历结果的列表return result;}
}    

五、矩阵置零

/*** 将矩阵中值为 0 的元素所在的行和列的所有元素都置为 0* * @param matrix 输入的二维矩阵*/
public void setZeroes(int[][] matrix) {// 获取矩阵的行数int m = matrix.length;// 获取矩阵的列数int n = matrix[0].length;// 标记第一行是否原本就存在 0boolean firstRowHasZero = false;// 标记第一列是否原本就存在 0boolean firstColHasZero = false;// 检查第一行是否有 0for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {// 如果第一行存在 0，将标记置为 truefirstRowHasZero = true;// 一旦发现 0，无需继续检查该行其他元素，跳出循环break;}}// 检查第一列是否有 0for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {// 如果第一列存在 0，将标记置为 truefirstColHasZero = true;// 一旦发现 0，无需继续检查该列其他元素，跳出循环break;}}// 标记需要置为 0 的行和列// 从第二行第二列开始遍历矩阵（避开第一行和第一列，因为它们用于标记）for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {// 如果当前元素为 0，将该元素所在行的第一个元素置为 0，标记该行需要置 0matrix[i][0] = 0;// 如果当前元素为 0，将该元素所在列的第一个元素置为 0，标记该列需要置 0matrix[0][j] = 0;}}}// 根据标记置 0// 再次从第二行第二列开始遍历矩阵for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {// 如果当前元素所在行的第一个元素为 0 或者所在列的第一个元素为 0，将该元素置为 0matrix[i][j] = 0;}}}// 处理第一行if (firstRowHasZero) {// 如果第一行原本就有 0，将第一行所有元素置为 0for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}// 处理第一列if (firstColHasZero) {// 如果第一列原本就有 0，将第一列所有元素置为 0for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}
}

六、拿两堆宝石，保证会赢

问题分析

这是一个典型的博弈论问题，目标是通过策略确保先手必胜。关键在于通过第一步操作使两堆宝石数量相等，之后采取对称策略（对方从某堆拿 k 个，自己从另一堆拿 k 个），最终自己拿完最后一个宝石。

必胜策略

1. 初始状态：两堆宝石数量为 12 和 13，差值为 1。
2. 第一步操作：从数量为 13 的堆中拿走 1 个，使两堆均为 12 个，形成对称状态。
3. 后续策略：对方从某一堆拿 k 个（1≤k≤3），自己从另一堆拿 k 个，始终保持两堆数量相等，最终自己拿完最后一个宝石。

Java 代码实现

public class StoneGameStrategy {public static void main(String[] args) {int pile1 = 12;int pile2 = 13;// 先手第一步操作：使两堆数量相等int firstMove = Math.abs(pile1 - pile2);if (pile1 < pile2) {pile2 -= firstMove;} else {pile1 -= firstMove;}System.out.println("第一步从数量为 " + (pile1 + firstMove) + " 的堆中拿 " + firstMove + " 个");System.out.println("剩余两堆数量：" + pile1 + " 和 " + pile2);System.out.println("之后对方拿k个，自己从另一堆拿k个，确保最终获胜");}
}

代码解释

1. 计算初始差值：通过 Math.abs(pile1 - pile2) 计算两堆宝石数量的差值，初始差值为 1。
2. 调整数量：从数量多的堆中拿走差值个宝石（本例中从 13 个的堆拿 1 个），使两堆数量相等（均为 12 个）。
3. 对称策略：后续对方每次从某一堆拿 k 个，自己从另一堆拿 k 个，始终保持两堆数量相等，最终自己拿完最后一个宝石，确保胜利。

结论

先手第一步从数量为 13 的堆中拿走 1 个宝石，之后采取对称策略，即可保证必胜。