题目

题目来源 分析 我的程序 运行结果 题目来源 LeetCode：https://leetcode-cn.com/problems/two-sum 分析 具体思想可以参考这个题解的演示：https://leetcode-cn.com/problems/two-sum/solution/tu-jie-guan-fang-tui-jian-ti-jie-liang-s-02xs/，LeetCode中使用的哈希算法是通过uthash.h这个文件实现的，该文件本来是个开源项目，目前已整合到gcc中，关于其使用请参考uthash的文档：https://troydhanson.github.io/uthash/userguide.html。 我的程序 struct numsHash{ int key; // 键值 int val; // 数据 UT_hash_handle hh; }; struct numsHash* pNumsHashHead = NULL; struct numsHash* Find_NumsHash(int targetKey) // 定义查询函数 { struct numsHash *pReturn; HASH_FIND_INT(pNumsHashHead, &targetKey, pReturn); return pReturn; } void Add_NumsHash(int addKey, int addVal) { struct numsHash* pTarget = Find_NumsHash(addKey); if(pTarget == NULL){ struct numsHash* pTempHash = malloc(sizeof(struct numsHash)); pTempHash->key = addKey; pTempHash->val = addVal; HASH_ADD_INT(pNumsHashHead, key, pTempHash); } } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { pNumsHashHead = NULL; for(int i = 0; i < numsSize; i++){ struct numsHash* pTempHash = Find_NumsHash(target - nums[i]); if(pTempHash != NULL){ int* ret = malloc(sizeof(int) * 2); ret[0] = pTempHash->val; ret[1] = i; *returnSize = 2; return ret; } Add_NumsHash(nums[i], i); } *returnSize = 0; return NULL; } 运行结果 执行用时 内存消耗 4ms 7.6MB

题目来源 我的程序 结果 官方答案 结果 分析 题目来源 LeetCode：https://leetcode-cn.com/problems/two-sum 我的程序 /** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int* ret = NULL; *returnSize = 0; int temp = 0; for(int i = 0; i < numsSize; ++i) { for(int j = i + 1; j < numsSize; ++j) { if(nums[i] + nums[j] == target) { *returnSize += 2; ret = realloc(ret, sizeof(int) * (*returnSize)); ret[temp++] = i; ret[temp++] = j; } } } return ret; } 结果 执行用时 内存消耗 152ms 6.1MB 官方答案 int* twoSum(int* nums, int numsSize, int target, int* returnSize) { for (int i = 0; i < numsSize; ++i) { for (int j = i + 1; j < numsSize; ++j) { if (nums[i] + nums[j] == target) { int* ret = malloc(sizeof(int) * 2); ret[0] = i, ret[1] = j; *returnSize = 2; return ret; } } } *returnSize = 0; return NULL; } 结果 执行用时 内存消耗 92ms 6.3MB 分析 我的程序是整个完全遍历完了找出所有解，而官方是找到后直接跳出。相对于这道题来说官方的答案很显然更加贴近题意，但是我的程序更加具有普遍性（因为适合满足多组解的情况）。

