目錄

第1題：分割數(shù)組為連續(xù)子序列

第2題：翻轉(zhuǎn)矩陣后的得分

第3題：尋找旋轉(zhuǎn)排序數(shù)組中的最小值

第4題：乘積最大子數(shù)組

第5題：不同路徑

第6題：判斷路徑是否相交

第7題：擺動(dòng)序列

第8題：單調(diào)遞增的數(shù)字

第9題：移除鏈表元素

第10題：計(jì)數(shù)二進(jìn)制子串

---

力扣(LeetCode)定期刷題，每期10道題，業(yè)務(wù)繁重的同志可以看看我分享的思路，不是最高效解決方案，只求互相提升。

第1題：分割數(shù)組為連續(xù)子序列

試題要求如下：

回答（C語(yǔ)言）：

#define SIZE 10001bool 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;
}

運(yùn)行效率如下所示：

---

第2題：翻轉(zhuǎn)矩陣后的得分

試題要求如下：

解題思路：

為了得到最高的分?jǐn)?shù)，矩陣的每一行的最左邊的數(shù)都必須為 1。為了做到這一點(diǎn)，可以翻轉(zhuǎn)那些最左邊的數(shù)不為 1 的那些行，而其他的行則保持不動(dòng)。

當(dāng)將每一行的最左邊的數(shù)都變?yōu)?1?之后，就只能進(jìn)行列翻轉(zhuǎn)了。為了使得總得分最大，我們要讓每個(gè)列中 1?的數(shù)目盡可能多。

因此，掃描除了最左邊的列以外的每一列，如果該列 0?的數(shù)目多于 1 的數(shù)目，就翻轉(zhuǎn)該列，其他的列則保持不變。

回答（C語(yǔ)言）：

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]);  // 如果這一行進(jìn)行了行反轉(zhuǎn)，則該元素的實(shí)際取值為 1 - A[i][j]}}int k = fmax(nOnes, m - nOnes);ret += k * (1 << (n - j - 1));}return ret;
}

運(yùn)行效率如下所示：

---

第3題：尋找旋轉(zhuǎn)排序數(shù)組中的最小值

試題要求如下：

回答（C語(yǔ)言）：

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

運(yùn)行效率如下所示：

---

第4題：乘積最大子數(shù)組

試題要求如下：

回答（C語(yǔ)言）：

#define MAX(A,B) A>B?A:B
#define MIN(A,B) A<B?A:Bint 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;
}

運(yùn)行效率如下所示：

---

第5題：不同路徑

試題要求如下：

回答（C語(yǔ)言）：

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

運(yùn)行效率如下所示：

---

第6題：判斷路徑是否相交

試題要求如下：

回答（C語(yǔ)言）：

#define MAX 1001bool 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 1for(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;
}

運(yùn)行效率如下所示：

---

第7題：擺動(dòng)序列

試題要求如下：

回答（C語(yǔ)言）：

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

運(yùn)行效率如下所示：

---

第8題：單調(diào)遞增的數(shù)字

試題要求如下：

回答（C語(yǔ)言）：

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; // 不單調(diào)遞減時(shí)去前面借一位}mod = curr % 10;curr /= 10;multi *= 10;}if (isInc == false) {return lastNum * lastMulti - 1;}return N;
}

運(yùn)行效率如下所示：

---

第9題：移除鏈表元素

試題要求如下：

回答（C語(yǔ)言）：

/*** 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 節(jié)點(diǎn)后面值為 val 的元素的節(jié)點(diǎn) */struct ListNode* res = removeElements(head->next, val);/* head 節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn) */if (head->val == val) {return res;} else {head->next = res;return head;}
}

運(yùn)行效率如下所示：

---

第10題：計(jì)數(shù)二進(jìn)制子串

試題要求如下：

回答（C語(yǔ)言）：

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

運(yùn)行效率如下所示

總結(jié)

以上是生活随笔為你收集整理的力扣(LeetCode)刷题，简单+中等题(第29期)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。