目录
第1题：连续的子数组和
第2题：连续数组
第3题：相交链表
第4题：目标和
第5题：最后一块石头的重量 II
第6题：构造矩形
第7题：零钱兑换 II
第8题：完全平方数
第9题：不同路径 II
第10题：石子游戏
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：连续的子数组和
试题要求如下：
回答（C语言）：
struct HashTable { int key, val; UT_hash_handle hh; }; bool checkSubarraySum(int* nums, int numsSize, int k) { int m = numsSize; if (m < 2) { return false; } struct HashTable* hashTable = NULL; struct HashTable* tmp = malloc(sizeof(struct HashTable)); tmp->key = 0, tmp->val = -1; HASH_ADD_INT(hashTable, key, tmp); int remainder = 0; for (int i = 0; i < m; i++) { remainder = (remainder + nums[i]) % k; HASH_FIND_INT(hashTable, &remainder, tmp); if (tmp != NULL) { int prevIndex = tmp->val; if (i - prevIndex >= 2) { return true; } } else { tmp = malloc(sizeof(struct HashTable)); tmp->key = remainder, tmp->val = i; HASH_ADD_INT(hashTable, key, tmp); } } return false; }
运行效率如下所示：
第2题：连续数组
试题要求如下：
回答（C语言）：
#include <stdio.h> int findMaxLength(int* nums, int numsSize){ int *hash = (int *)malloc(sizeof(int) * (numsSize * 2 + 1)); for (int i = 0; i < (numsSize * 2 + 1); i++) { hash[i] = -2; } int maxlen = 0; int count = 0; hash[numsSize] = -1; for (int i = 0; i < numsSize; i++) { count += nums[i] == 0 ? -1 : 1; if (hash[count + numsSize] != -2) { maxlen = fmax(maxlen, i - hash[count+numsSize]); } else { hash[count + numsSize] = i; } } free(hash); return maxlen; }
运行效率如下所示：
第3题：相交链表
试题要求如下：
回答（C语言）：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *p=headA, *q=headB; while(p!=q&&(p!=NULL||q!=NULL)) { if(p==NULL) p=headB; else p=p->next; if(q==NULL) q=headA; else q=q->next; } return p; }
运行效率如下所示：
第4题：目标和
试题要求如下：
回答（C语言）：
int findTargetSumWays(int* nums, int numsSize, int target){ int sum = 0; for (int i = 0; i < numsSize; i++) { sum += nums[i]; } if ((sum + target) % 2 != 0) { return 0; } int targetA = (sum + target) / 2; int *dp = (int *)malloc(sizeof(int) * (targetA + 1)); memset(dp, 0, sizeof(int) * (targetA + 1)); dp[0] = 1; for (int i = 0; i < numsSize; i++) { for (int j = targetA; j >= nums[i]; j--) { dp[j] = dp[j] + dp[j - nums[i]]; } } return dp[targetA]; }
运行效率如下所示：
第5题：最后一块石头的重量 II
试题要求如下：
回答（C语言）：
int lastStoneWeightII(int* stones, int stonesSize) { int sum = 0; for (int i = 0; i < stonesSize; i++) { sum += stones[i]; } int n = stonesSize, m = sum / 2; int dp[n + 1][m + 1]; memset(dp, 0, sizeof(dp)); dp[0][0] = true; for (int i = 0; i < n; ++i) { for (int j = 0; j <= m; ++j) { if (j < stones[i]) { dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]]; } } } for (int j = m;; --j) { if (dp[n][j]) { return sum - 2 * j; } } }
运行效率如下所示：
第6题：构造矩形
试题要求如下：
解题思路：
这道题主要的难点是要找到两个相近且相乘为面积的长和宽，所以用开平方求得最中间的数，然后依次递减，找到可以被整除的数，即可。
回答（C语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* constructRectangle(int area, int* returnSize){ *returnSize=2; int *a = (int *)malloc(sizeof(int)*2); int b = (int)sqrt(area); while(area % b !=0){ b--; } a[1]=b; a[0]=area/b; return a; }
运行效率如下所示：
第7题：零钱兑换 II
试题要求如下：
回答（C语言）：
int change(int amount, int* coins, int coinsSize) { int dp[amount + 1]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < coinsSize; i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; }
运行效率如下所示：
第8题：完全平方数
试题要求如下：
回答（C语言）：
int numSquares(int n) { int f[n + 1]; f[0] = 0; for (int i = 1; i <= n; i++) { int minn = INT_MAX; for (int j = 1; j * j <= i; j++) { minn = fmin(minn, f[i - j * j]); } f[i] = minn + 1; } return f[n]; }
运行效率如下所示：
第9题：不同路径 II
试题要求如下：
回答（C语言）：
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) { /* 1、dp数组含义：从(0, 0)到当前行的第j列的路径数 */ int dp[*obstacleGridColSize]; /* 2、状态转移方程： * if (obstacleGrid[i][j] == 1) { * dp[j] = 0; * } else { * dp[j] += dp[j - 1]; * } */ /* 3、dp初值 * 第一行当前列路障之前均为1，路障之后均为0 */ if (obstacleGrid[0][0] == 1) { dp[0] = 0; } else { dp[0] = 1; } for (int j = 1; j < *obstacleGridColSize; j++) { if (obstacleGrid[0][j] == 1) { dp[j] = 0; } else { dp[j] = dp[j - 1]; } } /* 4、遍历顺序：从左到右一层一层遍历 */ for (int i = 1; i < obstacleGridSize; i++) { for (int j = 0; j < *obstacleGridColSize; j++) { if (j == 0) { /* 开头 */ if (obstacleGrid[i][j] == 1) { /* 当前路径上有路障：dp为0 */ dp[j] = 0; } else { /* 当前路径上没有路障：跳过 */ continue; } } else { /* 非开头 */ if (obstacleGrid[i][j] == 1) { /* 当前路径上有路障：dp为0 */ dp[j] = 0; } else { /* 当前路径上没有路障：计算路径数 */ dp[j] += dp[j - 1]; } } } } return dp[*obstacleGridColSize - 1]; }
运行效率如下所示：
第10题：石子游戏
试题要求如下：
回答（C语言）：
bool stoneGame(int* piles, int pilesSize) { int dp[pilesSize][pilesSize]; for (int i = 0; i < pilesSize; i++) { dp[i][i] = piles[i]; } for (int i = pilesSize - 2; i >= 0; i--) { for (int j = i + 1; j < pilesSize; j++) { dp[i][j] = fmax(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]); } } return dp[0][pilesSize - 1] > 0; }
运行效率如下所示：
