机试常用算法总结

进制转换专题

使用sscanf将字符数组转为整型的办法

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
#include <cstdio>
#include <cstring>
//手动去除逗号的办法
void dispose(char a[])
{
char temp[15]={0};
int pos=0;
for(int i=0;i<strlen(a);i++)
if(a[i]!=',')
temp[pos++]=a[i];
for(int i=0;i<strlen(a);i++)
a[i]=temp[i];
}
/*
使用string处理的办法,更简洁
int dealStr(string str){
//好办法!!
while(str.find(',')!=string::npos){
size_t pos=str.find(',');
str.erase(pos,1);
}

//好函数
return atoi(str.c_str());
}
*/
int main()
{
char A[15],B[15];
while(scanf("%s %s",A,B)!=EOF)
{
int a,b;
dispose(A);
dispose(B);
//如何将字符数组转为输出成a,b整型
sscanf(A,"%d",&a);
sscanf(B,"%d",&b);
printf("%d\n",a+b);
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
}
return 0;
}

字符串到整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>
#include <cstdlib>
//atoi和itoa在头文件cstdlib中

//居然直接stoi就可以做到了!!
int num=stoi(temp);

int StringToInt(string str){
return atoi(str.c_str());
}
//stream方法
int str_to_int(const string &string_temp){
int temp;
stringstream stream(string_temp);
stream>>temp;
return temp;
}

整数到字符串(十进制转字符串)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <string>
#include <cstdlib>

//相当于to_string
string IntToString(int num){
char str[100];
//itoa()函数有3个参数:第一个参数是要转换的数字,第二个参数是要写入转换结果的目标字符串,第三个参数是转移数字时所用 的基数。在上例中,转换基数为10。10:十进制;2:二进制...
return itoa(num,str,10);
}
//有相同效果!!sprintf,<cstdlib>
//int sprintf(char *str, const char *format, ...)
//format -- 这是字符串,包含了要被写入到字符串 str 的文本。它可以包含嵌入的 format 标签,format 标签可被随后的附加参数中指定的值替换,并按需求进行格式化。format 标签属性是 %[flags][width][.precision][length]specifier,具体讲解如下:
char s[5],n[5];
sprintf(s,"%d",i);
sprintf(n,"%d",i*9);
//sstream相同效果
#include <sstream>
stringstream ss;
string s;
int a;
ss << a;
s = ss.str();

#include <cstdio>
#include <cstring>
int main()
{
char s[4],n[4];
for(int i=100;i<=999;i++)
{
for(int j=100;j<=999;j++)
{
if(i+j==532)
{
//将整数问题转为输出字符的问题,就很棒
sprintf(s,"%d",i);
sprintf(n,"%d",j);
if(s[1]==n[0]&&s[2]==n[1]&&s[2]==n[2])
printf("%c %c %c\n",s[0],s[1],s[2]);
}
}
}
return 0;
}

//sstream版整型到字符串
stringstream sstream;
string strResult;
int nValue = 1000;

// 将int类型的值放入输入流中
sstream << nValue;
// 从sstream中抽取前面插入的int类型的值,赋给string类型
sstream >> strResult;

cout << "[cout]strResult is: " << strResult << endl;
printf("[printf]strResult is: %s\n", strResult.c_str());

//to_string版本
to_string的头⽂件是 #include <string> , to_string最常⽤的就是把⼀个int型变量或者⼀个数字转
化为string类型的变量,当然也可以转doublefloat等类型的变量,这在很多PAT字符串处理的题⽬
中很有⽤处,以下是示例代码:

十进制转其他进制

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
#include <string>
#include <cstdlib>

string DecToOther(int dec){
char str[100];
return itoa(dec,str,16);
//十进制转十六进制保存在str中
}

string decToString(int n){
string str;
while(n!=0){
char c=(n%2)+'0';
str=c+str;
n=n/2;
}
return str;
}

#include <stdio.h>
main()
{
int a = 0 ;
printf ("Please enter a decimal number:") ;
scanf ("%d",&a) ;
//更简单办法
printf ("%d's octal number is %o\n",a,a) ;
}

其他进制转十进制,strtol最容易搞忘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <string>
#include <cstdlib>

int OtherToDec(string str){
const char *s=str.c_str();
char *stop;
return strtol(s,&stop,8);
//8进制转十进制
}
//八进制转十进制

int otherToDec(string str){
int num=0;
int len=str.size();
for(int i=len-1;i>=0;i--){
num=num+(str[i]-'0')*pow(2,len-1-i);
}
return num;
}

任意进制函数转换

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 <iostream>
#include <cstdlib>
#include <string>
using namespace std;

int OtherToDec(string str,int n){
const char *s=str.c_str();
char *stop;
return strtol(s,&stop,n);
}
string DecToOther(int dec,int m){
char str[100];
return itoa(dec,str,m);
}
int main()
{
int m,n;
string inputStr;
while(cin>>n>>inputStr>>m){
int temp=OtherToDec(inputStr,n);
string ans;
ans=DecToOther(temp,m);
cout<<ans<<endl;
}
}

strtol和itoa配合使用转换实例

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
47
48
49
50
51
52
/*给出两个不大于65535的非负整数,判断其中一个的16位二进制表示形式,是否能由另一个的16位二进制表示形式经过循环左移若干位而得到。 循环左移和普通左移的区别在于:最左边的那一位经过循环左移一位后就会被移到最右边去。比如: 1011 0000 0000 0001 经过循环左移一位后,变成 0110 0000 0000 0011, 若是循环左移2位,则变成 1100 0000 0000 0110*/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

string decToString(int n){

char str[100];
//这个基数是目标
return itoa(n,str,2);
}

int otherToDec(string str){
char *stop;
//基数搞错了,基数指的是当前
return strtol(str.c_str(),&stop,2);
}

int main()
{
int n;
while(cin>>n){
int m;
cin>>m;
string str=decToString(n);
while(str.size()<16){
str='0'+str;
}
str=str+str;
vector<string> ans;
//这样循环就不会包括100了!!
for(int i=1;i<16;i++){
string temp=str.substr(i,16);
ans.push_back(temp);
}
bool flag=false;
for(int i=0;i<ans.size();i++){
int temp=otherToDec(ans[i]);
if(m==temp){
flag=true;
break;
}
}

if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

strtol函数用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long int strtol(const char *str, char **endptr, int base)
str -- 要转换为长整数的字符串。
endptr -- 对类型为 char* 的对象的引用,其值由函数设置为 str 中数值后的下一个字符。
base -- 基数,必须介于 236(包含)之间,或者是特殊值 0
#include <stdio.h>
#include <stdlib.h>

int main()
{
char str[30] = "2030300 This is test";
char *ptr;
long ret;

ret = strtol(str, &ptr, 10);
printf("数字(无符号长整数)是 %ld\n", ret);
printf("字符串部分是 |%s|", ptr);

return(0);
}
数字(无符号长整数)是 2030300
字符串部分是 | This is test|

手工完成其他进制转十进制,十进制转其他进制

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
#include <iostream>
#include <string>
using namespace std;
int main(){
int a,b;
string str;
//在这里使用c输入时
// wh i l e ( s c an f ( " %d%s%d " , &a , s t r , &b ) ! = EOF ) {
while(cin>>a>>str>>b){

int tmp=0,c=1,lenth=str.size();

for(int i=lenth-1;i>=0;i--){
int x;
//计算该位数字
if(str[i]>='0'&&str[i]<='9'){
x=str[i]-'0';

}
else if(str[i]>='a'&&str[i]<='z'){
x=str[i]-'a'+10; //多想了。。a代表的是10
}
else{
x=str[i]-'A'+10;
}
tmp=tmp+x*c;
c=c*a;
}

string ans;
int size=0;
do{
int x=tmp%b;
//计算当前位的数字
ans[size++]=(x<10)?x+'0':x-10+'A';
tmp=tmp/b;
}while(tmp);
//while后面加分号
for(int i=size-1;i>=0;i--){
cout<<ans[i];
}
cout<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <string>
using namespace std;
int main(){
int res[1000];
string str;

while(cin>>str){
int len=str.size();
int k=str.size();
int num=0;
while(len>0){
res[num++]=(str[k-1]-'0')%2;
//取余之后,得要模拟出除以2的效果!!
int carry=0;
for(int i=0;i<k;i++){
int s=((str[i]-'0')+10*carry)/2;
carry=(str[i]-'0')%2;
str[i]=s+'0';
}
//除法会产生位数减少
while(str[k-len]=='0') len--;
}
for(int i=num-1;i>=0;i--) cout<<res[i];
cout<<endl;
}
return 0;
}
//终极无敌循环班,m进制转n进制,大数,无限制
#include <cstdio>
#include <cstring>
struct bign
{
int d[1000];
int len;
bign()
{
memset(d,0,sizeof(d));
len=0;
}
};
bign change(char s[])
{
bign a;
a.len=strlen(s);
for(int i=0;i<a.len;i++)
{
if(s[a.len-i-1]>='0'&&s[a.len-i-1]<='9')
a.d[i]=s[a.len-i-1]-'0';
else if(s[a.len-i-1]>='A'&&s[a.len-i-1]<='Z')
a.d[i]=s[a.len-i-1]-'A'+10;
}
return a;
}
int main()
{
int m,n;
while(~scanf("%d %d",&m,&n))
{
char a[1000]={'\0'};
char out[1000]={'\0'};
scanf("%s",a);
bign b=change(a);
int k=b.len,len=b.len,num=0;
while(len>0)
{
int c=0;
for(int i=len-1;i>=0;i--)
{
int s=(b.d[i]+m*c)/n;
//终于明白了!!,c是循环计算,得出最后结果!!我傻了!!
c=(b.d[i]+m*c)%n;
b.d[i]=s;
}
if(c>=0&&c<=9)
out[num++]=c+'0';
if(c>=10&&c<=36)
out[num++]=c+'a'-10;
while(b.d[len-1]==0)
len--;
}
for(int i=num-1;i>=0;i--)
printf("%c",out[i]);
printf("\n");
}
return 0;
}
实际安排数字运用的范例
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct bign
{
int d[1010];
int len;
bign()
{
memset(d,0,sizeof(d));
len=0;
}
}big[110];
bign change(char s[])
{
bign a;
a.len=strlen(s);
for(int i=0;i<a.len;i++)
a.d[i]=s[a.len-i-1]-'0';
return a;
}
void trans(int a[],int n)
{
for(int i=0;i<n/2;i++)
{
int temp=a[i];
a[i]=a[n-1-i];
a[n-1-i]=temp;
}
}
int main()
{
char s[1010];
int mid[10010]={0},out[1010]={0};
while(~scanf("%s",s))
{
bign c=change(s);
int len=0;
while(c.len>0)
{
int re=0;
//关键是这个算法很棒!!,高位放在末尾,先动高位,高位除以成为0,可以直接删去
for(int i=c.len-1;i>=0;i--)
{
int temp=c.d[i]+re*10;
c.d[i]=temp/2;
re=temp%2;
}
mid[len++]=re;
while(c.d[c.len-1]==0)
c.len--;
}
int sum=0;
trans(mid,len);
while(len>0)
{
int re=0;
for(int i=len-1;i>=0;i--)
{
int temp=mid[i]+re*2;
mid[i]=temp/10;
re=temp%10;
}
out[sum++]=re;
while(mid[len-1]==0)
len--;
}
for(int i=sum-1;i>=0;i--)
printf("%d",out[i]);
printf("\n");
}
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
26
27
28
29
30
31
32
33
34
35
36
37

#include<iostream>
#include<string>
#define N 4000
using namespace std;
int conversion(int d[],int data[],int n,int x,int y){
int size=0;
for(int i=0;i<n;){
int k=0;
for(int j=i;j<n;j++){
int t=(d[j]+k*x)%y;
d[j]=(d[j]+k*x)/y;
k=t;
}
data[size++]=k;
while(d[i]==0) i++;
}
return size;
}
int main(){
string s;
int d[N],data[N];
while(cin>>s){
for(int i=0;i<s.length();i++)
d[i]=s[i]-'0';
int n=conversion(d,data,s.length(),10,2);
int start;
for(start=0;data[start]==0;start++);
for(int i=start;i<n;i++)
data[i-start]=data[i];
n=conversion(data,d,n-start,2,10);
for(int i=n-1;i>=0;i--)
cout<<d[i];
cout<<endl;
}
return 0;
}

容器函数使用专题

string.h库函数memset()置零

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
47
48
49
50
51
52
53
char *strcpy(char *dest, const char *src)
#include <stdio.h>
#include <string.h>

int main()
{
char src[40];
char dest[100];

memset(dest, '\0', sizeof(dest));
strcpy(src, "This is runoob.com");
strcpy(dest, src);

printf("最终的目标字符串: %s\n", dest);

return(0);
}

char *strcat(char *dest, const char *src)
char src[50], dest[50];

strcpy(src, "This is source");
strcpy(dest, "This is destination");

strcat(dest, src);

printf("最终的目标字符串: |%s|", dest);

return(0);

int strcmp(const char *str1, const char *str2)
char str1[15];
char str2[15];
int ret;


strcpy(str1, "abcdef");
strcpy(str2, "ABCDEF");

ret = strcmp(str1, str2);

if(ret < 0)
{
printf("str1 小于 str2");
}
else if(ret > 0)
{
printf("str2 小于 str1");
}
else
{
printf("str1 等于 str2");
}

reverse()逆置函数algorithm头文件

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
vector<int> s;
int x;
for(int i=0;i<10;i++){
cin>>x;
s.push_back(x);
}
reverse(s.begin(),s.end());

for(int i=0;i<10;i++){
cout <<s[i] << endl;
}

return 0;
}
// reverse algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::reverse
#include <vector> // std::vector

int main () {
std::vector<int> myvector;

// set some values:
for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

std::reverse(myvector.begin(),myvector.end()); // 9 8 7 6 5 4 3 2 1

// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';

return 0;
}

strrev逆置字符数组

1
2
3
4
5
6
7
8
9
10
11
#include<stdio.h>
#include<string.h>

int main()
{
char s[]="hello";
strrev(s);
puts(s);

return 0;
}

排序sort函数

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
#include <algorithm>
#include <vector>

struct Node{
int x;
int y;
//或在此处使用重载
bool operator < (const Node &A) const{
if(x=A.x) return x<A.x;
else return y<A.y;
}
};

bool com(Node &a,Node &b){
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}

int main(){
vector<Node> vec;
//sort在vector容器中用法,在数组当中是sort(ans.ans+n);
sort(vec.begin(),vec.end(),com);
return 0;
}

//sort的其他写法,直接构造函数
sort(raw.begin(),raw.end(),[](const string &a,const string &b)->bool{return (a+b < b+a);});

stable_sort()稳定排序

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
//学生成绩排序
#include<bits/stdc++.h>
using namespace std;
int n, bs, score[500], r[500];
bool cmp(int i,int j){
return score[i]<score[j];
}
bool cmp1(int i,int j){
return score[i]>score[j];
}
int main() {
string name[500];
int i,j,k;
while(cin >>n>>bs){
for(i=0;i<n;i++){
r[i]=i;
cin >>name[i]>>score[i];
}
if(bs==1)
stable_sort(r,r+n,cmp);
else
stable_sort(r,r+n,cmp1);
for(i=0;i<n;i++){
int t = r[i];
cout << name[t]<<' '<<score[t]<<endl;
}
}
return 0;
}

algorithm头文件next_permulation函数(全排列)

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
47
48
49
50
// next_permutation example
#include <iostream> // std::cout
#include <algorithm> // std::next_permutation, std::sort

int main () {
int myints[] = {1,2,3};

std::sort (myints,myints+3);

std::cout << "The 3! possible permutations with 3 elements:\n";
do {
std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
} while ( std::next_permutation(myints,myints+3) );

std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

return 0;
}
output:
The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3

int main()
{
string temp;
while(cin>>temp)
{
do{
cout<<temp<<endl;
}while(next_permutation(temp.begin(),temp.end()));
cout<<endl;
}
return 0;
}
样例输入
xyz

样例输出
xyz
xzy
yxz
yzx
zxy
zyx

vector容器insert函数

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
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
string str;
int n;
while(cin>>n){
vector<string> nameArr;
for(int i=0;i<n;i++){
string name;
cin>>name;
//头部插入,倒序输出
nameArr.insert(nameArr.begin(),name);
if(i<3){
for(int j=0;j<nameArr.size();j++){
cout<<j+1<<"="<<nameArr[j]<<" ";
}
}else{
for(int j=0;j<4;j++){
cout<<j+1<<"="<<nameArr[j]<<" ";
}
}
cout<<endl;
}
}
return 0;
}

vector容器pop_back(),erase()方法删除元素

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
---- 向量容器vector的成员函数pop_back()可以删除最后一个元素.

---- 而函数erase()可以删除由一个iterator指出的元素,也可以删除一个指定范围的元素。

---- 还可以采用通用算法remove()来删除vector容器中的元素.

---- 不同的是:采用remove一般情况下不会改变容器的大小,而pop_back()与erase()等成员函数会改变容器的大小。
1、pop_back()

void pop_back();
Delete last element
Removes the last element in the vector, effectively reducing the container size by one.
2、erase()
C++11
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);
删除指定位置的一个元素或删除指定范围内的元素
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> vec;
    for(int i=0;i<10;i++)
    {
        vec.push_back(i);
    }
    vec.erase(vec.begin()+5);//erase the 6th element
    vec.erase(vec.begin(),vec.begin()+3);
    for(int i=0;i<vec.size();i++)
    {
        cout<<vec[i]<<' ';
    }
    cout<<endl;
    system("pause");
    return 0;
}

string容器实用函数

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
#include <iostream>
#include <string>
#include <iterator>
using namespace std;

int main(){
string a="xxxyyy";
string b="zzz";
//substr要好好研究下
string s2=a.substr(startpos,n);//取子串
string::size_type n=a.find("yy");
a.find("yyx"); //返回string::npos
string s3=a.replace(0,3,"fff"); //替换fffyyy
string::iterator p=a.insert(a.begin(),'_');
a.insert(a.find('y'),"_str_"); //在第一个找到"y"的下标前面插入一个指定字符
//begin用法
// sorts vec in "normal" order
sort(vec.begin(), vec.end());
// sorts in reverse: puts smallest element at the end of vec
sort(vec.rbegin(), vec.rend());
}

string c;
while(1){
cin>>c;
if(*(c.end()-1)== '*'){ //c.end() ;是一个迭代器,是个指针,前面加个* 就0k
break;
}
}

string::substr方法总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// string::substr
string substr (size_t pos = 0, size_t len = npos) const;
pos:要作为子字符串复制的第一个字符的位置。如果等于字符串长度,则函数返回空字符串。如果它大于字符串长度,则抛出范围。注意:第一个字符用0(不是1)表示。
len:要包含在子字符串中的字符数(如果字符串较短,则使用尽可能多的字符)。字符串::npos的值表示字符串结束之前的所有字符。

#include <iostream>
#include <string>

int main ()
{
std::string str="We think in generalities, but we live in details.";
// (quoting Alfred N. Whitehead)

std::string str2 = str.substr (3,5); // "think"

std::size_t pos = str.find("live"); // position of "live" in str

std::string str3 = str.substr (pos); // get from "live" to the end

std::cout << str2 << ' ' << str3 << '\n';

return 0;
}

erase删除方法总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    string str = "hello c++! +++";
// 从位置pos=10处开始删除,直到结尾
// 即: " +++"
str.erase(10);
cout << '-' << str << '-' << endl;
// 从位置pos=6处开始,删除4个字符
// 即: "c++!"
str.erase(6, 4);
cout << '-' << str << '-' << endl;

//删除迭代器[first, last)区间的所有字符,返回一个指向被删除的最后一个元素的下一个字符的迭代器.

string str = "hello c++! +++";
// 删除"+++"前的一个空格
str.erase(str.begin()+10);
cout << '-' << str << '-' << endl;
// 删除"+++"
str.erase(str.begin() + 10, str.end());
cout << '-' << str << '-' << endl;

find方法总结

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
string (1)	
size_t find (const string& str, size_t pos = 0) const;
c-string (2)
size_t find (const char* s, size_t pos = 0) const;
buffer (3)
size_t find (const char* s, size_t pos, size_t n) const;
character (4)
size_t find (char c, size_t pos = 0) const;

str
Another string with the subject to search for.
pos
Position of the first character in the string to be considered in the search.
If this is greater than the string length, the function never finds matches.
Note: The first character is denoted by a value of 0 (not 1): A value of 0 means that the entire string is searched.
s
Pointer to an array of characters.
If argument n is specified (3), the sequence to match are the first n characters in the array.
Otherwise (2), a null-terminated sequence is expected: the length of the sequence to match is determined by the first occurrence of a null character.
n
Length of sequence of characters to match.
c
Individual character to be searched for.

// string::find
#include <iostream> // std::cout
#include <string> // std::string

int main ()
{
std::string str ("There are two needles in this haystack with needles.");
std::string str2 ("needle");

// different member versions of find in the same order as above:
std::size_t found = str.find(str2);
if (found!=std::string::npos)
std::cout << "first 'needle' found at: " << found << '\n';

found=str.find("needles are small",found+1,6);
if (found!=std::string::npos)
std::cout << "second 'needle' found at: " << found << '\n';

found=str.find("haystack");
if (found!=std::string::npos)
std::cout << "'haystack' also found at: " << found << '\n';

found=str.find('.');
if (found!=std::string::npos)
std::cout << "Period found at: " << found << '\n';

// let's replace the first needle:
str.replace(str.find(str2),str2.length(),"preposition");
std::cout << str << '\n';

return 0;
}

first 'needle' found at: 14
second 'needle' found at: 44
'haystack' also found at: 30
Period found at: 51
There are two prepositions in this haystack with needles.

find和erase联合使用实例

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
#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;

int main()
{
string key;
char key2=' ';
getline(cin,key);
for(int i=0;i<key.size();i++) key[i]=toupper(key[i]);
string str;
while(getline(cin,str)){
string str2=str;
for(int i=0;i<str.size();i++) str[i]=toupper(str[i]);
while(str.find(key)!=string::npos){
size_t pos=str.find(key);
//用一个找位置,不输出,但也得同步删除
str.erase(pos,key.size());
str2.erase(pos,key.size());
}
while(str2.find(key2)!=string::npos){
size_t pos=str2.find(key2);
str2.erase(pos,1);
}
cout<<str2<<endl;
}
return 0;
}

replace使用方法

1
2
3
4
5
6
用法一:用str替换指定字符串从起始位置pos开始长度为len的字符 
string& replace (size_t pos, size_t len, const string& str);
用法二: 用str替换 迭代器起始位置 和 结束位置 的字符
string& replace (const_iterator i1, const_iterator i2, const string& str);
用法三: 用substr的指定子串(给定起始位置和长度)替换从指定位置上的字符串
string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);

string函数应用实例,小数指数转换

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
4 00.00120 000.012345
//stl应用,给出两个数,保留N位小数科学计数法之后是否相等,要给出转换结果
/*
考虑数据本身,可以按整数部分是否为两种情况讨论
0.a1a2a3...
从小数点后第一个非零数字开始的三位,指数则是,小数点与非零位之间0的个数的相反数
b1b2..bm,a1a2a2...
首先判断是哪一类数据
在根据本体部分和指数是否都相等,判断是凑是相等的
*/

#include <iostream>
#include <string>
using namespace std;
int n;
//引用也要学会使用!!,这样可以返回修改多个东西
string dipose(string str,int &num){

while(str[0]=='0') {
//忘记一个重要的东西!!,i可以自增!!
str.erase(0,1);
//str.erase(str.begin())//去掉前导!!
}

if(str[0]=='.'){
str.erase(0,1);
//终于理顺了这个逻辑,不能用循环1!,因为每次删除的是前面
while(str[0]=='0'){
str.erase(0,1);
num++;
}
num=-num;
}else{
if(str.find('.')!=string::npos){
int pos=str.find('.');
num=pos;
str.erase(pos,1);
}
else{
num=str.size();
}
}
if(str.size()==0) num=0;
if(str.size()<n){
for(int i=str.size();i<n;i++)
str=str+'0';
}else{
str=str.substr(0,n);
}
return str;
}

int main()
{
string str1,str2;

while(cin>>n>>str1>>str2){
int n1=0,m2=0;
str1=dipose(str1,n1);
str2=dipose(str2,m2);
cout <<str1<<" "<<n1<< endl;
cout <<str2<<" "<<m2<< endl;
if(n1==m2&&str1==str2){
cout<<"YES"<<" 0."<<str1<<"*10^"<<n1<<endl;
}else{
cout<<"NO"<<" 0."<<str1<<"*10^"<<n1<<" 0."<<str2<<"*10^"<<m2<<endl;
}
}

return 0;
}

reverse()函数使用方法

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
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
string str;

while(getline(cin,str)){
reverse(str.begin(),str.end());
cout<<str<<endl;
}
return 0;
}
//基础逆置方法
while(gets(str))
{
int len=strlen(str);
for(int i=0;i<len/2;++i)
{
char temp=str[i];
str[i]=str[len-1-i];
str[len-1-i]=temp;
}
printf("%s\n",str);
}

swap函数使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
C++中的swap函数:交换函数

好处:不用担心交换变量精度的缺失,无需构造临时变量,不会增加空间复杂度

swap 包含在命名空间std 里面

swap(a,b);

swap(a[i] = b[j]);

leetcode的一个反转字符串举例:
//leetcode 反转字符串
//编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
//不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
//你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

class Solution {
public:
void reverseString(vector<char>& s) {
for(int i = 0, j = s.size() - 1; i < j; i++, j--)
swap(s[i] = s[j]);
}
return
};

set容器使用

