目录
第1题:二进制表示中质数个计算置位
第2题:消失的数字
第3题:最小绝对差
第4题:按奇偶排序数组II
第5题:主要元素
第6题:逐步求和得到正数的最小值
第7题:找不同
第8题:魔术索引
第9题:托普利茨矩阵
第10题:下一个更大元素1
力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。
第1题:二进制表示中质数个计算置位
试题要求如下:
回答(C语言):
// 判断是否为质数 bool isPrime(int num){ if (num < 2) return false; int i; for(i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } int getOneCount(int num){ int count = 0; while (num != 0) { num &= (num - 1); count++; } return count; } // 算出含有1的个数m,m是否为素数 int countPrimeSetBits(int L, int R){ int i,num,count = 0; for (i = L; i <= R; i++) { num = getOneCount(i); if (isPrime(num)) count++; } return count; }
运行效率如下所示:
第2题:消失的数字
试题要求如下:
回答(C语言):
int missingNumber(int* nums, int numsSize){ int i=0; int* data_buf=(int*)malloc(sizeof(int)*(numsSize+1)); memset(data_buf,0,sizeof(int)*(numsSize+1)); for(i=0;i<numsSize;i++){ data_buf[nums[i]]++; } for(i=0;i<numsSize;i++){ if(data_buf[i]==0){ break; } } data_buf[numsSize]='\0'; return i; }
运行效率如下所示:
第3题:最小绝对差
试题要求如下:
回答(C语言):
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ int cmp(const void* num, const void* num2){ return *(int*)num - *(int*)num2; } int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes){ qsort(arr,arrSize,sizeof(int),cmp); int **returnarra = malloc(sizeof(int*)*arrSize), count = 0; int *ColumnSizes = (int*)malloc(sizeof(int)* arrSize); assert(returnarra!=NULL && ColumnSizes!=NULL); int different, min = abs(arr[0]-arr[arrSize-1]); for(int i = 1; i < arrSize;i++){ if((different = abs(arr[i] - arr[i-1])) < min){ min = different; } } for(int i = 1; i < arrSize; i++){ different = abs(arr[i] - arr[i-1]); if(different == min){ int *pair = malloc(sizeof(int) * 2); pair[0] = arr[i-1]; pair[1] = arr[i]; returnarra[count] =pair; ColumnSizes[count++] = 2; } } *returnSize = count; *returnColumnSizes = ColumnSizes; return returnarra; }
运行效率如下所示:
第4题:按奇偶排序数组II
试题要求如下:
回答(C语言):
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* sortArrayByParityII(int* A, int ASize, int* returnSize){ //int* arr = (int*)malloc(sizeof(int) * ASize); *returnSize = ASize; int odd = 1; for (int i = 0; i < ASize; i += 2) { if (A[i] % 2 != 0) { while (A[odd] % 2 == 1) { odd += 2; } int tmp = A[odd]; A[odd] = A[i]; A[i] = tmp; } } return A; }
运行效率如下所示:
第5题:主要元素
试题要求如下:
回答(C语言):
int majorityElement(int* nums, int numsSize){ int cur; int counter = 0; for (int i = 0; i < numsSize; i++) { if (counter == 0) { counter = 1; cur = nums[i]; } else if (cur != nums[i]) { counter--; } else { counter++; } } if(counter > 0) return cur; else return -1; }
运行效率如下所示:
第6题:逐步求和得到正数的最小值
试题要求如下:
回答(C语言):
int minStartValue(int* nums, int numsSize) { int min = nums[0], count = 0; for (int i = 0; i < numsSize; i ++) { count += nums[i]; min = min < count ? min : count; } min = 1 - min; return min > 0 ? min : 1; }
运行效率如下所示:
第7题:找不同
试题要求如下:
回答(C语言):
char findTheDifference(char * s, char * t){ int sum_s = 0,sum_t = 0; for(int i = 0;i < strlen(t);i++){ if(i < strlen(t)-1){ sum_s +=s[i]; } sum_t +=t[i]; } return sum_t-sum_s; }
运行效率如下所示:
第8题:魔术索引
试题要求如下:
回答(C语言):
int findMagicIndex(int* nums, int numsSize){ for(int i = 0;i < numsSize;i++){ if(nums[i] == i){ return i; } } return -1; }
运行效率如下所示:
第9题:托普利茨矩阵
试题要求如下:
回答(C语言):
//(r1, c1) (r2, c2)满足对角线的特点 r1 - c1 == r2 - c2 bool isToeplitzMatrix(int** matrix, int matrixSize, int* matrixColSize){ for(int i = 1;i < matrixSize;++i) { for(int j = 1;j < matrixColSize[0];++j) { if(matrix[i-1][j-1] != matrix[i][j]) return false; } } return true; }
运行效率如下所示:
第10题:下一个更大元素1
试题要求如下:
回答(C语言):
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){ int* res = (int*)malloc(sizeof(int) * nums1Size); int flag = 0; int i,j; for(i = 0; i < nums1Size; i++) { for(j = 0; j < nums2Size; j++) { if(nums1[i] == nums2[j]) { flag = 1; continue; } else if(nums1[i] < nums2[j] && flag == 1) { res[i] = nums2[j]; break; } } if(j == nums2Size) { res[i] = -1; } flag = 0; } *returnSize = nums1Size; return res; }
运行效率如下所示: