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

不脱发的程序猿

发布于 2021-01-20 11:38:02

2240

发布于 2021-01-20 11:38:02

文章被收录于专栏：AIoT技术交流、分享 AIoT技术交流、分享AIoT技术交流、分享

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

运行效率如下所示

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-12-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

c 语言

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

c 语言

编程算法

登录后参与评论

0 条评论

热度