华为OD机试 - 拔河比赛（Java 2023 B卷 100分）

### 华为 Java 算法面试题实现示例 #### 示例一：拔河比赛问题 在华为 OD 机试中，有一道关于 **拔河比赛** 的经典题目。该问题是基于字符串处理的逻辑设计而成[^1]。 以下是具体的解决方案： ```java import java.util.*; public class TugOfWar { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = Integer.parseInt(scanner.nextLine()); String s = scanner.nextLine(); List<Integer> list = new ArrayList<>(); for (int i = 0; i < n; ++i) { list.add(s.charAt(i) - 'a'); } System.out.println(tugOfWar(list)); } private static long tugOfWar(List<Integer> weights) { int sum = 0; for (Integer weight : weights) { sum += weight; } boolean[][] dp = new boolean[weights.size() + 1][sum + 1]; dp[0][0] = true; for (int i = 1; i <= weights.size(); ++i) { for (int j = 0; j <= sum; ++j) { if (!dp[i - 1][j]) continue; dp[i][j] = true; if (j + weights.get(i - 1) <= sum) { dp[i][j + weights.get(i - 1)] = true; } } } int minDiff = Integer.MAX_VALUE; for (int j = 0; j * 2 <= sum; ++j) { if (dp[weights.size()][j]) { minDiff = Math.min(minDiff, sum - 2 * j); } } return minDiff; } } ``` 上述代码实现了通过动态规划解决拔河比赛中两组力量差最小化的问题。 --- #### 示例二：最长回文子串问题 另一个常见的华为算法面试题是寻找给定字符串中的最长回文子串[^4]。此问题可以通过中心扩展法高效求解。 具体实现如下所示： ```java public class LongestPalindromeSubstring { public static String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); // 奇数长度回文 int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度回文 int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private static int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { --left; ++right; } return right - left - 1; } public static void main(String[] args) { String input = "babad"; System.out.println(longestPalindrome(input)); // 输出："bab" } } ``` 这段代码展示了如何利用中心扩展方法找到字符串中最长的回文子串。 --- #### 示例三：链表反转问题 链表操作也是华为面试中常考的内容之一[^3]。下面是一个简单的单向链表反转的例子： ```java class ListNode { int val; ListNode next; ListNode(int x) { this.val = x; } } public class ReverseLinkedList { public static ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode tempNext = curr.next; curr.next = prev; prev = curr; curr = tempNext; } return prev; } public static void main(String[] args) { ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); node1.next = node2; node2.next = node3; ListNode reversedHead = reverseList(node1); // 反转后的头节点应指向原链表最后一个节点 } } ``` 以上代码演示了如何逆序遍历并重新连接链表节点来完成链表反转的操作。 --- #### 总结 通过对上述几个典型例子的学习可以看出，在准备华为或其他大厂的技术面试时，掌握扎实的数据结构基础以及灵活运用各种常见算法技巧是非常重要的[^2]。