题目来源 题目内容 分析 我的程序 运行结果 题目来源 浙大数据结构MOOC-PTA的课后题 题目内容 分析 就是个普通的二分查找，没啥好分析的。 我的程序 Position BinarySearch( List L, ElementType X ) { Position left, right; left = 1; right = L->Last; while(left <= right) { Position middle = (left + right) / 2; // 记录中间位置 if(L->Data[middle] == X)return middle; else if(L->Data[middle] < X)left = middle +1; else if(L->Data[middle] > X)right = middle - 1; } return NotFound; } 运行结果

题目来源 题目内容 分析 我的程序 运行结果 题目来源 浙大数据结构MOOC-PTA的课后题 题目内容 分析 这一题时最大子列和问题的变形，需要输出最大子列和的子列首项与末项，且在数列全为负的情况下，最大子列和为0，且需要输出首尾。而且如果出现了前后有相同都是最大子列的情况，选择前面的那一个。 我继续沿用了最大子列和问题中的在线处理算法，但是加上了对子列首尾的处理。 说实话这题有点难，我的做法也稍微有点取巧，使用专门的标志来处理非正有0的情况，不过总体来说结果是过了。 我的程序 #include <stdio.h> int main() { // 获取数据 int size; scanf("%d", &size); int num[size]; int max = 0, this = 0; // 记录首尾位置 int start = 0, end = 0, temp = 0; // 记录负数和正数的个数 int negFlag = 0; int posFlag = 0; // 在线处理，寻找最大子列和同时记录该子列和首尾位置 for(int i = 0; i < size; i++) { scanf("%d", num + i); // 记录正数和负数的个数，等会有用 if(num[i] < 0)negFlag++; else if(num[i] > 0)posFlag++; // 计算子列和 this += num[i]; if(this > max) { max = this; // 当最大子列和发生了变化，记录其末尾，并将之前缓存的首部放入start end = i; start = temp; } else if(this < 0) { this = 0; // 当在线处理发现了子列和为负数的情况，需要丢弃前面的子列和，此时使用temp记录此次更新，因为它可能成为最大子列和的首项 temp = i + 1; } } if(negFlag == size)printf("%d %d %d", 0, num[0], num[size - 1]); // 全是负数，输出最大值0和首尾项 else if(posFlag > 0)printf("%d %d %d", max, num[start], num[end]); // 如果有正数，则必然存在非零最大子列 else if(posFlag == 0)printf("0 0 0"); // 如果没有正数，又不全是负数，则最大子列和是0，且子列内容也全是0，直接输出0 return 0; } 运行结果

题目来源 题目内容 分析 我的程序 运行结果 题目来源 浙大数据结构MOOC-PTA的课后题 题目内容 分析 这个程序在课程里讲过，一共有四种方法，其中两种是同一种方法，只是进行了优化，这道题没有什么好分析的，直接写就行了。 我的程序 暴力穷举： #include <stdio.h> int main() { // 获取数据 int size; scanf("%d", &size); int num[size]; int max = 0, this = 0; for(int i = 0; i < size; i++) { scanf("%d", num + i); } // 穷举所有子列并找出最大和 for(int i = 0; i < size; i++) // 分别以每个项作为子列起点，然后计算这个起点所有子列和 { this = 0; // 每次计算完子列，都需要清空 for(int j = i; j < size; j++) // 计算当前所在起点的所有子列和 { this += num[j]; if(this > max)max = this; // 当出现了更大的子列和时，将其存入max } } printf("%d", max); // 打印出来 return 0; } 这种解法的时间复杂度为O(N^2^)，虽然能用但是还差点意思。 分而治之： #include <stdio.h> int getMaxSequenceSum(int* num, int size); int main() { int size; scanf("%d", &size); int num[size]; int max = 0; for(int i = 0; i < size; i++) { scanf("%d", num + i); } max = getMaxSequenceSum(num, size); printf("%d", max); return 0; } int getMaxSequenceSum(int* num, int size) // 分而治之，左右分并分别计算最大子列和，然后从中间向两边延申计算最大子列和，比较三者，最终得到最大子列和 { if(size == 1) { return num[0]>0?num[0]:0; // 不可再分时，最大子列和就是本身或0（小于0的情况） } int left = getMaxSequenceSum(num, size / 2); int right = getMaxSequenceSum(num + size / 2, size - size / 2); int mid_l = 0, mid_r = 0; int max = 0, this = 0; for(int i = 1; i <= size / 2; i++) { this += num[size / 2 - i]; if(mid_l < this)mid_l = this; } this = 0; for(int i = 0; i < size / 2; i++) { this += num[size / 2 + i]; if(mid_r < this)mid_r = this; } max = mid_l + mid_r > left?mid_l + mid_r:left; return max > right?max:right; } 这种解法的时间复杂度为O(NlogN)，已经是一种非常优秀的解法了。 ...