初阶牛之牛客网刷题集（1）
前言
记录一下牛牛自己在牛客网上刷到的一些题目.分享一下牛牛的解题思路,希望可以帮到大家.
目录
- 前言
- 1.母牛的故事
- 解题思路：
- 代码实现：
- 2.替换空格
- 解题思路:
- 代码实现
- 3.二进制中1的个数
- 解题思路
- 代码实现
- 结语
1.母牛的故事
题目链接:传送门
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
输入描述:
输入数据由多个测试实例组成，每个测试实例占一行，
包括一个整数n(0输出描述:
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。
解题思路：
因为前四年都是由一头成年牛生产小牛牛，所以前四年的数量分别是
{1，2，3，4，}，从第5年开始则不同，因为第2年生产的小牛牛已经长大了，也可以生产了。
我们以第五年为例：
第5年牛牛数量=原来牛的数量+新增牛的数量
原来牛的数量：指上一年的数量，即第四年牛牛的数量。
新增牛的数量：第五年有哪些牛出生就是新增牛的数量，显然此时第2年牛的数量就为新增牛的数量，因为到第五年的时候第2年所有的牛都是成年牛了，所以都可以生小牛。
第n年牛牛的数量为=原来牛的数量（n-1年）+新增牛的数量（n-3年）
重点：很多小伙伴还是不理解为什么是n-3年，
因为
第一年： n-3题目看仔细哦，小牛是年初出生的，所以到n-3年结束，这里也是一年哦。
第二年 ：n-2
第三年 ：n-1
第四年 ： n（年初生产了）
代码实现：
#include
#define N 55
int main()
{//定义一个一维数组，用于存放每一年牛的数量int a[N] = {0,1,2,3,4}；int i = 0, n = 0;while (scanf("%d", &n) != EOF)//用于多组输入{for (i = 5; i <= n; i++)//从第五年开始，有小牛出生{//去年牛的数量+新出生的小牛的数量a[i] = a[i - 1] + a[i- 3];}printf("%d\n", a[n]);//输出这一年牛的数量}return 0;
}
最后：如有不了解多组输入的小伙伴。
请参照：scanf(“%d”, &n) != EOF，
2.替换空格
题目链接:传送门
描述:
请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
数据范围:1000 \0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。
示例1
输入：
"We Are Happy"
复制
返回值：
"We%20Are%20Happy"
复制
示例2
输入：
" "
复制
返回值：
"%20"
解题思路:
- 首先,我们观察到返回值是一串字符,所以我们可以创建一个足够大的数组来存储返回字符串.
- 其次题目要求是将目标字符串中的“空格”替换为“%20”,这里特别注意的是“%20“是三个字符(‘%’,‘2’,‘0’组成).所以我们不能直接将"空格"赋值为”%20”.
3.我们遍历目标字符数组(字符串)时,遇到空格,就将空格和空格后的两个字符都占据,这样就可以有三个字符空间来分别存储’%’ ‘2’ ‘0’.了
4.最后将返回值字符串返回即可.
代码实现
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @return string字符串*/
char* replaceSpace(char* s ) {// write code herechar ret[10000]={0};//创建一个用于存放返回字符串的数组int i=0;for(i=0;*s!='\0';i++){if(*s==' ')//如果遇到空格，就用三个字符来存储%20{ret[i]='%';ret[i+1]='2';ret[i+2]='0';i=i+2;}else{ret[i]=*s;//不是空格则直接存储}s++;}return ret;
}
3.二进制中1的个数
题目链接:传送门
题目描述:
输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
数据范围：- 2^{31} <= n <= 2^{31}-1−2
即范围为:-2147483648<= n <= 2147483647−2147483648<=n<=2147483647
示例1
输入：
10
复制
返回值：
2
复制
说明：
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010
,其中有两个1。
示例2
输入：
-1
复制
返回值：
32
复制
说明：
负数使用补码表示 ，-1的32位二进制表示为
1111 1111 1111 1111 1111 1111 1111 1111，其中32个1
解题思路
方法1:
当一个数n&1的时候,我们就可以得到n这个数的最低位.是否为1,为1则会返回1,反之返回0.
例如:
我们可以用">>"(逻辑右移操作符)每次移动一位后&1,判断最后一位是否为1.
方法2:
这个方法很巧妙,其实当我们用n&n-1的时候,每次都会减少二进制中的一个1.直到n为0;
例如:53
第一次相&
第二次相&
第三次相&
第四次相&
代码实现
//方法1
int NumberOf1(int n ) {
int count=0,i=0;for (i = 0; i < 32; i++){if (1 == ((n >> i) & 1))//每次移动i个位置{count++;}}return count;
}
//方法2
int NumberOf1(int n ) {int count = 0;while (n){n&=(n - 1);count++;}return count;
}
结语
希望牛牛可以坚持刷题,锻炼自己的思维能力,和各位小伙伴们逐渐成长,共同进步,早日成为大牛.
