devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++从零开始的打怪升级之路(day11)

作者：凡人多烦事01 | 2024-02-07 14:14:52

赞

踩

C++从零开始的打怪升级之路(day11)

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料

那么开启正题

为了巩固前面的知识，最近更新刷题贴，C++进度暂缓

1.反转字符串中的单词

反转字符串中的单词 III

 由于还没学C++的字符串有些题的ac代码是用C语言写的

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序

思路：实现一个子函数，来反转字符串，利用快慢指针在原字符串中“分隔单词”，利用子函数完成任务

  1. void _reverseWords(char* left,char* right)
  2. {
  3.     while(left < right)
  4.     {
  5.         char tmp = *left;
  6.         *left = *right;
  7.         *right = tmp;
  8.  
  9.         ++left;
  10.         --right;
  11.     }
  12. }
  13.  
  14. char* reverseWords(char* s) 
  15. {
  16.     char* fast = s;
  17.     char* slow = s;
  18.     while(*fast)
  19.     {
  20.         if(*fast == ' ')
  21.         {
  22.             _reverseWords(slow,fast - 1);
  23.             ++fast;
  24.             slow = fast;
  25.         }
  26.         else
  27.         {
  28.             ++fast;
  29.         }
  30.     }
  31.     _reverseWords(slow,fast - 1);
  32.  
  33.     return s;
  34. }

这是ac代码，要注意的是，出了while循环后还有最后一次翻转未完成

2.连续字符

1446. 连续字符

给你一个字符串 s ，字符串的「能量」定义为：只包含一种字符的最长非空子字符串的长度。

请你返回字符串 s 的 能量。

用前后双指针遍历字符串，用conut记录同一字符连续次数，用max存储最大值

  1. int maxPower(char* s) 
  2. {
  3.     int max = 0;
  4.     int count = 0;
  5.     char* slow = s;
  6.     char* fast = s;
  7.     while(*fast)
  8.     {
  9.         if(*fast == *slow)
  10.         {
  11.             ++count;
  12.             ++fast;
  13.         }
  14.         else
  15.         {
  16.             if(count > max)
  17.             {
  18.                 max = count;
  19.             }
  20.             count = 0;
  21.             slow = fast;
  22.         }
  23.     }
  24.     if(count > max)
  25.     {
  26.         max = count;
  27.     }
  28.  
  29.     return max;
  30. }

这是ac代码，同样要注意，出whlie循环后还有一次没有比较

3.字符串压缩

面试题 01.06. 字符串压缩

 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）

和上面的题类似，利用快慢指针获取拷贝题目所需的数据，需要注意的是数字转换成字符串，还有最后的返回标准 

  1. char* compressString(char* S) {
  2.     char* slow = S;
  3.     char* fast = S;
  4.     char* ret = (char*)malloc(sizeof(char) * 100000);
  5.     int reti = 0;
  6.     int count = 0;
  7.     while (*fast) 
  8.     {
  9.         if (*fast == *slow) 
  10.         {
  11.             ++count;
  12.             ++fast;
  13.         } else
  14.         {
  15.             ret[reti++] = *slow;
  16.             if (count < 10) 
  17.             {
  18.                 ret[reti++] = count + '0';
  19.             } 
  20.             else if (count >= 10 && count < 100) 
  21.             {
  22.                 ret[reti++] = count / 10 + '0';
  23.                 ret[reti++] = count % 10 + '0';
  24.             } 
  25.             else if (count >= 100 && count < 1000) 
  26.             {
  27.                 ret[reti++] = count / 100 + '0';
  28.                 ret[reti++] = count / 10 % 10 + '0';
  29.                 ret[reti++] = count % 10 + '0';
  30.             } 
  31.             else if (count >= 1000 && count < 10000) 
  32.             {
  33.                 ret[reti++] = count / 1000 + '0';
  34.                 ret[reti++] = count / 100 % 10 + '0';
  35.                 ret[reti++] = count / 10 % 10 + '0';
  36.                 ret[reti++] = count % 10 + '0';
  37.             }    
  38.             else if (count >= 10000 && count < 100000) 
  39.             {
  40.                 ret[reti++] = count / 10000 + '0';
  41.                 ret[reti++] = count / 1000 % 10 + '0';
  42.                 ret[reti++] = count / 100 % 10 + '0';
  43.                 ret[reti++] = count / 10 % 10 + '0';
  44.                 ret[reti++] = count % 10 + '0';
  45.             }
  46.             count = 0;
  47.             slow = fast;
  48.         }
  49.     }
  50.  
  51.     ret[reti++] = *slow;
  52.     if (count < 10) 
  53.     {
  54.         ret[reti++] = count + '0';
  55.     } 
  56.     else if (count >= 10 && count < 100) 
  57.     {
  58.         ret[reti++] = count / 10 + '0';
  59.         ret[reti++] = count % 10 + '0';
  60.     } 
  61.     else if (count >= 100 && count < 1000) 
  62.     {
  63.         ret[reti++] = count / 100 + '0';
  64.         ret[reti++] = count / 10 % 10 + '0';
  65.         ret[reti++] = count % 10 + '0';
  66.     }     
  67.     else if (count >= 1000 && count < 10000) 
  68.     {
  69.         ret[reti++] = count / 1000 + '0';
  70.         ret[reti++] = count / 100 % 10 + '0';
  71.         ret[reti++] = count / 10 % 10 + '0';
  72.         ret[reti++] = count % 10 + '0';
  73.     } 
  74.     else if (count >= 10000 && count < 100000) 
  75.     {
  76.         ret[reti++] = count / 10000 + '0';
  77.         ret[reti++] = count / 1000 % 10 + '0';
  78.         ret[reti++] = count / 100 % 10 + '0';
  79.         ret[reti++] = count / 10 % 10 + '0';
  80.         ret[reti++] = count % 10 + '0';
  81.     }
  82.     ret[reti] = '\0';
  83.  
  84.     int num1 = strlen(S);
  85.     int num2 = strlen(ret);
  86.  
  87.     if (num2 >= num1) 
  88.     {
  89.         return S;
  90.     } 
  91.     else 
  92.     {
  93.         return ret;
  94.     }
  95. }

