网站设计确认函,泰州哪家网做网站,南宁seo网络推广公司,中文seo wordpress 插件文章目录 题目一#xff1a;最长回文子串题目描述#xff1a;示例输入与输出#xff1a;题目分析#xff1a;解题思路#xff1a;示例代码#xff1a;深入剖析#xff1a; 题目二#xff1a;合并K个有序链表题目描述#xff1a;示例输入与输出#xff1a;题目分析最长回文子串题目描述示例输入与输出题目分析解题思路示例代码深入剖析 题目二合并K个有序链表题目描述示例输入与输出题目分析解题思路示例代码深入剖析 题目三全排列题目描述示例输入与输出题目分析解题思路示例代码深入剖析 你好呀我是 山顶风景独好 欢迎踏入我的博客世界能与您在此邂逅真是缘分使然 愿您在此停留的每一刻都沐浴在轻松愉悦的氛围中。 这里不仅有丰富的知识和趣味横生的内容等您来探索更是一个自由交流的平台期待您留下独特的思考与见解。 让我们一起踏上这段探索与成长的旅程携手挖掘更多可能共同进步✨ 题目一最长回文子串
题目描述 给定一个字符串 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等你哦我的主页
