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

不脱发的程序猿

关注

发布于: 2021 年 03 月 03 日

力扣(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 << (n - 1));     for (int j = 1; j < n; j++) {        int nOnes = 0;        for (int i = 0; i < m; i++) {            if (A[i][0] == 1) {                nOnes += A[i][j];            } else {                nOnes += (1 - A[i][j]);  // 如果这一行进行了行反转，则该元素的实际取值为 1 - A[i][j]            }        }        int k = fmax(nOnes, m - nOnes);        ret += k * (1 << (n - j - 1));    }    return ret;}

复制代码

运行效率如下所示：

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

试题要求如下：

回答（C 语言）：

int findMin(int* nums, int numsSize){    int left = 0,right = numsSize-1,mid;     while(left < right)    {        mid = left + (right - left)/2;        if(nums[mid]>nums[right])        {            left = mid + 1;        }        else        {            right = mid;        }    }    return nums[left];}

复制代码

运行效率如下所示：

第 4 题：乘积最大子数组

试题要求如下：

回答（C 语言）：

#define MAX(A,B) A>B?A:B#define MIN(A,B) A<B?A:B int maxProduct(int* nums, int numsSize){    int imax = 1, imin = 1, res = nums[0];    int tmp,i;        for(i = 0; i < numsSize; i++)    {        if(nums[i] < 0)        {            tmp = imax;            imax = imin;            imin = tmp;        }                imax = MAX(imax * nums[i], nums[i]);        imin = MIN(imin * nums[i], nums[i]);                res = MAX(imax, res);     }    return res;}

复制代码

运行效率如下所示：

第 5 题：不同路径

试题要求如下：

回答（C 语言）：

int uniquePaths(int m, int n) {    int f[m][n];        for (int i = 0; i < m; ++i) {        f[i][0] = 1;    }    for (int j = 0; j < n; ++j) {        f[0][j] = 1;    }    for (int i = 1; i < m; ++i) {        for (int j = 1; j < n; ++j) {            f[i][j] = f[i - 1][j] + f[i][j - 1];        }    }    return f[m - 1][n - 1];}

复制代码

运行效率如下所示：

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

试题要求如下：

回答（C 语言）：

#define MAX 1001 bool isPathCrossing(char * path){    if(path==NULL)  return false;    int hash[MAX][MAX]={0};    int x=500,y=500;     hash[x][y]=1;//zero point is 1     for(int i=0; i<strlen(path); i++){        if(path[i]=='N'){            if(hash[x][y+1]==1) return true;            else hash[x][++y]=1;        }         if(path[i]=='S'){            if(hash[x][y-1]==1) return true;            else hash[x][--y]=1;        }         if(path[i]=='W'){            if(hash[x-1][y]==1) return true;            else hash[--x][y]=1;        }         if(path[i]=='E'){            if(hash[x+1][y]==1) return true;            else hash[++x][y]=1;        }    }     return false;}

复制代码

运行效率如下所示：

第 7 题：摆动序列

试题要求如下：

回答（C 语言）：

int wiggleMaxLength(int* nums, int numsSize) {    if (numsSize < 2) {        return numsSize;    }     int up = 1, down = 1;    for (int i = 1; i < numsSize; i++) {        if (nums[i] > nums[i - 1]) {            up = fmax(up, down + 1);        } else if (nums[i] < nums[i - 1]) {            down = fmax(up + 1, down);        }    }        return fmax(up, down);}

复制代码

运行效率如下所示：

第 8 题：单调递增的数字

试题要求如下：

回答（C 语言）：

int monotoneIncreasingDigits(int N){    bool isInc = true;    int mod = N % 10;    int curr = N / 10;    int multi = 10;    int lastNum = curr;    int lastMulti = multi;     while(curr > 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;}

复制代码

运行效率如下所示

发布于: 2021 年 03 月 03 日阅读数: 10

原文链接:【http://xie.infoq.cn/article/6843ee59f8a8f973816ae0d66】。文章转载请联系作者。

不脱发的程序猿

关注

【研究方向】物联网、嵌入式、AI、Python 2018.02.09 加入

【公众号】美男子玩编程

发布

暂无评论

创作场景

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

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

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

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

第 4 题：乘积最大子数组

第 5 题：不同路径

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

第 7 题：摆动序列

第 8 题：单调递增的数字

第 9 题：移除链表元素

第 10 题：计数二进制子串

不脱发的程序猿

评论