当前位置: 首页 > news >正文

日志|电话号码的字母组合|子集|回溯

局部截取_20251009_214710

解题思路:

回溯三问:

1.当前操作?枚举数组path[i]要填入的字母
2.子问题?构造字符串>= i 的部分
3.下一个子问题?构造>= i+1 的部分

对于本题

1.当前操作:枚举放入path当前i的字母 例如第2个数字对应的a b c
2.子问题:下一位置要放的字母的枚举 例如第3个数字对应的 d e f
3.下一个子问题:下一位置的下一位置的要放的字母的枚举

总结

例如输入[23]
先dfs(0),
本层 a 有 dfs(1),本层层有def,d有dfs(2)e有dfs(2)f有dfs(2)。又回到最上层dfs(0)
本层 b 有 dfs(1),本层层有def,d有dfs(2)e有dfs(2)f有dfs(2)。又回到最上层dfs(0)
本层 c 有 dfs(1),本层层有def,d有dfs(2)e有dfs(2)f有dfs(2)。又回到最上层dfs(0)
结束返回ans

点击查看代码
class Solution {private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {int n = digits.length();if (n == 0) {return List.of();}List<String> ans = new ArrayList<>();char[] path = new char[n];dfs(0, ans, path, digits.toCharArray());return ans;}private void dfs(int i, List<String> ans, char[] path, char[] digits) {if (i == digits.length) {ans.add(new String(path));return;}String letters = MAPPING[digits[i] - '0'];for (char c : letters.toCharArray()) {path[i] = c;dfs(i + 1, ans, path, digits);}}}

局部截取_20251009_230833

点击查看代码
class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> ans = new ArrayList<>();List<Integer> path =  ArrayList<>();dfs(0, nums, path, ans);return ans;}private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> ans) {ans.add(new ArrayList<>(path)); // 复制 pathfor (int j = i; j < nums.length; j++) { // 枚举选择的数字path.add(nums[j]);dfs(j + 1, nums, path, ans);path.removeLast(); // path.remove(path.size() - 1);}}
}        
http://www.hskmm.com/?act=detail&tid=27658

相关文章:

  • Docker实用篇(初识Docker,Docker的基本操作,Dockerfile自定义镜像,Docker-Compose,Docker镜像仓库) - a
  • ROIR 2023
  • Rust 的验证码图像识别系统设计与实现
  • 【题解】P12992 [GCJ 2022 #1C] Intranets
  • ysyx:pa3.1批处理系统
  • C 语言的验证码图像识别系统实现
  • Nginx典型流控配置示例
  • 基于 C 语言的验证码图像识别系统实现
  • oppoR9m刷Linux系统: 引导知识
  • 操作系统知识点
  • JAVA: Mybatis添加xml执行多行更新语句时报错
  • 安装Docker(CentOS安装Docker,CentOS7安装DockerCompose,Docker镜像仓库) - a
  • 上代码演示下Profile-Guided Optimization (PGO)
  • 所有文档每页的第一行居中对齐
  • 109
  • 一个有趣的网站,可以给自己生成一个奖牌:aitokenawards.com
  • 20232416 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • day008
  • lzr 的区间(interval)
  • IRB-120机械臂socket通信接受上位机指令运行程序段
  • 1.1.1.1 金融市场的定义与功能
  • 使用c#操作elasticsearch8
  • CF45C Dancing Lessons 题解
  • APUE学习笔记之文件IO(三) - Invinc
  • note
  • 供应链优化技术助力应对疫情挑战
  • 搜索关键词 - 呓语
  • 阅读《构建之法》产生的问题
  • 每日反思
  • 每日反思(2025.10.09)