这是ac代码，数字转换成字符串的方式很粗糙，大家有更好的办法可以评论

4.数组中出现次数超一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2 

1.计数法

创建一个数组初始化全0，遍历给定数组，给创建数组++，遍历创建数组，根据条件改变返回值

  1. int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) 
  2. {
  3.     int ret = 0;
  4.     int a[10000] = {0};
  5.     int i=0;
  6.     for(i=0;i<numbersLen;i++)
  7.     {
  8.         ++a[numbers[i]];
  9.     }
  10.     for(i=0;i<10000;i++)
  11.     {
  12.         if(a[i] > numbersLen/2)
  13.         {
  14.             ret = i;
  15.         }
  16.     }
  17.     return ret;
  18. }

 这是ac代码

2.特殊法

利用题目特性，我们可以设计一个计数count，记录x数据出现的次数。遍历数组，拿到numbers[i]后，进行如下操作：

1. 如果count等于0，表明该元素第一次出现，使用x记录该元素，并将count设置为1

2. 否则：如果numbers[i] == x，count++；否则count-- 上述操作结束后，x中标记的元素可能是出现次数刚好超过一般的元素

  1. int MoreThanHalfNum_Solution(int* numbers, int numbersLen ) 
  2. {
  3.     int count = 0;
  4.     int x = numbers[0];
  5.     int i=0;
  6.     for(i=0;i<numbersLen;i++)
  7.     {
  8.         if(count == 0)
  9.         {
  10.             x = numbers[i];
  11.             count++;
  12.         }
  13.         else
  14.         {
  15.             if(x == numbers[i])
  16.             {
  17.                 count++;
  18.             }
  19.             else 
  20.             {
  21.                 count--;
  22.             }
  23.         }
  24.     }
  25.  
  26.     return x;
  27. }

这是ac代码 

5.两数之和

LCR 006. 两数之和 II - 输入有序数组

给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

这题首先肯定不能用暴力枚举，因为时间有限制

下面介绍两种方法

1.左右指针法

初始两个指针，一个指向数组的第一个元素，另一个指向数组最后一个元素，将下标对应的值之和与目标数进行比较，如果大了，就让右指针向左偏移一次，如果小了，就让左指针向右偏移一次，直到得到目标结果

  1. int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
  2. {
  3.     int* str = (int*)malloc(sizeof(int)*2);
  4.     *returnSize = 2;
  5.     int i = 0;
  6.     int j = numbersSize - 1;
  7.     while(1)
  8.     {
  9.         if(numbers[i] + numbers[j] == target)
  10.         {
  11.             str[0] = i;
  12.             str[1] = j;
  13.             break;
  14.         }
  15.         else if(numbers[i] + numbers[j] < target)
  16.             i++;
  17.         else
  18.             j--;
  19.     }
  20.  
  21.     return str;
  22. }

这是ac代码，具体怎么证明这样不会错过答案，可以自行看官方题解

2.二分法

假定一个数已经找到，将数组元素都减去目标值，另一个数必然存在改变后的数组当中，且数组有序，利用二分法即可求解

  1. int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
  2. {
  3.     int* ret = (int*)malloc(sizeof(int)*2);
  4.     *returnSize = 2;
  5.     int i=0;
  6.     for(i=0;i<numbersSize - 1;i++)
  7.     {
  8.         int left = i + 1;
  9.         int right = numbersSize - 1;
  10.  
  11.         while(left <= right)
  12.         {
  13.             int mid = (left + right) / 2;
  14.             if(numbers[mid] + numbers[i] == target)
  15.             {
  16.                 ret[0] = i;
  17.                 ret[1] = mid;
  18.                 return ret;
  19.             }
  20.             else if(numbers[mid] + numbers[i] > target)
  21.             {
  22.                 right = mid - 1;
  23.             }
  24.             else
  25.             {
  26.                 left = mid + 1;
  27.             }
  28.         }
  29.     }
  30.  
  31.     return ret;
  32. }

这是ac代码

6.几道难题

394. 字符串解码

43. 字符串相乘

这两道题有些难懂，待我功力深一点了再回头解决，明天开始继续C++学习 

今天的博客就到这里了，后续内容明天分享,最近因为考试周原因不能更新太多内容,等考试周结束了再"快马加鞭"

新手第一次写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！！！ 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/65896
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号