2011海南省java版本入门.docx

根据给定文件的部分内容，我们可以总结出以下几个关键的Java编程知识点： ### 1. 对一个 n×n 矩阵进行排序 #### 目标 编写一个程序，使得一个 n×n 的矩阵按照每行元素的平均值进行递增排序。 #### 实现思路 1. **计算每行平均值**：遍历矩阵的每一行，计算该行所有元素的平均值。 2. **排序**：使用一种排序算法（如冒泡排序、快速排序等）对行的索引进行排序，排序依据为上述计算得到的平均值。 3. **调整矩阵**：根据排序后的行索引重新构建矩阵。 #### 示例代码 ```java public class MatrixSort { public static void sortRows(double[][] matrix) { int n = matrix.length; double[] averages = new double[n]; // 计算每行的平均值 for (int i = 0; i < n; i++) { double sum = 0; for (int j = 0; j < n; j++) { sum += matrix[i][j]; } averages[i] = sum / n; } // 使用插入排序对行进行排序 for (int i = 1; i < n; i++) { double tempAverage = averages[i]; int tempIndex = i; int j = i - 1; while (j >= 0 && averages[j] > tempAverage) { averages[j + 1] = averages[j]; j--; } averages[j + 1] = tempAverage; // 调整矩阵 double[] tempRow = matrix[tempIndex]; while (j >= 0 && averages[j] > tempAverage) { matrix[j + 1] = matrix[j]; j--; } matrix[j + 1] = tempRow; } } public static void main(String[] args) { double[][] matrix = { {3, 2, 1}, {1, 2, 3}, {2, 1, 3} }; sortRows(matrix); // 输出结果 for (double[] row : matrix) { System.out.println(Arrays.toString(row)); } } } ``` ### 2. 约瑟夫环问题 #### 目标 解决约瑟夫环问题，即编号为 1 到 n 的 n 个人按顺时针方向围坐成一圈，从第 s 个人开始按顺时针方向报数，数到第 m 个人出列，然后从出列的下一个人重新开始报数，直到所有人出列为止。 #### 实现思路 1. **创建循环链表**：创建一个包含 n 个节点的循环链表，每个节点代表一个人。 2. **模拟报数过程**：使用指针指向当前报数的位置，并移动指针来模拟报数过程。 3. **出列操作**：当指针移动到指定位置时，将对应的节点从链表中移除。 #### 示例代码 ```java class Node { int value; Node next; public Node(int value) { this.value = value; } } public class JosephusProblem { public static void main(String[] args) { int n = 5; // 总人数 int m = 2; // 每次报数到 m 时出列 int s = 1; // 从第 s 个人开始报数 Node head = null, tail = null; for (int i = 1; i <= n; i++) { Node newNode = new Node(i); if (head == null) { head = newNode; tail = newNode; tail.next = head; } else { tail.next = newNode; tail = newNode; tail.next = head; } } Node current = head; for (int i = 0; i < s - 1; i++) { current = current.next; } System.out.print("出列顺序: "); while (current.next != current) { for (int i = 0; i < m - 1; i++) { current = current.next; } Node toRemove = current.next; System.out.print(toRemove.value + " "); current.next = toRemove.next; toRemove.next = null; } System.out.println(current.value); } } ``` ### 3. 单链表的逆置 #### 目标 实现单链表的就地逆置。 #### 实现思路 1. **初始化指针**：定义三个指针 prev、current 和 next。 2. **遍历链表**：遍历链表，每次将当前节点的 next 指向 prev，然后更新三个指针的位置。 3. **调整头指针**：完成遍历后，将头指针指向最后一个节点。 #### 示例代码 ```java class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; } } public class LinkedListReverse { public static ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; ListNode next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } return prev; } public static void main(String[] args) { ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); head.next.next.next = new ListNode(4); head = reverseList(head); while (head != null) { System.out.print(head.val + " "); head = head.next; } } } ``` ### 4. 数组转换为有序循环链表 #### 目标 将一个含有 n 个元素的数组转换为一个带有头结点的循环链表，并保持链表中元素从小到大的顺序。 #### 实现思路 1. **创建链表**：遍历数组，将每个元素添加到链表中。 2. **排序链表**：使用插入排序或其他合适的排序算法对链表进行排序。 #### 示例代码 ```java class Node { int data; Node next; public Node(int data) { this.data = data; } } public class ArrayToSortedLinkedList { public static Node arrayToSortedLinkedList(int[] arr) { Node head = new Node(arr[0]); Node tail = head; head.next = head; // 创建循环链表 for (int i = 1; i < arr.length; i++) { Node newNode = new Node(arr[i]); Node temp = head; while (temp.next != head && temp.next.data < newNode.data) { temp = temp.next; } newNode.next = temp.next; temp.next = newNode; } return head; } public static void main(String[] args) { int[] arr = {5, 3, 8, 4, 2}; Node head = arrayToSortedLinkedList(arr); Node temp = head; do { System.out.print(temp.data + " "); temp = temp.next; } while (temp != head); } } ``` ### 5. 寻找二叉树中最长路径 #### 目标 寻找二叉树中的最长路径。 #### 实现思路 1. **后序遍历**：使用后序遍历来遍历二叉树，维护一个栈来保存当前结点的祖先信息。 2. **记录最长路径**：每当访问到叶子结点时，检查当前路径是否是最长路径，如果是，则将其保存到另一个栈中。 3. **返回最长路径**：遍历完成后，最长路径保存在辅助栈中。 #### 示例代码 ```java class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class LongestPathInBinaryTree { public static void findLongestPath(TreeNode root) { if (root == null) return; TreeNode[] path = new TreeNode[1000]; // 栈大小足够大 int top = 0; int longest = 0; while (root != null || top > 0) { while (root != null) { path[++top] = root; root = root.left; } if (top > 0) { if (path[top].left == null && path[top].right == null) { if (top > longest) { // 更新最长路径 // ... } top--; } else { root = path[top].right; } } } } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); findLongestPath(root); } } ``` ### 6. 寻找二叉树中两个结点的最近公共祖先 #### 目标 在给定的二叉树中，找到两个结点 p 和 q 的最近公共祖先。 #### 实现思路 1. **后序遍历**：使用后序遍历的方式遍历二叉树。 2. **记录祖先**：使用栈来记录访问过的结点，这些结点都是 p 的祖先。 3. **比较结点**：当访问到 q 时，将栈中的元素与 q 进行比较，找到第一个相等的结点即为最近公共祖先。 #### 示例代码 ```java class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class LowestCommonAncestor { public static TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) { Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { while (root != null && root != p && root != q) { stack.push(root); root = root.left; } if (root == p) { Stack<TreeNode> auxStack = new Stack<>(); for (TreeNode node : stack) { auxStack.push(node); } // 处理 q 的情况 // ... while (!stack.isEmpty() && !auxStack.isEmpty() && stack.peek() == auxStack.peek()) { // 找到最近公共祖先 // ... } } // 继续遍历 // ... } return null; // 如果 p 和 q 没有公共祖先 } public static void main(String[] args) { TreeNode root = new TreeNode(3); root.left = new TreeNode(5); root.right = new TreeNode(1); root.left.left = new TreeNode(6); root.left.right = new TreeNode(2); root.right.left = new TreeNode(0); root.right.right = new TreeNode(8); root.left.right.left = new TreeNode(7); root.left.right.right = new TreeNode(4); TreeNode p = root.left; TreeNode q = root.left.right.right; TreeNode lca = findLCA(root, p, q); System.out.println("最近公共祖先是: " + lca.val); } } ``` ### 7. 判断有向图是否存在简单有向回路 #### 目标 判断给定的有向图是否存在一个简单的有向回路。 #### 实现思路 1. **深度优先搜索**：使用深度优先搜索来遍历有向图。 2. **回溯检测**：在遍历过程中，如果发现已经访问过的节点再次出现，则表明存在回路。 #### 示例代码 ```java public class DirectedCycleDetection { public static boolean hasCycle(int[][] graph) { int n = graph.length; boolean[] visited = new boolean[n]; boolean[] onPath = new boolean[n]; for (int i = 0; i < n; i++) { if (!visited[i] && hasCycleDFS(graph, i, visited, onPath)) { return true; } } return false; } private static boolean hasCycleDFS(int[][] graph, int start, boolean[] visited, boolean[] onPath) { visited[start] = true; onPath[start] = true; for (int next : graph[start]) { if (!visited[next] && hasCycleDFS(graph, next, visited, onPath)) { return true; } else if (onPath[next]) { return true; } } onPath[start] = false; return false; } public static void main(String[] args) { int[][] graph = { {1}, {2}, {0} }; boolean hasCycle = hasCycle(graph); System.out.println("图中是否存在回路: " + hasCycle); } } ``` 以上是根据给定文件内容整理的关键Java编程知识点及示例代码。这些知识点涵盖了矩阵操作、数据结构的应用（如链表、栈）、算法设计（如排序、遍历）等方面，具有较强的实用性和参考价值。