C++算法笔记

143 阅读 0 评论 95 点赞

我是靠谱客的博主迷你蓝天，这篇文章主要介绍C++算法笔记，现在分享给大家，希望可以做个参考。

1、题目描述

计算字符串最后一个单词的长度，单词以空格隔开。

输入描述:

一行字符串，非空，长度小于5000。

输出描述:

整数N，最后一个单词的长度。

示例1

输入：hello world

输出：5

方法一：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
string input;
vector<string>arr;
while (cin >> input)
{
arr.push_back(input);
}
cout << arr[arr.size() - 1].length() << endl;
return 0;
}

方法二：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
while(getline(cin,s)){
int n=0,flag=1;
for(int i=s.length()-1;i>=0;--i){//倒着计算
if(flag && s[i]==' '){//如果末尾有空格，先清除末尾空格
continue;
}
else if(s[i]!=' '){
flag = 0;
++n;
}
else{
break;
}
}
cout << n << endl;
}
return 0;
}

2、题目描述

写出一个程序，接受一个由字母和数字组成的字符串，和一个字符，然后输出输入字符串中含有该字符的个数。不区分大小写。

输入描述:

输入一个有字母和数字以及空格组成的字符串，和一个字符。

输出描述:

输出输入字符串中含有该字符的个数。

示例1

输入：ABCDEF A 输出：1

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string>
#include<ctype.h>
using namespace std;
int main()
{
string str;
while (getline(cin,str))
{
char s;
cin >> s;
int count = 0;
for (int i = 0; i < str.size(); i++)
{
if (tolower(s) == tolower(str[i])) //都转换成小写进行比较
count++;
}
cout << count << endl;
cin.ignore();
}
return 0;
}

3、C++中substr函数的用法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <string>
using namespace std;
int main()
{
//string str("123456abc"); string两种初始化方式均可以
string str = "123456abc";
string a = str.substr(6, str.size()); // substr（）可以获得指定字符串
cout << a << endl;
//输出abc
return 0;
}

4、

题目描述

•连续输入字符串，请按长度为8拆分每个字符串后输出到新的字符串数组；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。

输入描述:

连续输入字符串(输入2次,每个字符串长度小于100)

输出描述:

输出到长度为8的新字符串数组

输入：abc
123456789

输出：abc00000
12345678
90000000

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string>
using namespace std;
void fuck(string str)
{
if (str == "")
//明确分几种情况
return;
if (str.size() <= 8)
{
str.append(8 - str.size(), '0');
cout << str << endl;
return;
}
cout << str.substr(0, 8) << endl;
fuck(str.substr(8, str.size()));//递归调用
}
int main()
{
string str1, str2;
cin >> str1 >> str2;
fuck(str1);
fuck(str2);
return 0;
}

5、合并表并记录

题目描述

数据表记录包含表索引和数值，请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。

输入描述

先输入键值对的个数
然后输入成对的index和value值，以空格隔开

输出描述:

输出合并后的键值对（多行）

示例1

输入

4
0 1
0 2
1 2
3 4

输出

0 3
1 2
3 4
这道题的方法有很多种，其中最关键的一点是数据结构，也就是说你打算用什么样的方式来存放表每一项的索引和键值，最容易想到的一种方法是使用结构体，这个结构体包含两项分别为索引和键值，于是整个表就是这样的一个结构体数组，这种方法很常规，但是其实有一个更为简单的小技巧，我们不需要去定义结构体，只使用普通的数组就可以完成，我们需要处理的数据有两项，一项是index索引，一项是键值value，我们可以把index用数组下标来存放，而键值用数组元素的值来存放，这样我们存放的数据在数组中是不连续的，但是不论是代码还是思路都会大大简化，代码如下

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int
main()
{
int Key_Value[10000]={0},Key,Value,Number,i;
cin>>Number;
for(i=0;i<Number;i++)
{
cin>>Key>>Value;
Key_Value[Key]+=Value;
}
for(i=0;i<10000;i++)
{
if(Key_Value[i]!=0)
cout<<i<<"
"<<Key_Value[i]<<endl;
}
return 0;
}

