目录
第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 << (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]; }
运行效率如下所示：
第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; }
运行效率如下所示
