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

亦凉 2022-10-20 13:42 228阅读 0赞

# **目录** #

第1题：连续的子数组和

第2题：连续数组

第3题：相交链表

第4题：目标和

第5题：最后一块石头的重量 II

第6题：构造矩形

第7题：零钱兑换 II

第8题：完全平方数

第9题：不同路径 II

第10题：石子游戏

--------------------

力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。

# 第1题：[连续的子数组和][Link 1] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70][]

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

**运行效率如下所示：**

![20210602095145180.png][]

--------------------

# 第2题：[连续数组][Link 2] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 1][]

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

**运行效率如下所示：**

![20210603094534209.png][]

--------------------

# 第3题：[相交链表][Link 3] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 2][]

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

**运行效率如下所示：**

![20210604093641482.png][]

--------------------

# 第4题：[目标和][Link 4] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 3][]

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

**运行效率如下所示：**

![20210607093234135.png][]

--------------------

# 第5题：[最后一块石头的重量 II][II] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 4][]

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

**运行效率如下所示：**

![20210608091858175.png][]

--------------------

# 第6题：[构造矩形][Link 5] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 5][]

**解题思路：**

这道题主要的难点是要找到两个相近且相乘为面积的长和宽，所以用开平方求得最中间的数，然后依次递减，找到可以被整除的数，即可。

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

**运行效率如下所示：**

![20210609091017844.png][]

--------------------

# 第7题：[零钱兑换 II][II 1] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 6][]

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

**运行效率如下所示：**

![20210610093323837.png][]

--------------------

# 第8题：[完全平方数][Link 6] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 7][]

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

**运行效率如下所示：**

![20210611092601234.png][]

--------------------

# 第9题：[不同路径 II][II 2] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 8][]

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

**运行效率如下所示：**

![20210615093545531.png][]

--------------------

# 第10题：[石子游戏][Link 7] #

**试题要求如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 9][]

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

**运行效率如下所示：**

![20210616133306265.png][]

[Link 1]: https://leetcode-cn.com/problems/continuous-subarray-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70]: /images/20221020/ea67557e0a1c41789d6148f6306e5e2e.png
[20210602095145180.png]: /images/20221020/96d991bf95d34b48ae13fe922c8c667b.png
[Link 2]: https://leetcode-cn.com/problems/contiguous-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 1]: /images/20221020/145fa668a4aa4415aa0c23f20ef36305.png
[20210603094534209.png]: /images/20221020/fdc38894ee8c43ddb10668346c4fd16b.png
[Link 3]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 2]: /images/20221020/0497a80f65404da99dc96999b4c86871.png
[20210604093641482.png]: /images/20221020/5c6fcb151a6245dd870e2d2c74ddd19d.png
[Link 4]: https://leetcode-cn.com/problems/target-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 3]: /images/20221020/fcff08052b36433a88598c8fb2bee354.png
[20210607093234135.png]: /images/20221020/28db594c18af4019a1778fd6c8aefe1e.png
[II]: https://leetcode-cn.com/problems/last-stone-weight-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 4]: /images/20221020/e26fbc2e3b53443ab32e2cd2a54483ea.png
[20210608091858175.png]: /images/20221020/0c52a2d6f7af452aa30319a88b5922c7.png
[Link 5]: https://leetcode-cn.com/problems/construct-the-rectangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 5]: /images/20221020/5ec1635c708d45a89f925d389fdf287f.png
[20210609091017844.png]: /images/20221020/7bd34f93bca34efcb6d2da4ce2fbbb48.png
[II 1]: https://leetcode-cn.com/problems/coin-change-2/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 6]: /images/20221020/44066f2f58b64936acc31cc33db66724.png
[20210610093323837.png]: /images/20221020/5e4101013d20489c9655043eef8fca7e.png
[Link 6]: https://leetcode-cn.com/problems/perfect-squares/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 7]: /images/20221020/aeb77b98644741089db93692ce44a323.png
[20210611092601234.png]: /images/20221020/5ea44caac22c4707baa8dd3c82707e6e.png
[II 2]: https://leetcode-cn.com/problems/unique-paths-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 8]: /images/20221020/9c9798718d7c48f1a9e8e60429926b93.png
[20210615093545531.png]: /images/20221020/c869a68ac1d544a9bd4ea8788aff8588.png
[Link 7]: https://leetcode-cn.com/problems/stone-game/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA2OTIz_size_16_color_FFFFFF_t_70 9]: /images/20221020/0de5cdaf8f0c41eaa10158170bbfc2fb.png
[20210616133306265.png]: /images/20221020/38c049fc25964f88a03b144347e021d2.png