当前位置: 首页> 游戏> 攻略 > 热点新闻事件2023_目前网络最好的挣钱平台_重庆seo教程博客_网站seo搜索

热点新闻事件2023_目前网络最好的挣钱平台_重庆seo教程博客_网站seo搜索

时间:2025/7/11 23:51:40来源:https://blog.csdn.net/2301_79820263/article/details/147464990 浏览次数:0次
热点新闻事件2023_目前网络最好的挣钱平台_重庆seo教程博客_网站seo搜索

题目:

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2
输入:digits = “”
输出:[]

示例 3
输入:digits = “2”
输出:[“a”,“b”,“c”]

提示

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

代码:

(1)蛮力法:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** Note: The returned array must be malloced, assume caller calls free().*/
char** letterCombinations(char* digits, int* returnSize) {char data[8][5] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};*returnSize = 0;int len = strlen(digits);if (len == 0) {return NULL;}// 计算最大可能的组合数int maxCombinations = 1;for (int i = 0; i < len; i++) {if (digits[i] == '7' || digits[i] == '9') {maxCombinations *= 4;} else {maxCombinations *= 3;}}// 动态分配结果数组的内存char **result = (char **)malloc(maxCombinations * sizeof(char *));for (int i = 0; i < maxCombinations; i++) {result[i] = (char *)malloc((len + 1) * sizeof(char));result[i][0] = '\0';}if (len == 1) {char *letters = data[digits[0] - '2'];for (int i = 0; letters[i] != '\0'; i++) {result[*returnSize][0] = letters[i];result[*returnSize][1] = '\0';(*returnSize)++;}} else if (len == 2) {char *letters1 = data[digits[0] - '2'];char *letters2 = data[digits[1] - '2'];for (int i = 0; letters1[i] != '\0'; i++) {for (int j = 0; letters2[j] != '\0'; j++) {result[*returnSize][0] = letters1[i];result[*returnSize][1] = letters2[j];result[*returnSize][2] = '\0';(*returnSize)++;}}} else if (len == 3) {char *letters1 = data[digits[0] - '2'];char *letters2 = data[digits[1] - '2'];char *letters3 = data[digits[2] - '2'];for (int i = 0; letters1[i] != '\0'; i++) {for (int j = 0; letters2[j] != '\0'; j++) {for (int k = 0; letters3[k] != '\0'; k++) {result[*returnSize][0] = letters1[i];result[*returnSize][1] = letters2[j];result[*returnSize][2] = letters3[k];result[*returnSize][3] = '\0';(*returnSize)++;}}}} else if (len == 4) {char *letters1 = data[digits[0] - '2'];char *letters2 = data[digits[1] - '2'];char *letters3 = data[digits[2] - '2'];char *letters4 = data[digits[3] - '2'];for (int i = 0; letters1[i] != '\0'; i++) {for (int j = 0; letters2[j] != '\0'; j++) {for (int k = 0; letters3[k] != '\0'; k++) {for (int m = 0; letters4[m] != '\0'; m++) {result[*returnSize][0] = letters1[i];result[*returnSize][1] = letters2[j];result[*returnSize][2] = letters3[k];result[*returnSize][3] = letters4[m];result[*returnSize][4] = '\0';(*returnSize)++;}}}}}return result;
}

蛮力法做的话,需要有很清晰的逻辑思路,对嵌套循环有较深的了解和掌握。

(2)回溯法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** Note: The returned array must be malloced, assume caller calls free().*/
void backtrack(char* digits, int index, char** data, char* current, char** result, int* returnSize) {if (digits[index] == '\0') {result[*returnSize] = strdup(current);(*returnSize)++;return;}int digit = digits[index] - '2';char* letters = data[digit];for (int i = 0; letters[i] != '\0'; i++) {current[index] = letters[i];backtrack(digits, index + 1, data, current, result, returnSize);}
}char** letterCombinations(char* digits, int* returnSize) {char* data[8] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};*returnSize = 0;int len = strlen(digits);if (len == 0) {return NULL;}int maxCombinations = 1;for (int i = 0; i < len; i++) {if (digits[i] == '7' || digits[i] == '9') {maxCombinations *= 4;} else {maxCombinations *= 3;}}char** result = (char**)malloc(maxCombinations * sizeof(char*));char* current = (char*)malloc((len + 1) * sizeof(char));current[len] = '\0';backtrack(digits, 0, data, current, result, returnSize);free(current);return result;
}

采用回溯算法来生成所有可能的字母组合,这样可以避免嵌套循环过多的问题。

  1. 回溯函数 backtrack:
    当处理完所有数字时,将当前组合复制到结果数组。
    对于每个数字,遍历其对应的字母,递归处理下一个数字。
  2. 主函数 letterCombinations:
    若输入为空,返回 NULL。
    计算可能的组合数量,为结果数组分配内存。
    分配一个临时数组 current 用于存储当前组合。
    调用 backtrack 函数生成组合。
    释放临时数组的内存。
关键字:热点新闻事件2023_目前网络最好的挣钱平台_重庆seo教程博客_网站seo搜索

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: