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

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

题目一：最长回文子串

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例输入与输出：

输入：s = “babad”
输出：“bab” 或 “aba”
输入：s = “cbbd”
输出：“bb”

题目分析：

回文串是指正读和反读都相同的字符串。解决这个问题的关键在于如何高效地找到最长的回文子串。暴力解法的时间复杂度为O(n^3)，显然不可取。我们可以考虑使用动态规划或中心扩展法来优化。

解题思路：

动态规划：定义一个二维数组dp，其中dp[i][j]表示字符串s从索引i到j的子串是否为回文。通过填充这个数组，我们可以找到最长的回文子串。
中心扩展法：遍历字符串中的每个字符和每对相邻字符作为回文中心，然后向外扩展以找到最长的回文子串。
这里我们选择中心扩展法，因为它的实现更简洁且时间复杂度为O(n^2)，适合本题的要求。

示例代码：

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  char* longestPalindrome(char* s) {  int len = strlen(s);  if (len < 2) return s;  int start = 0, maxLen = 1;  for (int i = 0; i < len; i++) {  int len1 = expandAroundCenter(s, i, i); // 奇数长度回文中心  int len2 = expandAroundCenter(s, i, i + 1); // 偶数长度回文中心  int len = len1 > len2 ? len1 : len2;  if (len > maxLen) {  start = i - (len - 1) / 2;  maxLen = len;  }  }  char* result = (char*)malloc((maxLen + 1) * sizeof(char));  strncpy(result, s + start, maxLen);  result[maxLen] = '\0';  return result;  
}  int expandAroundCenter(char* s, int left, int right) {  while (left >= 0 && right < strlen(s) && s[left] == s[right]) {  left--;  right++;  }  return right - left - 1;  
}  int main() {  char s1[] = "babad";  char* result1 = longestPalindrome(s1);  printf("Longest palindrome in \"%s\" is \"%s\"\n", s1, result1);  free(result1);  char s2[] = "cbbd";  char* result2 = longestPalindrome(s2);  printf("Longest palindrome in \"%s\" is \"%s\"\n", s2, result2);  free(result2);  return 0;  
}

深入剖析：

中心扩展法的核心思想是以每个字符或每对相邻字符为中心，向外扩展以找到最长的回文子串。这种方法避免了不必要的比较，从而提高了效率。

题目二：合并K个有序链表

题目描述：

给定一个链表数组，每个链表都已经按升序排列。合并所有链表，并返回合并后的有序链表。

示例输入与输出：

输入：[[1,4,5],[1,3,4],[2,6]]
输出：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
输入：[]
输出：[]

题目分析：

这个问题可以通过逐个合并链表来解决，但效率较低。更优的方法是使用最小堆（优先队列）来维护当前所有链表中的最小元素，从而依次取出最小元素构建合并后的链表。

解题思路：

创建一个最小堆，并将所有链表的头节点加入堆中。
重复以下步骤，直到堆为空：
从堆中取出最小元素作为当前节点。
如果当前节点的下一个节点存在，则将其加入堆中。
将当前节点添加到合并后的链表中。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  typedef struct ListNode {  int val;  struct ListNode* next;  
} ListNode;  // 最小堆节点结构定义  
typedef struct MinHeapNode {  ListNode* node;  struct MinHeapNode* left;  struct MinHeapNode* right;  struct MinHeapNode* parent;  
} MinHeapNode;  // 最小堆结构定义  
typedef struct MinHeap {  MinHeapNode** array;  int size;  int capacity;  
} MinHeap;  // 辅助函数：比较两个节点值的大小  
int compare(ListNode* a, ListNode* b) {  return (a->val > b->val) - (a->val < b->val);  
}  // 创建最小堆  
MinHeap* createMinHeap(int size) {  MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));  minHeap->capacity = size;  minHeap->size = 0;  minHeap->array = (MinHeapNode**)malloc(size * sizeof(MinHeapNode*));  return minHeap;  
}  // 释放最小堆内存  
void freeMinHeap(MinHeap* minHeap) {  for (int i = 0; i < minHeap->size; i++) {  free(minHeap->array[i]);  }  free(minHeap->array);  free(minHeap);  
}  // 插入节点到最小堆  
void insertMinHeap(MinHeap* minHeap, ListNode* node) {  if (minHeap->size == minHeap->capacity) {  printf("Heap is full, cannot insert new node.\n");  return;  }  MinHeapNode* newNode = (MinHeapNode*)malloc(sizeof(MinHeapNode));  newNode->node = node;  newNode->left = NULL;  newNode->right = NULL;  newNode->parent = NULL;  int i = minHeap->size;  minHeap->array[i] = newNode;  minHeap->size++;  // 上浮调整  while (i && compare(minHeap->array[(i - 1) / 2]->node, node) > 0) {  MinHeapNode* temp = minHeap->array[i];  minHeap->array[i] = minHeap->array[(i - 1) / 2];  minHeap->array[(i - 1) / 2] = temp;  if (minHeap->array[i]->left) {  minHeap->array[i]->left->parent = minHeap->array[(i - 1) / 2];  }  if (minHeap->array[i]->right) {  minHeap->array[i]->right->parent = minHeap->array[(i - 1) / 2];  }  minHeap->array[(i - 1) / 2]->parent = minHeap->array[i];  i = (i - 1) / 2;  }  
}  // 提取最小节点  
ListNode* extractMin(MinHeap* minHeap) {  if (minHeap->size == 0) {  printf("Heap is empty, cannot extract minimum node.\n");  return NULL;  }  ListNode* minNode = minHeap->array[0]->node;  MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];  minHeap->array[0] = lastNode;  minHeap->size--;  // 下沉调整  int i = 0;  while (2 * i + 1 < minHeap->size) {  int leftChild = 2 * i + 1;  int rightChild = 2 * i + 2;  int smallest = i;  if (compare(minHeap->array[leftChild]->node, minHeap->array[smallest]->node) < 0) {  smallest = leftChild;  }  if (rightChild < minHeap->size && compare(minHeap->array[rightChild]->node, minHeap->array[smallest]->node) < 0) {  smallest = rightChild;  }  if (smallest != i) {  MinHeapNode* temp = minHeap->array[i];  minHeap->array[i] = minHeap->array[smallest];  minHeap->array[smallest] = temp;  if (minHeap->array[i]->left) {  minHeap->array[i]->left->parent = minHeap->array[i];  }  if (minHeap->array[i]->right) {  minHeap->array[i]->right->parent = minHeap->array[i];  }  if (minHeap->array[smallest]->left) {  minHeap->array[smallest]->left->parent = minHeap->array[smallest];  }  if (minHeap->array[smallest]->right) {  minHeap->array[smallest]->right->parent = minHeap->array[smallest];  }  i = smallest;  } else {  break;  }  }  free(lastNode);  return minNode;  
}  // 检查堆是否为空  
int isEmpty(MinHeap* minHeap) {  return minHeap->size == 0;  
}  // 获取堆的大小  
int getSize(MinHeap* minHeap) {  return minHeap->size;  
}  // 辅助函数：创建新链表节点  
ListNode* createNode(int val) {  ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));  newNode->val = val;  newNode->next = NULL;  return newNode;  
}  // 辅助函数：打印链表  
void printList(ListNode* head) {  ListNode* current = head;  while (current != NULL) {  printf("%d -> ", current->val);  current = current->next;  }  printf("NULL\n");  
}  // 主函数：合并K个有序链表  
ListNode* mergeKLists(ListNode** lists, int listsSize) {  if (listsSize == 0) return NULL;  MinHeap* minHeap = createMinHeap(listsSize);  for (int i = 0; i < listsSize; i++) {  if (lists[i] != NULL) {  insertMinHeap(minHeap, lists[i]);  }  }  ListNode dummy = {0, NULL};  ListNode* tail = &dummy;  while (!isEmpty(minHeap)) {  ListNode* minNode = extractMin(minHeap);  tail->next = minNode;  tail = tail->next;  if (minNode->next != NULL) {  insertMinHeap(minHeap, minNode->next);  }  }  freeMinHeap(minHeap);  return dummy.next;  
}  int main() {  ListNode* l1 = createNode(1);  l1->next = createNode(4);  l1->next->next = createNode(5);  ListNode* l2 = createNode(1);  l2->next = createNode(3);  l2->next->next = createNode(4);  ListNode* l3 = createNode(2);  l3->next = createNode(6);  ListNode* lists[] = {l1, l2, l3};  int listsSize = 3;  ListNode* mergedList = mergeKLists(lists, listsSize);  printList(mergedList);  return 0;  
}

深入剖析：

使用最小堆可以有效地合并K个有序链表，因为堆能够始终提供当前所有链表中的最小元素。这种方法的时间复杂度为O(N log K)，其中N是所有链表中节点的总数，K是链表的数量。

题目三：全排列

题目描述：

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例输入与输出：

输入：[1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入：[0,1]
输出：[[0,1],[1,0]]

题目分析：

全排列问题是一个经典的回溯算法问题。回溯算法通过递归和剪枝来搜索所有可能的解。

解题思路：

定义一个递归函数，该函数接收当前排列和剩余可选数字作为参数。
在每次递归调用中，选择一个数字加入当前排列，并从剩余可选数字中移除该数字。
当剩余可选数字为空时，将当前排列加入结果集中。
递归调用该函数，直到所有可能的排列都被找到。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  // 动态数组结构定义  
typedef struct {  int* data;  int size;  int capacity;  
} IntArray;  // 辅助函数：创建动态数组  
IntArray* createIntArray(int capacity) {  IntArray* array = (IntArray*)malloc(sizeof(IntArray));  array->data = (int*)malloc(capacity * sizeof(int));  array->size = 0;  array->capacity = capacity;  return array;  
}  // 辅助函数：向动态数组添加元素  
void append(IntArray* array, int val) {  if (array->size >= array->capacity) {  array->capacity *= 2;  array->data = (int*)realloc(array->data, array->capacity * sizeof(int));  }  array->data[array->size++] = val;  
}  // 辅助函数：释放动态数组内存  
void freeIntArray(IntArray* array) {  free(array->data);  free(array);  
}  // 主函数：生成全排列  
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {  *returnSize = 0;  IntArray* numsArray = createIntArray(numsSize);  for (int i = 0; i < numsSize; i++) {  append(numsArray, nums[i]);  }  IntArray* path = createIntArray(numsSize);  IntArray* used = createIntArray(numsSize);  for (int i = 0; i < numsSize; i++) {  used->data[i] = 0;  }  int* returnColumnSizesArray = (int*)malloc(numsSize * sizeof(int));  int** result = (int**)malloc(numsSize * numsSize * sizeof(int*));  // 回溯函数  void permuteHelper(IntArray* nums, IntArray* path, IntArray* used, IntArray** result, int* returnSize) {  if (path->size == nums->size) {  IntArray* temp = createIntArray(path->size);  for (int i = 0; i < path->size; i++) {  append(temp, path->data[i]);  }  result[*returnSize] = temp->data;  (*returnSize)++;  freeIntArray(temp);  return;  }  for (int i = 0; i < nums->size; i++) {  if (used->data[i]) continue;  used->data[i] = 1;  append(path, nums->data[i]);  permuteHelper(nums, path, used, result, returnSize);  used->data[i] = 0;  path->size--;  }  }  permuteHelper(numsArray, path, used, result, returnSize);  for (int i = 0; i < *returnSize; i++) {  returnColumnSizesArray[i] = path->size;  }  *returnColumnSizes = returnColumnSizesArray;  freeIntArray(numsArray);  freeIntArray(path);  freeIntArray(used);  return result;  
}  // 辅助函数：打印二维数组  
void printPermutations(int** permutations, int permutationsSize, int* returnColumnSizes) {  for (int i = 0; i < permutationsSize; i++) {  for (int j = 0; j < returnColumnSizes[i]; j++) {  printf("%d ", permutations[i][j]);  }  printf("\n");  }  
}  int main() {  int nums1[] = {1, 2, 3};  int numsSize1 = sizeof(nums1) / sizeof(nums1[0]);  int* returnColumnSizes1;  int returnSize1;  int** permutations1 = permute(nums1, numsSize1, &returnSize1, &returnColumnSizes1);  printPermutations(permutations1, returnSize1, returnColumnSizes1);  int nums2[] = {0, 1};  int numsSize2 = sizeof(nums2) / sizeof(nums2[0]);  int* returnColumnSizes2;  int returnSize2;  int** permutations2 = permute(nums2, numsSize2, &returnSize2, &returnColumnSizes2);  printPermutations(permutations2, returnSize2, returnColumnSizes2);  return 0;  
}

深入剖析：

回溯算法通过递归和剪枝来搜索所有可能的解空间。在全排列问题中，我们使用三个动态数组来分别存储原始数字、当前排列和已使用数字的状态。通过递归地选择数字并更新状态，我们可以找到所有可能的全排列。

---

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