试题要求如下：

回答（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;
}

运行效率如下所示：