力扣(LeetCode)刷题,简单题(第23期)

举报
不脱发的程序猿 发表于 2020/12/31 00:25:44 2020/12/31
【摘要】 目录 第1题:整数转换 第2题:重复的子字符串 第3题:范围求和2 第4题:反转数位 第5题:数字转换为十六进制 第6题:比较含退格的字符 第7题:三个数的最大乘积 第8题:珠玑妙算 第9题:旋转字符串 第10题:较大分组的位置 力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。 第...

目录

第1题:整数转换

第2题:重复的子字符串

第3题:范围求和2

第4题:反转数位

第5题:数字转换为十六进制

第6题:比较含退格的字符

第7题:三个数的最大乘积

第8题:珠玑妙算

第9题:旋转字符串

第10题:较大分组的位置


力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

第1题:整数转换

试题要求如下:

解答思路:

异或操作。

回答(C语言):


  
  1. int convertInteger(int A, int B){
  2. int res=0;
  3. unsigned int tmp = A^B;
  4. while(tmp){
  5. if(tmp&1==1){
  6. res=res+1;
  7. }
  8. tmp>>=1;
  9. }
  10. return res;
  11. }

运行效率如下所示:


第2题:重复的子字符串

试题要求如下:

解答思路:

回答(C语言):


  
  1. bool repeatedSubstringPattern(char* s) {
  2. int n = strlen(s);
  3. for (int i = 1; i * 2 <= n; ++i) {
  4. if (n % i == 0) {
  5. bool match = true;
  6. for (int j = i; j < n; ++j) {
  7. if (s[j] != s[j - i]) {
  8. match = false;
  9. break;
  10. }
  11. }
  12. if (match) {
  13. return true;
  14. }
  15. }
  16. }
  17. return false;
  18. }

运行效率如下所示:


第3题:范围求和2

试题要求如下:

解答思路:

这题最简单的做法就是去找所给二维矩阵的第一列了和第二列最小的数,因为数组每行的两个数都可以划分一个矩形,最后和最大的数,必定是共同的重叠部分,所以只需找数组每列的最小值,乘积为所求。

回答(C语言):


  
  1. int maxCount(int m, int n, int** ops, int opsSize, int* opsColSize){
  2. int min_c = m, min_r = n;
  3. for(int i = 0;i < opsSize;i++){
  4. if(ops[i][0] < min_c){
  5. min_c = ops[i][0];
  6. }
  7. if(ops[i][1] < min_r){
  8. min_r = ops[i][1];
  9. }
  10. }
  11. return min_c * min_r;
  12. }

运行效率如下所示:


第4题:反转数位

试题要求如下:

回答(C语言):


  
  1. void toBit(int num, int *val) {
  2. int i = 0;
  3. while(num) {
  4. val[i] = num & 1;
  5. num >>= 1;
  6. i++;
  7. }
  8. }
  9. int reverseBits(int num){
  10. int val[32] = {0};
  11. toBit(num, val);
  12. int count = 0;
  13. int countPre = 0;
  14. int max = 0;
  15. for (int i = 0; i < 32; i++) {
  16. if (val[i] == 1) {
  17. count++;
  18. }
  19. else {
  20. if (countPre + count + 1 > max) {
  21. max = countPre + count + 1;
  22. }
  23. countPre = count;
  24. count = 0;
  25. }
  26. }
  27. return max;
  28. }

运行效率如下所示:


第5题:数字转换为十六进制

试题要求如下:

解答思路:

取余、除以16(0X0F),装入数组,再反转。

回答(C语言):


  
  1. char g_stack[16 + 1] = {0};
  2. void swap(char *a, char *b) {char t = *a; *a = *b; *b = t; }
  3. char * toHex(int num) {
  4. int top = -1;
  5. unsigned int n = num;
  6. char index[] = "0123456789abcdef";
  7. // 这里用do...while()而不是while(),能直接覆盖num为0的情况
  8. do {
  9. g_stack[++top] = index[n % 16];
  10. n /= 16;
  11. } while (n != 0);
  12. g_stack[top + 1] = '\0';
  13. int lo = 0, hi = top;
  14. while (lo < hi) {
  15. swap(&g_stack[lo++], &g_stack[hi--]);
  16. }
  17. return g_stack;
  18. }

运行效率如下所示:


第6题:比较含退格的字符

试题要求如下:

解答思路:

采用双指针,遇到‘#’,下标减一,删除前一个字符;其他字符依次增加下标计数;得到新的字符串,然后就是字符串是否相同对比。