1
2
3
4
5
6
7
8
9
10
11
12
#include <set>
using namespace std;

int main(){
set<int> s;
for(int i=0;i<5;i++){
s.insert(i*i);
}
s.find(4); //查找返回迭代器,找不到返回end()
s.erase(4);
return 0;
}

map容器使用

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <map>
#include <iterator>
using namespace std;

int main(){
map<char,int> mp;
mp['c']=1;
mp['b']=2;
mp['a']=3;
map<char,int>::iterator p=mp.begin(); //使用迭代器遍历
for(;p!=mp.end();++p){
//输出顺序是a,b,c,map使用红黑树实现,自动排序的
cout<<p->first<<" "<<p->second<<endl;
}
cout<<mp['b']<<endl;
//使用下标访问,输出2
map<char,int>::iterator it=mp.find('b');
//it指向<'b',1>
cout<<it->second<<endl;
mp.erase(it);
mp.erase('a');
cout<<mp.size()<<endl;
return 0;
}

//map使用方式
int main()
{

int n;
map<char,int> mp1;
mp1['C']=0;
mp1['J']=0;
mp1['B']=0;
map<char,int> mp2;
mp2['C']=0;
mp2['J']=0;
mp2['B']=0;
int A[3]={0},B[3]={0};
while(cin>>n){
char c1,c2;
for(int i=0;i<n;i++){
cin>>c1>>c2;
if(c1==c2){
A[1]++;
B[1]++;
}else if((c1=='C'&&c2=='J')||(c1=='J'&&c2=='B')||(c1=='B'&&c2=='C')){
A[0]++;
B[2]++;
mp1[c1]++;
}else if((c2=='C'&&c1=='J')||(c2=='J'&&c1=='B')||(c2=='B'&&c1=='C')){
A[2]++;
B[0]++;
mp2[c2]++;
}
}
for(int i=0;i<3;i++){
cout<<A[i]<<" ";
}
cout<<endl;
for(int i=0;i<3;i++){
cout<<B[i]<<" ";
}
cout<<endl;
map<char,int>::iterator p1=mp1.begin();
map<char,int>::iterator p2=mp2.begin();
cout<<p1->first<<" "<<p2->first;
}
return 0;
}

map使用实例,借用key的自动排序功能:

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
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
while(cin>>n){
map<int,string> mp1;
for(int i=0;i<n;i++){
int key;
string color;
cin>>key>>color;
//可以这样赋值,确实是按照key自动增序排列的
//mp1[key]=color;
mp1.insert(pair<int,string>(key,color));
}

/*for(auto it=mp1.begin();it!=mp1.end();it++){
cout<<it->second<<endl;
} 正向遍历 */

for(map<int,string>::reverse_iterator rit=mp1.rbegin();rit!=mp1.rend();rit++){
//cout<<rit->second<<endl;
cout<<(*rit).second<<endl;
}
}

return 0;
}

unorder_map容器使用(hash树)

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
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <unordered_map>
using namespace std;
int main()
{
int n,m,temp;
while(~scanf("%d",&n))
{
unordered_map<int,bool> mp;
/*
bool型 default 是 false;
bool 是基本型别,同 int;
BOOL 是个类,同INTEGER,可以调相应的方法.
*/
for(int i=0;i<n;i++)
{
scanf("%d",&temp);
mp[temp]=true;
}
scanf("%d",&m);
for(int i=0;i<m;i++)
{
scanf("%d",&temp);
if(mp[temp]==false)
printf("NO\n");
else
printf("YES\n");
}
}
return 0;
}
//unordered_map,运用出神入化!!学生id映射结构体student,用无序是为了使用hash,不让他乱排序
#include <cstdio>
#include <unordered_map>
using namespace std;
struct student
{
int id,age;
char name[100],sex[100];
}stu;
int main()
{
int n,m,temp;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
unordered_map<int,student> mp;
scanf("%d",&n);
for(int j=0;j<n;j++)
{
scanf("%d %s %s %d",&stu.id,stu.name,stu.sex,&stu.age);
mp[stu.id]=stu;
}
scanf("%d",&temp);
printf("%d %s %s %d\n",mp[temp].id,mp[temp].name,mp[temp].sex,mp[temp].age);
}
return 0;
}

堆栈+ordermap使用括号匹配

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <string>
#include <unordered_map>
#include <stack>
using namespace std;

void dispose(string str,unordered_map<char,int> list){
stack<char> bracket;
//规则是,左括号全都入栈,直到找到右括号就全部弹出到第一个左括号
int flag=0;
for(auto it=str.begin();it!=str.end();it++){
if(list.count(*it)>0){
//此处应当是只将括号入栈
//在list当中有括号的情况下
if(bracket.empty()==false){
//这个意思是匹配上了!!一定要注意两个状态,栈顶和当前
if(list[bracket.top()]+list[*it]==7)
bracket.pop();
else {
if(list[*it]<=3)
//左括号全部推入
bracket.push(*it);
//如果it右部匹配又是右括号就要跳出循环
else
break;
}
}
else{
//如果当前是空的话,若是立马遇见错括号可以直接跳楼了
bracket.push(*it);
if(list[*it]>3)
break;
}
}
}
//这里是左括号多余的情况
if(bracket.empty()==false)
flag=0;
else
flag=1;
if(flag==0)
printf("no\n");
else
printf("yes\n");
}


