算法 目录 华为OD常考算法题 1. 字符串处理 1.1 统计相同字符串个数 原题 ：给定一个字符串和一个子串，统计子串在字符串中出现的次数（不区分大小写）。
示例 ：
1 2 3 4 输入： Hello World Hello hello 输出：2
解题思路 ：将原字符串和子串都转为小写，通过替换子串为空，计算长度差来得到出现次数。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import java.util.Scanner;public class StrNumbers { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); String str = scanner.nextLine(); String target = scanner.nextLine(); System.out.println(countOccurrences(str, target)); } static int countOccurrences (String str, String target) { String s = str.toLowerCase(); String t = target.toLowerCase(); if (t.isEmpty()) return 0 ; return (s.length() - s.replace(t, "" ).length()) / t.length(); } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 def count_occurrences (s: str , target: str ) -> int : s_lower = s.lower() t_lower = target.lower() if not t_lower: return 0 return s_lower.count(t_lower) if __name__ == "__main__" : s = input () target = input () print (count_occurrences(s, target))
1.2 字符串反转 原题 ：输入一个字符串，反转输出该字符串。
示例 ：
1 2 输入：hello world 输出：dlrow olleh
解题思路 ：双指针法，左右交换字符。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java.util.Scanner;public class StringReverse { public static void main (String[] args) { Scanner sc = new Scanner (System.in); String s = sc.nextLine(); System.out.println(reverse(s)); } static String reverse (String s) { char [] chars = s.toCharArray(); int left = 0 , right = chars.length - 1 ; while (left < right) { char temp = chars[left]; chars[left] = chars[right]; chars[right] = temp; left++; right--; } return new String (chars); } }
Python 源码 ：
1 2 3 4 5 6 def reverse_string (s: str ) -> str : return s[::-1 ] if __name__ == "__main__" : s = input () print (reverse_string(s))
2. 数组与链表 2.1 明明的随机数 原题 ：明明生成了N个1到500之间的随机整数，请你删去其中重复的数字，然后从小到大排序输出。
示例 ：
1 2 3 4 5 6 7 8 9 10 11 12 输入： 5 3 2 2 1 4 输出： 1 2 3 4
解题思路 ：使用TreeSet（Java）或sorted(set)（Python）进行去重和排序。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import java.util.Iterator;import java.util.Scanner;import java.util.TreeSet;public class RandomNumbers { public static void main (String[] args) { Scanner sc = new Scanner (System.in); int num = sc.nextInt(); TreeSet<Integer> set = new TreeSet <>(); for (int i = 0 ; i < num; i++) { set.add(sc.nextInt()); } Iterator<Integer> iterator = set.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); } } }
Python 源码 ：
1 2 3 4 5 6 7 if __name__ == "__main__" : n = int (input ()) nums = set () for _ in range (n): nums.add(int (input ())) for num in sorted (nums): print (num)
2.2 两数之和 原题 ：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
示例 ：
1 2 3 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] = 2 + 7 = 9
解题思路 ：使用哈希表存储已遍历的数字及其索引，时间复杂度O(n)。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import java.util.HashMap;import java.util.Map;public class TwoSum { public int [] twoSum(int [] nums, int target) { Map<Integer, Integer> map = new HashMap <>(); for (int i = 0 ; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int []{map.get(complement), i}; } map.put(nums[i], i); } return new int []{-1 , -1 }; } }
Python 源码 ：
1 2 3 4 5 6 7 8 def two_sum (nums: list [int ], target: int ) -> list [int ]: num_map = {} for i, num in enumerate (nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i return [-1 , -1 ]
3. 排序与搜索 3.1 快速排序 原题 ：实现快速排序算法。
示例 ：
1 2 输入：[3,6,8,10,1,2,1] 输出：[1,1,2,3,6,8,10]
解题思路 ：选择一个基准元素，将小于基准的放左边，大于基准的放右边，递归排序左右子数组。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class QuickSort { public void quickSort (int [] arr, int left, int right) { if (left < right) { int pivotIndex = partition(arr, left, right); quickSort(arr, left, pivotIndex - 1 ); quickSort(arr, pivotIndex + 1 , right); } } private int partition (int [] arr, int left, int right) { int pivot = arr[right]; int i = left - 1 ; for (int j = left; j < right; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1 , right); return i + 1 ; } private void swap (int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def quick_sort (arr: list [int ], left: int , right: int ): if left < right: pivot_index = partition(arr, left, right) quick_sort(arr, left, pivot_index - 1 ) quick_sort(arr, pivot_index + 1 , right) def partition (arr: list [int ], left: int , right: int ) -> int : pivot = arr[right] i = left - 1 for j in range (left, right): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1 ], arr[right] = arr[right], arr[i + 1 ] return i + 1
4. 动态规划 4.1 三角形最小路径和 原题 ：给定一个三角形，找到从顶部到底部的最小路径和。每一步只能移动到下一行中相邻的数字。
示例 ：
1 2 3 4 5 6 7 8 9 输入： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 输出：11 解释：自顶向下的最小路径和为 2 + 3 + 5 + 1 = 11
解题思路 ：动态规划，从下往上递推更简洁。dp[i][j]表示从(i,j)到底部的最小路径和。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import java.util.List;public class TriangleMinimumTotal { public int minimumTotal (List<List<Integer>> triangle) { int n = triangle.size(); int [] dp = new int [n + 1 ]; for (int i = n - 1 ; i >= 0 ; i--) { for (int j = 0 ; j <= i; j++) { dp[j] = Math.min(dp[j], dp[j + 1 ]) + triangle.get(i).get(j); } } return dp[0 ]; } }
Python 源码 ：
1 2 3 4 5 6 7 def minimum_total (triangle: list [list [int ]] ) -> int : n = len (triangle) dp = [0 ] * (n + 1 ) for i in range (n - 1 , -1 , -1 ): for j in range (i + 1 ): dp[j] = min (dp[j], dp[j + 1 ]) + triangle[i][j] return dp[0 ]
4.2 最长上升子序列 原题 ：给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例 ：
1 2 3 输入：[10,9,2,5,3,7,101,18] 输出：4 解释：最长的上升子序列是 [2,3,7,101]，它的长度是 4
解题思路 ：动态规划，dp[i]表示以i结尾的最长上升子序列长度。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class LongestIncreasingSubsequence { public int lengthOfLIS (int [] nums) { if (nums == null || nums.length == 0 ) return 0 ; int [] dp = new int [nums.length]; int max = 1 ; for (int i = 0 ; i < nums.length; i++) { dp[i] = 1 ; for (int j = 0 ; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1 ); } } max = Math.max(max, dp[i]); } return max; } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 def length_of_lis (nums: list [int ] ) -> int : if not nums: return 0 dp = [1 ] * len (nums) max_len = 1 for i in range (len (nums)): for j in range (i): if nums[i] > nums[j]: dp[i] = max (dp[i], dp[j] + 1 ) max_len = max (max_len, dp[i]) return max_len
5. 树与图 5.1 二叉树的层序遍历 原题 ：给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。
示例 ：
1 2 3 4 5 6 7 输入：[3,9,20,null,null,15,7] 输出： [ [3], [9,20], [15,7] ]
解题思路 ：使用队列进行广度优先搜索（BFS）。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this .val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this .val = val; this .left = left; this .right = right; } } public class BinaryTreeLevelOrder { public List<List<Integer>> levelOrder (TreeNode root) { List<List<Integer>> result = new ArrayList <>(); if (root == null ) return result; Queue<TreeNode> queue = new LinkedList <>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList <>(); for (int i = 0 ; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null ) queue.offer(node.left); if (node.right != null ) queue.offer(node.right); } result.add(level); } return result; } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 from collections import dequefrom typing import List , Optional class TreeNode : def __init__ (self, val=0 , left=None , right=None ): self .val = val self .left = left self .right = right def level_order (root: Optional [TreeNode] ) -> List [List [int ]]: result = [] if not root: return result queue = deque([root]) while queue: level_size = len (queue) level = [] for _ in range (level_size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result
5.2 二叉树的最大深度 原题 ：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
示例 ：
1 2 输入：[3,9,20,null,null,15,7] 输出：3
解题思路 ：递归或BFS。
Java 源码 ：
1 2 3 4 5 6 7 8 public class MaxDepth { public int maxDepth (TreeNode root) { if (root == null ) return 0 ; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1 ; } }
Python 源码 ：
1 2 3 4 5 6 def max_depth (root: Optional [TreeNode] ) -> int : if not root: return 0 left = max_depth(root.left) right = max_depth(root.right) return max (left, right) + 1
6. 双指针与滑动窗口 6.1 无重复字符的最长子串 原题 ：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 ：
1 2 3 输入：s = "abcabcbb" 输出：3 解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3
解题思路 ：滑动窗口，用哈希表记录字符最后出现的位置。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.HashMap;import java.util.Map;public class LongestSubstringWithoutRepeating { public int lengthOfLongestSubstring (String s) { Map<Character, Integer> map = new HashMap <>(); int max = 0 ; int left = 0 ; for (int right = 0 ; right < s.length(); right++) { char c = s.charAt(right); if (map.containsKey(c)) { left = Math.max(left, map.get(c) + 1 ); } map.put(c, right); max = Math.max(max, right - left + 1 ); } return max; } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 def length_of_longest_substring (s: str ) -> int : char_map = {} max_len = 0 left = 0 for right in range (len (s)): c = s[right] if c in char_map: left = max (left, char_map[c] + 1 ) char_map[c] = right max_len = max (max_len, right - left + 1 ) return max_len
6.2 盛最多水的容器 原题 ：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例 ：
1 2 3 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水的最大值为 49。
解题思路 ：双指针，每次移动较短的那一边。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class ContainerWithMostWater { public int maxArea (int [] height) { int left = 0 ; int right = height.length - 1 ; int max = 0 ; while (left < right) { int area = Math.min(height[left], height[right]) * (right - left); max = Math.max(max, area); if (height[left] < height[right]) { left++; } else { right--; } } return max; } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 def max_area (height: list [int ] ) -> int : left = 0 right = len (height) - 1 max_area = 0 while left < right: area = min (height[left], height[right]) * (right - left) max_area = max (max_area, area) if height[left] < height[right]: left += 1 else : right -= 1 return max_area
7. 回溯与DFS 7.1 全排列 原题 ：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。
示例 ：
1 2 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解题思路 ：回溯算法，交换法或visited数组标记。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.util.ArrayList;import java.util.List;public class Permutations { public List<List<Integer>> permute (int [] nums) { List<List<Integer>> result = new ArrayList <>(); backtrack(nums, 0 , result); return result; } private void backtrack (int [] nums, int start, List<List<Integer>> result) { if (start == nums.length) { List<Integer> list = new ArrayList <>(); for (int num : nums) list.add(num); result.add(list); return ; } for (int i = start; i < nums.length; i++) { swap(nums, start, i); backtrack(nums, start + 1 , result); swap(nums, start, i); } } private void swap (int [] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 def permute (nums: list [int ] ) -> list [list [int ]]: result = [] def backtrack (start: int ): if start == len (nums): result.append(nums.copy()) return for i in range (start, len (nums)): nums[start], nums[i] = nums[i], nums[start] backtrack(start + 1 ) nums[start], nums[i] = nums[i], nums[start] backtrack(0 ) return result
7.2 组合总和 原题 ：给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。
示例 ：
1 2 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
解题思路 ：回溯，剪枝优化。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class CombinationSum { public List<List<Integer>> combinationSum (int [] candidates, int target) { List<List<Integer>> result = new ArrayList <>(); Arrays.sort(candidates); backtrack(candidates, target, 0 , new ArrayList <>(), result); return result; } private void backtrack (int [] candidates, int target, int start, List<Integer> path, List<List<Integer>> result) { if (target == 0 ) { result.add(new ArrayList <>(path)); return ; } for (int i = start; i < candidates.length; i++) { if (candidates[i] > target) break ; path.add(candidates[i]); backtrack(candidates, target - candidates[i], i, path, result); path.remove(path.size() - 1 ); } } }
Python 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def combination_sum (candidates: list [int ], target: int ) -> list [list [int ]]: result = [] candidates.sort() def backtrack (remain: int , start: int , path: list [int ] ): if remain == 0 : result.append(path.copy()) return for i in range (start, len (candidates)): if candidates[i] > remain: break path.append(candidates[i]) backtrack(remain - candidates[i], i, path) path.pop() backtrack(target, 0 , []) return result
8. 其他经典题目 8.1 进制转换 原题 ：输入一个十六进制的字符串，输出其十进制的表示。
示例 ：
解题思路 ：直接使用语言内置函数，或手动计算每一位。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import java.util.Scanner;public class HexToDecimal { public static void main (String[] args) { Scanner sc = new Scanner (System.in); while (sc.hasNextLine()) { String s = sc.nextLine().trim(); if (s.startsWith("0x" ) || s.startsWith("0X" )) { s = s.substring(2 ); } System.out.println(Integer.parseInt(s, 16 )); } } }
Python 源码 ：
1 2 3 4 5 6 7 if __name__ == "__main__" : import sys for line in sys.stdin: s = line.strip() if s.startswith(('0x' , '0X' )): s = s[2 :] print (int (s, 16 ))
8.2 斐波那契数列 原题 ：写一个函数，输入 n ，求斐波那契数列的第 n 项。
示例 ：
1 2 3 输入：n = 5 输出：5 解释：F(5) = F(4) + F(3) = 3 + 2 = 5
解题思路 ：动态规划，避免递归的重复计算。
Java 源码 ：
1 2 3 4 5 6 7 8 9 10 11 12 public class Fibonacci { public int fib (int n) { if (n <= 1 ) return n; int a = 0 , b = 1 ; for (int i = 2 ; i <= n; i++) { int c = a + b; a = b; b = c; } return b; } }
Python 源码 ：
1 2 3 4 5 6 7 def fib (n: int ) -> int : if n <= 1 : return n a, b = 0 , 1 for _ in range (2 , n + 1 ): a, b = b, a + b return b
基础算法思想 深度优先遍历（DFS） 思路 ：递归，访问顶点v后，继续以深度优先的方式访问其邻节点。
模板 ：
1 2 3 4 5 6 7 8 void dfs (Node node, Set<Node> visited) { if (node == null || visited.contains(node)) return ; visited.add(node); for (Node neighbor : node.neighbors) { dfs(neighbor, visited); } }
广度优先遍历（BFS） 思路 ：画弧，访问顶点v后，继续访问顶点v的所有邻节点，待其访问最后最后一邻节点，按顺序访问首次访问的邻节点的所有邻节点。依次进行。
模板 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void bfs (Node start) { Queue<Node> queue = new LinkedList <>(); Set<Node> visited = new HashSet <>(); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { Node node = queue.poll(); for (Node neighbor : node.neighbors) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } } }
面试技巧 先问清楚 ：确认输入输出格式、边界条件、数据范围思路先行 ：先讲思路，再写代码复杂度分析 ：时间、空间复杂度分析测试用例 ：正常情况、边界情况、异常情况代码规范 ：变量命名清晰，适当注释
