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

目录

第1题：分割数组为连续子序列

第2题：翻转矩阵后的得分

第3题：寻找旋转排序数组中的最小值

第4题：乘积最大子数组

第5题：不同路径

第6题：判断路径是否相交

第7题：摆动序列

第8题：单调递增的数字

第9题：移除链表元素

第10题：计数二进制子串

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

第1题：分割数组为连续子序列

试题要求如下：

回答（C语言）：

#define SIZE 10001

bool isPossible(int* nums, int numsSize){
    int one[SIZE] = {0};
    int two[SIZE] = {0};
    int safe[SIZE] = {0};
    int oneSize = 0;
    int twoSize = 0;
    int now;
    int minValue = nums[0] - 1;

    for (int i = 0; i < numsSize; ++i) {
        now = nums[i] - 1 - minValue;
        
        if (one[now] == 0 && two[now] == 0 && safe[now] == 0) {
            ++one[now + 1];
            ++oneSize;
        } else if (one[now] > 0) {
            ++two[now + 1];
            --one[now];
            --oneSize;
            ++twoSize;
        } else if (two[now] > 0) {
            ++safe[now + 1];
            --two[now];
            --twoSize;
        } else{
            ++safe[now + 1];
            --safe[now];
        }
    }

    return twoSize == 0 && oneSize == 0;
}

运行效率如下所示：

第2题：翻转矩阵后的得分

试题要求如下：

解题思路：

为了得到最高的分数，矩阵的每一行的最左边的数都必须为 1。为了做到这一点，可以翻转那些最左边的数不为 1 的那些行，而其他的行则保持不动。

当将每一行的最左边的数都变为 1 之后，就只能进行列翻转了。为了使得总得分最大，我们要让每个列中 1 的数目尽可能多。

因此，扫描除了最左边的列以外的每一列，如果该列 0 的数目多于 1 的数目，就翻转该列，其他的列则保持不变。

回答（C语言）：

int matrixScore(int** A, int ASize, int* AColSize) {
    int m = ASize, n = AColSize[0];
    int ret = m * (1 B?A:B
#define MIN(A,B) A 0) {
        if (mod < curr % 10) {
            isInc = false;
            lastNum = curr;
            lastMulti = multi;
            curr -= 1; // 不单调递减时去前面借一位
        }
        mod = curr % 10;
        curr /= 10;
        multi *= 10;
    }

    if (isInc == false) {
        return lastNum * lastMulti - 1;
    }
    
    return N;
}

运行效率如下所示：

第9题：移除链表元素

试题要求如下：

回答（C语言）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val){ 
    if (head == NULL) {
        return NULL;
    }     

    /* 删除 head 节点后面值为 val 的元素的节点 */
    struct ListNode* res = removeElements(head->next, val);
    /* head 节点是要删除的节点 */
    if (head->val == val) {
        return res;
    } else {
        head->next = res;
        return head;
    }
}

运行效率如下所示：

第10题：计数二进制子串

试题要求如下：

回答（C语言）：

int countBinarySubstrings(char* s) {
    int ptr = 0, n = strlen(s), last = 0, ans = 0;

    while (ptr < n) {
        char c = s[ptr];
        int count = 0;
        
        while (ptr < n && s[ptr] == c) {
            ++ptr;
            ++count;
        }
        ans += fmin(count, last);
        last = count;
    }

    return ans;
}

运行效率如下所示