//堆栈括号匹配,主要是不记得括号匹配的规则了,
int main()
{
int n;
unordered_map<char,int> list;
//只想说这样匹配太好用了,优雅
list['{']=1;
list['[']=2;
list['(']=3;
list[')']=4;
list[']']=5;
list['}']=6;
while(cin>>n){
string temp;
for(int i=0;i<n;i++){
cin>>temp;
dispose(temp,list);
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

int str_to_int(const string &string_temp){
int temp;
stringstream stream(string_temp);
stream>>temp;
return temp;
}

void compute(stack<double> &number,stack<string> &sign){
double b=number.top();
//终于知道了,取值只能靠top!!,pop相当于清除
number.pop();
double a=number.top();
number.pop();
string op=sign.top();
sign.pop();
if(op=="+"){
//果然是按照算法一步步来的
number.push(a+b);
}else if(op=="-"){
number.push(a-b);
}
else if(op=="*"){
number.push(a*b);
}else{
number.push(a/b);
}
}

double dispose(unordered_map<string,int> isp,unordered_map<string,int> osp,string str){
stack<double> number;
stack<string> sign;
int flag=0;
//这仿佛是在寻找数字和操作符
while(str.empty()==false){
string temp;
int pos=str.find(" ");
if(pos!=string::npos){
temp=temp+str.substr(0,pos);
str.erase(0,pos+1);
}
else{
//找不到空格的时候,直接可以取最后剩余作为字符串
temp=str;
str.clear();
}
if(flag==0){
number.push(str_to_int(temp));
//fflag表示已经转换??,最后存成了double型??
//flag为1应当表示的是操作符而不是数字
flag=1;
}else{
if(sign.empty()==false){
//比较栈顶的和当前temp中的优先级
if(isp[sign.top()]>=osp[temp]){
while(sign.empty()==false){
//比较堆栈优先级和当前操作符优先级
if(isp[sign.top()]<osp[temp])
break;
//只有栈顶的优先级比较大的时候才可以计算,否则得要符号入栈
compute(number,sign);
}
}
}
sign.push(temp);
//操作符入栈,并且表示下一个字符为数字
flag=0;
}
}
while(sign.empty()==false){
compute(number,sign);
}
return number.top();
}

//中缀表达式转后缀表达式,最后按照相应规则处理数字栈和符号栈
int main()
{

string temp;
while(getline(cin,temp)){
if(temp!="0"){
unordered_map<string,int> isp,osp;
isp["+"]=1;
isp["-"]=1;
isp["*"]=2;
isp["/"]=2;
osp["+"]=1;
osp["-"]=1;
osp["*"]=2;
osp["/"]=2;
double result=dispose(isp,osp,temp);
printf("%.2f\n",result);
temp.clear();
}else{
break;
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <32/bits/stdc++.h>
//如何模仿计算器
/*
步骤一:中缀表达式转后缀表达式
设立一个操作符栈,可以临时存放操作符,设立一个数组或者队列,用以存放后缀表达式
步骤二:计算后缀表达式
从左到右扫描后缀表达式,操作数则入栈,操作符则连续弹出两个操作数
*/
using namespace std;


struct node{
double num; //操作数
char op; //操作符
bool flag; //true表示操作数,false表示操作符

};

string str;
//处理输入

stack<node> s; //操作符栈
queue<node> q; //后缀表达式序列
map<char,int> op; //存储优先级!!

void Change(){
double num;
node temp;
for(int i=0;i<str.size();){
if(isdigit(str[i])){
temp.flag=true; //标记为数字
temp.num=str[i++]-'0'; //由于可能是一个百位数字,先记录高位
while(i<str.size()&&isdigit(str[i])){
temp.num=temp.num*10+(str[i]-'0');
i++;
}
q.push(temp);
}else{
temp.flag=false;
//标记是操作符,只要栈顶元素比该操作符优先级高,就把栈顶元素弹到表达式中
while(!s.empty()&&op[str[i]]<=op[s.top().op]){
q.push(s.top());
s.pop();
}
temp.op=str[i];
//压入新的操作符
s.push(temp);
i++;

}

}

while(!s.empty()){

//若操作符中还有操作符,就得都弹入后缀表达式序列
q.push(s.top());
s.pop();
}
}

double Cal(){
//计算后缀表达式
double temp1,temp2;
node cur,temp;

while(!q.empty()){
cur=q.front(); //cur记录队首元素
q.pop();
if(cur.flag==true) s.push(cur); //操作数直接压栈
else{
temp2=s.top().num; //先弹出来的是第二操作数
s.pop();
temp1=s.top().num; //弹出第一操作数
s.pop();

temp.flag=true;
//临时记录草锁住
if(cur.op=='+') temp.num=temp1+temp2;
else if(cur.op=='-') temp.num=temp1-temp2;
else if(cur.op=='*') temp.num=temp1*temp2;
else if(cur.op=='/') temp.num=temp1/temp2;

s.push(temp);
}
}

return s.top().num;
//栈顶元素为后缀表达式的值

}

int main()
{
op['+']=op['-']=1;
op['*']=op['/']=2;

while(getline(cin,str),str!="0"){
for(auto it=str.end();it!=str.begin();it--){
if(*it==' ') str.erase(it); //去除掉表达式中空格
}

while(!s.empty()) s.pop(); //初始化栈
Change(); //中缀转后缀
printf("%.2f\n",Cal());
}
cout << "Hello world!" << 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
48*((70-65)-43)+8*1
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <cctype>
#include <map>
using namespace std;

struct node{
int num;
char op;
bool flag;
//true表示操作数
};
string str;

stack<node> s; //操作符栈
queue<node> q;//后缀表达式序列
map<char,int> op; //map存储符号优先级

void Change(){
int num;
node temp;

for(int i=0;i<str.size();){
//括号处理出的问题
if(str[i]=='('){
temp.flag=false;
temp.op=str[i];
s.push(temp);
i++;
}else if(str[i]==')'){
while(s.top().op!='('){
q.push(s.top());
s.pop();
}
s.pop();
i++;
}
else if(isdigit(str[i])){
temp.flag=true;
temp.num=str[i++]-'0';
//多位数怎么办
while(i<str.size()&&isdigit(str[i])){
temp.num=temp.num*10+(str[i]-'0');
i++;
}
//真正的队列压入
q.push(temp);
}else{
temp.flag=false;
while(!s.empty()&&op[str[i]]<=op[s.top().op]){
q.push(s.top());
s.pop();
}
temp.op=str[i];
//真正的操作符压入
s.push(temp);
i++;

}

}

while(!s.empty()){
q.push(s.top());
s.pop();
}
}

int Cal(){
int temp1,temp2;
node cur,temp;

while(!q.empty()){
cur=q.front();
q.pop();
if(cur.flag==true)
//一个栈多用
s.push(cur);
else{
//第二操作数
temp2=s.top().num;
s.pop();
//弹出第一操作数
temp1=s.top().num;
s.pop();

temp.flag=true;
//temp1,temp2生成
if(cur.op=='+')
temp.num=temp1+temp2;
else if(cur.op=='-')
temp.num=temp1-temp2;
else if(cur.op=='*')
temp.num=temp1*temp2;
else if(cur.op=='/')
temp.num=temp1/temp2;

s.push(temp);
}
}
return s.top().num;
//栈顶元素为最后值
}


int main()
{
op['+']=op['-']=1;
op['*']=op['/']=2;

while(getline(cin,str)){
while(!s.empty()) s.pop(); //初始化栈
Change(); //中缀转后缀
printf("%d\n",Cal());
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<map>
#include<cstring>
#include<ctype.h>
#include<stack>
#include<queue>
using namespace std;
struct node{
int data;
char op;
int flag;
}Node;
stack<char> s;
queue<node> q;
char str[1010];
map<char,int> m;

int main(){
m['+']=1;
m['-']=1;
m['(']=0;
m['*']=2;
m['/']=2;
scanf("%s",str);
int len=strlen(str);
for(int i=0;i<len;++i){
if(str[i]>='0'&&str[i]<='9'){
int sum=0;
while(str[i]>='0'&&str[i]<='9'){
sum=sum*10+str[i]-'0';
i++;
}
Node.data=sum;
Node.flag=1;
q.push(Node);
i--;
}

else if(!(str[i]>='0'&&str[i]<='9')){
if(str[i]=='(')
s.push(str[i]);
else if(str[i]==')'){
while(s.top()!='('){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
s.pop();
}else if(s.empty()||m[str[i]]>m[s.top()]){
s.push(str[i]);
}else{
while(!s.empty()&&m[str[i]]<=m[s.top()]){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
s.push(str[i]);
}
}
//printf("2");
}
while(!s.empty()){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
stack<int> s1;
int sum=0;
while(!q.empty()){
node no=q.front();
if(no.flag==1){
s1.push(no.data);
}else{
int a=s1.top();
s1.pop();
int b=s1.top();
s1.pop();
if(no.op=='+'){
sum=a+b;
}else if(no.op=='-'){
sum=b-a;
}else if(no.op=='*'){
sum=a*b;
}else{
sum=b/a;
}
s1.push(sum);
}
q.pop();
}
printf("%d",s1.top());
return 0;
}

队列使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <queue>
#include <iterator>
using namespace std;

int main(){
queue<int> q;
for(int i=1;i<=5;i++){
q.push(i);
//入队
}
if(q.empty()){
cout<<q.front()<<" ";
}
//输出队首1和队尾5
cout<<q.back()<<endl;
if(q.empty()){
q.pop();
}
return 0;
}

任务调度:优先队列+string处理和unordermap

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//优先队列进行任务调度
/*
输入
输入包含多组测试数据。

每组第一行输入一个整数n(n<100000),表示有n个任务。

接下来n行,每行第一个表示前序任务,括号中的任务为若干个后序任务,表示只有在前序任务完成的情况下,后序任务才能开始。若后序为NULL则表示无后继任务。

输出
输出调度方式,输出如果有多种适合的调度方式,请输出字典序最小的一种。

*/
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;

struct Task{
string name;
int level;
//定义优先规则
friend bool operator < (const Task &t1,const Task &t2){
if(t1.level!=t2.level)
return t1.level>t2.level;
else return t1.name>t2.name;
}
};

//使用引用表示要修改
void dispose(string str,priority_queue<Task> &task,unordered_map<string,int> &list){
string first;
int pos;
int firstlevel;
//从输入当中分理出任务
pos=str.find('(');
first=str.substr(0,pos);
str.erase(0,pos+1);
//list.count只能是1或0,,1表示存在,0表示没有,类似find
//而find返回的则是元素的迭代器
if(list.count(first)==0){
Task newtask;
newtask.name=first;
newtask.level=0;
task.push(newtask);
firstlevel=list[first]=0;
}
else{
firstlevel=list[first];
}
//str也可以使用empty函数
while(str.empty()==false){
string last;
pos=str.find(',');
if(str.find(',')==string::npos){
pos=str.find(')');
last=str.substr(0,pos);
str.clear();
}else{
last=str.substr(0,pos);
str.erase(0,pos+1);
}
if(last!="NULL"){
Task newtask;
newtask.name=last;
newtask.level=firstlevel+1;
list[last]=newtask.level;
task.push(newtask);
}
}

}

int main()
{
int n;
while(cin>>n){
priority_queue<Task> task;
//hash对应,且不排序
unordered_map<string,int> list;
string temp;
for(int i=0;i<n;i++){
cin>>temp;
dispose(temp,task,list);

}
while(task.empty()==false){
cout<<task.top().name;
task.pop();
if(!task.empty()){
cout<<" ";
}
}
list.clear();
}
return 0;
}

输入输出专题

控制小数点后精度位数及补齐整数位数

1
2
3
4
5
6
7
8
9
10
#include <cstdio>
#include <cstdlib>

int main(){
int n=9;
double pi=3.1415926;
printf("%02d\n",n); //保存两位然后补齐,输出09
printf("0.3f\n",pi); //小数保留三位,输出3.142
return 0;
}

scanf输入规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//输入字符
char c;
scanf("%c",&c);

//输入字符串
char a[26],b[10];
scanf("%s%s",a,&b);

//不同整型输出
short a = 10;
int b = 100;
long c = 9437;
printf("a=%hd, b=%d, c=%ld\n", a, b, c);

# include <stdio.h>
int main(void)
{
char str1[10], str2[10], str3[10];
printf("请输入字符串:");
scanf("%s%s%s", str1, str2, str3);
printf("输出结果:%s %s %s\n", str1, str2, str3); //%s间要加空格
return 0;
}
//需要注意的是,前面讲“清空缓冲区”的时候讲过,用 scanf 输入时,不管输入什么,最后“敲”的回车都会被留在缓冲区,这里也不例外。输入字符串时最后“敲”的回车也会被留在缓冲区,如果紧接着要给一个字符变量赋值的话,那么还没等你输入系统就自动退出来了。因为系统自动将回车产生的字符 '\n' 赋给该字符变量了,所以此时对字符变量赋值前要首先清空缓冲区。

其他输入规则,getchar(),cin,get(),gets()如何终止循环输入跳出

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
string str;
while(cin>>str){
char ch=getchar();
if(ch=='\n') break;
}

//另一种强悍输入,每一次可以读两个东西
while((cin>>word).get(c)&&flag){
if(c=='\n'){
flag==false;
}
for (int i = 0; i < word.size(); i++)
{
count[tolower(word[i])]++; //将字符全部转换为小写,并以ascii值为下标,数组值为出现次数计数
}
words.push_back(word);
if (!flag) //判断回车
{
break;
}
}

第一:要注意不同的函数是否接受空格符、是否舍弃最后的回车符的问题!
读取字符时:
scanf()以Space、Enter、Tab结束一次输入,不会舍弃最后的回车符(即回车符会残留在缓冲区中);
getchar()以Enter结束输入,也不会舍弃最后的回车符;
回车本身也是一个字符,getchar得到的是键盘流字符,须要清除一下键盘缓冲区:如用fflush(stdin); rewind(stdin);等
读取字符串时:
scanf()以Space、Enter、Tab结束一次输入
gets()以Enter结束输入(空格不结束),接受空格,会舍弃最后的回车符!

第二:为了避免出现上述问题,必须要清空缓冲区的残留数据,可以用以下的方法解决:
方法1:C语言里提供了函数清空缓冲区,只要在读数据之前先清空缓冲区就没问题了!
这个函数是fflush(stdin)。
方法2:自己取出缓冲区里的残留数据。
(说实话这个语句我也没看懂,呵呵!为什么格式控制是这样的!希望高手指点一下!)
scanf("%[^\n]",string);

//getchar()的正确使用方式
int main(void)
{
int ch;
int line_no = 0;
int flag = 1;
while((ch = getchar()) != EOF)
{
if (flag)
{
printf("%d--", line_no);
flag = 0;
}
putchar(ch);
if(ch == '\n')
{
line_no++;
flag = 1;
}
}
}

getchar:int getchar(void);从标准输入流(stdin,通常是键盘)中读取一个字符。
函数声明在头文件<stdio.h>中。 getc:
int getc(FILE *stream);
从文件流中读取一个字符。
函数声明在头文件<stdio.h>中。 fgetc:
与 getc 完全相同,从文件中读取一个字符。

scanf("%d", &n) 是从标准输入读入一个整数赋值给n,并且返回值是读入的值。
while( scanf(..) != EOF ) 就是一直从读取数据,直到读到一个EOF标记为止
EOF 是 end of line的意思,也就是行结束标识
getline(cin,str)输入一行//gets也是一行,但是需要char arr[100]型
string str;
while(getline(cin,str)){
if(islower(str[0])) str[0]=toupper(str[0]);
for(int i=1;i<str.size();i++){
if((str[i]==' '&&isalpha(str[i+1]))||(str[i]=='\t'&&isalpha(str[i+1]))||(str[i]=='\r'&&isalpha(str[i+1]))||(str[i]=='\n'&&isalpha(str[i+1]))){
if(islower(str[i+1])) str[i+1]=toupper(str[i+1]);
}
}
cout<<str<<endl;
}

cin.get()该函数有三种格式:无参,一参数,二参数即cin.get(),cin.get(char ch), cin.get(array_name, Arsize) 读取字符的情况:输入结束条件:Enter键对结束符处理:不丢弃缓冲区中的Entercin.get() 与 cin.get(char ch)用于读取字符,他们的使用是相似的,即:ch=cin.get() 与 cin.get(ch)是等价的。

sstream输入流

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
47
48
49
50
51
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

int main()
{
string str;

while(getline(cin,str)){
string word1;
string word2;
//隔行的还是选择行读好了,使用cin有风险,不用置零,清一下vec即可
getline(cin,word1);
getline(cin,word2);

//输入流输入范例
string buf;
stringstream ss(str);
vector<string> vec;
while(ss>>buf) vec.push_back(buf);

for(auto it=vec.begin();it!=vec.end();it++){
if(*it==word1) *it=word2;
cout<<*it<<" ";
}
cout<<endl;
vec.clear();
}
return 0;
}
//int型转string型变得这么简单
stringstream sstream;
string strResult;
int nValue = 1000;

// 将int类型的值放入输入流中
sstream << nValue;
// 从sstream中抽取前面插入的int类型的值,赋给string类型
sstream >> strResult;

cout << "[cout]strResult is: " << strResult << endl;
printf("[printf]strResult is: %s\n", strResult.c_str());
//string型转int型
int str_to_int(const string &string_temp){
int temp;
stringstream stream(string_temp);
stream>>temp;
return temp;
}

sstream输入排序实例istringstream

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
/*
考察字符串的划分和排序
我用的是istringstream 对读入的字符串进行划分,但是时间会比sscanf慢
毕竟io还是c快的多
*/

#include <bits/stdc++.h>
using namespace std;
struct Log{
string s; // 保存原本的数据
string name; // 名字
double time; // 记录时间
}logs[10000];
bool cmp(Log a,Log b){ // 排序函数
if(a.time == b.time) return a.name<b.name;
else return a.time<b.time;
}
int main(){
int i = 0;
while(getline(cin,logs[i].s)){ // 读入一行
istringstream is(logs[i].s); // 绑定s,对读入的数据进行划分
string str1,str2,str3;
//hs_10000_p 2007-01-17 19:22:53,315 253.035(s)
is>>str1>>str2>>str3>>logs[i].time;
logs[i].name = str2+str3;
i++;
}
sort(logs,logs+i,cmp); // 排序
for(int j=0;j<i;j++){
cout<<logs[j].s<<endl;
}
}

sscanf输入实例

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

#include <cstdio>
#include <algorithm>
using namespace std;

struct Message {
char raw[101];
char task[21];
int year, month, day;
int hour, minute, second, msecond;
int timeSecond, timeMsecond;

bool operator < (const Message& b) const {
if(timeSecond != b.timeSecond) return timeSecond < b.timeSecond;
if(timeMsecond != b.timeMsecond) return timeMsecond < b.timeMsecond;
if(year != b.year) return year < b.year;
if(month != b.month) return month < b.month;
if(day != b.day) return day < b.day;
if(hour != b.hour) return hour < b.hour;
if(minute != b.minute) return minute < b.minute;
if(second != b.second) return second < b.second;
return msecond < b.msecond;
}
} message[10000];

int main() {
int cnt = 0;
while(gets(message[cnt].raw)) {
sscanf(message[cnt].raw, "%s %d-%d-%d %d:%d:%d,%d %d.%d",
message[cnt].task, &message[cnt].year, &message[cnt].month,
&message[cnt].day, &message[cnt].hour, &message[cnt].minute,
&message[cnt].second, &message[cnt].msecond, &message[cnt].timeSecond, &message[cnt].timeMsecond);
cnt++;
}
sort(message, message+cnt);
for(int i = 0; i < cnt; i++) {
printf("%s\n", message[i].raw);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;

int main(){

//打开文件,清空内容,重新写入,ofstream::out指示以写模式打开
ofstream out1("D\\abc.txt",ofstream::out);
string s;
while(getline(cin,s)){
out1<<s<<endl;
}
out1.close();

//打开文件,向文件追加内容
//ofstream::out指示以写模式打开,ofstream::app指示写操作前定位到文件末尾
ofstream out2("D:\\abc.txt",ofstream::out|ofstream::app);
while(getline(cin,s)){
out2<<s<<endl;
}
out2.close();

//读取文件
ifstream in("D:\\abc.txt");
vector<string> vecs;
while(getline(in,s)){
vecs.push_back(s);
}
in.close();
return 0;
}

//输入输出流配合操作
vector<string> inputArr;
string inStr;
while(cin>>inStr){
inputArr.push_back(inStr);
char ch=getchar();
if(ch=='\n') break;

}
int len=inputArr.size();
ofstream out1(inputArr[len-1].c_str(),ofstream::out|ofstream::app);
for(int i=1;i<len-1;i++){
ifstream in(inputArr[i].c_str());

string s;
while(getline(in,s)){

cout<<s<<endl;
//直接从文件里进文件里出

//终于领会到了cout,cin流的精髓
out1<<s<<endl;
}
in.close();
out1.close();
//app定位到文件末尾,追加内容

typedef std::string String;
//还有一种用法
void loadDirect(const String& filename)
{

std::ifstream fp;
fp.open(filename.c_str(), std::ios::in | std::ios::binary);
cout<<fp.rdbuf();
fp.clear();
if(!fp.bad())
{
cout<<"打开 失败。";
}


}

fstream f;
f.open("1.txt", ios::in | ios::binary);
if (!f.is_open()) // 检查文件是否成功打开
cout << "cannot open file." << endl;
ios::in与ios::bianry均为int型,定义文件打开的方式。
ios::in -- 打开文件用于读。
ios::out -- 打开文件用于写,如果文件不存在,则新建一个;存在则清空其内容。
ios::binary -- 以二进制bit流方式进行读写,默认是ios::text,但最好指定这种读写方式,即使要读写的是文本。因为在ios::text模式下,在写入时’\ n’字符将转换成两个字符:回车+换行(HEX: 0D 0A) 写入,读入时作逆转换,这容易引起不必要的麻烦。ios::app -- 打开文件在文件尾进行写入,即使使用了seekp改变了写入位置,仍将在文件尾写入。
ios::ate -- 打开文件在文件尾进行写入,但seekp有效。
读写位置的改变
f.seekg(0, ios::beg); // 改变读入位置 g mean Get
f.seekp(0, ios::end); // 改变写入位置 p mean Put
第一个参数是偏移量offset(long),第二个参数是offset相对的位置,三个值:
ios::beg -- 文件头 ios::end -- 文件尾 ios::cur -- 当前位置

strlen和sizeof区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//c语言没有字符串,用的是字符串数组来模拟字符串,c风格字符串数组再末尾加0表示结尾
//strlen不加结束标志表示字符串长度,sizeof求得是字符串在内存中的长度

#include <stdio.h>
#include <string.h>

int main(){
char buf[]="abcd";
printf("sizeof(buf) = %d\n",sizeof(buf));
printf("strlen(buf) = %d\n",strlen(buf));

return 1;
}

结果
sizeof(buf) = 5
strlen(buf) = 4

short ,int,long区别

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
116位编译器

char1个字节
char*(即指针变量): 2个字节
short int : 2个字节
int2个字节
unsigned int : 2个字节
float: 4个字节
double: 8个字节
long: 4个字节
long long: 8个字节
unsigned long: 4个字节

232位编译器

char1个字节
char*: 4个字节
short int : 2个字节
int4个字节
unsigned int : 4个字节
float: 4个字节
double: 8个字节
long: 4个字节
long long: 8个字节
unsigned long: 4个字节

#include<iostream>
#include<climits>
int main()
{
using namespace std;
int n_int=INT_MAX;
short n_short=SHRT_MAX;
long n_long=LONG_MAX;
long long n_llong=LLONG_MAX;

cout<<"int is "<<sizeof(int)<<" bytes."<<endl;
cout<<"short is "<<sizeof n_short<<" bytes."<<endl;
cout<<"long is "<<sizeof n_long<<" bytes."<<endl;
cout<<"long long is "<<sizeof n_llong<<" bytes."<<endl;
cout<<endl;

cout<<"Maximum values:"<<endl;
cout<<"int: "<<n_int<<endl;
cout<<"short: "<<n_short<<endl;
cout<<"long: "<<n_long<<endl;
cout<<"long long: "<<n_llong<<endl<<endl;

cout<<"Minimum int value="<<INT_MIN<<endl;
cout<<"Bits per byte= "<<CHAR_BIT<<endl;
return 0;
}


结果
int is 4 bytes.(32位) 10^9大小
short is 2 bytes.
long is 4 bytes. 2^32
long long is 8 bytes. 2^64

Maximum values:
int: 2147483647
short: 32767 //10^5
long: 2147483647 //10^10
long long: 9223372036854775807 //10^19

Minimum int value=-2147483648
Bits per byte= 8

Process returned 0 (0x0) execution time : 1.937 s
Press any key to continue.

//这说明,再有符号计算中第一位是0或1表示政府
类型名称 字节数 取值范围
signed char 1 -2^7 ~ 2^7-1 -128~+127

short int 2 -2^14 ~ 2^14-1 -32768~+32767

int 4 -2^31 ~ 2^31-1 -2147483648~+2147483647
unsigned int 4 0 ~ 2^32-1 0 ~ 4294967295

long int 4 -2^31 ~ 2^31-1 -2147483648~+2141483647 (同int//soga
unsigned long 4 0 ~ 2^32-1 04294967295

long long int 8 -2^63 ~ 2^63-1 -9223372036854775808~+9223372036854775807
unsigned long long 8 0 ~ 2^64-1 18446744073709551615


__int64的最大值:9223372036854775807
__int64的最小值:-9223372036854775808
unsigned __int64的最大值:18446744073709551615

//无符号区别
unsigned long ulA = 0x70000000; // 数值范围不大
unsigned long ulB = 0x80000000; // 数值范围大
unsigned long ulC = 3;
printf("%lu 0x%x %ld\n",ulA,ulA,ulA);
printf("%lu 0x%x %ld\n",ulB,ulB,ulB);
printf("%lu 0x%x %ld\n",ulC,ulC,ulC);

transform函数应用大小写转换

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
unary operation(1)	
template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperation op);
binary operation(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op);
(1) unary operation
Applies op to each of the elements in the range [first1,last1) and stores the value returned by each operation in the range that begins at result.
(2) binary operation
Calls binary_op using each of the elements in the range [first1,last1) as first argument, and the respective argument in the range that begins at first2 as second argument. The value returned by each call is stored in the range that begins at result.
template <class InputIterator, class OutputIterator, class UnaryOperator>
OutputIterator transform (InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperator op)
{
while (first1 != last1) {
*result = op(*first1); // or: *result=binary_op(*first1,*first2++);
++result; ++first1;
}
return result;
}
first1, last1
Input iterators to the initial and final positions of the first sequence. The range used is [first1,last1), which contains all the elements between first1 and last1, including the element pointed to by first1 but not the element pointed to by last1.
first2
Input iterator to the initial position of the second range. The range includes as many elements as [first1,last1).
result
Output iterator to the initial position of the range where the operation results are stored. The range includes as many elements as [first1,last1).
op
Unary function that accepts one element of the type pointed to by InputIterator 一元函数,接受InputIterator所指类型的一个元素作为参数,并返回一些可转换为OutputIterator所指类型的结果值。这可以是函数指针,也可以是函数对象。
binary_op
二元函数,接受两个元素作为参数(两个序列中的一个),并返回一些可转换为OutputIterator所指类型的结果值。这可以是函数指针,也可以是函数对象。
// transform algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::transform
#include <vector> // std::vector
#include <functional> // std::plus

int op_increase (int i) { return ++i; }

int main () {
std::vector<int> foo;
std::vector<int> bar;

// set some values:
for (int i=1; i<6; i++)
foo.push_back (i*10); // foo: 10 20 30 40 50

bar.resize(foo.size()); // allocate space

std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);
// bar: 11 21 31 41 51

// std::plus adds together its two arguments:
std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
// foo: 21 41 61 81 101

std::cout << "foo contains:";
for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';

return 0;
}
foo contains: 21 41 61 81 101

链表专题

链表增删改查

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cstdio>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
int str_to_int(const string &temp)
{
int temp_int;
stringstream stream(temp);
stream>>temp_int;
return temp_int;
}
struct node
{
int data;
node * next;
};

void create(node * &L,int n)
{
L=new node;
L->next=NULL;
int elem;
node * p;
for(int i=0;i<n;i++)
{
scanf("%d",&elem);
p=new node;
p->data=elem;
p->next=L->next;
L->next=p;
}
}
void show(node * L)
{
node *p=L->next;
if(p==NULL)
{
printf("Link list is empty\n");
return ;
}
while(p!=NULL)
{
if(p->next==NULL)
{
printf("%d\n",p->data);
}
else
{
printf("%d ",p->data);
}
p=p->next;
}
}
void Delete(node * &L,int n)
{
node * pre=L;
node * p=L->next;
if(p==NULL)
{
printf("delete fail\n");
return ;
}
for(int i=0;i<n-1;i++)
{
pre=p;
p=pre->next;
}
if(p==NULL)
{
printf("delete fail\n");
return ;
}
pre->next=p->next;
free(p);
printf("delete OK\n");
}
void insert(node * &L,int n,int e)
{
node *p=L;
//每次都是要移入到插入位置的
for(int i=0;i<n-1;i++)
{
p=p->next;
if(p==NULL)
{
printf("insert fail\n");
return ;
}
}
node * q;
//关键是使用new方法
q=new node;
q->data=e;
q->next=p->next;
p->next=q;
printf("insert OK\n");
}
void get(node * L,int n)
{
node *p=L;
for(int i=0;i<n;i++)
{
p=p->next;
}
if(p==NULL)
{
printf("get fail\n");
}
else
{
printf("%d\n",p->data);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
node * L;
create(L,n);
int row;
scanf("%d",&row);
string temp;
getchar();
for(int i=0;i<row;i++)
{
getline(cin,temp);
if(temp[0]=='s')
{
show(L);
}
else if(temp[0]=='d')
{
temp.erase(0,7);
Delete(L,str_to_int(temp));
}
else if(temp[0]=='g')
{
temp.erase(0,4);
get(L,str_to_int(temp));
}
else if(temp[0]=='i')
{
temp.erase(0,7);
int pos=temp.find(' ');
int x=str_to_int(temp.substr(0,pos));
temp.erase(0,pos+1);
insert(L,x,str_to_int(temp));
}
else
{
cout<<"error!"<<temp<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>

using namespace std;

typedef struct Node{
int sno;
int grade;
Node *next;
}Node,*List;

void create(Node * &L,int n){
L=new Node;
L->next=NULL;
//空的头结点
int x,y;
Node *p;
for(int i=0;i<n;i++){
cin>>x>>y;
p=new Node;
p->sno=x;
p->grade=y;
//头插法
p->next=L->next;
L->next=p;
}
}

void show(Node *L){
while(L->next!=NULL){
cout<<L->next->sno<<" "<<L->next->grade<<endl;
L=L->next;
}
}

void sortL(Node *&L){
Node *p,*q,*small;
int temp1,temp2;

//选择排序,找出最小的,while已经不够用
for(p=L->next;p->next!=NULL;p=p->next){
//果然是将第一个值当做最小
small=p;
//类似于i,j,指针(j)q向后寻找,最小值放在i(p)
for(q=p->next;q!=NULL;q=q->next){
if(q->sno<small->sno){
small=q;
}
}

if(small!=p){
temp1=p->sno;
temp2=p->grade;
p->sno=small->sno;
p->grade=small->grade;
small->sno=temp1;
small->grade=temp2;
}

}

}

//链表排序和合并
int main()
{
int n,m;
while(cin>>n>>m){
Node *L1,*L2;
create(L1,n+m);
sortL(L1);
show(L1);
}
return 0;
}

#include <cstdio>
struct node
{
int number;
int grade;
node * next;
};

int main()
{
int m,n;
while(~scanf("%d %d",&m,&n))
{
node * L=new node;
L->next=NULL;
for(int i=0;i<m+n;i++)
{
node * temp=new node;
scanf("%d %d",&temp->number,&temp->grade);
node * pre=L;
node * p=L->next;
while(p!=NULL)
{
if(temp->number<p->number)
{
break;
}
else
{
pre=p;
p=p->next;
}
}
temp->next=pre->next;
pre->next=temp;
}
node * p=L->next;
while(p!=NULL)
{
printf("%d %d\n",p->number,p->grade);
p=p->next;
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
struct node
{
int data;
node * next;
};

int main()
{
int m,n;
while(~scanf("%d",&m))
{
node * L1=new node;
L1->next=NULL;
node * rear1=L1;
for(int i=0;i<m;i++)
{
node * temp=new node;
scanf("%d",&temp->data);
rear1->next=temp;
temp->next=L1;
rear1=rear1->next;
}
scanf("%d",&n);
node * L2=new node;
L2->next=NULL;
node * rear2=L2;
for(int i=0;i<n;i++)
{
node * temp=new node;
scanf("%d",&temp->data);
rear2->next=temp;
temp->next=L2;
//直接找到尾部2
rear2=rear2->next;
}
rear1->next=L2->next;
rear2->next=L1;
//delete释放L2结点
delete(L2);
node * p=L1->next;
while(p!=L1)
{
if(p->next==L1)
{
printf("%d\n",p->data);
}
else
{
printf("%d ",p->data);
}
p=p->next;
}
}
return 0;
}

#include <iostream>

using namespace std;

typedef struct Node{
int data;
Node *next;
}Node,*List;

void create(Node * &L,int n){
L=new Node;
L->next=NULL;
//空的头结点
int x;
Node *p;
Node *q=L;
for(int i=0;i<n;i++){
cin>>x;
p=new Node;
p->data=x;
//尾插法
q->next=p;
q=q->next;

}
q->next=L;
}

void show(Node *L,int n){
for(int i=0;i<n;i++){
cout<<L->next->data<<" ";
L=L->next;
}
cout<<endl;
}

void mergeL(Node *&L1,Node *L2,int n,int m){
Node *p=L1,*q=L2;
for(int i=0;i<n;i++) {
p=p->next;
}
for(int i=0;i<m;i++) {q=q->next;
}
p->next=L2->next;
q->next=L1;
}
//链表排序和合并
int main()
{
int n,m;
while(cin>>n){
Node *L1,*L2;
create(L1,n);
cin>>m;
create(L2,m);
mergeL(L1,L2,n,m);
show(L1,n+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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>

using namespace std;

typedef struct Node{
int data;
Node *next;
}Node,*List;

void create(Node * &L,int n){
L=new Node;
L->next=NULL;
//空的头结点
int x;
Node *p;
Node *q=L;
for(int i=0;i<n;i++){
cin>>x;
p=new Node;
p->data=x;
//尾插法
q->next=p;
q=q->next;
q->next=NULL;

}

}

void show(Node *L){
while(L->next!=NULL){
cout<<L->next->data<<" ";
L=L->next;
}
cout<<endl;
}

void findL(Node *&L,int x){
Node *pre=L;
Node *p=L->next;
int temp;
while(p->data<x){
pre=p;
p=p->next;
}
if(x==p->data){
cout<<x<<endl;
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}else {
Node *s=new Node;
s->data=x;
s->next=p;
pre->next=s;
cout<<"no"<<endl;

}
}

//链表排序和合并
int main()
{
int n,m;
while(cin>>n>>m){
Node *L1;
create(L1,m);
findL(L1,n);
show(L1);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <stdlib.h>
using namespace std;

typedef struct Node{
int data;
Node *next;
}Node;

Node *InitialList(){
Node *L;
L=(Node *)malloc(sizeof(Node));
L->next=NULL;
return L;
}

Node *createList(Node *List,int data){
Node *p=List;
Node *newNode;
newNode=(Node *)malloc(sizeof(Node));
newNode->data=data;
while(p->next){
p=p->next;
}
p->next=newNode;
p=p->next;
p->next=NULL;
//老师忘记了返回
//老师忘记了返回
return List;
}

//找出最大值,就应该是找到最大值的位置!!
//删除成功
Node *Delete_max(Node *List){
Node *q=List->next;
Node *pre=List;
Node *p=List->next;
int maxL=-1;
while(p->next){
if(p->data>maxL){
maxL=p->data;
}
p=p->next;
}
while(q->data!=maxL){
q=q->next;
pre=pre->next;
}
//如何删除
pre->next=q->next;
free(q);
cout<<maxL<<endl;
return List;
}

//排序不用交换结点,只需要交换数字,很重要!!
Node *sort_List(Node *List){
Node *p,*q,*small;
int temp;
//终于搞好了for循环,主要是边界问题
for(p=List->next;p->next!=NULL;p=p->next)
{
small=p;
//链表循环如何描写,循环边界的控制
for(q=p->next;q!=NULL;q=q->next)
{
//选择交换法最适合链表。选择最小的和当前的交换
if(q->data<small->data)
small=q;
}
if(small!=p){
temp=p->data;
p->data=small->data;
small->data=temp;
}
}
return List;

}


int main(){
Node *L;
L=InitialList();
int x;
while(cin>>x){
L=createList(L,x);
char ch=getchar();
if(ch=='\n') break;
}
//终于成功打印了,按照自己的理解
L=Delete_max(L);
L=sort_List(L);


while(L->next){
Node *temp=L->next;
free(L);
L=temp;
//一开始十个空节点,之后才有值
cout<<L->data<<" ";

}

}

循环链表删除结点

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}LNode,*LinkList;

LinkList createList(int a[],int len){//创建单链表;
LinkList L,p,r;
int i;
if(len<=0){
return NULL;
}
L=(LinkList)malloc(sizeof(LNode));
L->data=a[0];
p=L;
for(i=1;i<len;i++){
r=(LinkList)malloc(sizeof(LNode));
r->data=a[i];
p->next=r;
p=r;
}
p->next=NULL;//表尾;
return L;
}

LinkList changeList(LinkList L){//把单链表变成单循环链表;
LinkList p;
p=L;
while(p->next!=NULL){
p=p->next;//p移至表尾;
}
p->next=L;
return L;
}

LinkList deleteLNode(LinkList L){//从链表中删除结点;
LinkList p,r;
int count=1;
p=L;
while(count<=16){
r=p;//r指向前驱;
p=p->next;//p移至第17个结点;
count++;
}
r->next=p->next;
free(p);
return r->next;//新的头结点;
}

void display(LinkList L){//输出单链表;
if(L!=NULL){
LinkList p;
p=L;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
}
}

int main(){
int a[21],i;
LinkList L,p;
for(i=0;i<21;i++){
a[i]=i+1;
}
L=createList(a,21);
L=changeList(L);
//L=deleteLNode(L);
while(L->next!=L){
L=deleteLNode(L);
}
printf("链表中最后剩下的结点是:%d\n",L->data);
//display(L);
}

链表中的排序操作,链表复制s[k]用法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
1 78 90 56
2 89 56 97
3 78 97 95
0

/*输入学生信息:学号,三门课程的成绩,学号为0时结束,将其存储在链表A中,从中找出分数大于平均分的学生,并将该学生信息按平均分降序排列存入到链表B中,最后输出链表B*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{char xuehao[20];
int chengji[3];
float av;
struct node *next;
}stud,*UerInfo;
int main()

{
UerInfo ui;
ui=(UerInfo)malloc(sizeof(stud));
//多个指针指针用完位置变化了
UerInfo p=ui;
UerInfo q=ui;

printf("input students' information:\n");
int cnt=0;
while (1)
{
printf("input 学号:");
scanf("%s",ui->xuehao);
if(strcmp(ui->xuehao,"0")==0)
break;
printf("input 成绩:");
scanf("%d",&ui->chengji[0]);
printf("input 成绩:");
scanf("%d",&ui->chengji[1]);
printf("input 成绩:");
scanf("%d",&ui->chengji[2]);
ui->av=((ui->chengji[0]+ui->chengji[1]+ui->chengji[2])/3);
//创建了新节点
//创建了新节点
ui->next=(UerInfo)malloc(sizeof(stud));
ui=ui->next;
cnt++;
}
int chengji1=0;
int chengji2=0;
int chengji3=0;
while (p&&strcmp(p->xuehao,"0")!=0)
{
//三科成绩相加
chengji1+=p->chengji[0];
chengji2+=p->chengji[1];
chengji3+=p->chengji[2];
p=p->next;
}
float chengji1av=0.0;
float chengji2av=0.0;
float chengji3av=0.0;
float avfinal=0.0;
if(cnt)
{
//算3可平均分和最终评分,平均分计算方法,各科平均数除以三科
chengji1av=(float)chengji1/(float)cnt;
chengji2av=(float)chengji2/(float)cnt;
chengji3av=(float)chengji3/(float)cnt;
avfinal=(chengji1av+chengji2av+chengji3av)/3;
}
printf("高于平均分的有:\n");
UerInfo s;
//复制链表
s=(UerInfo)malloc(cnt*sizeof(stud));
int k=0;
while (q&&strcmp(q->xuehao,"0")!=0)
{
//如何借用s[k].复制链表
s[k].av=q->av;
s[k].chengji[0]=q->chengji[0];
s[k].chengji[1]=q->chengji[1];
s[k].chengji[2]=q->chengji[2];
strcpy(s[k].xuehao,q->xuehao);
k++;
if(q->av>avfinal)
{
//输出高于平均分的学生
printf("%s\n",q->xuehao);
printf("%f\n",q->av);
}
q=q->next;
}
printf("\n降序排列如下:\n");

//如何复制链表

int l,m;
stud temps;
//选择排序,每次选出最大的
for (l=0;l<cnt-1;l++)
{
for (m=l+1;m<cnt;m++)
{
if(s[l].av<s[m].av)
{
//可怕的交换
temps.chengji[0]=s[l].chengji[0];
temps.chengji[1]=s[l].chengji[1];
temps.chengji[2]=s[l].chengji[2];
strcpy(temps.xuehao,s[l].xuehao);
s[l].chengji[0]=s[m].chengji[0];
s[l].chengji[1]=s[m].chengji[1];
s[l].chengji[2]=s[m].chengji[2];
strcpy(s[l].xuehao,s[m].xuehao);
s[m].chengji[0]=temps.chengji[0];
s[m].chengji[1]=temps.chengji[1];
s[m].chengji[2]=temps.chengji[2];
strcpy(s[m].xuehao,temps.xuehao);
}
}
}
for (int i=0;i<cnt;i++)
{
printf("学号:%s\n",s[i].xuehao);
printf("成绩:%d\n",s[i].chengji[0]);
printf("成绩:%d\n",s[i].chengji[1]);
printf("成绩:%d\n",s[i].chengji[2]);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//输入形式
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

#include <bits/stdc++.h>

using namespace std;

struct node{
int address;
int data;
int next;
};

int main()
{
int N,first,K;
vector<node> shunxu;
vector<node> rev;
cin>>first>>N>>K;
//如何给结点组输入值
node temp;
node addr[100000];
//由于结点的下标是五位数
for(int i=0;i<N;i++){
cin>>temp.address>>temp.data>>temp.next;
addr[temp.address]=temp;
}
//first是头结点下标,接下来就是考虑怎样将分散结点联系起来
int nextAdd=first;
while(nextAdd!=-1){
//我傻了@@,存储起来就好
shunxu.push_back(addr[nextAdd]);
nextAdd=addr[nextAdd].next;
}
int size=shunxu.size(); //输入结点可能有些不在链表中,记录下链表长度
int tempInt=K-1; //翻转个数
while(tempInt<size){
for(int i=tempInt;i>tempInt-K;i--){
rev.push_back(shunxu[i]);
//反转链表,每次反转K个,不足K个反转并退出循环
}
tempInt=tempInt+K;
}

for(int i=tempInt-K+1;i<size;i++){
rev.push_back(shunxu[i]);
//最后没有反转的复制
}

for(int i=0;i<size-1;i++){
rev[i].next=rev[i+1].address;
//如何修改next值,改为下一个元素的Address
printf("%05d %d %05d\n",rev[i].address,rev[i].data,rev[i].next);
}//最后一个结点的处理办法--单独~~
printf("%05d %d %d\n",rev[size-1].address,rev[size-1].data,-1);

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <string>
using namespace std;

//复原二叉树,。想出算法,

//静态版,递归的边界条件和递归式由str1的s1,e1,str2的s2,e2联合确定,缩小开头和结尾划分子问题

struct Node{
char data;
Node *rchild;
Node *lchild;
}Tree[50];

//静态如何创建新节点,就是loc游标移动
int loc;
Node *create(){
Tree[loc].lchild=Tree[loc].rchild=NULL;
//返回的是指针
return &Tree[loc++];
}
string str1,str2;
//在函数当中就要用到,提前定义
Node *build(int s1,int e1,int s2,int e2){
//直接每个都要创建新节点的!!我傻了
Node *ret=create();
ret->data=str1[s1];
int rootIdx=str2.find(str1[s1]);
//找到根节点在str2中的位置
//递归边界+递归式
if(rootIdx!=s2){
//左子树不为空
ret->lchild=build(s1+1,s1+(rootIdx-s2),s2,rootIdx-1);
//边界的确定最难了
}
if(rootIdx!=e2){
ret->rchild=build(s1+(rootIdx-s2)+1,e1,rootIdx+1,e2);
}
return ret;
}
//动态创建的办法,以及带出口边界的写法
node * create(int preL,int preR,int inL,int inR)
{
if(preL>preR)
return NULL;
node * p=new node;
p->data=pre[preL];
int k;
for(k=inL;k<inR;++k)
if(in[k]==pre[preL])
break;
int numleft=k-inL;
p->lchild=create(preL+1,preL+numleft,inL,k-1);
p->rchild=create(preL+numleft+1,preR,k+1,inR);
return p;
}


void postOrder(Node *r){
//遍历出口
if(r==NULL){
return;
}
postOrder(r->lchild);
postOrder(r->rchild);
printf("%c",r->data);
}
int main()
{
while(cin>>str1>>str2){
Node *T;
int e1=str1.size()-1;
int e2=str2.size()-1;
T=build(0,e1,0,e2);
postOrder(T);
printf("\n");
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
7
8 6 5 7 10 8 11

#include <iostream>
#include <vector>
using namespace std;

struct node{
int data;
node *rchild;
node *lchild;
};

//创建新结点还是要写一个,这样的话,才可以创建空结点,类似于链表知道到了链表尾部
node *newNode(int x){
node *Node=new node;
Node->data=x;
Node->rchild=Node->lchild=NULL;
return Node;
}

//如何构造二叉排序树
//有无到有,其实就是n次插入,而插入其实是查找的更进一步,找到空的位置!!

void insL(node *&root,int x)
{
//次数一定要加上引用,因为root结构发生了变化
if(root==NULL) {
//定义出口,空结点的位置创建新点
root=newNode(x);
return;
}
//原因在这里,相等时也可以插
/* if(x==root->data){
return;
//查找结点,如果发现这个结点被插入,就不用二次插入
}else if(x<root->data){
insL(root->lchild,x);
}else {
insL(root->rchild,x);
}*/
if(x<root->data) insL(root->lchild,x);
else insL(root->rchild,x);
}
//数组参数如何处理



//换成高级写法
void preOrder(node *T,vector<int> &vi){
if(T==NULL) return;
vi.push_back(T->data);
preOrder(T->lchild,vi);
preOrder(T->rchild,vi);
}

void postOrder(node *T,vector<int> &vi){
if(T==NULL) return;

postOrder(T->lchild,vi);
postOrder(T->rchild,vi);
vi.push_back(T->data);
}

void mirOrderPre(node *T,vector<int> &vi){
if(T==NULL) return;
vi.push_back(T->data);

mirOrderPre(T->rchild,vi);
mirOrderPre(T->lchild,vi);
}

void mirOrderPost(node *T,vector<int> &vi){
if(T==NULL) return;

mirOrderPost(T->rchild,vi);
mirOrderPost(T->lchild,vi);
vi.push_back(T->data);
}


vector<int> origin,pre,preM,post,postM;
int main()
{

int n;
while(cin>>n){

node *T=NULL;
for(int i=0;i<n;i++){
int x;
cin>>x;
origin.push_back(x);
//循环插入即可
insL(T,x);
}

preOrder(T,pre);
postOrder(T,post);
mirOrderPre(T,preM);
mirOrderPost(T,postM);
//容器vector可以直接相等!!!
if(origin==pre){
cout<<"YES"<<endl;
for(int i=0;i<post.size();i++){
cout<<post[i]<<" ";
}
}else if(origin==preM){
cout<<"YES"<<endl;
for(int i=0;i<postM.size();i++){
cout<<postM[i]<<" ";
}
}else{
cout<<"NO"<<endl;
}
cout<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*第三题:输入一个字符串,建立一个二叉排序树,并中序遍历输出;*/

/*这里采用了两种遍历,此处是非递归。下面注释的是递归*/
/*测试数据: poiuyt 输出数据;i o p t u y
测试数据: 621345 输出数据: 1 2 3 4 5 6*/
/*程序:*************************爱X的味道 07级华中农业大学计算机系*****************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 50
typedef struct Node
{
char data;
struct Node *Lchild;
struct Node *Rchild;
}Node,*BiTree;

typedef struct
{
BiTree elem[MAX];
int top;
}Stack;
void InitStack(Stack *s)
{
s->top=-1;
}
int Push(Stack *s,BiTree *T)
{
if(s->top>MAX-1) return 0;
s->top++;
s->elem[s->top]=(*T);
return 1;
}
int Pop(Stack *s,BiTree *T)
{
if(s->top<-1) return 0;
*T=s->elem[s->top];
s->top--;
return 1;
}
int IsEmpty(Stack s)
{
if(-1==s.top)
return 1;
else
return 0;
}
void InsertSortTree(BiTree *tree, char key)
{
BiTree T;
if(*tree == NULL)
{
T=(BiTree)malloc(sizeof(Node));
T->data=key;
T->Lchild=NULL;
T->Rchild=NULL;
*tree=T;
}
else
if((*tree)->data>key)
InsertSortTree(&((*tree)->Lchild),key);
else
if((*tree)->data<key)
InsertSortTree(&((*tree)->Rchild),key);
}
void CreateSortTree(BiTree *tree,char *str )
{
*tree=NULL;
int i=0;
while(str[i]!='\0')
{
InsertSortTree(&(*tree),str[i]);
i++;
}
}

void InOrdTree(BiTree T)
{
Stack s;
BiTree p=T;
InitStack(&s);
while(p!=NULL || !IsEmpty(s))
{
if(p!=NULL)
{
Push(&s,&p);
p=p->Lchild;
}
else
{
Pop(&s,&p);
printf(" %c ",p->data);
p=p->Rchild;
}
}
printf("\n\n");
}
int main()
{
char str[100]="\0";
BiTree tree;
printf("请输入一个字符串:\n\n");
gets(str);
CreateSortTree(&tree,str);
printf("中序遍历的结果是:\n\n");
InOrdTree(tree);
printf("\n\n");
return 0;
}

/*
/*输入一个字符串,建立一个二叉排序树,并中序遍历输出;
要考虑字符串,好难

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

typedef struct Node{
int data;
Node *lchild,*rchild;
}Node,*BiTree;

Node * creatNode(int data){
Node *T=(Node*)malloc(sizeof(Node));
if(T==NULL){
exit(0);
}
T->data=data;
T->lchild=NULL;
T->rchild=NULL;
return T;
}

//只有返回值时树节点才node *好不好
int InsertNode(BiTree &T,int key){
if(T==NULL){
T=creatNode(key);
return 1;
}

//应当要检查要插入的是否已经存在的,如果查找失败直接插入,则p指向遍历最后一个节点
//主要是根据key找位置
else if(key==T->data){
return 0;
}else if(key<T->data){
return InsertNode(T->lchild,key);
}else return InsertNode(T->rchild,key);
}

void inOrder(Node *T){
if(T!=NULL){
inOrder(T->lchild);
printf("%c ",T->data);
inOrder(T->rchild);
}

}

int main(){
Node *T=NULL;
string str;
cin>>str;
for(int i=0;i<str.size();i++){
//我错了,strcpy(c,s.c_str()); 用在一整个串
char c=str[i];
InsertNode(T,c);

}
//这个怎么能在循环内部呢.想看一下传值里面是怎么变化的!!
//刚才使用返回return,每次都返回当前节点~~
inOrder(T);
}
*/

无冗余字符串数组加建立二叉排序树

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct BiNode
{
char *s;
struct BiNode *lchild;
struct BiNode *rchild;
}BiNode,*BiTree;

void PreOrder(BiTree T)
{
if(T)
{
printf("%s\n",T->s);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main()
{
char **str,e;
int row=1,col=1;
int tag,i,len;
BiTree T,r,t;
str=(char **)malloc(row*sizeof(char *));
str[col-1]=(char *)malloc(col*sizeof(char));
tag=1;
while((e=getchar())!='\n')
{
if(e==' ')
{
str[row-1][col-1]='\0';
tag=0;
continue;
}
else
{
if(tag==0)
{
row++;
col=2;
str=(char **)realloc(str,row*sizeof(char *));
str[row-1]=(char *)malloc(col*sizeof(char));
str[row-1][col-2]=e;
tag=1;
}
else
{
col++;
str[row-1]=(char *)realloc(str[row-1],col*sizeof(char));
str[row-1][col-2]=e;
}
}
}
str[row-1][col-1]='\0';
for(i=0;i<row;i++)
printf("%s\n",str[i]);
printf("\n");

len=strlen(str[0]);
T=(BiTree)malloc(sizeof(BiNode));
T->s=(char *)malloc((len+1)*sizeof(char));
strcpy(T->s,str[0]);
T->lchild=T->rchild=NULL;
t=T;
for(i=1;i<row;i++)
{
len=strlen(str[i]);
r=(BiTree)malloc(sizeof(BiNode));
r->s=(char *)malloc((len+1)*sizeof(char));
r->lchild=NULL;
r->rchild=NULL;
strcpy(r->s,str[i]);
while(t)
{
if(strcmp(t->s,r->s)>0)
{
if(t->lchild)
t=t->lchild;
else
{
t->lchild=r;
break;
}
}
else
{
if(t->rchild)
t=t->rchild;
else
{
t->rchild=r;
break;
}
}
}
t=T;
}
PreOrder(T);
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*输入一个数列以0结尾,建立二叉遍历数,并对其进行逆中序遍历,释放空间*/
/*(2)输入一个数列以0位结束标志,建立二叉遍历树,并对其进行逆中序遍历,释放空间。*/
/*示例树为 : 1
/ \
2 3
\ \
4 5
/ \ \
6 7 8 每次输入一个数,按一次回车
输入的序列为 : 1 2 0 4 6 0 0 7 0 0 3 0 5 0 8 0 0
输出的结果应为: 8 5 3 1 7 4 6 2 */
————————————————

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode{//二叉树数据结构定义;
int data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree CreateTree(){//创建二叉树;
int value;
BiTree t;
scanf("%d",&value);
if(value==0)return NULL;
else{
t=(BiTree)malloc(sizeof(BiTNode));
t->data=value;
t->lchild=CreateTree();
t->rchild=CreateTree();
return t;
}
}

void ReInOrder(BiTree t){//逆中序遍历二叉树;
if(t!=NULL){
ReInOrder(t->rchild);
printf("%d ",t->data);
ReInOrder(t->lchild);
free(t);
}
}

int main(){
BiTree t;
printf("请按序输入二叉树结点的值(以0为标志结束):\n");
t=CreateTree();
printf("逆中序遍历二叉树:\n");
ReInOrder(t);
system("pause");
}

//另一种写法
#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;

struct node{
int data;
node *lchild,*rchild;
};

//两种方式,引用或者node *返回!!!
void insertT(node *&root){
int x;
cin>>x;
if(x==0) return;
if(root==NULL){
//应当创建新结点
root=new node;
root->data=x;
root->lchild=NULL;
root->rchild=NULL;
}
//每个结点应该都是空的,可以自己往下接s
insertT(root->lchild);
insertT(root->rchild);

}

void inOrdedr(node *root){
if(root!=NULL){
inOrdedr(root->rchild);
cout<<root->data<<" ";
inOrdedr(root->lchild);
}

}


int main()
{

node *T=NULL;
insertT(T);
inOrdedr(T);

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

//后序加中序遍历推出

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct node{
int data;
node *lchild;
node *rchild;
};

int a[40],b[40];

node *build(int s1,int e1,int s2,int e2){
//终于知道了!!没有创建新结点,咋个有空间放数据和指针
if(s1>e1) return NULL;
//启示!!写法要配套,不然会出现没有NULL结点无法结束的情况
node *newNode=new node;

//后序遍历最后一个结点为根结点
newNode->data=a[e1];

int i;
for(i=s2;i<=e2;i++){
if(b[i]==a[e1]) break;
}
int pos=i;

int leftNum=pos-s2;

//左子树非空,构建左子树
newNode->lchild=build(s1,s1+leftNum-1,s2,pos-1);
newNode->rchild=build(s1+leftNum,e1-1,pos+1,e2);

return newNode;
}

void preOrder(node *T){
if(T==NULL) return;
cout<<T->data<<" ";
preOrder(T->lchild);
preOrder(T->rchild);
}

void floor(node *T){
queue<node*> q;
//注意队列当中存放的是地址
q.push(T);
//while条件就出口
while(!q.empty()){
//取队头,出队,访问
node *now=q.front();
q.pop();
cout<<now->data<<" ";
if(now->lchild!=NULL) q.push(now->lchild);
if(now->rchild!=NULL) q.push(now->rchild);
}
}
int main()
{
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
node *T;
T=build(0,n-1,0,n-1);
floor(T);
cout<<endl;
}
}

排序算法-冒泡、选择

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
47
//冒泡排序,每次都将一个最大的浮出水面
void buble_sort(int arr[], int length)
{
int i, j, max;
for(i=0, i<length-1, i++)
{
for(j=0, j<length-i-1, j++)
{
if(a[j]>a[j+1])
{
max = a[j];
a[j] = a[j+1];
a[j+1] = max;
}
}
}
}

//另一种,冒泡排序
for(int i=0;i<n;i++)
for(int j=1;j<n;j++)
{//每次选择最小的来进行排序
if(temp[j]<temp[j-1])
{
num=temp[j-1];
temp[j-1]=temp[j];
temp[j]=num;
}
}
//这个选择比较正宗
for (i=0; i<n-1; ++i) //n个数比较n-1轮
{
MinIndex = i;
for (j=i+1; j<n; ++j) //每轮比较n-1-i次, 找本轮最小数的下标
{
if (a[MinIndex] > a[j])
{
MinIndex = j; //保存小的数的下标
}
}
if (MinIndex != i) /*找到最小数之后如果它的下标不是i则说明它不在最左边, 则互换位置*/
{
buf = a[MinIndex];
a[MinIndex] = a[i];
a[i] = buf;
}
}

高低字节交换,循环左右移动

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//十六进制的表达0xff前面是填充4字节
%x可以输出16进制的数

位移操作

int a = 0xf12d2ec2

int c = a >> 8 位移8个 后面的82进制将变成0 结果是 0xf12d2e

然后 c & 0xff 做与运算 之后最后的2位会保留 (2e会因为FF都是1做与运算保留下来 ,2e前面的因为和0做了运算所以会变成0

0xf12d2ec2

0x000000ff 做与运算则会保留下来c2

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
//Q1:第1、4字节交换
unsigned long int ulIn,ulHigh=0,ulLow=0,rolBit;
int n,bit;
printf("请输入一个十六进制数:\n");
scanf("%x",&ulIn);
//fflush(stdin);
//必须移位!!才可以交换位置
ulHigh=ulIn>>24;

ulLow=ulIn<<24;
//不动才可以相与
ulIn=ulIn&0x00ffff00;
ulIn=ulIn|ulHigh;
ulIn=ulIn|ulLow;
printf("交换后的结果为:%x\n",ulIn);
//Q2:在Q1的基础上,2、3字节左移n位
printf("\n输入移位的位数:\n");
scanf("%d",&n);
n=n%16;
rolBit=ulIn&0x00ffff00;
//循环左移的操作实现
rolBit=rolBit>>8;
rolBit=rolBit<<n;
//最多可以移动16位,创造16位的移动环境,循环移动2个字节效果和移动4个字节一样
ulHigh=0;
ulHigh=(rolBit&0xffff0000)>>16;
//高位循环结果
rolBit=(rolBit&0x0000ffff)|ulHigh;
//借8位还原
rolBit=rolBit<<8;
ulIn=(ulIn&0xff0000ff)|rolBit;
printf("对2、3字节循环移位后的结果为:%x\n",ulIn);

//Q3:按照位输出Q2的结果
printf("\n二进制格式输出为:\n");
//16进制如何移位输出2进制!!太强了!
ulHigh=1;
for(bit=0;bit<=31;bit++)
{
//
if(bit%8==0)
putchar(' ');
ulLow=ulIn&(ulHigh<<(31-bit));
//得到最高位,其余为都是0
printf("%d",ulLow>>(31-bit));
//最高位移到最低位,输出值
}
putchar('\n');putchar('\n');
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
26
27
28
29
30
#include<stdio.h>
#include<stdlib.h>

int f(int n){
int c;
for(c=0;n!=0;c++)
//通过n的相与,1&1&1=1,1
//相与就是位与,但为什么减1就可以呢
//有几个1就可以减动几次1
n=n&(n-1);
return c;
}
int main(){
char str[1000];
for(;scanf("%s",str)!=EOF;){
for(int i=0;str[i];i++){
int x=f(str[i]);
printf("%d\n",x);
//x是用来判断奇数还是偶数
//有4个1时4&1=0,3&1=1;!!
//str[i]不用转为2进制,直接移位就可以显示二进制表达,与1相与就可以得到当前位的信息!!
printf("%d",x&1?0:1);
for(int j=6;j>=0;j--){
printf("%d",(str[i]>>j)&1);
}
printf(" ");
}
}
system("pause");
}

16位循环移位

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
//做复杂了!!位操作就可以解决,结合进制转换一起学习

/*

可以不用转化成二进制, 直接用位操作即可,
但是需要注意整数的位操作默认是32位的,题目中要求是16位二进制,
所以左移的结果要与上低16位都为1 ,
高16位都为0 的数(65535)。循环左移可以用左移n位 与上 右移16-n位

*/
#include <iostream>

using namespace std;

int main()
{
int n,m;
while(cin>>n>>m){
int flag=0;
for(int i=0;i<=16;i++){
//实现16位循环位移的关键
if(n==(((m<<i)&65535)|(m>>(16-i)))){
printf("YES\n");
flag=1;
break;
}
}
if(flag==0){
printf("NO\n");
}
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef void (*ptask)();
//函数指针如何定义
//8个任务函数,task0,task1就是相当于指向函数头部的指针;
void task0(){
printf("task0 is called!\n");
}
void task1(){
printf("task1 is called!\n");
}
void task2(){
printf("task2 is called!\n");
}
void task3(){
printf("task3 is called!\n");
}
void task4(){
printf("task4 is called!\n");
}
void task5(){
printf("task5 is called!\n");
}
void task6(){
printf("task6 is called!\n");
}
void task7(){
printf("task7 is called!\n");
}
//ptask fun[9]={task0,task1,task2,task3,task4,task5,task6,task7};

void execute(ptask* fun,int len){//执行函数
for(int i=0;i<len;i++){
//我懂了!!fun[i]指向的是函数名,函数指针!!
ptask pfun=fun[i];
pfun();
}
}

void schedule(){//调度函数;
//和一般指针一样,可以定义指针数组
ptask fun[100];//定义函数指针数组**;
int len;//字符串长度;
char s[1000];
printf("请输入字符串:\n");
scanf("%s",s);
len=strlen(s);
for(int i=0;i<len;i++){
int temp;
temp=s[i]-'0';
if(temp==0)fun[i]=task0;
else if(temp==1)fun[i]=task1;
else if(temp==2)fun[i]=task2;
else if(temp==3)fun[i]=task3;
else if(temp==4)fun[i]=task4;
else if(temp==5)fun[i]=task5;
else if(temp==6)fun[i]=task6;
else if(temp==7)fun[i]=task7;
}
execute(fun,len);
}

int main(){
schedule();
system("pause");
}

如何定义二维数组并初始化new方法使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   int M = 10, N = 5;//10行5列。
int ** a;
//指针数组,表示有M个数组指针
a = new int *[M];
for(int i = 0; i < M; i ++)
a[i] = new int[N];

for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
a[i][j]=1;
}
}
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}

fill(a[0],a[0]+M*N,1);

动态分配内存,new方法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
using namespace std;

int example1()
{
//可以在new后面直接赋值
int *p = new int(3);
//也可以单独赋值
//*p = 3;

//如果不想使用指针,可以定义一个变量,在new之前用“*”表示new出来的内容
int q = *new int;
q = 1;
cout << q << endl;

return *p;
}

int* example2()
{
//当new一个数组时,同样用一个指针接住数组的首地址
int *q = new int[3];
for(int i=0; i<3; i++)
q[i] = i;

return q;
}

struct student
{
string name;
int score;
};


student* example3()
{
//这里是用一个结构体指针接住结构体数组的首地址
//对于结构体指针,个人认为目前这种赋值方法比较方便
student *stlist = new student[3]{{"abc", 90}, {"bac", 78}, {"ccd", 93}};

return stlist;
}



int main()
{
int e1 = example1();
cout <<"e1: "<< e1 << endl;

int *e2 = example2();
for(int i=0; i<3; i++)
cout << e2[i] << " ";
cout << endl;


student *st1 = example3();

for(int i=0; i<3; i++)
cout << st1[i].name << " " << st1[i].score << endl;



return 0;
}

动态分配内存,实现输入无限制长度字符串malloc和realloc

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STRLEN 20 //每次分配的长度

int main(){

int strSize=STRLEN; //字符串能存储的最大长度
int strLength=0; //已使用长度
char input=NULL; //接受输入的字符
char *arr=(char*)malloc(sizeof(char)*STRLEN);
//数组如何分配内存
while((input=getc(stdin))!='\n'){
arr[strLength++]=input;
if(strLength==STRLEN){
strSize=strSize+STRLEN;//更新数组能存储最大长度
arr=(char*)realloc(arr,strSize); //如何在已经申请空间上扩展
}
}
arr[strLength]='\0';
printf("%d,%s\n",strlen(arr),arr);
}


realloc总结-主要用来实现无冗余:
void *realloc(void *ptr, size_t size)
ptr -- 指针指向一个要重新分配内存的内存块,该内存块之前是通过调用 malloc、calloc 或 realloc 进行分配内存的。如果为空指针,则会分配一个新的内存块,且函数返回一个指向它的指针。
size -- 内存块的新的大小,以字节为单位。如果大小为 0,且 ptr 指向一个已存在的内存块,则 ptr 所指向的内存块会被释放,并返回一个空指针。

无冗余输入字符串

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int main()
{
fflush(stdin);
int lenth=0; //已使用长度
char input; //接受输入字符
//括号的原因,必须要带括号,且位置不能出错

//关键在于malloc分配空间
char *arr=(char*)malloc(sizeof(char));
while((input=getchar())!='\n'){
if(input!=' '){
arr[lenth++]=input;
arr=(char*)realloc(arr,sizeof(char)*(lenth+1));
}
}
arr[lenth]='\0';
printf("%s\n",arr);

char a[lenth/2+1];
char b[lenth/2+1];
int num1=0,num2=0;
for(int i=0;i<lenth;i++){
if((i+1)%2==1){
a[num1++]=arr[i];
}else{
b[num2++]=arr[i];
}
}
printf("%s %s\n",a,b);

sort(a,a+num1);
sort(b,b+num2);
printf("%s %s\n",a,b);
return 0;
}


#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int *preal = NULL;
int num, count = 0;

do {
printf("请输入一个整数(-1表示结束):" );
scanf("%d", &num);

if (num != -1) {
count++;
preal = (int *)realloc(preal, count * sizeof(int)); // 申请内存,随count的增加而扩展
if (preal == NULL) { printf("申请内存失败" ); exit(1); }
preal[count - 1] = num;
}

} while (num != -1);

free(preal); // 释放内存

return 0;
}

char和string的转换方法

1
2
3
4
5
6
7
8
9
10
11
char c[20]; 
string s="1234";

strcpy(c,s.c_str());

这样才不会出错,c_str()返回的是一个临时指针,不能对其进行操作。
语法: const char *c_str();

c_str()函数返回一个指向正规C字符串的指针, 内容与本string串相同.,这是为了与c语言兼容,在c语言中没有string类型,故必须通过string类对象的成员函数c_str()把string 对象转换成c中的字符串样式。

注意:一定要使用strcpy()函数 等来操作方法c_str()返回的指针

日期问题

日期问题的常规操作

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
/*给出年份m和一年中的第几天,算出第几天是几月几号,按照yyyy-mm-dd格式打印*/
#include <stdio.h>

int IsYeap(int year){
if(year%400==0||(year%100!=0&&year%4==0)) return 1;
else return 0;
}
int DayOfMonth[13][2]={
0,0,
31,31,
28,29,
31,31,
30,30,
31,31,
30,30,
31,31,
31,31,
30,30,
31,31,
30,30,
31,31
};

int main(){
int m,n;
while(scanf("%d %d",&m,&n)!=EOF){
int month=0;
for(int i=1;i<=12;i++){
if(n>DayOfMonth[i][IsYeap(m)]){
n=n-DayOfMonth[i][IsYeap(m)];
}else{
month=i;
break;
}
}
//c语言的格式输出好处
printf("%d-%02d-%02d\n",m,month,n);
}
}

日期问题相差天数

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
47
48
49
50
51
52
53
54
55
56
57
//太复杂的做法    
string s1,s2,tmp;
cin>>s1>>s2;
if(s1>s2){
tmp=s1;
s1=s2;
s2=tmp;
}
string yearS1=s1.substr(0,4),monS1=s1.substr(4,2),dayS1=s1.substr(6,2);
string yearS2=s2.substr(0,4),monS2=s2.substr(4,2),dayS2=s2.substr(6,2);
int year1,mon1,day1,year2,mon2,day2;
year1=atoi(yearS1.c_str());
mon1=atoi(monS1.c_str());
day1=atoi(dayS1.c_str());
year2=atoi(yearS2.c_str());
mon2=atoi(monS2.c_str());
day2=atoi(dayS2.c_str());
cout << year1 <<" "<< mon1 <<" "<<day1<< endl;

//机制简便的处理办法
#include <cstdio>
int month[13][2]={{0,0},{31,31},{28,29},{31,31},{30,30},{31,31},
{30,30},{31,31},{31,31},{30,30},{31,31},{30,30},{31,31}};
int main()
{
int time1,y1,m1,d1;
int time2,y2,m2,d2;
while(scanf("%d%d",&time1,&time2)!=EOF)
{
if(time1>time2)
{
int temp=time1;
time1=time2;
time2=temp;
}
y1=time1/10000;m1=time1%10000/100;d1=time1%100;
y2=time2/10000;m2=time2%10000/100;d2=time2%100;
int ans=1;
while(y1<y2||m1<m2||d1<d2)
{
d1++;
if(d1==month[m1][(y1%4==0&&y1%100!=0)||(y1%400==0)]+1)
{
m1++;
d1=1;
}
if(m1==13)
{
y1++;
m1=1;
}
ans++;
}
printf("%d\n",ans);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int month[13][2]={{0,0},{31,31},{28,29},{31,31},{30,30},{31,31},
{30,30},{31,31},{31,31},{30,30},{31,31},{30,30},{31,31}};
char weekname[8][15]={"","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
char monthname[13][15]={"","January","February","March","April","May","June","July","August","September","October","November","December"};
int StringtoNumber(char a[])
{
for(int i=1;i<13;++i)
if(strcmp(a,monthname[i])==0)
return i;
}
void NumbertoString(char a[],int ans,int flag)
{
int b;
if(flag==0)
b=6-ans%7;
else
b=(ans+6)%7;
if(b==0)
b=7;
strcat(a,weekname[b]);
}
int main()
{
char m[20],week[20];
int y1,m1,d1;
while(scanf("%d %s %d",&d1,m,&y1)!=EOF)
{
int y2=2018,m2=1,d2=6,flag=0,ans=0;
m1=StringtoNumber(m);
memset(m,'\0',sizeof(m));
memset(week,'\0',sizeof(week));
if(y1>y2||(y1==y2&&m1>m2)||(y1==y2&&m1==m2&&d1>d2))
{
flag=1;
swap(y1,y2);
swap(m1,m2);
swap(d1,d2);
}
while(y1<y2||m1<m2||d1<d2)
{
d1++;
if(d1==month[m1][(y1%4==0&&y1%100!=0)||(y1%400==0)]+1)
{
m1++;
d1=1;
}
if(m1==13)
{
y1++;
m1=1;
}
ans++;
}
NumbertoString(week,ans,flag);
printf("%s\n",week);
}
return 0;
}

矩阵转置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<string>
#include <ctype.h>
using namespace std;
int main()
{
int a[2][3];

for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
cin>>a[i][j];
}
}
for(int j=0;j<3;j++){
for(int i=0;i<2;i++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}

for循环的进阶用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int main()
{
int n,m;
while(cin>>n>>m){
int count=0;
for(int i=n%10;n!=0;n=n/10,i=n%10){
//开始循环前的定义,可以多个先后语句 ; 循环终止的条件;每次执行一次循环之后的操作
for(int temp=m,j=temp%10;temp!=0;temp=temp/10,j=temp%10){
count=count+i*j;
}
}
cout<<count<<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
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstring>

using namespace std;

struct student{
char name[100];
char sex[100];
int age;
}stu[1000];
int main()
{ int n,no,m;
char temp[100];
//可以自动省去001前缀
while(cin>>n){
for(int i=0;i<n;i++){
cin>>no;
cin>>stu[no].name>>stu[no].sex>>stu[no].age;
}
cin>>m;
if(m==0) break;
//终于知道了。由于要输出学号,因此需要要使用字符串转整型
for(int i=0;i<m;i++){
memset(temp,'\0',sizeof(temp));
cin>>temp;
//使用方法不对,和scanf一样,得要赋给地址
sscanf(temp,"%d",&no);
if(stu[no].age!=NULL)
cout<<temp<<" "<<stu[no].name<<" "<<stu[no].sex<<" "<<stu[no].age<<endl;
else cout<<"No Answer!"<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <cstring>
int main()
{//静态数组,进行填充
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
printf(" ");
for(int j=0;j<n-1-i;j++)
printf("* ");
printf("*");
for(int j=0;j<i;j++)
printf(" ");
printf("\n");
}
for(int i=n-1;i>0;i--)
{
for(int j=0;j<i-1;j++)
printf(" ");
for(int j=0;j<n-1-i+1;j++)
printf("* ");
printf("*");
for(int j=0;j<i-1;j++)
printf(" ");
printf("\n");
}
}
return 0;
}
//直接找规律输出,太强
#include <cstdio>
#include <cstring>
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
printf(" ");
for(int j=0;j<n-1-i;j++)
printf("* ");
printf("*");
for(int j=0;j<i;j++)
printf(" ");
printf("\n");
}
for(int i=n-1;i>0;i--)
{
for(int j=0;j<i-1;j++)
printf(" ");
for(int j=0;j<n-1-i+1;j++)
printf("* ");
printf("*");
for(int j=0;j<i-1;j++)
printf(" ");
printf("\n");
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
d
a b c d c b a
a b c b a
a b a
a
#include <iostream>
#include <cctype>
using namespace std;

int main()
{
char c;
while(cin>>c){
if(islower(c)){
int h=c-'a'+1;
int l=2*h-1;
for(int i=0;i<h;i++){
for(int j=0;j<=i-1;j++) printf(" ");
for(int j=i;j<h;j++) printf("%c ",'a'+j-i);
for(int j=h;j<l-i;j++) printf("%c ",'a'+l-i-j-1);
for(int j=l-i;j<l;j++) printf(" ");
printf("\n");
}
}else{
int h=c-'A'+1;
int l=2*h-1;
for(int i=0;i<h;i++){
for(int j=0;j<=i-1;j++) printf(" ");
for(int j=i;j<h;j++) printf("%c ",'A'+j-i);
for(int j=h;j<l-i;j++) printf("%c ",'A'+l-i-j-1);
for(int j=l-i;j<l;j++) printf(" ");
printf("\n");


}
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
C
AA
AB BA
ABC CBA
AB BA
AA
#include<stdio.h>
int main(){
char c;
int sum,i,j;
while(scanf("%c",&c)!=EOF){
sum=c-'A'+1;
for(i=0;i<sum;i++){
for(j=0;j<2*(sum-1-i);j++){
printf(" ");//输出前边的空格;
}
for(j=0;j<=i;j++){
printf("%c",'A'+j);//输出前边一串字符串;
}
for(j=0;j<i;j++){
printf(" ");//输出中间的字符串;
}
for(j=i;j>=0;j--){
printf("%c",'A'+j);
}
printf("\n");
}
for(i=sum-2;i>=0;i--){
for(j=0;j<2*(sum-1-i);j++){
printf(" ");//输出前边的空格;
}
for(j=0;j<=i;j++){
printf("%c",'A'+j);//输出前边一串字符串;
}
for(j=0;j<i;j++){
printf(" ");//输出中间的字符串;
}
for(j=i;j>=0;j--){
printf("%c",'A'+j);
}
printf("\n");
}
getchar();//接受回车符;
}
}

哈希专题

hash表的用法

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 <iostream>

using namespace std;

int main()
{

int n,m;
while(cin>>n>>m){
//最好还是固定住值,不然会编译报错,初始化为0
int hashTable[201]={0};
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
hashTable[arr[i]]++;
}
for(int i=0;i<n;i++){
if(hashTable[arr[i]]>1)
cout<<hashTable[arr[i]]-1<<endl;
else cout<<"BeiJu"<<endl;
}
}
return 0;

}

hash表高阶用法,二维数组存放不同组的hash值

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n,m,s[110],g[110],t[110];
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
int z[110][2100]={0};
scanf("%d",&m);
for(int j=0;j<m;j++)
scanf("%d",&s[j]);
for(int j=0;j<m;j++)
{
scanf("%d",&g[j]);
z[g[j]][s[j]]++;
}
//这里的排序算法,使用很是巧妙
sort(s,s+m);
sort(g,g+m);
for(int j=0;j<m;j++)
{//关键要落实到此处,输出第一个之后,每次都输出与前一个不同的数
if(j==0||(j>0&&g[j]!=g[j-1]))
{//输出格式也很关键
printf("%d={",g[j]);
for(int k=0;k<m;k++)
{
if(k==0||(k>0&&s[k]!=s[k-1]))
{
printf("%d=%d",s[k],z[g[j]][s[k]]);
if(k!=m-1&&s[k]!=s[m-1])
printf(",");
}
}
printf("}\n");
}
}
}
}
return 0;
}

hash结合字母表处理字符串的使用方法

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
47
48
49
50
51
//这个题的输出处理方式太强了
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{

string str1,str2;
while(getline(cin,str1)){
int hashTable[26]={0};
getline(cin,str2);
for(int i=0;i<str2.size();i++){
hashTable[str2[i]-'a']++;
}
for(int i=0;i<str1.size();i++){
if(str1[i]!=' '&&hashTable[str1[i]-'a']!=0)
{
str1.erase(i,1);
//这个减一必不可少,因为erase去除了当前的i,则原来的i+1向前移动,如果不向前移动,会错过检查原来的i+1
i=i-1;
}

}
cout<<str1<<endl;
}

return 0;

}
//其实做的复杂了,可以更简单的,不用删除,控制输出即可
#include <cstdio>
#include <cstring>
int main()
{
char s1[10010],s2[10010];
//255表示全部字符的范围
int flag[255];
while(gets(s1))
{
memset(flag,0,sizeof(flag));
gets(s2);
for(int i=0;s2[i]!='\0';++i)
flag[s2[i]]=true;
for(int i=0;s1[i]!='\0';++i)
if(flag[s1[i]]==false)
printf("%c",s1[i]);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
样例输入
1
6
样例输出
0
0 1 1
0 1 1 2 3
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34 55
*/
#include <iostream>

using namespace std;

//递归输出中间值不是从中间输出的1!!,观念性错误,应当从传入的值入手

int f(int a){

if(a==0||a==1) return 1;
else return f(a-1)+f(a-2);
}

int main()
{
int n;
while(cin>>n){
for(int k=0;k<n;k++){
int num;
cin>>num;
for(int i=0;i<num;i++){
//一定要学会找规律啊~~,不能只想着把它们存在数组里一起输出
for(int j=0;j<2*(num-1-i);j++)
cout<<" ";
if(i!=0){
cout<<"0 ";
for(int j=0;j<2*i-1;j++)
cout<<f(j)<<" ";
cout<<f(2*i-1)<<endl;
}
//特殊情况都得要考虑到
else cout<<0<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
int count;
void scheme(int a)
{
//出口是当a减成0
if(a==0)
{
count++;
return;
}
//每次都从最大处开始减少,减少的方式不同
for(int i=1;i<=2&&i<=a;i++)
scheme(a-i);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
count=0;
scheme(n);
printf("%d\n",count);
}
return 0;
}

#include <iostream>

using namespace std;

//简单的递归,主要是要理清楚逻辑,对于所有的物品,都可以选择放入或者不放入,最后能使总和为40即为一种解~

int count,n,a[20];
//n要在此处定义的原因,作为界限
void search(int index,int sum){
if(sum==0)
{
//出口是最后可以完全拿满40,这才可以出去
count++;
return;
}
if(index>=n)
//如果n个值都遍历完了,还找不到那么就失败了
return;
if(sum-a[index]>=0)
search(index+1,sum-a[index]);

//最关键的来了,一种方法失败,则把index往后面进移动,从后面开始计算,即使没失败,也要继续往下试探
search(index+1,sum);
}

int main()
{
while(cin>>n){
count=0;
for(int i=0;i<n;i++)
cin>>a[i];
search(0,40);
cout<<count<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>

using namespace std;

int n;
//正确定义是集合
bool flag[20]={false};
int ans[20];
void combine(int cnt){
if(cnt==n){
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
printf("\n");
return;
}
for(int i=0;i<n;i++){
if(flag[i]==false){
//cnt计数的是以第几个数打头
ans[cnt]=i+1;
//访问过
flag[i]=true;
combine(cnt+1);
//访问完之后恢复
flag[i]=false;
}
}
}

int main()
{
while(cin>>n){
combine(0);
}
return 0;
}
//非递归方法,还没有研究透彻,但是调试有了进步
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> answer;
stack<int> process;
bool flag[20]={false};
int n;
void combine()
{
process.push(1);
answer.push_back(1);
flag[1]=true;
int visit;
bool pop=false;
while(!process.empty())
{
if(answer.size()==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",answer[i]);
}
printf("\n");
pop=true;
}
visit=-1;
for(int i=1;i<=n;i++)
{
if(flag[i]==false)
{
visit=i;
break;
}
}
if(visit==-1)
{
flag[process.top()]=false;
process.pop();
answer.pop_back();
pop=true;
continue;
}
if(pop)
{
bool search=false;
for(int i=process.top()+1;i<=n;i++)
{
if(flag[i]==false)
{
search=true;
visit=i;
break;
}
}
flag[process.top()]=false;
process.pop();
answer.pop_back();
if(search==false)
{
pop=true;
continue;
}
else
{
pop=false;
}
}
if(visit!=-1)
{
flag[visit]=true;
process.push(visit);
answer.push_back(visit);
}
}

}
int main()
{
while(cin>>n)
{
combine();
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>

using namespace std;

int n;
int m;
//正确定义是集合
bool flag[20]={false};
int ans[20];
void combine(int x,int cnt){
//只能证明出口问题,关键在于不知道如何分叉,返回数据
if(cnt==n){
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
printf("\n");
return;
}
//果然x是变化的,只是没想到怎么变1!,可以带参数的,循环一次之后前面那个就不用参与循环
for(int i=x;i<=m;i++){
if(flag[i-1]==false){
//cnt计数的是以第几个数打头
ans[cnt]=i;
//访问过
flag[i-1]=true;
//可以理解为记住了x的值!!往下走
combine(i,cnt+1);
//访问完之后恢复
flag[i-1]=false;
}
}
}

int main()
{
while(cin>>m>>n){
combine(1,0);
}
return 0;
}
//非递归方法,关键是什么时候入栈,什么时候出战,利用栈的特性,可以将一个数定住循环其他
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
int n,r;
void combine()
{
stack<int> process;
vector<int> answer;
process.push(1);
answer.push_back(1);
int elem;
bool pop=false;
while(!process.empty())
{
if(answer.size()==r)
{
for(int i=0;i<r;i++)
{
printf("%d ",answer[i]);
}
printf("\n");
pop=true;
}
elem=process.top();
//如果elem已经达到最大值,就一定要出栈了,不然没得位置,并且后面不能继续,直接跳过
if(elem==n)
{
process.pop();
answer.pop_back();
pop=true;
continue;
}
//后面的行为就是先出再进
if(pop)
{
process.pop();
answer.pop_back();
pop=false;
}
//只要初始的第一个值还没到n,process就不会为空
if(elem<n)
{
process.push(elem+1);
answer.push_back(elem+1);
}
}
}

int main()
{
while(~scanf("%d %d",&n,&r))
{
combine();
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cmath>
using namespace std;
int n,k,count;
int number[25],sum;
bool isPrime(int n)
{
if(n<=1)
return false;
int sqr=(int)sqrt(1.0*n);
for(int i=2;i<=sqr;i++)
{
if(n%i==0)
return false;
}
return true;
}
void combine_judge(int pos,int level)
{
if(level==k)
{
if(isPrime(sum)==true)
{
count++;
}
return;
}
for(int i=pos;i<n;i++)
{
sum+=number[i];
combine_judge(i+1,level+1);
//回退之后减去,目的是换下一条路径
sum-=number[i];
}
}
int main()
{
while(~scanf("%d %d",&n,&k))
{
for(int i=0;i<n;i++)
{
scanf("%lld",&number[i]);
}
count=0;
sum=0;
combine_judge(0,0);
printf("%d",count);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <cmath>
using namespace std;

const int maxn=26;
int n,p[maxn];
int cnt=0;
bool hashTable[maxn]={false};

//要类比全排列,找出所有n*n行元素的排列方式,就是皇后可能排列的位置
//要筛选出其中在对角线上的
void DFS(int index){
//递归边界,表示已经处理完1-n位
if(index==n+1){
bool flag=true;
//flag为true表示当前排列为合法方案
for(int i=1;i<=n;i++){
//遍历任意两个皇后,判断是否合法
for(int j=i+1;j<=n;j++){
//相当于两个坐标(i,p[i)和(j,p[j])进行比较
//由于全排列行列肯定不一致,关键是看是否在同一对角线
if(abs(i-j)==abs(p[i]-p[j]))
flag=false;//表示不合法
}
}
if(flag){
for(int i=1;i<=n;i++){
cout<<p[i]<<" ";
}
cout<<endl;
}
return;
}
//此处是递归分叉
for(int i=1;i<=n;i++){
if(hashTable[i]==false){
//访问未访问
hashTable[i]=true;
//令p的第index位为i,就是把i带入当前排列
p[index]=i;
DFS(index+1);
//返回后如何进入下一个分叉
hashTable[i]=false;
}
}


}

int main()
{
while(cin>>n){
DFS(1);
}
return 0;
}

//剪枝版,可以去掉多余的递归,对于p[index]=i表示index列的行号为i
#include <iostream>
#include <cmath>
using namespace std;

const int maxn=26;
int n,p[maxn];
int cnt=0;
bool hashTable[maxn]={false};

//要类比全排列,找出所有n*n行元素的排列方式,就是皇后可能排列的位置
//要筛选出其中在对角线上的
void DFS(int index){
//递归边界,表示已经处理完1-n位
if(index==n+1){
//出口不变,判定的地方会变,能到这里的一定是合法的
for(int i=1;i<=n;i++){
cout<<p[i]<<" ";
}
cout<<endl;
return;
}
//此处是递归分叉
for(int i=1;i<=n;i++){
if(hashTable[i]==false){
bool flag=true; //表示当前皇后不会和之前的皇后冲突
for(int pre=1;pre<index;pre++){
//第index列皇后的行号为x,第pre列皇后的行号为p[pre]
if(abs(index-pre)==abs(i-p[pre])){
flag=false; //冲突,是与之前的皇后在对角线,而不是全部选出来再判断
break;
}
}
if(flag){
//这里变成可以吧皇后放在第x行
hashTable[i]=true;
//令p的第index位为i,就是把i带入当前排列
p[index]=i;
DFS(index+1);
//返回后如何进入下一个分叉
hashTable[i]=false;
}

}
}


}

int main()
{
while(cin>>n){
DFS(1);
}
return 0;
}

走迷宫-深度遍历DFS版

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//深度优先遍历解决迷宫问题

#include <iostream>

using namespace std;

//如果不想递归当中带太多的内容,就应该多定义全局变量
int m,n,last_x,last_y,start_x,start_y;
int atlas[20][20];
//存放矩阵
bool flag[20][20]={false}; //还是得要定义是否访问过,不走回头路
int direct[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int index,cnt; //记录index是为了知道结果中有几个点
int answer[250][2]; //存放x,y坐标的办法

bool judge(int x,int y){
if(x==0||y==0||y>n||x>m)
return false;
//当前位置为0或者(x,y)已经访问过了或者越界返回false
if(atlas[x][y]==0||flag[x][y]==true)
return false;
return true;
}

void dispose(int x,int y,int index){
//出口地址
if(x==last_x&&y==last_y){
for(int i=0;i<index;i++){
//格式的问题,不要当成大问题
if(i!=index-1)
printf("(%d,%d)->",answer[i][0],answer[i][1]);
else
printf("(%d,%d)\n",answer[i][0],answer[i][1]);
}
cnt++;
return;

}
for(int i=0;i<4;i++){
int new_x=x+direct[i][0];
int new_y=y+direct[i][1];
if(judge(new_x,new_y)){
//表示已经访问
flag[new_x][new_y]=true;
answer[index][0]=new_x;
answer[index][1]=new_y;
dispose(new_x,new_y,index+1);
flag[new_x][new_y]=false;
//回退时候的操作
}
}
}


int main()
{
while(cin>>m>>n){
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>atlas[i][j];
flag[i][j]=false;
}
}
cin>>start_x>>start_y;
cin>>last_x>>last_y;
//每次循环都要设定index和方案数位0,对全局变量的处理
index=0;
cnt=0;
//入口也得要判断处理
if(judge(start_x,start_y)){
flag[start_x][start_y]=true;
answer[index][0]=start_x;
answer[index][1]=start_y;
dispose(start_x,start_y,index+1);
if(cnt==0){
cout<<-1<<endl;
}

}
else{
cout<<-1<<endl;
}
}
return 0;
}

计算矩阵中含1块-BFS版

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
4
#include <iostream>
#include <queue>
using namespace std;
const int maxn =100;

struct node{
int x,y; //坐标(x,y)
}Node;

int n,m; //矩阵大小
int matrix[maxn][maxn]; //01矩阵
bool inq[maxn][maxn]={false}; //记录位置是否已经入过队
int X[4]={0,0,1,-1}; //增量数组,表示上下左右位置
int Y[4]={1,-1,0,0};

bool judge(int x,int y){
//判断坐标是否需要访问,越界返回false
if(x>=n||x<0||y>=m||y<0) return false;
//是因为入队了,所以暂时不访问,当不在队中的时候还是得要访问
if(matrix[x][y]==0||inq[x][y]==true) return false;
return true;

}

void BFS(int x,int y){
queue<node> Q; //定义队列
Node.x=x,Node.y=y; //当前结点的坐标
Q.push(Node); //将节点入队,从队尾进的
inq[x][y]=true;
while(!Q.empty()){
node top=Q.front(); //从队首取出元素
Q.pop(); //取出就可以出栈了
for(int i=0;i<4;i++){
//循环四次得到四个相邻位置,只能标识已经入队,不能标识已经访问
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(judge(newX,newY)){
//设置Node的新坐标
Node.x=newX,Node.y=newY;
Q.push(Node);
//广义遍历不用回溯走回头路,去过了就去过了
inq[newX][newY]=true;
}
}
}
}

//求出给定矩阵若干个相邻1构成的块个数
int main()
{
while(cin>>n>>m){
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
cin>>matrix[x][y];
}
}
int ans=0; //存放块数
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
//循环所有元素,若元素为1且未入队
if(matrix[x][y]==1&&inq[x][y]==false){
ans++;
BFS(x,y);
}
}
}
printf("%d\n",ans);
}

return 0;
}

BFS得出玛雅人密码交换次数

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
玛雅人密码-BFS该怎么想

该题目的思路就是:
如何用队列广度优先遍历所有可能性(QUEUE) +
如何判别并标示某串是否访问过(MAP) +
如何记录某串已经交换字符的次数 +
子串2012是否存在
这几个问题如果解决了我想你肯定能写出来。

*/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

map<string,int> mp; //mp[str]表示str交换次数
queue<string> q; //队列用于BFS

string swapStr(string str,int i){
//分布思想,交换写一个办法
string newStr=str;
char tmp=newStr[i];
newStr[i]=newStr[i+1];
newStr[i+1]=tmp;
return newStr;
}

//再分步,判断是否含有2012
bool judge(string str){
if(str.find("2012",0)==string::npos) return false;
else return true;
}

//广度优先搜索特点,扩展,遍历所有结果
int BFS(string str){
string newStr;
mp.clear();
while(!q.empty()) q.pop();
q.push(str); //直接将初始字符串作为起点放入队列

mp[str]=0; //初始交换次数

while(!q.empty()){
str=q.front();
q.pop();
//终于知道为啥要用BFS了,因为交换第一次算作第一层,交换第二层算第二层
for(int i=0;i<str.size();i++){
newStr=swapStr(str,i);

if(mp.find(newStr)==mp.end()) //表示这个字符串没有出现
{

mp[newStr]=mp[str]+1;
if(judge(newStr)) return mp[newStr];
else q.push(newStr);
}
else continue; //出现过的不用处理
}
}
return -1; //遍历完成,没发现符合要求的字符串
}

int main()
{
int n;
string str;
while(cin>>n){
cin>>str;
if(judge(str)) printf("0\n"); //一开始就符合要求
else{
int ans=BFS(str);
printf("%d\n",ans);
}
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
5 5
. . . . .
. * . * .
. * S * .
. * * * .
. . . T *
2 2 4 3
11

#include <iostream>
#include <queue>
using namespace std;

const int maxn=100;

struct node{
int x,y;
int step;
//step是从起点S到达该位置的最少步数即层数
}S,T,Node;

int n,m;
char maze[maxn][maxn]; //迷宫信息
bool inq[maxn][maxn]={false}; //记录位置(x,y)是否已经入过队
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};

bool test(int x,int y){
if(x>=n||x<0||y>=m||y<0) return false;
if(maze[x][y]=='*') return false;
//墙壁或者已经入过队
if(inq[x][y]==true) return false;
return true;
}

int BFS(){
queue<node> q;
q.push(S); //将起点S入队
while(!q.empty()){
node top=q.front(); //取出队首元素
q.pop();
if(top.x==T.x&&top.y==T.y){
return top.step; //终点直接返回最少步数
}
for(int i=0;i<4;i++){
//检查4个相邻位置
int newX=top.x+X[i];
int newY=top.y+Y[i];
if(test(newX,newY)){
//相当于创建新点了
Node.x=newX,Node.y=newY;
Node.step=top.step+1;
q.push(Node);
inq[newX][newY]=true;
}
}
}
return -1;
}

int main()
{
while(cin>>n>>m){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>maze[i][j];
}
}
cin>>S.x>>S.y>>T.x>>T.y;
S.step=0;
cout<<BFS()<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

char a[8][9];
int dx[] = {0, 1, -1, 0, 0, -1, 1, -1, 1};
int dy[] = {0, 0, 0, 1, -1, 1, 1, -1, -1};
bool flag;

struct node{
int x, y;
int step;
}s, temp;

bool check(int x, int y)
{
if(x >= 8 || x < 0 || y >= 8 || y < 0)
return false;
return true;
}

void bfs()
{
int i, j;
s.x = 7;
s.y = 0;
s.step = 0;
queue<node>q;
q.push(s);
while(!q.empty())
{

s = q.front();
q.pop();

for(i = 0;i < 9; i++)
{
temp.x = s.x + dx[i];
temp.y = s.y + dy[i];
temp.step = s.step + 1;
/*因为我们记下来所走的步数为step,所以判断点a[temp.x-temp.step+1][temp.y]是否为石头即可知道所走的下一步是否为石头
点a[temp.x-temp.step][temp.y]即为所走点的上面是否为石头*/
if(check(temp.x, temp.y) && a[temp.x-temp.step][temp.y] != 'S' && a[temp.x-temp.step+1][temp.y] != 'S')
{
//用判断是否走满了八步来代替判重
if(a[temp.x][temp.y] == 'A' || temp.step > 8)
{
flag = 1;
return ;
}
q.push(temp);
}
}
}
return ;
}

int main()
{
int t, i, j, k;
scanf("%d", &t);
k = 1;
getchar();
while(t--)
{

for(i = 0; i < 8; i++)
{
scanf("%s", a[i]);


}
flag = 0;
bfs();
printf("Case #%d: ", k);
if(flag)
printf("Yes\n");
else
printf("No\n");
k++;
}
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
//著名的八皇后问题
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;


//果然是逻辑关系没有理顺,要代入数学知识的!!
int main()
{
int n;
while(cin>>n){
for(int i=0;i<=n/5;i++){
for(int j=0;j<=(n-i*5)/3;j++){
for(int k=0;k<=(n-i*5-j*3)/(1.0/3.0);k++){
if(i+k+j==100)
printf("x=%d,y=%d,z=%d\n",i,j,k);
}
}
}
}

}

矩阵乘法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//大佬的输入处理和轻描淡写的循环
#include <cstdio>
#include <cstring>
int main()
{
int a[2][3],b[3][2],c[2][2],n;
while(~scanf("%d",&n))
{
a[0][0]=n;
for(int i=0;i<2;i++)
for(int j=0;j<3;j++)
if(i!=0||j!=0)
scanf("%d",&a[i][j]);
for(int i=0;i<3;i++)
for(int j=0;j<2;j++)
scanf("%d",&b[i][j]);
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
{
//此处的直接处理怎么想不到呢
printf("%d",a[i][0]*b[0][j]+a[i][1]*b[1][j]+a[i][2]*b[2][j]);
if(j!=1) printf(" ");
else printf("\n");
}
}
return 0;
}
//以下是我总结出来的规律,计算矩阵成绩的办法,要加入一层循环用来计算
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{ int n;
int a[2][3],b[3][2],c[2][2]={0};
int a1,a2,a3;
while(cin>>a1>>a2>>a3){
memset(c,0,sizeof(c));
a[0][0]=a1;
a[0][1]=a2;
a[0][2]=a3;
for(int i=1;i<2;i++){
for(int j=0;j<3;j++){
cin>>a[i][j];
}
}
for(int i=0;i<3;i++){
for(int j=0;j<2;j++){
cin>>b[i][j];
}
}

for(int i=0;i<2;i++){
for(int m=0;m<2;m++){
//最关键的在这里,m次表示一行分别乘以两列,而j则值控制每列乘以的次数
for(int j=0;j<3;j++){
c[i][m]=c[i][m]+a[i][j]*b[j][m];
}
}

}

for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
cout<<c[i][j]<<" ";
}
cout<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
1/1 1/2 1/3
1/2 1/1 1/2
1/3 1/2 1/1
矩阵对角线上的元素始终是1/1,对角线两边分数的分母逐个递增。
请求出这个矩阵的总和。
*/
//充分利用对称性!!
#include <cstdio>
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==0) break;
double sum=0.0;
for(int i=n;i>=2;i--)
//这里很关键,只需要计算有几种分数相乘即可
sum+=1.0/i*(n-i+1)*2;
sum+=n*1;
printf("%.2f\n",sum);
}
return 0;
}
//找规律的办法
int main()
{
int N;
while(cin>>N){
if(N==0) break;
double ans=0;
for(double i=1;i<=N;i++){
for(double j=1;j<=i;j++){
ans=ans+(1.0/(1.0+i-j));
}
for(double j=i+1;j<=N;j++){
ans=ans+(1.0/(1.0+j-i));
}
}
printf("%.2f\n",ans);
}

return 0;
}

贪心算法,求代理服务器访问IP方法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
基本贪心思想,要访问的全部server列表及顺序已经给定
并且***ip可以多次重复选择,每次选择能访问最远的ip地址进行访问
再从断点开始换下一个能访问最远的ip

*/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
while(cin>>n){
string ip[1005];
string server[5005];
int i,j,m;

for(i=0;i<n;i++)
cin>>ip[i];
cin>>m;
for(i=0;i<m;i++)
cin>>server[i];

//判断输出-1的情况
if(n==1){
int feasible=1;
for(i=0;i<m;i++){
if(ip[0]==server[i])
feasible=0;
}
//遍历全部server,看唯一的ip是否在其中
if(feasible)
cout<<1<<endl;
else
cout<<-1<<endl;
continue;
}

int cnt=0,start=0,maxn=0;
//贪心的关键
while(start!=m){
for(i=0;i<n;i++){
for(j=start;j<m;j++){
if(ip[i]==server[j])
break;
}
//该循环结束后,如果j==m,则说明走通,否则表明最远可走到server[j]
if(j>maxn)
maxn=j;
}
start=maxn;
//找到并记录所有ip中最远能走到的server,下次从这里开始
cnt++;

}
cout<<cnt-1<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
using namespace std;
string Addition(string one, string two);
int main()
{
int n, i;
string first, second;
cout << "Please enter two numbers: ";
cin >> first >> second;
cout << "The result is: " << Addition(first, second) << endl;
//return 0;
system("pause");
}
string Addition(string one, string two)
{
int j, max;
//分别表示第一,二个字符串的长度
int flen, slen;
string sum;
flen = one.size();
slen = two.size();
if(flen >= slen)
{
sum = one;
for(j=0;j<slen;j++)
sum[flen-j-1] = sum[flen-j-1] + two[slen-j-1] - '0';
max = flen;
}
else
{
sum = two;
for(j=0;j<flen;j++)
sum[slen-j-1] = sum[slen-j-1] + one[flen-j-1] - '0';
max = slen;
}
//如果第j位的数大于9,则将其减10,并向上一位进一
for(j=max-1;j>=1;j--)
{
if(sum[j] > '9')
{
sum[j] -= 10;
sum[j-1]++;
}
}
if(sum[0] > '9')
{
sum[0] -= 10;
sum = "1" + sum;
}
return sum;
}

大数加法,进阶转换版

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
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

struct bign{
int d[1000];
int len;
bign()
{
memset(d,0,sizeof(d));
len=0;
}
};

bign change(string s)
{
bign a;
a.len=s.size();
for(int i=0;i<a.len;i++)
//将字符换成整型
{
a.d[i]=s[a.len-i-1]-'0';
}

return a;
}

bign add(bign a,bign b){
bign c;
int carry=0;
//这里漏掉了i导致循环出错
for(int i=0;i<a.len||i<b.len;i++){
//还是转换成整数来计算更保险
int temp=a.d[i]+b.d[i]+carry;
c.d[c.len++]=temp%10;
carry=temp/10;
}
//对于最后一个carry的处理!!我的分情况处理太low了
if(carry!=0)
c.d[c.len++]=carry;
return c;
}
int main()
{
string str1,str2;
while(cin>>str1>>str2){
bign a=change(str1);
bign b=change(str2);
bign c=add(a,b);
for(int i=c.len-1;i>=0;i--){
cout<<c.d[i];
}
cout<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct bign
{
int d[110];
int len;
bign()
{
memset(d,0,sizeof(d));
len=0;
}
}big[110];
void change(char s[],bign &a,bign &b)
{
int len=strlen(s),len1=0;
for(int i=0;i<len;i++)
{
if(s[i]=='.')
break;
else
len1++;
}
a.len=len1;
for(int i=len1-1;i>=0;i--)
a.d[len1-1-i]=s[i]-'0';
b.len=len-len1-1;
for(int i=len1+1;i<len;i++)
b.d[i-len1-1]=s[i]-'0';
}
void trans(bign &a)
{
int s[110];
for(int i=0;i<a.len;i++)
s[i]=a.d[a.len-1-i];
for(int i=0;i<a.len;i++)
a.d[i]=s[i];
}
int add1(bign a,bign b,bign &c)
{
int carry=0,temp;
for(int i=((a.len-1)>(b.len-1)?(a.len-1):(b.len-1));i>=0;i--)
{
temp=a.d[i]+b.d[i]+carry;
c.d[c.len++]=temp%10;
carry=temp/10;
}
trans(c);
while(c.d[c.len-1]==0&&c.len>=2)
c.len--;
return carry;
}
void add2(bign a,bign b,bign &c,int carry)
{
int temp;
for(int i=0;i<a.len||i<b.len;i++)
{
temp=a.d[i]+b.d[i]+carry;
c.d[c.len++]=temp%10;
carry=temp/10;
}
if(carry!=0)
c.d[c.len++]=carry;
while(c.d[c.len-1]==0&&c.len>=2)
c.len--;
}
int main()
{
char a[110],b[110];
int n;
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
bign a1,b1,c1,d1,e,f;
scanf("%s",a);
change(a,a1,b1);
scanf("%s",b);
change(b,c1,d1);
int carry=add1(b1,d1,f);
add2(a1,c1,e,carry);
for(int j=e.len-1;j>=0;j--)
printf("%d",e.d[j]);
printf(".");
for(int j=0;j<f.len;j++)
printf("%d",f.d[j]);
printf("\n");
getchar();
}
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
题目描述
输入一个正整数N,输出N的阶乘。
输入描述:
正整数N(0<=N<=1000)
输出描述:
输入可能包括多组数据,对于每一组输入数据,输出N的阶乘
示例1
输入
n的阶乘简单写法,王道机试写得太复杂
*/

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxx = 5000;
int str[maxx];
void Cal(int n)
{
for (int i = 0; i<maxx; i++)str[i] = 0;
//阶乘的初值赋值1,c是进位,由于改成数组装,所以进位加到下一位
str[1] = 1; int j;
int len = 1, c = 0;
//用len来确定结果有几位
for (int i = 2; i <= n; i++)
{
for (j = 1; j <= len; j++)
{
//终于懂了!!,没问题24*23可以拆成20*23+4*23而这个20的0可以去掉,因为用位置来表示了10进制
str[j] = str[j] * i + c;
c = str[j] / 10;
str[j] = str[j] % 10;

}
while (c>0)
{ //此时的j已经到len+1了。新开辟的一个点,要不停的往前放
str[j] = c % 10;
j++;
c /= 10;
}
//j就是当前最远的一位的位置
len = j - 1;
}
//然后从逆开始输出!!,终于看懂了
for (int j = len; j >= 1; j--)
cout << str[j];
cout << "\n";
}
int main()
{
int n;
while (cin >> n)
{
if (n == 0)printf("1\n");
else Cal(n);

}
}
//阶乘新写法
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int main()
{
int n;
while(cin>>n){
int cnt[1001];
int len=1;
cnt[0]=1;
for(int i=1;i<=n;i++){
int carry=0;
for(int j=0;j<len;j++){
cnt[j]=cnt[j]*i+carry;
//终于知道问题了!!顺序不大对,cnt[j]先变了!!
carry=cnt[j]/10;
cnt[j]=cnt[j]%10;

}
if(carry!=0){
while(carry!=0){
cnt[len]=carry%10;
carry=carry/10;
len++;
}
}

}
for(int i=len-1;i>=0;i--){
cout<<cnt[i];
}
cout<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
这题有个小坑,当然也不算是坑,就是,看起来是求并查集的没错,但是额外附加了一个条件,单个端点只接收一次消息,所以,不能有环出现,排除也很简单,根据树的边数为n-1定则,而且要所有端点必须为同一集合,那么M必须等于N-1,否则,
所有端点无法连通,或出现环,so~题目就简单啦~~
*/

#include <iostream>

using namespace std;
//通信系统,要求所有结点都能收到发端消息且不重复


int father[1000];

int findFather(int a){
int x=a;
while(x!=father[x]){
x=father[x];
}
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;

}

void init(int n){
for(int i=1;i<=n;i++){
father[i]=i;
}
}

void Union(int a,int b){
int A=findFather(a);
int B=findFather(b);
if(A!=B){
father[A]=B;
}
}

int main()
{
int n,k,a,b;
while(cin>>n>>k){
if(n==0) break;
init(n);
for(int i=0;i<k;i++){
cin>>a>>b;
Union(a,b);
}
int ans=0;
for(int i=1;i<=n;i++){
if(father[i]==i)
ans++;
}
//边只能有n-1条时才不会有环!!
if(ans==1&&k==n-1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}

图的遍历DFS邻接矩阵和邻接表法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//给定一个无向图和所有边,判断这个图是否所有顶点都是联通的
#include <iostream>
#include <cstring>
using namespace std;

const int maxn=1010;
bool G[maxn][maxn];
bool flag[maxn]={false};
int n;
//n是点数,m是边数
void DFS(int x){
flag[x]=true;
for(int i=1;i<=n;i++){
//由于是无向边true表示可达
if(flag[i]==false&&G[x][i]==true){
G[x][i]=false;
G[i][x]=false;
//上面这个操作是为了提前清除已经访问边,这样就可以 不用下一组初始化
DFS(i);
}
}
}
int main(){
int m,d1,d2;
while(cin>>n>>m){
if(n==0) break;
for(int i=0;i<m;i++){
cin>>d1>>d2;
if(G[d1][d2]==false)
G[d1][d2]=G[d2][d1]=true;
}
int number=0;
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++){
if(flag[i]==false){
number++;
DFS(i);
}
}
if(number==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}


//邻接矩阵法,其实就要最后的连通块只有一个,有点类似并查集!!

//邻接表法
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=1010;
vector<int> Adj[maxn];
bool flag[maxn]={false};
int n;

void DFS(int x){
flag[x]=true;
for(int i=0;i<Adj[x].size();i++){
int u=Adj[x][i];
//x的后继点!!
if(flag[u]==false){
DFS(u);
}
}
//清空,这样不用初始化为空
Adj[x].clear();
}

using namespace std;

int main()
{
int m,d1,d2;
while(cin>>n>>m)
{
if(n==0)
break;
for(int i=0;i<m;i++){
cin>>d1>>d2;
Adj[d1].push_back(d2);
Adj[d2].push_back(d1);
}
int number=0;
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++){
if(flag[i]==false){
number++;
DFS(i);
}
}
if(number==1) printf("YES\n");
else printf("NO\n");
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
0 1 5 3 4 6

//迪杰特斯拉最短路劲
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXV=1000; //最大顶点数
const int INF=1000000000; //设置一个很大值表示不可达

int n,m,s,G[MAXV][MAXV]; //n为顶点数,m为边数,s为起点
int d[MAXV]; //起点到各点的最短路径长度
int pre[MAXV]; //prev【v】表示从起点到顶点v的最短路径上v的前一个顶点

bool vis[MAXV]={false}; //标记数组
void Dijkstra(int s){
fill(d,d+MAXV,INF); //s到所有点先设置成不可达
d[s]=0; //这个也很关键,s一开始到自己为0
for(int i=0;i<n;i++){
int u=-1,MIN=INF; //找到使d[u]最小的u,MIn存放最小的d[u]
for(int j=0;j<n;j++){
//第一轮自由一个d[s]=0,之后每轮d[u]都是更新的!!
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1) return;
//找不到小于INF的d[u]说明剩下的顶点和起点s不连通
vis[u]=true;
//找到了标记成已访问
//从u出发能到达的下一个点,这样每次相当于都知道了下一轮要访问的点的距离
for(int v=0;v<n;v++){
//如果v未访问&&u能到达v&&以u为中介点,可以使d[v]更优
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
//优化d[v]
pre[v]=u;
//记录前驱顶点是u
}
}
}
}
//如何使用递归,根据前驱顶点,求最短路径
void DFS(int s,int v){
//s为起点编号,v为当前访问的顶点编号,要从重点开始递归,这样才能从头输出
if(v==s){
//递归重点,就是达到起点
printf("%d\n",s);
return;
}
DFS(s,pre[v]); //递归访问v的前驱顶点pre[v]
printf("%d\n",v); //从最深return回来之后再输出每一层
}


int main()
{
int u,v,w;
cin>>n>>m>>s;
//顶点个数,边数,起点编号
fill(G[0],G[0]+MAXV*MAXV,INF);
//对于矩阵如何初始化,学到了
for(int i=0;i<m;i++){
cin>>u>>v>>w;
G[u][v]=w;
//输入u,v以及u->v的边权,有向图
}
Dijkstra(s);
//直接算法入口
for(int i=0;i<n;i++){
//输出s到所有顶点的最短距离
printf("%d ",d[i]);
}
cout<<endl;
DFS(0,3);

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn=60;
const int INF=0x3fffffff;
int G[maxn][maxn],n,d[maxn];
bool vis[maxn]={false};

struct Node{
int v,dis;
//这是有点队列所需要的!!
bool operator<(const Node &a)const{
return dis>a.dis;
}
//结构定义
Node(int x,int y){
v=x;
dis=y;
}
};

void Dijkstra(int s){
fill(d,d+maxn,INF);
d[s]=0;
//使用优先队列查找未访问的距离最短结点
priority_queue<Node> q;
q.push(Node(s,d[s]));
for(int i=0;i<n;i++){
if(q.empty()==true) return;
while(vis[q.top().v]==true){
q.pop();
if(q.empty()==true) return;
}

int u=q.top().v;
q.pop();
for(int v=0;v<n;v++){
if(G[u][v]!=0&&vis[v]==false&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
q.push(Node(v,d[v]));
}
}
}

}

int main()
{
int s;
while(cin>>n){
cin>>s;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>G[i][j];
}
}
Dijkstra(s);
for(int i=0;i<n;i++){
if(i!=s){
if(d[i]==INF)
printf("-1 ");
else printf("%d ",d[i]);
}
}
printf("\n");

}
return 0;
}

prim最小生成树算法

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=110;
const int INF=0x3fffffff;
int G[maxn][maxn],d[maxn];
int n;
bool vis[maxn];

int prim()
{
fill(d,d+maxn,INF);
memset(vis,0,sizeof(vis));
d[1]=0;
int ans=0;
for(int i=0;i<n;i++)
{
int min=INF,u=-1;
for(int j=1;j<=n;++j)
{
if(d[j]<min&&vis[j]==false)
{
u=j;
min=d[j];
}
}
//终于知道-1的作用,表示存在没有联通的地方!!
if(u==-1)
return -1;
vis[u]=true;
ans+=d[u];
for(int v=1;v<=n;++v)
{
if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v])
{
d[v]=G[u][v];
}
}
}
return ans;
}
int main()
{
int w,u,v;
while(~scanf("%d",&n))
{
if(n==0)
break;
fill(G[0],G[0]+maxn*maxn,INF);
for(int i=0;i<n*(n-1)/2;++i)
{
scanf("%d %d %d",&u,&v,&w);
G[u][v]=G[v][u]=w;
}
int ans=prim();
printf("%d\n",ans);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


#include <iostream>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
//关键算法,找到爸爸节结点的标号
int findRoot(int x){
//查找代表集合的树的根节点,分成两个集合,以此来判断是否要合并两点到一个集合
if(Tree[x]==-1){
return x;
}else{
//当Tree[x]=1时,表示x爸爸是1,Tree[1]=-1,return Tree[x]=1是一个整体!!
int tmp=findRoot(Tree[x]);
//找x的爸爸,递归
Tree[x]=tmp;
//tmp确实是x的爸爸,爸爸存了
return tmp;
}
}

struct Edge{
//边要有结构体,来进行排序
int a,b;//顶点编号
int cost;
//重载小于运算符很关键!!
bool operator < (const Edge &A) const{
return cost<A.cost;
}edge[6000];


int main(){
int n;
while(cin>>n){
for(int i=1;i<=n*(n-1)/2;i++){
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge+1,edge+1+n*(n-1)/2);
for(int i=1;i<=n;i++){
Tree[i]=-1;
//初始所有边都处于孤立集合
}
int ans=0;

for(int i=1;i<=n*(n-1)/2;i++){
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);

//查找两个顶点的集合信息
if(a!=b){
Tree[b]=a;
//合并两个集合,加入了一个边
cout<<a<<" "<<b<<" "<<edge[i].cost<<endl;
ans=ans+edge[i].cost;
}
}
cout<<ans;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
6 10
0 1 4
0 4 1
0 5 2
1 2 1
1 5 3
2 3 6
2 5 5
3 4 5
3 5 4
4 5 3
11

//克鲁斯卡尔最小生成树算法

#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;

const int MAXV=110;
const int MAXE=10010;

struct edge{
int u,v; //边的两个端点编号
int cost; //边权
}E[MAXE];

bool cmp(edge a,edge b){
return a.cost<b.cost;
}

//并查集部分
int father[MAXV]; //并查集数组
int findFather(int x){
//并查集查询函数
int a=x;
while(x!=father[x]){
x=father[x];
}
//路径要锁,直接得到每个点的爸爸
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}

//n为顶点个数,m为图的边数
int kruskal(int n,int m){
//ans为所求边权和,Num_Edge为当前生成树的边数
int ans=0,Num_Edge=0;
for(int i=0;i<n;i++){
father[i]=i; //并查集初始化
}
sort(E,E+m,cmp); //所有边按权值大小排序
for(int i=0;i<m;i++){
cout<<E[i].v<<" "<<E[i].u<<" "<<E[i].cost<<endl;
}
cout<<"路径:"<<endl;
for(int i=0;i<m;i++){
//枚举所有边
int faU=findFather(E[i].u); //查询测试边两个端点所在集合根结点
int faV=findFather(E[i].v);
//这就是合并了
if(faU!=faV){
//只有不在同一个集合才可以合并

father[faU]=faV;
ans+=E[i].cost;
cout<<E[i].v<<"->"<<E[i].u<<endl;
Num_Edge++; //当前生成树边数加1
if(Num_Edge==n-1) break;

//边数等于顶点数减一时结束算法
}
}
if(Num_Edge!=n-1) return -1; //无法连通时返回-1
else return ans; //返回最小生成树的边权之和
}

int main()
{
int n,m;
cin>>n>>m; //顶点数和边数
for(int i=0;i<m;i++){
cin>>E[i].u>>E[i].v>>E[i].cost;
}
int ans=kruskal(n,m);

cout << ans<< 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//最大连续子序列和,最简单基础班
//状态转移方程 dp[i]=max{A[i],dp[i-1]+A[i]}
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=10010;
int A[maxn],dp[maxn]; //A[i]存放序列,dp[i]存放以A[i]为结尾的联系序列最大和
int main()
{
int n;
while(cin>>n){
if(n==0) break;
for(int i=0;i<n;i++){
cin>>A[i];
}
//确定边界,相当于就是本身就是最大和
dp[0]=A[0];
//是从i=1开始的,这是递推,而不是递归
for(int i=1;i<n;i++){
dp[i]=max(A[i],dp[i-1]+A[i]);
}
//dp[i]存放所有以A[i]为结尾的序列最大和,还需要比较最大值
int k=0;
//如何找最大值,排序也可,此处选择比较!!,值得学习
for(int i=1;i<n;i++){
if(dp[i]>dp[k]) k=i;
}
cout << dp[k] << endl;
}

return 0;
}
//最大连续子序列和进阶版!!还要输出序列的头和尾
//状态转移方程 dp[i]=max{A[i],dp[i-1]+A[i]}
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=10010;
int A[maxn];
struct node{
int start,end,sum;
}dp[maxn];

int main()
{
int n,data;
while(cin>>n){
if(n==0) break;
for(int i=0;i<n;i++){
cin>>A[i];
}
//确定边界,相当于就是本身就是最大和
dp[0].sum=A[0];
dp[0].start=dp[0].end=0;
//是从i=1开始的,这是递推,而不是递归
for(int i=1;i<n;i++){
//把max函数拆解后的结果
if(A[i]>dp[i-1].sum+A[i]){
dp[i].start=dp[i].end=i;
dp[i].sum=A[i];
//就是自身了
}
else{
dp[i].sum=A[i]+dp[i-1].sum;
dp[i].start=dp[i-1].start;
dp[i].end=i;
}
}
//dp[i]存放所有以A[i]为结尾的序列最大和,还需要比较最大值
int k=0;
//如何找最大值,排序也可,此处选择比较!!,值得学习
for(int i=1;i<n;i++){
if(dp[i].sum>dp[k].sum) k=i;
}
if(dp[k].sum<0)
printf("0 %d %d\n",A[0],A[n-1]);
else
printf("%d %d %d\n",dp[k].sum,A[dp[k].start],A[dp[k].end]);
}

return 0;
}

方法二:很巧妙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include<stdio.h>
#include<algorithm>
//#include<windows.h>
using namespace std;
int main(){
int N,i;
//freopen("input.txt","r",stdin);
while(scanf("%d",&N)!=EOF){
long sum=0,Max=-999999999,x;
for(i=0;i<N;i++){
scanf("%ld",&x);
sum=max(sum+x,x);
Max=max(Max,sum);
}
printf("%ld\n",Max);
}
}

最大加权子矩阵-矩阵压缩

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
47
48
49
50
//最大加权矩形变形,只需要矩阵的和大于k来求矩阵的面积!!
#include <bits/stdc++.h>

using namespace std;
#define maxn 150
int n,m,t;
int matrix[maxn][maxn];
int ans=-21000000;
int temp[maxn];
int dp[maxn];

void Arrsum(){
memset(dp,0,sizeof(dp));

for(int i=1;i<=n;i++){
dp[i]=max(dp[i],dp[i-1]+temp[i]);
ans=max(ans,dp[i]);
}
}

void MatrixSum(){
for(int i=1;i<=n;i++){
memset(temp,0,sizeof(temp));
//这个压缩是所有行分级压缩!!
for(int j=i;j<=n;j++){

//temp是每一列的和
for(int k=1;k<=n;k++){
temp[k]=temp[k]+matrix[j][k];
}
//计算行中最大
Arrsum();
}
}

}

int main()
{
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>matrix[i][j];
}
}
MatrixSum();
printf("%d\n",ans);

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
26
27
28
29
//最长不下降子序列,此处不要求连续,只要求是递增,间隔也可,因而双循环
#include <iostream>
#include <algorithm>
using namespace std;

const int N=100;
int A[N],dp[N];


int main()
{
int n;
while(cin>>n){
for(int i=1;i<=n;i++) cin>>A[i];
int ans=-1; //记录最大的dp[i]
for(int i=1;i<=n;i++){
dp[i]=1; //边界初始条件,先假设每个元素自成一格子序列
//i是最后一个点,就是边界
for(int j=1;j<i;j++){
if(A[i]>=A[j]&&(dp[j]+1>dp[i])){
dp[i]=dp[j]+1;
}
}
ans=max(ans,dp[i]);
}
printf("%d",ans);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1, 2, …, K,他们的身高分别为T1, T2, …, TK, 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。*/
/*动态规划的最长子列问题,分别从前往后和从后往前寻找以i点为尾的最长子列,
寻找两个子列和的最大值*/
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int N,i,j,maxn;
while(cin>>N){
int high[200],marka[200],markb[200];
for(int i=1;i<=N;i++){
cin>>high[i];
marka[i]=markb[i]=1;
//每点为尾的子列长度最小都为1

}

for(i=2;i<=N;i++) /*从前往后寻找以i点为尾的最长递增子列*/
{
maxn=marka[i];
for(j=i-1;j>=1;j--)
{
if(high[i]>high[j])
//问题出在这里啊
maxn=max(maxn,marka[j]+1);
//maxn=(maxn>marka[j]+1)?maxn:marka[j]+1;
}
marka[i]=maxn;
}
for(i=N-1;i>=1;i--) /*从后往前寻找以i点为尾的最长递增子列*/
{
maxn=markb[i];
for(j=i+1;j<=N;j++)
{
if(high[i]>high[j])
// maxn=(maxn>markb[j]+1)?maxn:markb[j]+1;
maxn=max(maxn,markb[j]+1);
}
markb[i]=maxn;
}
maxn=marka[1]+markb[1];
//寻找点i两个子列和的最大值
for(i=2;i<=N;i++){
maxn=max(maxn,marka[i]+markb[i]);
}
cout<<N-maxn+1<<endl;
}

return 0;
}

最长公共子序列-字符串A,B

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
47
48
49
50
51
sadstory
adminsorry

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

string str1,str2;
int dp[1001][1001];

//记住模板
int lcs(string str1,string str2)
{
int len1=str1.size();
int len2=str2.size();
//0位已经设置为边界,i and j都从1开始
for(int i=1; i<=len1; i++)
{
for(int j=1; j<=len2; j++)
{
if(str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else if(dp[i-1][j] > dp[i][j-1])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i][j-1];
}
}
return dp[len1][len2];
}

int main()
{

while(cin>>str1)
{
cin>>str2;
//此处为边界,很关键dp[0][j] and d[i][0]均表示字符串0位与其他各字符串的比较
memset(dp, 0, sizeof(dp));

int ans=lcs(str1, str2);
printf("%d\n", ans);
}
return 0;
}

最长公共子序列求具体LCS

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
 dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + (A[i]==B[j] ? 1 : 0)),表示在这三种状态中取到最大值,

(1)第一种状态表示不录入第一个序列的第i个字符时的最长公共子序列,

(2)第二种状态表示不录入第二个序列的第j个字符时的最长公共子序列,

(3)第三种状态表示第一个序列的前i-1个字符与第二个序列前j-1个字符的公共子序列加上最后一个字符的录入状态,如果最后的一个字符相等则录入状态为1,否则为0。

然后根据动归的状态,来判断我们要求得的序列中的字符有哪些。

*/
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

string str1,str2;
int dp[1001][1001];

//记住模板,在lcs求长度的基础上进行改变,求最长子序列具体
void lcs(string str1,string str2)
{
int len1=str1.size();
int len2=str2.size();
//0位已经设置为边界,i and j都从1开始
for(int i=1; i<=len1; i++)
{
for(int j=1; j<=len2; j++)
{
if(str1[i-1] == str2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else if(dp[i-1][j] > dp[i][j-1])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i][j-1];
}
}
}

void llcs(){
int i,j,z=0;
string temp;
i=str1.size(),j=str2.size();
//从尾到头的状态进行判断,根据判断可以知道字符加入没有
while(i!=0&&j!=0){
if(str1[i-1]==str2[j-1]){
//只有当两个字符都相等时才可以加入输出字符串
temp[z++]=str1[--i];
j--;
}
else if(dp[i-1][j]<dp[i][j-1])
//判断的意思,此时没有相等,且j加的没效果,j不等
j--;
else if(dp[i][j-1]<=dp[i-1][j])
i--;
//还是看小的,此时是i加的不如j加的有效果,所以减i
}
for(i=z-1;i>=0;i--)
cout<<temp[i];
cout<<endl;
}

int main()
{

while(cin>>str1)
{
cin>>str2;
//此处为边界,很关键dp[0][j] and d[i][0]均表示字符串0位与其他各字符串的比较
memset(dp, 0, sizeof(dp));

lcs(str1, str2);
llcs();
}
return 0;
}

hash字符串求最长公共连续子串

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
求最长公共子串(连续)的方法,
可以用KMP,当然也可以用字符串hash,
分别计算两个字符串的所有子串的hash值,
然后一一对比,当两个字符串的hash值相等时,
如果长度大于之前访问得到的公共子串长度的最大值,
则更新最大值,并存储此子串的起始位置,
最终得到最长的公共子串~

*/

#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=1010;
const LL p=1e7+19;
const LL mod=1e9+7;
LL powP[maxn],H1[maxn]={0},H2[maxn]={0};

struct Node{
int hashValue,length,start,end;
Node(int a,int b,int c,int d):hashValue(a),length(b),start(c),end(d){};
};

vector<Node> pr1,pr2;

void init(int len)
{
powP[0]=1;
for(int i=1;i<=len;++i){
powP[i]=(powP[i-1]*p)%mod;
}
}

void calH(LL H[],string &str){
H[0]=str[0];
for(int i=1;i<str.length();i++){
H[i]=(H[i-1]*p+str[i])%mod;
}
}

int calSingleSubH(LL H[],int i,int j){
if(i==0)
return H[j];
return ((H[j]-H[i-1]*powP[j-i+1])%mod+mod)%mod;
}

void calSubH(LL H[],int len,vector<Node> &p){
for(int i=0;i<len;i++){
for(int j=i;j<len;j++){
int value=calSingleSubH(H,i,j);
p.push_back(Node(value,j-i+1,i,j));
}
}
}


string getMax(string str1)
{
string str;
int ans=0;
for(int i=0;i<pr1.size();++i)
for(int j=0;j<pr2.size();++j)
{
if(pr1[i].hashValue==pr2[j].hashValue)
{
if(pr1[i].length>ans)
{
ans=pr1[i].length;
str=str1.substr(pr1[i].start,pr1[i].end);
}
}
}
return str;
}

int main()
{
string str1,str2;
getline(cin,str1);
getline(cin,str2);
init(max(str1.length(),str2.length()));
calH(H1,str1);
calH(H2,str2);
calSubH(H1,str1.length(),pr1);
calSubH(H2,str2.length(),pr2);

cout << getMax(str1) << endl;
return 0;
}

最长公共子串是最长公共子序列的的特殊情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int lcs(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
int result = 0; //记录最长公共子串长度
int c[][] = new int[len1+1][len2+1];
for (int i = 0; i <= len1; i++) {
for( int j = 0; j <= len2; j++) {
if(i == 0 || j == 0) {
c[i][j] = 0;
} else if (str1.charAt(i-1) == str2.charAt(j-1)) {
c[i][j] = c[i-1][j-1] + 1;
result = max(c[i][j], result);
} else {
c[i][j] = 0;
}
}
}
return result;
}

最长回文子序列

方法一:递归方法,自顶向下

str[0…n-1]是给定的字符串序列,长度为n,假设lps(0,n-1)表示序列str[0…n-1]的最长回文子序列的长度。

1.如果str的最后一个元素和第一个元素是相同的,则有:lps(0,n-1)=lps(1,n-2)+2;例如字符串序列“AABACACBA”,第一个元素和最后一个元素相同,其中lps(1,n-2)表示红色部分的最长回文子序列的长度;

2.如果str的最后一个元素和第一个元素是不相同的,则有:lps(0,n-1)=max(lps(1,n-1),lps(0,n-2));例如字符串序列“ABACACB”,其中lps(1,n-1)表示去掉第一元素的子序列,lps(0,n-2)表示去掉最后一个元素的子序列。

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int lps(string str,int i,int j){
//递归出口
if(i==j)
return 1; //只有一个元素,回文长度为1
if(i>j)
return 0; //字符序列str[i...j]

//如果首尾相同
if(str[i]==str[j])
return lps(str,i+1,j-1)+2;
//如果首尾不相同
return max(lps(str,i,j-1),lps(str,i+1,j));

}

int main()
{
string str;
while(cin>>str){
int n=str.size();
int ans=lps(str,0,n-1);
cout<<ans<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

int dp[1000][1000];

int lpsDp(string str,int n){
int temp;
memset(dp,0,sizeof(dp));
//边界条件
for(int i=0;i<n;i++)
dp[i][i]=1;

//dp[j][i]的含义表示首为j,尾为i
for(int i=1;i<n;i++){
temp=0;
//考虑所有连续的长度为i+!的子串,str[j...j+i
for(int j=0;j+i<n;j++){
//如果首尾相同
if(str[j]==str[j+i])
temp=dp[j+1][j+i-1]+2;
else
temp=max(dp[j+1][j+i],dp[j][j+i-1]);
dp[j][j+i]=temp;
}
}
//返回字符串str[0....n-1]的最长回文子序列长度
return dp[0][n-1];
}
int main()
{
string str;
while(cin>>str){
int ans=lpsDp(str,str.size());
cout<<ans<<endl;
}
return 0;
}

最长回文子串,连续的!!

动态规划法:

回文字符串的子串也是回文,比如P[i,j](表示以i开始以j结束的子串)是回文字符串,那么P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O(N^2),算法复杂度也是O(N^2)。

首先定义状态方程和转移方程:

P[i,j]=false:表示子串[i,j]不是回文串。P[i,j]=true:表示子串[i,j]是回文串。

P[i,i]=true:当且仅当P[i+1,j-1] = true && (s[i]==s[j])

否则p[i,j] =false;

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
47
48
49
50
51
52
PATZJUJZTACCBCC

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

bool dp[1000][1000];

int maxlength=0;
string flp(string s){
int len=s.size();
int start=0;
//子串长度为1和2的初始化,边界条件
for(int i=0;i<len;i++){
dp[i][i]=true;
if(i<len-1&&s[i]==s[i+1]){
dp[i][i+1]=true;
start=i;
maxlength=2;
}
}
//使用上述结果可以dp出子串长度为3~len-1的子串
for(int strlen=3;strlen<len;strlen++){
for(int i=0;i<=len-strlen;i++){
int j=i+strlen-1; //子串结束位置
if(dp[i+1][j-1]&&s[i]==s[j]){
dp[i][j]=true;
maxlength=strlen;
//这个start的记忆就很灵性
start=i;
}
}
}
if(maxlength>0)
return s.substr(start,start+maxlength-1);
return NULL;

}


int main()
{
string str;
while(cin>>str){
memset(dp,0,sizeof(dp));
string ans=flp(str);
cout<<ans<<endl;
cout<<maxlength<<endl;
}
return 0;
}

暴力法:

遍历字符串S的每一个子串,去判断这个子串是不是回文,是回文的话看看长度是不是比最大的长度maxlength大。遍历每一个子串的方法要O(n^2),判断每一个子串是不是回文的时间复杂度是O(n),所以暴利方法的总时间复杂度是O(n^3)。

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
PATZJUJZTACCBCC
#include <iostream>
#include <string>
using namespace std;

int maxlength=0;
string flp(string str){
int len=str.size();

int start=0;

for(int i = 0; i < len; i++){
for(int j = i + 1; j < len; j++){
int index1 = 0;
int index2 = 0;
// 对每个子串都从两边开始向中间遍历
for(index1 = i, index2 = j; index1 < index2; index1 ++, index2--) {
if(str[index1] != str[index2])
break;
}
// 若index1=index2,表示串是类似于abcba这种类型;若大于,则是abccba这种类型
if(index1 >= index2 && j - i > maxlength){
maxlength = j - i + 1;
start = i;
}
}

}

if(maxlength>0)
return str.substr(start,start+maxlength-1);
return NULL;
}

int main()
{
string str;
while(cin>>str){
string ans=flp(str);

cout << ans<< endl;
cout << maxlength<< endl;
}

return 0;
}

中心扩展法:

中心扩展就是把给定的字符串的每一个字母当做中心,向两边扩展,这样来找最长的子回文串。算法复杂度为O(N^2)。

但是要考虑两种情况:

1、像aba,这样长度为奇数。

2、想abba,这样长度为偶数

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
47
48
49
#include <iostream>
#include <string>
using namespace std;

string flp(string str){
int len=str.size();
int maxlength=0,start=0;
//先处理aba情况
for(int i=0;i<len;i++){
int j=i-1;
int k=i+1;
while(j>=0 && k<len && str[j]==str[k]){
if(k-j+1>maxlength){
maxlength=k-j+1;
start=j;
}
j--;
k++;
}
}

//类似于abba情况,以i,i+!为中心两边扩展
for(int i=0;i<len;i++){
int j=i;
int k=i+1;
while(j>=0 && k<len&&str[j]==str[k]){
if(k-j+1>maxlength){
maxlength=k-j+1;
start=j;
}
j--;
k++;
}
}
if(maxlength>0)
return str.substr(start,start+maxlength-1);
}

int main()
{
string str;
while(cin>>str){
string ans=flp(str);

cout << ans<< 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <string>
#include <vector>

using namespace std;
//从中间往两边扫,就有两种情况
int main()
{
string str;
while(cin>>str){
int len=str.size();
int mid =len/2;
bool flag=true;
if(len%2==1){
for(int i=0;mid+i<len;i++){
if(str[mid-i]!=str[mid+i])
{
flag=false;
break;
}
}
}else{
for(int i=0;mid+i<len;i++){
if(str[mid+i]!=str[mid-i-1])
{
flag=false;
break;
}
}

}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}

return 0;
}

//或者从两端往中间扫
#include <cstdio>
#include <cstring>
int main()
{
char a[300];
while(gets(a))
{
int len=strlen(a);
bool flag=1;
for(int i=0;i<len/2;i++)
{
if(a[i]!=a[len-i-1])
{
flag=0;
break;
}
}
printf("%s\n",flag?"YES":"NO");
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
Confuciuss say:Madam,I'm Adam.
//最长回文子串暴力法
#include <iostream>
#include <string>
#include <cstring>
#include <ctype.h>

using namespace std;

bool dp[5010][5010];
int pos[5010];
string str;

string flp(char s[]){
int maxlength=0;
int len=strlen(s);
int start=0,end=0;
//子串长度为1和2的初始化,边界条件
//dp[i][j] 表示以i开始,j结尾的子串是否是回文字符串!!,则dp[i+1][j-1]也是回文字符串
for(int i=0;i<len;i++){
dp[i][i]=true;
if(i<len-1&&s[i]==s[i+1]){
dp[i][i+1]=true;
start=i;
maxlength=2;
}
}
//使用上述结果可以dp出子串长度为3~len-1的子串
for(int strlen=3;strlen<len;strlen++){
for(int i=0;i<=len-strlen;i++){
int j=i+strlen-1; //子串结束位置
if(dp[i+1][j-1]&&s[i]==s[j]){
dp[i][j]=true;
maxlength=strlen;
start=pos[i];
end=pos[j];
}
}
}
if(maxlength>0)
return str.substr(start,end-start+1);
return NULL;

}


int main()
{
//终于知道哪里错了
while(getline(cin,str)){
memset(dp,0,sizeof(dp));
memset(pos,0,sizeof(pos));
char temp[5010];
int num=0;
for(int i=0;i<str.size();i++){
if(isalpha(str[i]) || isdigit(str[i])){
temp[num]=toupper(str[i]);
pos[num]=i;
num++;
}
}
temp[num]='\0';
cout<<temp;
cout<<endl;
string ans=flp(temp);
cout<<ans<<endl;
}
return 0;
}
for(int i=0;i<str.size();i++){
if(isalpha(str[i]) || isdigit(str[i])){
char c=toupper(str[i]);
temp=temp+c;
pos[num]=i;
num++;
}
}

01背包问题

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
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
01背包
5 8 //n==5,V==8
3 5 1 2 2 //w[i]
4 5 2 1 3 //c[i]
//表示用重量8达到最大价值c

分为两种策略,
不放第i件物品,即i-1件物品满足条件 dp[i-1][v]
放第i件物品 dp[i-1][v-w[i]]+c[i]

又由于dp[i][v]总是只需要dp[i-1][v]左半部分
故可以直接开一个dp[v]数组
但是枚举方向该位i从1到n,v从V到0(逆序!!!)
dp[v]=max(dp[v],dp[v-w[i]]+c[i])

*/

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=100;
const int maxv=1000;

int w[maxn],c[maxn],dp[maxv];

int main()
{
int n,V;
cin>>n>>V;

for(int i=0;i<n;i++){
cin>>w[i];
}
for(int i=0;i<n;i++){
cin>>c[i];
}
//边界
for(int v=0;v<=V;v++){
dp[v]=0;
}

for(int i=0;i<n;i++){
for(int v=V;v>=w[i];v--){
dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
}
}

int maxans=0;
for(int v=0;v<=V;v++){
if(dp[v]>maxans){
maxans=dp[v];
}
}
cout<<maxans<<endl;

return 0;
}

完全背包-拆分整数成2的幂的和

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

/*这道题确实可以用动态规划来解,它其实是一个完全背包求恰装满背包时的方案总数
问题.具体是,因为每一个拆分必须是1,2,4,2^3,...2^19(考虑n最大为10^6),
所以对于一个整数n,看它的这种拆分数有多少个,就相当于现在有20种物品,第i种物品
的花费是2^(i-1),每一种可以重复取, dp[i][j]表示前i种物品恰装满容量为j的物品时
的方案总数,从而dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]
*/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int n,dp[1000002],a[21];

int main()
{
int i,j,t;
for(i=1;i<=20;i++){
a[i]=(1 << (i-1));
}
dp[0]=1;
while(cin>>n){
memset(dp+1,0,sizeof(dp));
for(i=1;i<=20;i++){
for(j=a[i];j<=n;j++){
//终于明白滚动数字的含义,二维降一维
dp[j]=dp[j]+dp[j-a[i]];
dp[j]=dp[j]%1000000000;
}
}
cout<<dp[n]<<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
25
26
27
28
29
/*方法一没怎么看懂,不过dp[i]应当表示以i号开头时最长长度*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
string str;
cin>>str;
int maxn=0;
vector<int> dp(str.size(),0);
//vector高级用法,快速初始化

for(int i=str.size()-2;i>=0;i--){
if(str[i]=='('){
int j=i+1+dp[i+1];
if(j<str.size()&&str[j]==')'){
dp[i]=dp[i]+dp[i+1]+2;
if(j+1<str.size())
dp[i]=dp[i]+dp[j+1];
}
if(maxn<dp[i])
maxn=dp[i];
}
}

cout <<maxn << 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int maxAvailiable(string str){
int maxn=0;
int i,j;
int len=str.size();

int *dp=(int *)malloc(sizeof(int)*len);
memset(dp,0,sizeof(int)*len);

//至少有两个才可以匹配,故从i=2开始
for(int i=2;i<len;i++){
//这个才是以i结尾,j是匹配头部
if(str[i]==')'){
j=i-1-dp[i-1];
//减去i-1匹配的
if(j>=0&&str[j]=='('){
dp[i]=dp[i-1]+2;
if(j>0)
//终于懂这里了,j前面的也算是匹配了
dp[i]=dp[i]+dp[j-1];
}
maxn=maxn<dp[i]?dp[i]:maxn;
}

}
free(dp);
return maxn;

}

int main()
{
string str;
cin>>str;

cout <<maxAvailiable(str)<< 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
若干邮票,选取最小张数凑成一个给定总值
不是贪心算法,居然是0-1背包,求的是最小数量

dp[i][j]表示i个邮票,j表示总量面额,dp表示最小邮票数量
*/

/*
最少邮票数 >> 01动态规划

状态
集合中数字
dp[i][j] 0 1 2 3 4 5 6 7 8 9 10
1 0 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 3 0 1 ∞ 1 2 ∞ ∞ ∞ ∞ ∞ ∞
1 3 3 0 1 ∞ 1 2 ∞ 2 3 ∞ ∞ ∞
1 3 3 3 0 1 ∞ 1 2 ∞ 2 ∞ ∞ 3 4
1 3 3 3 4 0 1 ∞ 1 2 2 2 2 3 3 3

状态迁移方程
dp[j] = min{dp[j],dp[j-stamp[i]]+1}
其中dp[j-stamp[i]]+1,表示将第i个邮票加入集合后 凑总量为j的面额 所需要的最少邮票数量
*/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define INF 1000
int stamp[1000];
int dp[1000];

int minStamp(int num,int deno){
//邮票个数和总额
int i,j;

//状态全部初始化
for(j=0;j<=deno;j++){
dp[j]=(j==0)?0:INF;
}
for(i=0;i<num;i++){
//从后往前寻找若能凑成,且使数量变少就使用
for(j=deno;j>=stamp[i];j--){
if(dp[j-stamp[i]]!=INF)
dp[j]= (dp[j]<dp[j-stamp[i]]+1)? dp[j]:dp[j-stamp[i]]+1;

}
}
return dp[deno]==INF?0:dp[deno];
}

int main()
{
int num,deno;
while(cin>>deno>>num){
for(int i=0;i<num;i++)
cin>>stamp[i];
cout<<minStamp(num,deno);
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
递归法解决问题,自顶向下方法,
动态规划确实自底向上!!一个问题两个方向

*/
#include <iostream>

using namespace std;
int M; //邮票总价值
int N; //n张邮票
int minn; //最小票数

void compute(int data[],int m,int n,int num){
//m是递归中几张邮票面值的和,n表示data还未参与递归的最高位,num表示m由num张邮票相加得到
int i;
if(m==M){
if(num<minn) minn=num;
return;
}
else if(m>M) return;
for(i=n;i>=0;i--)
//更好理解
compute(data,m+data[i],i-1,num+1);
}

int main()
{
int i,j,k;
while(cin>>M>>N){
minn=N+1;
int data[20];
for(i=0;i<N;i++){
cin>>data[i];
}
compute(data,0,N-1,0);

if(minn==N+1)
//如果可以凑成M,则minn<=N;
printf("0\n");
else
printf("%d\n",minn);
}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
放苹果,递归+动态规划
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,
问共有多少种不同的分法?
(用K表示)5,1,1和1,5,1 是同一种分法。

*/


/*
M个苹果放在N个盘子里分法有:dp[M][N], 0 <= M,N <= 10
设dp(m,n) 为m个苹果,n个盘子的放法数目,则先对n作讨论,
当m<n:必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。dp(m,n) = dp(m,m)
当m>=n:不同的放法可以分成两类:
1、有至少一个盘子空着,即相当于dp(m,n) = dp(m,n-1);
2、所有盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即dp(m,n) = dp(m-n,n).
而总的放苹果的放法数目等于两者的和,即 dp(m,n) =dp(m,n-1)+dp(m-n,n)
初始条件说明
当m=0,n=0时,没苹果,没盘子,定为0种放法。这个条件在计算的时候用不到。题设至少一个盘子一个苹果。
当m=0,n>0时,没苹果,有盘子,定为1种放法。这个有点抽象,考虑:dp[1][1]=dp[1][0]+dp[0][1]=0+1。
当m>0,n=0时,有苹果,没盘子,定为0种放法。
dp两条路,第一条n会逐渐减少,终会到达出口n=0;
第二条m会逐渐减少,因为n>m时,会计算dp(m,m) 所以终会到达出口m=0.
*/

/*#include <iostream>

using namespace std;

int dfs(int m,int n){
if(m>=0&&n==0)
return 0;
else if(m==0&&n>0)
return 1;
else if(m>=n)
return dfs(m,n-1)+dfs(m-n,n);
else
return dfs(m,m);
}

int main()
{
int m,n;
while(cin>>m>>n){
cout<<dfs(m,n)<<endl;
}
return 0;
}
*/

#include <iostream>
using namespace std;
int dp[11][11];

int main(){

int m,n;

while(cin>>m>>n){
for(int i=1;i<=m;i++){
dp[i][0]=0;
}

for(int j=1;j<=n;j++){
dp[0][j]=1;
}

for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(i>=j)
dp[i][j]=dp[i][j-1]+dp[i-j][j];
else
dp[i][j]=dp[i][i];
}
}
cout<<dp[m][n]<<endl;
}
return 0;
}

字符串专题

1.统计单词频率

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
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

int main()
{
string str;

while(getline(cin,str)){
int hashTable[26]={0};
int maxn=-1;
for(int i=0;i<str.size();i++){
if(isalpha(str[i])){
str[i]=tolower(str[i]);
hashTable[str[i]-'a']++;
maxn=max(maxn,hashTable[str[i]-'a']);
}

}

for(int i=0;i<26;i++){
if(hashTable[i]==maxn){
printf("%c %d\n",i+'a',maxn);
}
}

}

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>
#include <cmath>
using namespace std;

int main()
{
string str;
int hashTable[26]={0};
int anum=0,wnum=0,cntMax=0;
while(cin>>str){
anum=anum+str.size();
wnum++;
for(int i=0;i<str.size();i++){
str[i]=tolower(str[i]);
hashTable[str[i]-'a']++;
cntMax=max(cntMax,hashTable[str[i]-'a']);
}
//这个要用对地方!!,用在前面没处理,少读字符串
char ch=getchar();
if(ch=='\n') break;
}
printf("字母个数:%d\n",anum);
printf("单词个数:%d\n",wnum);
bool nofirst=false;
printf("最多的字母:");
for(int i=0;i<26;i++){
if(hashTable[i]==cntMax){

if(nofirst){
printf(",%c",i+'a');
}else{
nofirst=true;
printf("%c",i+'a');
}
}
}
printf("\n出现的次数:%d\n",cntMax);

return 0;
}

2.密文加密

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 <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

int main()
{
string str;

while(getline(cin,str)){
for(int i=0;i<str.size();i++){
if(isalpha(str[i])){
if(islower(str[i])){
str[i]=(str[i]+3-'a')%26+'a';
}else{
str[i]=(str[i]+3-'A')%26+'A';
}
}
}
cout<<str<<endl;
}

return 0;
}

cctype头文件中处理字符函数

v2-94c2a8501687810e30d1aaae267aa394_hd

3.find使用,删除指定子串,transform使用

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
47
48
49
50
51
对于字符串string,需要使用string头文件,包含以下常用方法:

s.find(str,[pos]):在字符串s中从第 pos 个字符开始寻找 str ,并返回位置,如果找不到返回-1。pos 可省略,默认为0

s.erase(pos,n):从给定起始位置 pos 处开始删除,要删除字符的长度为n,返回修改后的string对象
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

int main()
{
string str;

while(cin>>str){
int pos=0;
string word="gzu";
//果然字符串还是得要用双引号稳妥,pos放在下面也更稳妥
while(str.find(word,pos)!=string::npos){
pos=str.find(word,pos);

str.erase(pos,3);
}
cout<<str<<endl;
}

return 0;
}

//进阶版
int main()
{
string str;

while(cin>>str){
int pos=0;
string word="gzu";
string temp=str;
transform(str.begin(),str.end(),str.begin(),::tolower);
//while ((pos = str1.find("gzu")) != -1)也可!!
while(str.find(word,pos)!=string::npos){
pos=str.find(word,pos);
str.erase(pos,3);
temp.erase(pos,3);
}
cout<<temp<<endl;
}

return 0;
}

4.字符串前缀识别

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
#include <iostream>
#include<string.h>
using namespace std;
int main()
{
char str[100][100];
int n;
while (cin >> n&& n)
{
for (int i = 0; i < n; i++)
{
cin >> str[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)continue;//比较不同字符串
if (str[i][0] == '@')continue;//已经修改过的就不用再判断了
bool flag = true;
for (int k = 0; k < strlen(str[i])&& flag; k++)
{
if (str[i][0] == '@')
flag = false;
if (str[i][k] != str[j][k])
flag = false;
}
if (flag)
{
str[i][0] = '@';
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
{
if (str[i][0] != '@')
ans++;
}
cout << ans << 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
25
26
27
28
29
30
31
32
33
34
35
/*对于给定字符串,找出有重复的字符,并给出其位置*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
string str;
while(cin>>str){
int len=str.size();
for(int i=0;i<len-1;i++){
bool first=true;
bool isDup=false;
if(str[i]!='*'){
//i.j不要老搞错
for(int j=i+1;j<len;j++){
if(str[i]==str[j]){
isDup=true;
str[j]='*';
if(first){
cout<<str[i]<<","<<i+1<<";"<<str[i]<<","<<j+1;
first=false;
}else{
cout<<";"<<str[i]<<","<<j+1;
}
}
}

}
if(isDup){
cout<<endl;
}
}
}

}

5.string循环截取的两种办法

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
//记录当前位置截取法,有当前位置和新位置,不改变原来字符串
void CutString(string line,vector<string> &subline,char a){
//a就是截取的标号
size_t pos=0;
while(pos<line.length()) {
size_t curpos=pos;
pos=line.find(a,curpos);
if(pos==string::npos)
{
pos=line.length();
}
subline.push_back(line.substr(curpos,pos-curpos));
pos++;
}
}

//查找截取之后删除法,不管咋样,pos还是不要放在判定中
while(str.find('.')!=-1){
//观念一直没有改过来,pos是位置,pos-0就是长度,0-pos长度就是pos+!
//pos用法果然有问题
pos=str.find('.');
//下面逻辑没得问题
temp=str.substr(0,pos);
arr.push_back(temp);
str=str.erase(0,pos+1);
}
arr.push_back(str);

6.读入用户输入的,以“.”结尾的一行文字,统计一共有多少个单词

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
2#include<stdio.h>
3#include<string.h>
4int main(){
5char s[1000];
6int len,a[1000]={0},i,cnt;
7、 gets(s);
8、 len=strlen(s);
9printf("len=%d\n",len);
10、 cnt=0;//记录单词数;
11、 i=0;
//如果是这样计算就不要老想着for循环,while自己i++
12while(i<len-1&&s[i]==' '){//去掉开头的空格;
13、 i++;
14、 }
15while(i<len-1){
16if(s[i]!=' '){//遇到字符;
17、 a[cnt]+=1;
18、 i++;
19、 }
20else{//遇到空格;
21、 cnt++;//下一个单词;
22while(i<len-1&&s[i]==' '){//去掉中间的连续空格;
23、 i++;
24、 }
25、 }
26、 }
27printf("单词个数:%d.\n",cnt+1);
28printf("每个单词所含有的字符数是:\n");
29for(i=0;i<cnt+1;i++){
30printf("%d ",a[i]);
31、 }
32、 }

7.找出数组中最长无重复子串的长度

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
/*
输出一个整数,代表arr的最长无重复字符的长度。
不要和最长公共子串搞混,这个就是自己的子串
*/
#include<iostream>
using namespace std;
int A[100001];
int main() {
int n; int length = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i];
}
int start = 0; int i = 1;
while (i < n) {
int temp = 1;
for (int j = start; j < i; j++) {
if (A[j] == A[i]) {
start = j + 1;
}
else {
temp++;
}
if (temp > length)length = temp;
}
i++;
}
cout << length;
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<unordered_set>
using namespace std;

int main()
{
int n;
cin>>n;
int *arr = new int[n];

for(int i = 0; i<n; i++)
{
int temp;
cin>>temp;

arr[i] = temp;
}

int length =0;
int left = 0;
int right = 0;
unordered_set<int> rec;

while (left < n && right < n)
{
int cur = arr[right];
//终于明白了,end()相当于a[n]指向最后一个后一个元素
if (rec.end() == rec.find(cur))
{
rec.insert(cur);
right++;
length = (right - left) > length?(right - left):length;
}
else
{ //没有指向最后一个,也就是说找到了!!,这个意思也就是起点需要后移
//如果一直都是找到的,那么就得一直后移
rec.erase(arr[left]);
left++;
}
}


cout<<length<<endl;
delete [] arr;
return 0;
}

8.手机键盘按键,find和hash办法

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
/*
手机键盘
*/
#include <iostream>

using namespace std;

int main()
{
string arr[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

string str;
while(cin>>str){
int cnt=0;
for(int i=0;i<str.size();i++){
int pos;
for(int j=0;j<8;j++){
if(arr[j].find(str[i])!=-1){
//找到的意思
pos=arr[j].find(str[i]);
if(i+1<str.size()&&arr[j].find(str[i+1])!=-1){
cnt=cnt+2;
}
}
}

cnt=cnt+pos+1;

}

cout<<cnt<<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

1其实只需要一个数组就够用了啊。用key顺序记录26个字母按键次数,
2然后判断两个字母是否在同一个按键上,如果在同一个按键上,那么下标差(字母间距)
就等于按键次数差。
#include<iostream>
#include<string>
using namespace std;
int main()
{
int key[26] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4,1,2,3,1,2,3,4};
string str;
while(cin>>str)
{
int count = key[str[0]-'a'];
for(int i=1;i<str.size();++i)
{
count += key[str[i]-'a'];
if(key[str[i]-'a']-key[str[i-1]-'a']==str[i]-str[i-1])//判断是否在同一个按键上
count+=2;
}
cout<<count<<endl;
}
}

9.给定一个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

/*map方法,自动按照字典序增序
使用substr轻松截取子串,为啥老是忘记了!!*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
string s;
while(cin>>s){
map<string,int> m;
for(int i=0;i<=s.size();i++){
for(int j=0;j<i;j++){
m[s.substr(j,i-j)]++;
}
}

for(auto it=m.begin();it!=m.end();it++){
if(it->second>1)
cout<<it->first<<" "<<it->second<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//一前一后两个指针来截取子串

#include <iostream>
#include <bits/stdc++.h>
#define N 5050

using namespace std;

struct STR{
string s;
unsigned cnt;
}buf[N]; //子串集合

int n; //子串数量
string str; //读取的字符串
string child; //临时存储子串


void MakeChild(int from,int len){
child.clear();
for(int i=0;i<len;i++){
//果然在于这里的处理方式
child=child+str[from+i];
}
}

bool cmp(STR a,STR b){
return a.s<b.s;
}

void letsGo(){
//生成子串列表并完成统计
int len=str.size();
for(int i=1;i<len;i++){
//i是子串长度
for(int from=0;from+i<=len;from++){
MakeChild(from,i); //生成子串
bool repeat=false; //用来检查这个子串以前是否出现
for(int i=0;i<n;i++){
if(buf[i].s==child){
buf[i].cnt++;
repeat=true;
break;
}
}
if(!repeat){
//这个字串以前没有出现过
buf[n].cnt=1;
buf[n].s=child;
n++;
}
}
}


}

int main()
{
while(cin>>str){
n=0; //子串个数
letsGo();
sort(buf,buf+n,cmp);
for(int i=0;i<n;i++){
if(buf[i].cnt>1){
cout<<buf[i].s<<" "<<buf[i].cnt<<endl;
}
}
}
return 0;
}

数学专题,模拟

素数问题,普通筛和埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
bool judge(int x){
if(x<=1) return false;
int bound=(int)sqrt(x)+1;
//计算枚举上界,采用根号值取整后再加1
for(int i=2;i<bound;i++){
if(x%i==0) return false;
}

/*
或者直接for(int i=2,i*i<=n,i++) 会更省事
*/
return true;
}
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
//埃氏筛法
#include <iostream>

using namespace std;
//必须得要const int变量才可s
const int maxn=10001;
int prime[maxn],num=0;
bool p[maxn]={0};

void Find_Prime(){
for(int i=2;i<maxn;i++){
if(p[i]==false){
prime[num++]=i;
for(int j=i+i;j<maxn;j=j+i){
//倍数全都不是素数
p[j]=true;
}
}
}
}
int main()
{
int n;
Find_Prime();
while(cin>>n){
int count=0;
for(int i=0;i<maxn;i++){
if(prime[i]<n&&prime[i]%10==1){
count++;
cout<<prime[i];
if(i!=num-1)
cout<<" ";
}else if(prime[i]>=n)
break;
}
if(count==0) cout<<-1;
cout<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//超级素数要求是连续几个素数之和

//知识点:素数大表,计算小于N的素数并存储
//若N不是素数,返回结束
//若N是素数,用i,j对连续素数表进行遍历,若连续素数之和小于N
//j指针向后移动,累加求和,若连续素数之和大于N,将当前
//连续素数之和sum减去当前i指针指向素数,i指针向后移动

#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;

bool vis[100000];
int prime[100000];

//素数打表部分
void init_prime(int n){
fill(vis,vis+100000,true);
vis[0]=vis[1]=false;
int num=0;

for(int i=2;i<=n;i++){
if(vis[i]==true){
num++;
prime[num]=i;
}
//j<=num保证prime[]存在,prime[]*i保证数字在n的范围内
for(int j=1;(j<=num)&&(i*prime[j]<=n);j++){
vis[i*prime[j]]=false; //prime[]倍数肯定不是素数
if(i%prime[j]==0){
break;
}
}
}
}

int main()
{
init_prime(100000);
int n;
cin>>n;

if(!vis[n]){
//若n不是素数,直接输出no,结束程序
cout<<"no"<<endl;
return 0;
}

int i=1,j=1,sum=0,count=0;
bool flag=false;

while(i<=j&&!flag){
sum+=prime[j]; //将i~j之间的素数求和
count++;
if(sum==n&&count>1){
flag=true;
break;
}else if(sum<n){
//如果连续素数之和小于n,则j往后移动
j++;
continue;
}
//sum超了的话,就移动i从小的减起
while(sum>n&&!flag&&count>1){
//连续素数之和大于n,减去i指针指向素数
sum=sum-prime[i];
count--;
if(sum==n&&count>1){
i++;
flag=true;
break;
}else if(sum<n&&count>1){
j++;
i++;
break;
}
i++;
//指针向后移动
}

}
if(flag){
cout<<"yes"<<endl;
int res=0;
for(int k=i;k<=j;k++){
cout<<prime[k]<<" ";
}
cout<<endl;
}else{
cout<<"no"<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//埃氏筛法
#include <iostream>
#include <cmath>
using namespace std;
//必须得要const int变量才可s
const int maxn=1000001;
int prime[maxn],num=0;
bool p[maxn]={0};

void Find_Prime(){
for(int i=2;i<maxn;i++){
if(p[i]==false){
prime[num++]=i;
for(int j=i+i;j<maxn;j=j+i){
p[j]=true;
}
}
}
}

struct factor{
int cnt,x;
}fac[10];
int main()
{
Find_Prime();
int n;
while(cin>>n){
int no=0;
int sqr=(int)sqrt(1.0*n);
//质因数一定是小于数的根号!!
for(int i=0;i<num&&prime[i]<=sqr;i++){
if(n%prime[i]==0){
fac[no].cnt=0;
fac[no].x=prime[i];
//重复除以当前质数,计算该质数的数量
while(n%prime[i]==0){
fac[no].cnt++;
n=n/prime[i];
}
no++;
}
if(n==1) break;
}
//次数的意思是n不为1,且n是质数时,自己是自己的质因数
if(n!=1){
fac[no].x=n;
fac[no].cnt=1;
no++;
}

int count=0;
for(int i=0;i<no;i++)
//次数如果是求约数的话!!要用乘以所有质因数的办法
// count*=(fac[i].cnt+1);
count=count+fac[i].cnt;
cout<<count<<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
25
方法二:太强了!!,这个逻辑
#include <iostream>

using namespace std;

int main()
{
long m;
while(cin>>m){
long cnt=0;
for(long j=2;j*j<=m;j++){
while(m%j==0){
m=m/j;
cnt++;
}
}
//这个意思是质数本身么
if(m>1) cnt++;
cout<<cnt<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//C程序设计第五版(谭浩强)
//章节:第六章 利用数组处理批量数据
//题号:6.7
//题目:输出奇数阶魔方阵
// 将1放在第一行中间一列;
// 从2开始直到 n×n为止各数依次按照如下规则存放
// 1)每一个数存放的行是前一个数的行减去1,列数加1(例如三阶魔方阵,5在4的上一行后一列);
// 2)如果前一个数的行数为1,那么下一个数的行数为n(最后一行),列同样,如果前一个数的列数为n,那么下一个数的列数为1;
// 3)如果按照上面规则存放时发现位置上已存在数或者上一个数是第一行第n列时,则把下一个数放在上一个数的下面即可。

#include <stdio.h>

int main(){
int x[100][100]={0},i,j,n,a,b;
printf("您打算输出几阶魔方阵(奇数阶):");
scanf("%d", &n);
a = 0;
b = n/2;
x[a][b] = 1; // 1
for(i=2;i<=n*n;i++){
//特殊情况都输出也不错
if(a==0 && b!=n-1){ // 前一个数在第一行但是不在最后一列
a = n-1;
b = b+1;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数,则把这个数放在上一个数的下方
a = 1;
b = b-1;
x[a][b] = i;
}
}
else if(a!=0 && b==n-1){ // 前一个数不在第一行但是在最后一列
a = a-1;
b = 0;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
a = a+1;
b = n-1;
x[a][b] = i;
}
}
else if(a==0 && b==n-1){ // 前一个数在第一行同时在最后一列
a = n-1;
b = 0;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
a = 1;
b = n-1;
x[a][b] = i;
}
}
else{
a = a-1;
b = b+1;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
//终于看懂了!!不变的意思,自己对自己操作!!
a = a+2;
b = b-1;
x[a][b] = i;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%5d", x[i][j]);
}
printf("\n");
}
return 0;
}

//优化版!!,主要是总结归纳特殊情况为a = (a-1+3)%3;b = (b+1+3)%3;
int main(){
int x[100][100]={0},i,j,n,a,b;
printf("您打算输出几阶魔方阵(奇数阶):");
scanf("%d", &n);
a = 0;
b = n/2;
x[a][b] = 1; // 1
for(i=2;i<=n*n;i++){
//特殊情况都输出也不错,特殊情况应当优先判断!!!
if(a==0 && b==n-1){ // 前一个数在第一行同时在最后一列
a = n-1;
b = 0;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
a = 1;
b = n-1;
x[a][b] = i;
}
}
else{
a = (a-1+3)%3;
b = (b+1+3)%3;
if(x[a][b]==0){ // 如果这个位置不存在数
x[a][b] = i;
}else{ // 如果这个位置存在数
//终于看懂了!!不变的意思,自己对自己操作!!
a = a+2;
b = b-1;
x[a][b] = i;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%5d", x[i][j]);
}
printf("\n");
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
using namespace std;

/*
①11<13,11*10/13=8,余数=6
②6<13,6*10/13=4,余数=8
③8<13,8*10/13=6,余数=2
④2<13,2*10/13=1,余数=7
⑤7<13,7*10/13=5,余数=5
⑥5<13,5*10/13=3,余数=11
⑦11<13,11*10/13=8,余数=6

都是用余数乘以10去除以的,最终商和余数都相等,则有循环节
分成两部分:
第一部分模拟除法运算,每进行一步除法运算,
都需要将得到的商和余数分别保存在数组中,商用来输出,余数用来
判断是否循环,要在第二部分当中检测。

第二部分:将传递进来的商和余数,和保存在数组中的历史商和余数进行比较
若不相等,第一部分继续运算,若相等,记下当前商的所在下标
下标即为循环节的起始位置


*/
//第二部分的判断
int pos=0;
bool findR(vector<int> rem, vector<int> dec, int r, int c)
{
for (int i = 0; i < dec.size(); i++)
{
if (rem[i] == r && dec[i] == c)
{
pos = i;
return false;
}
}
return true;
}



void dipose(int n, int d)
{
string fp = to_string(n / d) + "."; //整数部分
if (n > d) //第一次除法
{
n = n % d;
}
int r, c; //r是余数,c是商
c = n * 10 / d;
r = (n * 10) % d;

vector<int> rem, dec; //rem是商数组保存之前的商,dec是余数数组保存之前的余数
bool flag = true;
while (findR(rem, dec, r, c))
{
dec.push_back(c);
rem.push_back(r);
r *= 10;
c = r / d;
r %= d;
if (c == 0)
{
flag = false; //flag为true为循环小数,flag为false为不循环小数
break;
}
}

cout << fp;
for (int i = 0; i < pos; i++)
{
cout << dec[i];
}

for (int i = pos; i < dec.size(); i++)
{
if (i == pos && flag)
{
cout << "(";
}
cout << dec[i];
if (i == dec.size() - 1 && flag)
{
cout << ")";
}
}
cout << endl;
}


int main()
{
int a1,b1,a2,b2,a3,b3;
scanf("%d/%d %d/%d %d/%d",&a1,&b1,&a2,&b2,&a3,&b3);
dipose(a1,b1);
dipose(a2,b2);
dipose(a3,b3);
}

求最大公约数

1
2
3
4
int gcd(int a,int b){
if(b==0) return a;
else return gcd(b,a%b);
}

求最小公约数

求得A和B的最大公约数是C,则最小公倍数A*B/C

矩阵排序思想

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
47
48
49
50
51
52
53
/*输入一个四行五列矩阵,找出每列对最大的两个数*/

/*
第二题:输入一个四行五列的矩阵,找出每列最大的两个数,如:
输入:
1 2 3 4 9
-1 4 9 8 8
12 9 8 7 0
7 8 9 7 0
输出:12 9 9 8 9

7 8 9 7 8*/
/*循环五次,每次对每一列进行快排(降序),最后将前两行的结果输出即可*/

#include <iostream>
#include <algorithm>
using namespace std;

//bool型返回值
bool comp(int a,int b){
return a>b;
}

//好思想,先排序,排序好后再将原来的数字替换,输出前两行即可,关键是思想到位,知道怎样
//在矩阵当中对于列排序
int main(){
int buf[4][5];
int x;
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
cin>>x;
buf[i][j]=x;
}
}
int tmp[4];
for(int j=0;j<5;j++){
for(int i=0;i<4;i++){
//傻傻了,行列依然不变,i,j,这样就是(0,0)(1,0)(2,0)(3,0)
tmp[i]=buf[i][j];
//不用会表达一列,只需要把它们可以取出来,用中间数列进行排序
}
sort(tmp,tmp+4,comp);
for(int i=0;i<4;i++){
buf[i][j]=tmp[i];
}
}
for(int i=0;i<2;i++){
for(int j=0;j<5;j++){
cout<<buf[i][j]<<" ";
}
cout<<endl;
}
}

求约数节省效率办法

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>
#include <bits/stdc++.h>
using namespace std;

//求约数的方法太落后了,没考虑时间复杂度
int yueshu(int x){
int cnt=0;
for(int i=1;i*i<=x;i++){
if(x==i*i)
cnt=cnt+1;
else if(x%i==0){
//仔细考虑一下确实是对称的!!
cnt=cnt+2;
}or
}
return cnt;
}


//这个方法也不错
int numOfDivisor(int num)
{
int ans = 0;
int i;
for (i = 1; i*i<num; i++)
{
if (num%i == 0)
ans += 2;
}
if (i*i == num) ans++;
return ans;
}

int main()
{
int n;
while(cin>>n){
for(int i=0;i<n;i++){
int x;
cin>>x;
cout<<yueshu(x)<<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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*n个人排一圈123报数,报到3的人退到圈外,直到剩最后一个人为止。*/
//终于自我分析出了约瑟夫环
#include <iostream>

using namespace std;

int main()
{
int n;
while(cin>>n){
int count=n;
int num=1;
//这样分配内存保险
int arr[1000];
for(int i=0;i<=n;i++){
arr[i]=1;
}

while(count!=1){
for(int i=1;i<=n;i++){

if(arr[i]==0) continue;
else{
if(num!=3){
num++;
}else{
cout<<i<<endl;
num=1;
arr[i]=0;
count--;
}
}
if(i==n) i=0;
}
}
for(int i=1;i<=n;i++){
if(arr[i]==1) cout<<i<<endl;
}
}
}

高级链表版约瑟夫环(单循环链表)

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
47
48
49
50
51
#include<stdio.h>
#include<stdlib.h>
typedef struct node{//链表结点数据结构定义;
int data;
struct node *next;
}LNode,*LinkList;

void Josephus(int n,int k,int m){//约瑟夫环问题;n:人数,k:开始计数位置,m:数到几退出一个人;
LinkList p,q,r;//p指向表头;
int i,cnt;
p=(LinkList)malloc(sizeof(LNode));
p->data=1;
p->next=NULL;
q=p;
for(i=2;i<=n;i++){//创建单循环链表;如何创建单循环链表
r=(LinkList)malloc(sizeof(LNode));
r->data=i;
r->next=NULL;
q->next=r;
q=q->next;
}
//此处指向队头,完成连接
q->next=p;
//走到开始计数的位置
for(i=1;i<k;i++){
q=p;//q始终指向前驱;
p=p->next; //p移到开始的结点;
}
cnt=1;
//也就是说只剩最后一个结点时,自己指向自己
while(q->next!=q){
cnt++;
q=p;
p=p->next;
if(cnt%m==0){//将要退出一个人;
printf("%d ",p->data);
q->next=p->next;
p=p->next;
cnt++;
}
}
printf("%d/n",q->data);
}

int main(){
int n,k;
printf("请输入人数n、从谁开始数k:\n");
scanf("%d %d",&n,&k);
Josephus(n,k,3);
system("pause");
}

约瑟夫环再进阶版,拆封成.h和.c多个文件

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
生成一个长度为21的数组,依次存入1到21;建立一个长度为21的单向链表,将上述数组中的数字依次存入链表每个结点中;将上述链表变为单向封闭(循环)链表;从头结点开始数,将第17个结点删除,将它的下一个结点作为新的头结点;重复上述过程,直到该链表中只剩一个结点,显示该结点中存入的数字。
分三个文件,一个main; 一个.h; 一个.c 文件。
*/
count21.h文件:
#ifndef COUNT_21_H_INCLUDED
#define COUNT_21_H_INCLUDED
#define NUM 21//链表节点数;
typedef struct node{//链表结点数据结构定义;
int data;
struct node *next;
}LNode,*LinkList;

LinkList CreateList();//创建单循环链表;
#endif

count21.c文件:
#include<stdio.h>
#include<stdlib.h>
#include"Count21.h"
LinkList CreateList(){//建立单循环链表;
LinkList L,p,q;
int i;
L=(LinkList)malloc(sizeof(LNode));
p=L;
L->data=1;
L->next=NULL;
for(i=2;i<=NUM;i++){
q=(LinkList)malloc(sizeof(LNode));
q->data=i;
q->next=NULL;
p->next=q;
p=p->next;
}
p->next=L;//构成循环链表;
return L;
}
main.c文件
#include<stdio.h>
#include<stdlib.h>
#include"Count21.h"
int main(){
LinkList L,p,q;
L=CreateList();
p=L;//p指向当前节点;
q=L;
while(q->next!=L){
q=q->next;
}//q指向前驱;
int cnt=1;
while(q->next!=q){
cnt++;
q=p;
p=p->next;
if(cnt%17==0){
printf("%d ",p->data);
q->next=p->next;
p=p->next;
cnt++;
}
}
printf("%d/n",p->data);
system("pause");
}

打赏一瓶冰阔落,马上继续又创作