力扣(LeetCode)刷题，简单+中等题(第36期)

目录

第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 

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