每周一道算法题(十三)
2017-06-10 本文已影响651人
CrazySteven
本周的算法题难度级别“Medium”,用了我三天工作之余的时间，总算过了，效率较低
题目:给你一串数字，在9宫格键盘上输入这串数，需要求所有可能得到的字符串
分析:题目其实就是手机的九宫格输入法，把按键的字母进行排列组合即可。明确了题目，下面就来实现本道题
- 确定行数和列数
我们可以发现，列数其实就是你输入数字的个数，行数就是数字代表字母个数的乘积
- 确字每行每列显示的字母
我发现的规律是：第一列的字母是你输入的第一个数字所代表的字母的循环，第二列是第二个数字对应字母的循环。。。最后一列循环的次数是最后一列字母的个数/最后一列字母的个数，倒数第二列的循环次数是（倒数第二列字母的个数 ＊ 倒数第一列字母的个数）/倒数第二列字母的个数，倒数第三列的循环次数是（倒数第三列字母的个数 ＊ 倒数第二列字母的个数 ＊ 倒数第一列字母的个数）/倒数第三列字母的个数。。。
通过以上的两个规则我们就能把这道题搞定了，由于这两个规则不好理解，我们先举个例子来理解下这两条规则，假设我们输入了2､3､4三个数字，则排列组合如下图：
通过第一条规则来确字行数和列数：2代表a/b/c三个字母,3代表d/e/f三个字母,4代表g/h/i三个字母,则行数为3＊3＊3=27行，输入了三个数字，所以列数为3
通过第二条规则来确定字母：我们先看最后一列，循环次数是3/3＝1,即只循环一次，则直接g-h-i的循环填序即可，看倒数第二列，循环次数是(3*3)/3=3,循环3次，则按照d-d-d,e-e-e,f-f-f循环填序即可，倒数第三列的循环次数是(3*3*3)/3=9,循环9次，即9个a，9个b，9个c的循环填序即可。思路上实现以后，我们就用代码来实现：
char** letterCombinations(char* digits, int* returnSize) {
//列数就是输入数字的个数
int column = (int)strlen(digits);
//str用于存储输入数字所对应的字母
char **str = malloc(column * sizeof(char *));
//如果输入的个数为0
if (column == 0) {
*returnSize = 0;
return str;
}
//通过计算每个数字所对应字母的个数的乘积来求出行数
int row = 1;
for (int i = 0;i < column; i++) {
int num = (int)(digits[i] - '0');
if (num == 0) str[i] = " ";
else if (num == 1) str[i] = "*";
else if (num == 2) str[i] = "abc";
else if (num == 3) str[i] = "def";
else if (num == 4) str[i] = "ghi";
else if (num == 5) str[i] = "jkl";
else if (num == 6) str[i] = "mno";
else if (num == 7) str[i] = "pqrs";
else if (num == 8) str[i] = "tuv";
else if (num == 9) str[i] = "wxyz";
row *= (int)strlen(str[i]);
}
//result为结果
char **result = malloc(row * sizeof(char *));
for (int i = 0; i < row; i++)
result[i] = malloc(column+1);
//为result填充字母
for (int c = column - 1; c >= 0; c--) {
//确定循环次数temp
int temp = c,sum = 1;
while (temp <= column - 1) {
sum *= strlen(str[temp]);
temp++;
}
temp = sum / strlen(str[c]);
//按列填充字母
int r = 0;
while (r < row) {
result[r][c] = str[c][r/temp%strlen(str[c])];
r++;
}
//填充结束符'\0'
if (c == 0) {
int r = 0;
while (r < row) {
result[r][column] = '\0';
r++;
}
}
}
//返回结果
*returnSize = row;
return result;
}
这道题用了一天多的空闲时间就总结出了规律，思路一直没错（应该不是最优思路），但代码实现却花了我近两天的时间，不得不叹息想法和做法之间还是有一些距离，代码实现中主要的问题是内存问题，着实的被strlen这个函数坑了好久，又被'\0'这个坑坑了半天，也使得我对指针、c语言内存机制等方面又有了新的认识，看来光有想法还不够，程序猿就要多敲代码，将想法落地才能更好的成长，做出来了也是有成就感的。。。
