目录
力扣(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;
-
}
运行效率如下所示
文章来源: handsome-man.blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：handsome-man.blog.csdn.net/article/details/110467580