力扣(LeetCode)刷題，簡單+中等題(第36期)

目錄

第1題：連續的子數組和

第2題：連續數組

第3題：相交連結清單

第4題：目标和

第5題：最後一塊石頭的重量 II

第6題：構造矩形

第7題：零錢兌換 II

第8題：完全平方數

第9題：不同路徑 II

第10題：石子遊戲

力扣(LeetCode)定期刷題，每期10道題，業務繁重的同志可以看看我分享的思路，不是最高效解決方案，隻求互相提升。

試題要求如下：

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

運作效率如下所示：

#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;
}      

/**
 * 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; 
}      

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];
}      

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;
        }
    }
}      

解題思路：

這道題主要的難點是要找到兩個相近且相乘為面積的長和寬，是以用開平方求得最中間的數，然後依次遞減，找到可以被整除的數，即可。

/**
 * 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;
}      

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];
}      

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];
}      

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];
}      

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;
}