国外网站做网上生意哪个好,贵阳网站开发推荐,怎么做教育培训网站,wordpress全ajax主题方法1 if-else方法 if-else方法的思路及其简单粗暴#xff0c;如下图所示#xff0c;以数字234为例#xff0c;数字2所对应的字母是abc#xff0c;数字3所对应的是def#xff0c;数字4所对应的是ghi#xff0c;最后所产生的结果就类似于我们中学所学过的树状图一样…方法1 if-else方法 if-else方法的思路及其简单粗暴如下图所示以数字234为例数字2所对应的字母是abc数字3所对应的是def数字4所对应的是ghi最后所产生的结果就类似于我们中学所学过的树状图一样从左到右的一组一组生成结果首先取出数字2的第一个索引对应的a然后紧接着添加数字3对应的第一个索引的字母d然后再添加数字4所对应的ghi分别组成adg、adh、adi然后一直进行排列组合直到把所有的结果都列举完那么就程序就执行完了。 python完整代码
class Solution:def letterCombinations(self, digits):# 获取输入数字串的长度n len(digits)result [] # 用于存储最终的字母组合结果if n 0:return result # 如果输入为空字符串则直接返回空列表for i in range(n):self.AddString(result, digits[i])return resultdef AddString(self, result, t): # 定义一个添加字符串的函数n len(result)letters if t 2:letters abcelif t 3:letters defelif t 4:letters ghielif t 5:letters jklelif t 6:letters mnoelif t 7:letters pqrselif t 8:letters tuvelif t 9:letters wxyzif n 0:result.extend(list(letters)) # 如果结果集为空直接添加第一个数字对应的字母else:temp_result []for i in range(n): # i表示第一个数字所对应的字母的位置for letter in letters:# 将当前结果集中的每个组合与新的字母组合得到新的结果集temp_result.append(result[i] letter)result[:] temp_result # 用新的结果集替换原有结果集if __name__ __main__:solution Solution()combinations solution.letterCombinations(234)print(combinations)
c完整代码
#includeiostream
#includevectorusing namespace std;class Solution{
public:vectorstring letterCombinations(string digits){int n digits.length(); //获取输入数字串的长度vectorstring result; //用于存储最终的字母组合结果if(n 0){return result;}for(int i0;in;i){AddString(result, digits[i]); // 调用添加字母函数}return result;}
private:void AddString(vectorstring result, char digit){int n result.size();string letters ;if (digit 2){letters abc;} else if(digit 3){letters def;} else if(digit 4){letters ghi;} else if(digit 5) {letters jkl;} else if(digit 6){letters mno;} else if(digit 7){letters pqrs;} else if(digit 8){letters tuv;} else if(digit 9){letters wxyz;}if (n 0){for(char letter : letters){result.push_back(string(1, letter));// 如果结果集为空直接添加第一个数字对应的字母}} else{vectorstring temp_result;for(int i 0;i n; i){for(char letter : letters){// 将当前结果集中的每个组合与新的字母组合得到新的结果集temp_result.push_back(result[i] letter);}}result temp_result; // 用新的结果集替换原有结果集}}
};int main(){Solution solution;vectorstring combinations solution.letterCombinations(234);for(const auto combination : combinations){cout combination endl;}return 0;
}
java完整代码
import java.util.List;
import java.util.ArrayList;
public class LetterCombinations {public ListString letterCombinations(String digits) {// 获取输入数字串的长度int n digits.length();// 用于存储最终的字母组合结果ListString list new ArrayList();// 如果输入为空字符串则直接返回空列表if (n 0) {return list;}// 遍历每个数字字符for (int i 0; i n; i) {// 调用 StringAdd 函数处理每个数字对应的字母StringAdd(list, digits.charAt(i));}return list;}// 定义一个添加字符串的函数public void StringAdd(ListString list, char t) {// 获取当前结果集的长度int n list.size();if(t 2){ // 处理数字 2 对应的字母组合if(n0){list.add(a);list.add(b);list.add(c);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 a, b, c得到新的结果集list.add(list.get(i)a);list.add(list.get(i)b);list.add(list.get(i)c);}for(int i0;in;i){list.remove(0);}}// 3}else if(t 3){if(n0){list.add(d);list.add(e);list.add(f);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 d, e, f得到新的结果集list.add(list.get(i)d);list.add(list.get(i)e);list.add(list.get(i)f);}for(int i0;in;i){list.remove(0);}}// 4}else if(t 4){if(n0){list.add(g);list.add(h);list.add(i);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 g, h, i得到新的结果集list.add(list.get(i)g);list.add(list.get(i)h);list.add(list.get(i)i);}for(int i0;in;i){list.remove(0);}}// 5}else if(t 5){if(n0){list.add(j);list.add(k);list.add(l);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 j, k, l得到新的结果list.add(list.get(i)j);list.add(list.get(i)k);list.add(list.get(i)l);}for(int i0;in;i){list.remove(0);}}// 6}else if(t 6){if(n0){list.add(m);list.add(n);list.add(o);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 m, n, o得到新的结果list.add(list.get(i)m);list.add(list.get(i)n);list.add(list.get(i)o);}for(int i0;in;i){list.remove(0);}}// 7}else if(t 7){if(n0){list.add(p);list.add(q);list.add(r);list.add(s);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 p, q, r, s得到新的结果list.add(list.get(i)p);list.add(list.get(i)q);list.add(list.get(i)r);list.add(list.get(i)s);}for(int i0;in;i){list.remove(0);}}// 8}else if(t 8){if(n0){list.add(t);list.add(u);list.add(v);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 t, u, v得到新的结果list.add(list.get(i)t);list.add(list.get(i)u);list.add(list.get(i)v);}for(int i0;in;i){list.remove(0);}}// 9}else if(t 9){if(n0){list.add(w);list.add(x);list.add(y);list.add(z);}else{for(int i0;in;i){// 遍历当前结果集为每个组合添加 w, x, y, z得到新的结果list.add(list.get(i)w);list.add(list.get(i)x);list.add(list.get(i)y);list.add(list.get(i)z);}for(int i0;in;i){list.remove(0);}}}}public static void main(String[] args){LetterCombinations solution new LetterCombinations();ListString combinations solution.letterCombinations(234);System.out.println(combinations);}
}方法2 回溯法 上面我们讨论了通过列举的方法生成结果但是发现程序写起来实在是太长了而且看着很low那么此时我们就可以把数字组合里面每一个数字所对应的字母组合通过一个篮子哈希表存起来要用哪个就拿哪一个紧接着再通过回溯的方法进行解决以下是chatgpt所回答的回溯算法 回溯算法Backtracking是一种通过尝试所有可能的候选解并在找到可行解之前放弃部分或全部解空间的策略。在问题的解空间中通过深度优先搜索一步一步地探索各个可能的解当发现当前的部分解不能满足问题的约束条件时就放弃该部分解回溯到上一步继续搜索其他可能的解。 回溯算法通常采用递归的方式实现每一层递归代表问题的一个阶段通过递归的深入逐步构建出问题的解。在搜索过程中如果当前解不满足问题的条件则回溯到上一步尝试其他可能的选择。 典型的回溯问题包括组合问题、排列问题、子集问题等。回溯算法通常用于解决组合优化问题其中问题的解是某种组合的集合而且问题通常可以分解为多个子问题通过递归地解决子问题来构建整体的解。 关键特点 状态空间树 回溯算法可以通过状态空间树的形式进行表示每个节点代表问题的一个阶段树的每一层对应算法的一个递归调用。深度优先搜索 回溯算法采用深度优先搜索的策略即一条路走到底如果发现当前路径不能满足问题的条件就回溯到上一步。剪枝 在搜索的过程中可以通过剪枝来减少搜索空间提高效率。当发现当前部分解无法满足问题的条件时可以提前结束搜索。 经典的回溯问题包括八皇后问题、0-1背包问题、图的着色问题等。回溯算法的复杂度通常比较高因此在设计时需要注意优化搜索空间以提高效率。 但是本题不存在不可行的解所以通过穷举的方法就可以实现。该方法的思路和上述的方法基本上是一致的。 python完整代码
class Solution:def letterCombinations(self, digits):# 如果输入为空则直接返回空列表if not digits:return list()# 定义电话号码到字母的映射关系phoneMap {2: abc,3: def,4: ghi,5: jkl,6: mno,7: pqrs,8: tuv,9: wxyz,}def backtrack(index):# 当前组合字符串长度等于输入数字串长度时将其加入结果集if index len(digits):combinations.append(.join(combination)) # 获取当前数字对应的字母集合else:digit digits[index] # 将当前字母加入组合字符串递归调用下一层for letter in phoneMap[digit]:combination.append(letter)backtrack(index 1)# pop()函数用于移除列表中的一个元素(默认最后一个元素)并且返回该元素的值combination.pop() # 当combinations里面存有adg紧接着执行for letter in phoneMap[digit]:其中digit4combination list() # 初始化组合列表和当前组合字符串combinations list()backtrack(0) # 初始调用回溯函数return combinationsif __name__ __main__:# 创建 Solution 对象solution Solution()# 调用 letterCombinations 函数并输出结果combinations solution.letterCombinations(234)print(combinations)
class Solution:def letterCombinations(self, digits):# 如果输入为空则直接返回空列表if not digits:return list()# 定义电话号码到字母的映射关系phoneMap {2: abc,3: def,4: ghi,5: jkl,6: mno,7: pqrs,8: tuv,9: wxyz,}def backtrack(index):# 当前组合字符串长度等于输入数字串长度时将其加入结果集if index len(digits):combinations.append(.join(combination)) # 获取当前数字对应的字母集合else:digit digits[index] # 将当前字母加入组合字符串递归调用下一层for letter in phoneMap[digit]:combination.append(letter)backtrack(index 1)# pop()函数用于移除列表中的一个元素(默认最后一个元素)并且返回该元素的值combination.pop() # 当combinations里面存有adg紧接着执行for letter in phoneMap[digit]:其中digit4combination list() # 初始化组合列表和当前组合字符串combinations list()backtrack(0) # 初始调用回溯函数return combinationsif __name__ __main__:# 创建 Solution 对象solution Solution()# 调用 letterCombinations 函数并输出结果combinations solution.letterCombinations(234)print(combinations)
c完整代码
#includeiostream
#includevector
#includeunordered_mapusing namespace std;class Solution{
public:vectorstring letterCombination(string digits){unordered_mapchar, string phoneMap { // 定义数字对应的字母映射关系{2, abc},{3, def},{4, ghi},{5, jkl},{6, mno},{7, pqrs},{8, tuv},{9, wxyz}};// 处理特殊情况如果输入为空字符串则直接返回空列表if(digits.empty()){return vectorstring ();}// 用于存储最终的字母组合结果vectorstring result;// 回溯函数参数分别为当前数字索引和当前已形成的组合字符串backtrack(digits,0,,phoneMap,result); //可以试试index等于1是什么结果就能明白该参数具体指的是什么return result;}
private:// index --- 数字所对应字母的索引void backtrack(const string digits, int index, const string path,const unordered_mapchar, string phoneMap, vectorstring result){// 如果当前组合字符串的长度等于输入数字串的长度将其加入结果集if(index digits.length()){result.push_back(path);return;}// 获取当前数字对应的字母集合char currentDigit digits[index];const string letters phoneMap.at(currentDigit);// 遍历当前数字对应的字母集合进行递归回溯for(char letter : letters){// 将当前字母加入组合字符串递归调用下一层backtrack(digits, index 1, path letter, phoneMap, result);}}
};int main(){// 创建 Solution 对象Solution solution;// 调用 letterCombinations 函数并输出结果vectorstring combinations solution.letterCombination(234);for(const string combination : combinations){cout combination endl;}return 0;
}
java完整代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class letterCombinations_1 {public ListString letterCombinations(String digits) {MapCharacter, String phoneMap new HashMap(); // 定义数字对应的字母映射关系phoneMap.put(2, abc);phoneMap.put(3, def);phoneMap.put(4, ghi);phoneMap.put(5, jkl);phoneMap.put(6, mno);phoneMap.put(7, pqrs);phoneMap.put(8, tuv);phoneMap.put(9, wxyz);// 处理特殊情况如果输入为空字符串则直接返回空列表if (digits null || digits.isEmpty()) {return new ArrayList();}// 用于存储最终的字母组合结果ListString result new ArrayList();// 回溯函数参数分别为当前数字索引和当前已形成的组合字符串backtrack(digits, 0, , phoneMap, result);return result;}private void backtrack(String digits, int index, String path,MapCharacter, String phoneMap, ListString result) {// 如果当前组合字符串的长度等于输入数字串的长度将其加入结果集if (index digits.length()) {result.add(path);return;}// 获取当前数字对应的字母集合char currentDigit digits.charAt(index);String letters phoneMap.get(currentDigit);// 遍历当前数字对应的字母集合进行递归回溯for (char letter : letters.toCharArray()) {// 将当前字母加入组合字符串递归调用下一层backtrack(digits, index 1, path letter, phoneMap, result);}}public static void main(String[] args) {// 创建 Solution 对象letterCombinations_1 solution new letterCombinations_1();// 调用 letterCombinations 函数并输出结果ListString combinations solution.letterCombinations(234);for (String combination : combinations) {System.out.println(combination);}}
}
