leadcode的Hot100系列--17. 电话号码的字母组合--回溯的另一种想法的应用
提交leetcode的时候遇到了问题,一直说访问越界,但仔仔细细检查n多遍,就是检查不出来。
因为我用到了count全局变量,自加一来表明当前数组访问的位置,
后来突然想到,是不是在leetcode在运行测试用例的时候,是连续测试的,用的同一个上下文,这样的话,就没有对这个全局变量清零……
果然,清零之后就可以了……已经3:47了,这里先上代码,明天再详细说吧……
今天更新一下这道题的思路。
可以先参考一下之前的两篇文章,循序渐进,好理解一些:
leadcode的hot100系列--78. 子集--位运算
leadcode的hot100系列--78. 子集--回溯
在 子集--回溯
的文章里面,介绍了一下数字的排列组合,用01来表示对应的数字是否存在。
如果我们还是按照这个思路,但是换一个想法呢?
0、1是不是本身就可以代表着字符串?
对应排列出来的000\001\010 ... 是不是就是相当于:
我需要一个数字组合,组合需要三位数,每一位的数字要么是0,要么是1。
这么一想,是不是就与题目一致了:
我需要一个字母组合,组合的位数就是输入的字符串长度,每一位的字母是对应的几个字母中的某一个。
对,就是这么想的,比如,输入“89”,就说明,字母组合的位数是两位,第一位字母是'tuv'里面的一个,第二位字母是'wxyz'里面的一个。
这里再看下之前上一篇中回溯的代码:
void backtrack (int t) { if (t == level) show(); else for (int i=0;i<=1;i++) { y[t]=i; backtrack(t+1); } }
重点来了!!!!
- 第三行的level表示层数,也就是遍历的深度,也就是组合所需要的位数,当需要两位字母的时候,就只要两层。
- 第六行的for循环,表示了每一层的选项,之前因为只需要表示存在和不存在,所以只需要用0和1就够了,但在这里,是由数字对应的字符串的某一个,例如如果数字是8,则对应的选项就是't'和'u'和'v'。
所以,当输入为“89”的时候,就可以生成这样一种树:
控制了树的层数和树的分支(分支就是可选项)之后,就可以完成所有组合。
char table[][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; char level = 0; char *p[8]; // 指向数字对应的字符串,例如,当输入数字为"89"时,p[0]为"tuv",p[1]为"wxyz"。 char len[8]; // 对应上面p存储的字符串的长度,例如,当输入数字为"89"是,len[0]=3,len[1]=4。 char **out; //二维数组,是最终输出 int count = 0; // 用来记录当前已经生成了几个组合,对应着out数组的行坐标 char y[8] = {0}; // 记录每一次的组合结果 void backtrack(int level_now) { if (level_now == level) { memcpy(out[count], y, level); // 把这次组合结果拷贝到out数组中。这里为什么需要用一个y数组来记录组合结果,然后拷贝到out中呢?大家可以自己想一想 count ++; // 完成一个字符串 return; } for (int i=0; i<len[level_now]; i++) { y[level_now] = p[level_now][i]; backtrack(level_now+1); } return; } char ** lettercombinations(char * digits, int* returnsize){ level = strlen(digits); // 遍历的层数 *returnsize = 0; if (0 == level) return null; *returnsize = 1; for(int i=0; i<level; i++) { p[i] = table[digits[i]-'0']; // 对p数组进行赋值 len[i] = strlen(p[i]); if (len[i] == 0) { *returnsize = 0; return null; } *returnsize *= len[i]; // 计算总共有多少个组合 } out = (char **)calloc(*returnsize, sizeof(char *)); // 先分配行指针 if (null == out) return null; for (int i=0; i<*returnsize; i++) { out[i] = (char *)calloc(1, sizeof(char) * (level+1)); // 再分配每个行指针的内容,因为字符串后面需要一个结束符'\0',所以这里需要level+1 if (null == out[i]) return null; } backtrack(0); count = 0; // 这里很重要!很重要!!很重要!!! return out; }
上一篇: Go语言设计模式之函数式选项模式
下一篇: XPath简介、功能及使用方法