链接：https://www.nowcoder.com/questionTerminal/de044e89123f4a7482bd2b214a685201
来源：牛客网

以上的这种方法虽然比较简单，但是中间有一个小Bug，在这里虽然可以通过所有测试，但是必须是在相同索引项最后的键值和不为0的情况下才能正确，而这里牛客的测试数据最后的输出结果的键值都是非0值，所以也通过了，但是更严谨地来应该采用一种更为常规的方法，也就是用结构体来设计算法，这样输入的每一项是一种连续存放的数据结构，相对第一种方法来说代码更复杂一点，但是更具有普适性，代码如下

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
using namespace std;
struct Key_Value_Pair
{
int index;
int value;
};
int main()
{
Key_Value_Pair Part[1000];
int Key_Value_Pairs_Num,i,j,k;
cin>>Key_Value_Pairs_Num;
for(i=0;i<Key_Value_Pairs_Num;i++)
cin>>Part[i].index>>Part[i].value;
for(i=0;i<Key_Value_Pairs_Num;i++)
{
for(j=i+1;j<Key_Value_Pairs_Num;j++)
{
if(Part[i].index==Part[j].index)
{
Part[i].value+=Part[j].value;//对第二键值求和，累加在第一次出现的键值项上，下一步进行重复索引的删除操作
for(k=j;k<Key_Value_Pairs_Num-1;k++)
Part[k]=Part[k+1];
j--;
Key_Value_Pairs_Num--;
}
}
}
//下面进行排序操作
Key_Value_Pair Temp;//定义一个结构体，作为交换操作的中间值
for(i=0;i<Key_Value_Pairs_Num-1;i++)
{
for(j=0;j<Key_Value_Pairs_Num-1-i;j++)
{
if(Part[j].index>Part[j+1].index)
{
Temp=Part[j];
Part[j]=Part[j+1];
Part[j+1]=Temp;
}
}
}
for(i=0;i<Key_Value_Pairs_Num;i++)
cout<<Part[i].index<<" "<<Part[i].value<<endl;
return 0;
}

6、以下代码是把一个字符串倒序，如“abcd”倒序后变为“dcba”。

方法一：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
char *src = "hello,world";
int len = strlen(src);
char *dest = (char *)malloc(len + 1); //要为分配一个空间
char *d = dest;
char *s = &src[len - 1]; //指向最后一个字符
while ( len-- != 0 )
*d++ = *s--;
*d = 0; //尾部要加
printf("%sn", dest);
free(dest);// 使用完，应当释放空间，以免造成内存汇泄露
return 0;
}

方法二：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
char str[] = "hello,world";
int len = strlen(str);
char t;
for (int i = 0; i < len; i++)
{
t = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = t;
}
printf("%s", str);
return 0;
}

7、实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

复制代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
string toLowerCase(string str) {
for(auto &c:str){
//对字符串str中的每个字符
c = tolower(c);
}
return str;
}
};

8、汉诺塔用递归实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
void hanoi(int n, char A, char B, char C)
{
if(n==1){
printf("%c -> %cn",A,C);
}
else{
hanoi(n-1,A,C,B);
printf("%c -> %cn",A,C);
hanoi(n-1,B,A,C);
}
}
int main(){
hanoi(3,'A','B','C');
}

9、求数组最大值

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int findMax(int arr[], int n){
int max = arr[0];
int i;
for (i=1;i<n;i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
int main(){
int arr[10] = {8,2,3,4,6,5,1,10,9,7};
int m= findMax(arr,10);
printf("m = %dn", m);
return 0;
}

用递归实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
int findMax(int arr[], int L, int R){
if(L == R){
return arr[L];
}
else{
int a = arr[L];
int b = findMax(arr, L+1, R);
if (a > b)
{
return a;
}
else
{
return b;
}
}
}
int main(){
int arr[10] = {8,2,3,4,6,5,1,10,9,7};
int m= findMax(arr,0,9);
printf("m = %dn", m);
return 0;
}