回答(C语言):


  
  1. int deletebackspace(char *str,int size){
  2. if(str==NULL||size==0){
  3. return 0;
  4. }
  5. int index = 0;
  6. for(int i=0;i<size;i++){
  7. if(str[i] != '#'){
  8. str[index++] = str[i];
  9. }
  10. else{
  11. if(index>0){
  12. index--;
  13. }
  14. }
  15. }
  16. return index;
  17. }
  18. bool backspaceCompare(char * S, char * T){
  19. int slen = deletebackspace(S,strlen(S));
  20. int tlen = deletebackspace(T,strlen(T));
  21. if(slen != tlen){
  22. return false;
  23. }
  24. else{
  25. for(int i=0;i<slen;i++){
  26. if(S[i] != T[i]){
  27. return false;
  28. }
  29. }
  30. return true;
  31. }
  32. }

运行效率如下所示:


第7题:三个数的最大乘积

试题要求如下:

解答思路:

我们将数组进行升序排序,如果数组中所有的元素都是非负数,那么答案即为最后三个元素的乘积。

如果数组中出现了负数,那么我们还需要考虑乘积中包含负数的情况,显然选择最小的两个负数和最大的一个正数是最优的,即为前两个元素与最后一个元素的乘积。

回答(C语言):


  
  1. int Compare(const void* a, const void* b)
  2. {
  3. return *(int*)a - *(int*)b;
  4. }
  5. int Max(int a, int b)
  6. {
  7. return a > b ? a : b;
  8. }
  9. int maximumProduct(int* nums, int numsSize){
  10. qsort(nums, numsSize, sizeof(int), Compare);
  11. return Max(nums[numsSize - 1] * nums[numsSize -2] * nums[numsSize - 3], nums[numsSize - 1] * nums[0] * nums[1]);
  12. }

运行效率如下所示:


第8题:珠玑妙算

试题要求如下:

回答(C语言):


  
  1. /**
  2. * Note: The returned array must be malloced, assume caller calls free().
  3. */
  4. int* masterMind(char* solution, char* guess, int* returnSize){
  5. returnSize[0] = 2;
  6. int dict[26] = {0}, *res = (int *)malloc (sizeof (int) * 2);
  7. res[0] = res[1] = 0;
  8. for (int i = 0; solution[i] != '\0'; ++i) {
  9. dict[solution[i] -'A']++;
  10. if (guess[i] == solution[i]) res[0]++;
  11. }
  12. for (int i = 0; solution[i] != '\0'; ++i) {
  13. if (dict[guess[i] - 'A']) {
  14. dict[guess[i] - 'A']--;
  15. res[1]++;
  16. }
  17. }
  18. res[1] -= res[0];
  19. return res;
  20. }

运行效率如下所示:


第9题:旋转字符串

试题要求如下:

回答(C语言):


  
  1. bool rotateString(char * A, char * B){
  2. int len = strlen(A);
  3. if(strlen(B) != len) return false;
  4. if(strcmp(A, B) == 0) return true;
  5. for(int i = 0; i < len; i++) {
  6. if(A[0] == B[i]) {
  7. int j;
  8. for(j=0; j < len; j++) {
  9. if(j<i && A[j+len-i] != B[j]) {
  10. break;
  11. }
  12. if(j >= i && A[j-i] != B[j]) {
  13. break;
  14. }
  15. }
  16. if(j == len) {
  17. return true;
  18. }
  19. }
  20. }
  21. return false;
  22. }

运行效率如下所示:


第10题:较大分组的位置

试题要求如下:

回答(C语言):


  
  1. /**
  2. * Return an array of arrays of size *returnSize.
  3. * The sizes of the arrays are returned as *returnColumnSizes array.
  4. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
  5. */
  6. int** largeGroupPositions(char * S, int* returnSize, int** returnColumnSizes){
  7. int size = 0;
  8. int len =strlen(S);
  9. if(len < 3){
  10. *returnSize = 0;
  11. ** returnColumnSizes = 0;
  12. return 0;
  13. }
  14. int ** res = (int **)malloc(len * sizeof(int *));
  15. for(int i=0;i<len;i++){
  16. res[i] = (int *)calloc(2,sizeof(int));
  17. }
  18. for(int i=0; i<len-2 ; i++){
  19. if( S[i] == S[i+1] && S[i] == S[i+2]){
  20. (*returnColumnSizes)[size] = 2;
  21. char temp = S[i];
  22. res[size][0]=i;
  23. i+=3;
  24. while(temp == S[i] && i<len) i++;
  25. res[size][1]=--i; //由于循环体内有i++,此处的S[i]已经是新值的起始点,为了一致,应退回1
  26. size++;
  27. }
  28. }
  29. *returnSize = size;
  30. return res;
  31. }

运行效率如下所示:

文章来源: handsome-man.blog.csdn.net,作者:不脱发的程序猿,版权归原作者所有,如需转载,请联系作者。

原文链接:handsome-man.blog.csdn.net/article/details/108213568

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。