菜鸟刷题Day3

⭐作者：别动我的饭
⭐专栏：菜鸟刷题
⭐标语：悟已往之不谏，知来者之可追

一.字符串压缩：面试题 01.06. 字符串压缩 - 力扣（LeetCode）

描述

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

---

解题思路

遍历字符串，统计字符的个数就行，但是将数字转成字符串会有些麻烦，其实给每一位数字加上’\0’就可以得到相应的数字字符。可以考虑这个办法。

int itoa(char*str,int num)
{//简单的一个数字转字符串函数，将转换后的数字字符串放到str空间中char tmp[16]={0};int count=0;while(num){tmp[count++]=(num%10)+'0';//将个位数字转换为对应数字字符放到tmp空间中（逆序的）num/=10;}for(int i=0;i<count;i++){str[i]=tmp[count-i-1];//逆序将数字字符放入传入的str空间中}
return count;//返回转换的数字字符串长度
}
char*compressString(char*S)
{int len=strlen(S);//申请新的空间，注意空间有可能所需会变大，比如abc->a1b1c1char*newstr=(char*)calloc(len,3);int pos=0;char*s=S;while(*s!='\0'){char*n=s+1;while(*n!='\0'&&*n==*s)n++;//走到下一个不同字符处停下int l=n-s;//相同字符的长度newstr[pos++]=*s;//先赋值对应字符pos+=itoa(newstr+pos,l);//编写了一个数字转字符函数，将数字放到字符串空间指定位置s=n;//下一个不同的字符处}return strlen(newstr)>=len?S:newstr;
}

但是作为一个手搓过string的博主，这种题目不来占个string的便宜说的过去吗？

首先介绍一个库函数：to_string这是一个将数字转为数字字符的库函数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NR29I3cA-1679378671546)(C:\Users\羽北冥\AppData\Roaming\Typora\typora-user-images\image-20230321132933270.png)]

在统计字符的时候，如果下一个字符和当前字符不一致或者说已经到结尾了的时候，该字符也就结束了。

class Solution {
public:string compressString(string S) {string ans="";int cnt=0;int len=S.size();//string有效字符用sizefor(int i=0;i<len;i++){cnt++;if(i==len-1||S[i]!=S[i+1])//到结尾或者下一个字符和该字符不相同就结束了{ans+=S[i]+to_string(cnt);cnt=0;//从头开始计数}}return ans.size()<len?ans:S;}
};

---

二.配对交换：面试题 05.07. 配对交换 - 力扣（LeetCode）

描述

配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）

---

解题思路

这没什么骚操作，就当老实人呗。通过按位与分别拿到一个数的奇数位和偶数位，再将奇数位左移一位+偶数位右移一位，就可以达到最后的结果。

int exchangeBits(int num){int odd=0b10101010101010101010101010101010;//二进制int jdd=0b01010101010101010101010101010101;odd&=num;jdd&=num;int ret=(odd>>1)+(jdd<<1);return ret;}

---

三.递归乘法：面试题 08.05. 递归乘法 - 力扣（LeetCode）

描述

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

---

解题思路

a*b也就是a个b相加的结果，所以只要递归调用加法就行了。如果有一个数为0，那就直接返回0，有1就直接返回那个数本身。没有这些特殊数，那就只好递归调用咯。递归要有限制条件，这题的限制条件是，我们只需要调用a/b次递归。

int multiply(int A, int B){if(B==0)return 0;if(B==1)return A;return A+multiply(A,B-1);}

---

四.挑7：挑7_牛客题霸_牛客网 (nowcoder.com)

描述

输出 1到n之间 的与 7 有关数字的个数。

一个数与7有关是指这个数是 7 的倍数，或者是包含 7 的数字（如 17 ，27 ，37 … 70 ，71 ，72 ，73…）

---

解题思路

这个题目要注意的地方在于，存在那种既是七的倍数又包含七的数字，所以判断的时候用||对这两个条件一起判断会比较好，否则还要做额外处理。将这个数与七取模结果为零就表明这个数是七的倍数，至于包含七就只需要不断除十模十即可。

#include <stdio.h>int main() 
{int n=0;int count=0;while(scanf("%d",&n)!=EOF){for(int i=7;i<=n;i++)//直接从7开始，因为之前不可能有包含7或者7的倍数{int tmp=i;while(tmp>0){if(tmp%10==7)break;tmp/=10;}if(i%7==0||tmp%10==7){count++;}}printf("%d",count);}return 0;
}

---

人们总是高估短期努力带来的提升，而小看长期坚持带来的提升。今天是刷题第三天了，你还在坚持吗？