【Leecode 随笔】C语言版看了不后悔系列持续更新中。。。

🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

一、电话号码的字母组合

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射如下（与电话按键相同）：
2 -> “abc”
3 -> “def”
4 -> “ghi”
5 -> “jkl”
6 -> “mno”
7 -> “pqrs”
8 -> “tuv”
9 -> “wxyz”

示例输入：

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]
输入：“”
输出：[“”]

解题思路：

这是一个典型的回溯问题。我们可以使用递归函数来遍历每个数字对应的字母，并在递归的每一层将当前字母与之前的组合进行拼接。当遍历完所有数字时，将当前的组合添加到结果集中。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  #define MAX_COMBINATIONS 10000 // 预设一个足够大的空间来存储组合  
#define MAX_LENGTH 10 // 输入数字串的最大长度  char* mappings[] = {  "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"  
};  void backtrack(char* digits, char* combination, int index, int len, char** result, int* returnSize) {  if (index == len) {  // 当遍历完所有数字时，将组合添加到结果集中  result[*returnSize] = strdup(combination);  (*returnSize)++;  return;  }  // 遍历当前数字对应的字母  for (int i = 0; mappings[digits[index] - '0'][i] != '\0'; i++) {  combination[index] = mappings[digits[index] - '0'][i];  backtrack(digits, combination, index + 1, len, result, returnSize);  }  
}  char** letterCombinations(char* digits, int* returnSize) {  if (digits == NULL || *digits == '\0') {  *returnSize = 1;  char** result = (char**)malloc(sizeof(char*) * 1);  result[0] = strdup("");  return result;  }  int len = strlen(digits);  char** result = (char**)malloc(sizeof(char*) * MAX_COMBINATIONS);  *returnSize = 0;  char* combination = (char*)malloc(sizeof(char) * (len + 1));  combination[len] = '\0';  backtrack(digits, combination, 0, len, result, returnSize);  free(combination);  return result;  
}  // 测试函数  
void testLetterCombinations() {  char* digits = "23";  int returnSize = 0;  char** result = letterCombinations(digits, &returnSize);  for (int i = 0; i < returnSize; i++) {  printf("%s\n", result[i]);  free(result[i]);  }  free(result);  
}  int main() {  testLetterCombinations();  return 0;  
}

深入剖析：

我们使用一个二维字符数组 mappings 来存储数字到字母的映射关系。
backtrack 函数是递归的核心，它负责遍历每个数字对应的字母，并在递归的每一层拼接组合。
letterCombinations 函数是入口函数，它处理边界情况，并为递归函数准备必要的参数。
注意在递归结束后要释放动态分配的内存，以避免内存泄漏。

二、四数之和

题目描述：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断数组中是否存在四个元素 a、b、c 和 d ，使得 a + b + c + d = target？你可以假设 nums 中的每个元素都不超过 INT_MAX 的绝对值，且 nums 的长度不超过 2000。

示例输入：

输入：nums = [1, 0, -1, 0, -2, 2], target = 0
输出：[[-1, -1, 0, 2], [-2, -1, 1, 2], [-2, 0, 0, 2]]
输入：nums = [], target = 0
输出：[]

解题思路：

这是一个经典的四指针问题。我们可以先对数组进行排序，然后使用四个指针来遍历数组。具体来说，我们可以固定前两个指针，然后使用双指针法来遍历后两个指针。当遍历完所有可能的组合后，即可得到结果。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  // 辅助函数：比较函数，用于qsort排序  
int compare(const void* a, const void* b) {  return (*(int*)a - *(int*)b);  
}  // 辅助函数：检查结果集中是否已经包含当前组合  
int contains(int** result, int* returnSize, int* combination, int combinationSize) {  for (int i = 0; i < *returnSize; i++) {  int match = 1;  for (int j = 0; j < combinationSize; j++) {  if (result[i][j] != combination[j]) {  match = 0;  break;  }  }  if (match) {  return 1;  }  }  return 0;  
}  // 主函数：寻找数组中四个数的和等于目标值的所有组合  
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {  if (numsSize < 4) {  *returnSize = 0;  return NULL;  }  qsort(nums, numsSize, sizeof(int), compare);  int** result = (int**)malloc(sizeof(int*) * numsSize * numsSize * numsSize);  *returnSize = 0;  *returnColumnSizes = (int*)malloc(sizeof(int) * numsSize * numsSize * numsSize);  for (int i = 0; i < numsSize - 3; i++) {  if (i > 0 && nums[i] == nums[i - 1]) {  continue; // 跳过重复元素  }  for (int j = i + 1; j < numsSize - 2; j++) {  if (j > i + 1 && nums[j] == nums[j - 1]) {  continue; // 跳过重复元素  }  int left = j + 1;  int right = numsSize - 1;  while (left < right) {  int sum = nums[i] + nums[j] + nums[left] + nums[right];  if (sum == target) {  int combination[4] = {nums[i], nums[j], nums[left], nums[right]};  if (!contains(result, returnSize, combination, 4)) {  result[*returnSize] = (int*)malloc(sizeof(int) * 4);  result[*returnSize][0] = nums[i];  result[*returnSize][1] = nums[j];  result[*returnSize][2] = nums[left];  result[*returnSize][3] = nums[right];  (*returnColumnSizes)[*returnSize] = 4;  (*returnSize)++;  }  while (left < right && nums[left] == nums[left + 1]) {  left++; // 跳过重复元素  }  while (left < right && nums[right] == nums[right - 1]) {  right--; // 跳过重复元素  }  left++;  right--;  } else if (sum < target) {  left++; // 和太小，增大左指针  } else {  right--; // 和太大，减小右指针  }  }  }  }  // 如果没有找到任何结果，释放内存并返回空  if (*returnSize == 0) {  free(result);  free(*returnColumnSizes);  result = NULL;  *returnColumnSizes = NULL;  }  return result;  
}  // 测试函数  
void testFourSum() {  int nums[] = {1, 0, -1, 0, -2, 2};  int numsSize = sizeof(nums) / sizeof(nums[0]);  int target = 0;  int returnSize = 0;  int* returnColumnSizes = NULL;  int** result = fourSum(nums, numsSize, target, &returnSize, &returnColumnSizes);  for (int i = 0; i < returnSize; i++) {  printf("[");  for (int j = 0; j < returnColumnSizes[i]; j++) {  printf("%d", result[i][j]);  if (j < returnColumnSizes[i] - 1) {  printf(", ");  }  }  printf("]\n");  free(result[i]); // 释放每个结果数组的内存  }  free(result); // 释放结果数组指针的内存  free(returnColumnSizes); // 释放列大小数组的内存  
}  int main() {  testFourSum();  return 0;  
}

深入剖析：

排序：首先对数组进行排序，这是使用双指针法的前提。
四指针遍历：通过四个指针的嵌套循环来遍历所有可能的四元组。
去重：在固定指针和内层双指针法中，都要注意跳过重复的元素，以避免结果集中出现重复。
内存管理：注意在函数结束时释放动态分配的内存。

三、不同的二叉树数量

题目描述：

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种不同的结构。

示例输入：

输入：3
输出：5
输入：1
输出：1

解题思路：

这是一个动态规划问题。对于给定的 n，我们可以选择 1 到 n 中的任何数字作为根节点。然后，对于根节点左边的数字（比根节点小），它们可以形成一棵左子树，右边的数字（比根节点大）可以形成一棵右子树。左子树和右子树本身也是二叉搜索树，因此我们可以递归地求解这个问题。
为了避免重复计算，我们可以使用动态规划来存储中间结果。定义一个数组 dp，其中 dp[i] 表示以 1 … i 为节点组成的二叉搜索树的数量。
动态规划状态转移方程：
dp[n] = sum(dp[i-1] * dp[n-i]) for i in [1, n]
特别地，当 n=0 或 n=1 时，dp[n] = 1，因为只有一个节点（或者没有节点）时，只有一种可能的树。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  int numTrees(int n) {  int* dp = (int*)malloc((n + 1) * sizeof(int));  dp[0] = 1;  dp[1] = 1;  for (int i = 2; i <= n; i++) {  dp[i] = 0;  for (int j = 1; j <= i; j++) {  dp[i] += dp[j - 1] * dp[i - j];  }  }  int result = dp[n];  free(dp);  return result;  
}  // 测试函数  
void testNumTrees() {  int n = 3;  printf("Number of unique BSTs for n=%d: %d\n", n, numTrees(n));  
}  int main() {  testNumTrees();  return 0;  
}

深入剖析：

动态规划数组：使用 dp 数组来存储以 1 … i 为节点组成的二叉搜索树的数量。
状态转移：通过遍历所有可能的根节点，并计算左子树和右子树的数量，来得到以当前数字为节点数量的二叉搜索树的数量。
边界条件：当 n=0 或 n=1 时，只有一种可能的树。
内存管理：在函数结束时释放动态分配的内存。

---

✨ 这就是今天要分享给大家的全部内容了，我们下期再见！😊
🏠 我在CSDN等你哦！我的主页😍