本文共 6358 字，大约阅读时间需要 21 分钟。
本文将介绍几种常见算法问题及其实现方法，主要采用深度优先搜索（DFS）和广度优先搜索（BFS）解决。
电话号码全排列问题是将电话键盘上的数字组合成所有可能的号码序列。典型的电话键盘布局如下：
实现方法是使用DFS，从根节点开始逐层探索所有可能的组合路径。每次选择一个数字，然后递归处理其子节点，直到所有数字都被使用。通过回溯的方式删除当前路径的最后一个数字，以避免重复计算。
import java.util.ArrayList;import java.util.List;public class 电话号码全排列问题复现 { public List letterCombinations(String digits) { List result = new ArrayList<>(); if (digits.length() == 0) return result; Map map = new HashMap<>(); map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz"); dfs(result, map, digits, 0, new StringBuilder()); return result; } private void dfs(List result, Map map, String digits, int index, StringBuilder sb) { if (index == digits.length()) { result.add(sb.toString()); return; } char current = digits.charAt(index); String numbers = map.get(current); for (int i = 0; i < numbers.length(); i++) { sb.append(numbers.charAt(i)); dfs(result, map, digits, index + 1, sb); sb.deleteCharAt(sb.length() - 1); } }} 给定一组数字，生成所有可能的排列，确保每个数字只使用一次。可以使用DFS来实现，通过一个visited数组记录已使用的索引位置，避免重复。
import java.util.ArrayList;import java.util.List;public class 全排列问题没有重复 { @Test public void test() { List > permute = permute(new int[]{1, 2, 3}); for (List p : permute) { for (int num : p) { System.out.print(num + " "); } System.out.println(); } } public List > permute(int[] nums) { List > result = new ArrayList<>(); if (nums.length == 0) return result; int[] visited = new boolean[nums.length]; List path = new ArrayList<>(); dfs(result, path, 0, nums, visited); return result; } private void dfs(List > result, List path, int index, int[] nums, boolean[] visited) { if (index == nums.length) { result.add(new ArrayList<>(path)); } else { for (int i = 0; i < nums.length; i++) { if (!visited[i]) { visited[i] = true; path.add(nums[i]); dfs(result, path, index + 1, nums, visited); path.remove(path.size() - 1); visited[i] = false; } } } }}
生成n对括号的所有可能组合，可以使用递归DFS方法，确保每次递归选择左括号或右括号，但避免不平衡的情况。
import java.util.ArrayList;import java.util.List;public class 括号的生成 { public List generateParenthesis(int n) { List result = new ArrayList<>(); if (n == 0) return result; StringBuilder sb = new StringBuilder(); dfs(result, sb, 0, 0, n); return result; } private void dfs(List result, StringBuilder cur, int left, int right, int max) { if (cur.length() == max * 2) { result.add(cur.toString()); return; } if (left < max) { cur.append('('); dfs(result, cur, left + 1, right, max); cur.deleteCharAt(cur.length() - 1); } if (right < left) { cur.append(')'); dfs(result, cur, left, right + 1, max); cur.deleteCharAt(cur.length() - 1); } }} 给定一个字符串，恢复出可能的IP地址。需要注意每个段的取值范围（0-255），并确保每个段都有效。
public class 复原IP地址93 { static final int SEG_COUNT = 4; int[] segments = new int[SEG_COUNT]; public List restoreIpAddresses(String s) { List ans = new ArrayList<>(); dfs(ans, s, 0, 0); return ans; } private void dfs(List ans, String s, int seg_number, int index) { if (seg_number == SEG_COUNT) { if (index == s.length()) { StringBuffer ipAddr = new StringBuffer(); for (int i = 0; i < SEG_COUNT; ++i) { ipAddr.append(segments[i]); if (i != SEG_COUNT - 1) { ipAddr.append('.'); } } ans.add(ipAddr.toString()); } return; } if (index == s.length()) { return; } if (s.charAt(index) == '0') { segments[seg_number] = 0; dfs(ans, s, seg_number + 1, index + 1); } for (int segEnd = index; segEnd < s.length(); segEnd++) { int addr = addr * 10 + (s.charAt(segEnd) - '0'); if (addr > 0 && addr <= 255) { segments[seg_number] = addr; dfs(ans, s, seg_number + 1, segEnd + 1); } else { break; } } }} 给定二叉树，计算从根节点到叶子节点的路径和是否等于目标值。可以采用两种方法：递归DFS和广度优先搜索。
public class 路径和112 { public 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 boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null) { return targetSum == root.val; } return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } public boolean hasPathSum2(TreeNode root, int targetSum) { if (root == null) return false; Queue queue = new LinkedList<>(); queue.offer(root); Queue queueVal = new LinkedList<>(); queueVal.offer(root.val); while (!queue.isEmpty()) { TreeNode now = queue.poll(); int temp = queueVal.poll(); if (now.left == null && now.right == null) { if (temp == targetSum) { return true; } } if (now.left != null) { queue.offer(now.left); queueVal.offer(now.left.val + temp); } if (now.right != null) { queue.offer(now.right); queueVal.offer(now.right.val + temp); } } return false; }} 转载地址：http://hwjh.baihongyu.com/