1. 南昌大学计算机考研机试高频算法题解析
南昌大学计算机考研机试向来以算法题为核心考察点，题目难度适中但注重基础算法的灵活运用。根据历年真题分析，数组操作、字符串处理、二叉树遍历等题型出现频率极高。下面我将结合具体题目，分享几种典型算法的解题思路和优化技巧。
先说说数组类题目。这类题目往往考察对数组特性的理解，比如"数组中重复的数字"这道经典题。题目要求在长度为n的数组中找出任意一个重复数字，所有数字都在0到n-1范围内。最直观的解法是排序后遍历，时间复杂度O(nlogn)。但更优解是利用数组下标特性：遍历时将元素值作为下标，给对应位置的元素加上数组长度n作为标记。这样当再次遇到该下标时，就能发现重复元素。这种方法只需O(n)时间，且空间复杂度为O(1)。
public static int findDuplicate(int[] nums) { for (int i = 0; i < nums.length; i++) { int index = nums[i] % nums.length; if (nums[index] >= nums.length) { return index; } nums[index] += nums.length; } return -1; }对于字符串处理题，比如"验证回文字符串"，题目允许删除最多一个字符来判断是否能构成回文。这类题目适合采用双指针法：从字符串两端向中间遍历，当遇到不匹配字符时，分别尝试跳过左指针或右指针的字符，继续验证剩余部分是否为回文。这种解法时间复杂度为O(n)，只需常数空间。
public boolean validPalindrome(String s) { int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1); } left++; right--; } return true; }2. 栈与队列的经典应用
栈和队列是机试中的常客，考察重点在于对这两种数据结构特性的灵活运用。"设计一个getMin的栈"就是典型代表。题目要求实现一个能在O(1)时间内返回栈中最小元素的特殊栈。最优解法是使用辅助栈：主栈正常存储数据，辅助栈存储当前最小值。当新元素入栈时，若小于等于辅助栈顶元素，则同时压入辅助栈；出栈时，若主栈顶元素等于辅助栈顶元素，则辅助栈也弹出栈顶。
class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if (minStack.isEmpty() || x <= minStack.peek()) { minStack.push(x); } } public void pop() { if (stack.pop().equals(minStack.peek())) { minStack.pop(); } } public int getMin() { return minStack.peek(); } }另一个经典题目是"用栈解决汉诺塔问题"。传统汉诺塔使用递归解法，但用栈实现非递归版本更能考察对栈的理解。解题关键在于使用三个栈模拟三根柱子，通过枚举所有可能的移动方式（左到中、中到左、中到右、右到中），避免连续逆移动和重复移动。每次移动都检查是否满足小盘在大盘上的规则，并记录上一步操作防止重复。
public int hanoiWithStack(int n) { Stack<Integer> left = new Stack<>(); Stack<Integer> mid = new Stack<>(); Stack<Integer> right = new Stack<>(); // 初始化左栈 for (int i = n; i > 0; i--) left.push(i); int steps = 0; while (right.size() != n) { // 枚举四种可能的移动方式 steps += move(left, mid, "left", "mid"); steps += move(mid, left, "mid", "left"); steps += move(mid, right, "mid", "right"); steps += move(right, mid, "right", "mid"); } return steps; }3. 二叉树相关算法精解
二叉树题目在机试中占比很大，常见题型包括遍历、判断平衡性等。"判断二叉树是否为平衡二叉树"要求检查树中任意节点的左右子树高度差不超过1。高效解法是后序遍历过程中计算子树高度，一旦发现不平衡立即返回。这种方法避免了重复计算，时间复杂度O(n)。
public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } private int getHeight(TreeNode node) { if (node == null) return 0; int left = getHeight(node.left); if (left == -1) return -1; int right = getHeight(node.right); if (right == -1) return -1; if (Math.abs(left - right) > 1) return -1; return Math.max(left, right) + 1; }"二叉树的中序遍历"也有递归和非递归两种实现。非递归版本使用栈模拟递归过程：从根节点开始，将所有左子节点入栈，然后弹出栈顶访问，再转向右子树。这种方法虽然代码稍复杂，但有助于理解遍历的本质。
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); res.add(curr.val); curr = curr.right; } return res; }4. 位运算的巧妙应用
位运算题目往往考察对二进制特性的理解。"只出现一次的数字"系列就是典型代表。基础版本是所有数字出现两次，找出唯一出现一次的数字。利用异或运算的性质：a^a=0，a^0=a，将所有数字异或即可得到结果。
public int singleNumber(int[] nums) { int res = 0; for (int num : nums) { res ^= num; } return res; }进阶版本是数字出现三次，找出唯一出现一次的数字。解法一是统计每位1出现的次数，如果不是3的倍数，则结果在该位为1。解法二使用两个变量模拟三进制计数，通过状态转换找出唯一数字。
public int singleNumberII(int[] nums) { int ones = 0, twos = 0; for (int num : nums) { ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones; } return ones; }最难的是有两个唯一数字的情况。解法是先异或所有数得到两个目标数的异或值，根据某位是否为1将数组分成两组，分别异或得到最终结果。
public int[] singleNumberIII(int[] nums) { int diff = 0; for (int num : nums) diff ^= num; diff &= -diff; // 获取最右边的1 int[] res = new int[2]; for (int num : nums) { if ((num & diff) == 0) res[0] ^= num; else res[1] ^= num; } return res; }5. 动态规划与回溯算法
虽然原始题目中未涉及，但动态规划和回溯算法也是机试高频考点。以"最长递增子序列"为例，标准解法是用dp数组记录以每个位置结尾的最长序列长度，时间复杂度O(n^2)。更优的解法是结合二分查找，将时间复杂度降至O(nlogn)。
public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int size = 0; for (int num : nums) { int i = 0, j = size; while (i != j) { int m = (i + j) / 2; if (tails[m] < num) i = m + 1; else j = m; } tails[i] = num; if (i == size) size++; } return size; }回溯算法常用于排列组合问题，如"全排列"。通过交换元素位置生成所有可能的排列，注意在递归返回时需要恢复现场。
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(nums, 0, res); return res; } private void backtrack(int[] nums, int start, List<List<Integer>> res) { if (start == nums.length) { List<Integer> list = new ArrayList<>(); for (int num : nums) list.add(num); res.add(list); return; } for (int i = start; i < nums.length; i++) { swap(nums, start, i); backtrack(nums, start + 1, res); swap(nums, start, i); } }6. 图论基础算法
图论题目虽然出现频率不如前几类高，但也值得准备。"图的广度优先搜索"是基础中的基础，常用于最短路径等问题。下面是用邻接表表示图的BFS实现：
public void bfs(List<List<Integer>> graph, int start) { boolean[] visited = new boolean[graph.size()]; Queue<Integer> queue = new LinkedList<>(); queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int node = queue.poll(); System.out.print(node + " "); for (int neighbor : graph.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } }对于"拓扑排序"问题，可以使用Kahn算法：统计每个节点的入度，将入度为0的节点加入队列，依次处理并更新相邻节点的入度。
public List<Integer> topologicalSort(int numCourses, int[][] prerequisites) { List<List<Integer>> graph = new ArrayList<>(); int[] inDegree = new int[numCourses]; for (int i = 0; i < numCourses; i++) { graph.add(new ArrayList<>()); } for (int[] edge : prerequisites) { graph.get(edge[1]).add(edge[0]); inDegree[edge[0]]++; } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) queue.offer(i); } List<Integer> res = new ArrayList<>(); while (!queue.isEmpty()) { int node = queue.poll(); res.add(node); for (int neighbor : graph.get(node)) { if (--inDegree[neighbor] == 0) { queue.offer(neighbor); } } } return res.size() == numCourses ? res : new ArrayList<>(); }7. 字符串处理进阶技巧
字符串处理题目除了基础的回文判断，还有更复杂的模式匹配问题。"Z字形变换"要求将字符串按Z字形排列后按行读取。解法是模拟Z字形遍历过程，使用多个字符串构建器存储每行字符，最后拼接结果。
public String convert(String s, int numRows) { if (numRows == 1) return s; List<StringBuilder> rows = new ArrayList<>(); for (int i = 0; i < Math.min(numRows, s.length()); i++) { rows.add(new StringBuilder()); } int curRow = 0; boolean goingDown = false; for (char c : s.toCharArray()) { rows.get(curRow).append(c); if (curRow == 0 || curRow == numRows - 1) { goingDown = !goingDown; } curRow += goingDown ? 1 : -1; } StringBuilder res = new StringBuilder(); for (StringBuilder row : rows) { res.append(row); } return res.toString(); }另一个典型题目是"字符串相乘"，要求实现大数乘法。解法是模拟手工乘法过程，使用数组存储中间结果，注意处理进位。
public String multiply(String num1, String num2) { int m = num1.length(), n = num2.length(); int[] pos = new int[m + n]; for (int i = m - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); int p1 = i + j, p2 = i + j + 1; int sum = mul + pos[p2]; pos[p1] += sum / 10; pos[p2] = sum % 10; } } StringBuilder sb = new StringBuilder(); for (int p : pos) { if (!(sb.length() == 0 && p == 0)) { sb.append(p); } } return sb.length() == 0 ? "0" : sb.toString(); }8. 排序与搜索算法优化
排序算法虽然基础，但优化版本常出现在机试中。"快速排序"的优化版本需要注意以下几点：三数取中选择基准、小数组切换为插入排序、三向切分处理大量重复元素。
public void quickSort(int[] nums, int low, int high) { if (high <= low) return; if (high - low < 15) { insertionSort(nums, low, high); return; } int[] p = partition(nums, low, high); quickSort(nums, low, p[0] - 1); quickSort(nums, p[1] + 1, high); } private int[] partition(int[] nums, int low, int high) { // 三数取中 int mid = low + (high - low) / 2; if (nums[low] > nums[high]) swap(nums, low, high); if (nums[mid] > nums[high]) swap(nums, mid, high); if (nums[mid] > nums[low]) swap(nums, mid, low); int pivot = nums[low]; int lt = low, gt = high, i = low + 1; while (i <= gt) { if (nums[i] < pivot) { swap(nums, lt++, i++); } else if (nums[i] > pivot) { swap(nums, i, gt--); } else { i++; } } return new int[]{lt, gt}; }二分查找的变种也是常考点，如"在旋转排序数组中搜索"。这类题目需要处理部分有序的情况，通过比较中间元素与左右边界来确定搜索范围。
public int search(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; if (nums[left] <= nums[mid]) { // 左半部分有序 if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { // 右半部分有序 if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; }
