1.求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。
方法1
层序遍历，它不需要遍历所有的节点，一旦找到一个叶节点，它肯定是最短的。
class Solution {
public:
typedef TreeNode* tree;
int run(TreeNode *root) {
//采用广度优先搜索，或者层序遍历，找到的第一个叶节点的深度即是最浅。
if(! root) return 0;
queue<tree> qu;
tree last,now;
int level,size;
last = now = root;
level = 1;qu.push(root);
while(qu.size()){
now = qu.front();
qu.pop();
size = qu.size();
if(now->left)qu.push(now->left);
if(now->right)qu.push(now->right);
if(qu.size()-size == 0)break;
if(last == now){
level++;
if(qu.size())last = qu.back();
}
}
return level;
}
};
方法2
递归，若为空树返回0；
若左子树为空，则返回右子树的最小深度+1；（加1是因为要加上根这一层，下同）
若右子树为空，则返回左子树的最小深度+1；
若左右子树均不为空，则取左、右子树最小深度的较小值，+1；
class Solution {
public:
int run(TreeNode *root)
{
if(root == nullptr) return 0;
if(root->left == nullptr) // 若左子树为空，则返回右子树的最小深度+1
{
return run(root->right)+1;
}
if(root->right == nullptr) // 若右子树为空，则返回左子树的最小深度+1
{
return run(root->left)+1;
}
// 左右子树都不为空时，取较小值
int leftDepth = run(root->left);
int rightDepth = run(root->right);
return (leftDepth<rightDepth)?(leftDepth+1):(rightDepth+1);
}
};
2.成绩排序
作者：▁▁▁久而久之;
链接：[https://www.nowcoder.com/questionTerminal/0383714a1bb749499050d2e0610418b1](https://www.nowcoder.com/questionTerminal/0383714a1bb749499050d2e0610418b1)
来源：牛客网
#include<iostream>
#include<string>
using namespace std;
int main()
{
int m, t;
while (cin >> m >> t)
{
int grade;
string name;
string M[101];
while (m--)//比for循环简洁
{
char ch[10];
cin >> name >> grade;
itoa(grade,ch,10);
M[grade] = M[grade] + name + " " + ch + '\n';
}
if (t == 1)
{
for (int i = 0;i <= 100; ++i)
if (!M[i].empty())
cout<<M[i];
}
else
{
for (int i = 100; i >= 0; --i)
if (!M[i].empty())
cout<<M[i];
}
}
return 0;
}
知识点1：while(cin>>n){}
cin>>a代表获取键盘输入的值赋值给变量a，将cin>>a置于while的循环条件内将会一直测试输入流是否正常。
如果输入流正常，就会继续循环获取键盘值，如果输入流错误，或者达到文件末尾，该循环就会终止。
测试代码如下：
#include<iostream>
using namespace std;
int main()
{
int a= 0 ;
int cnt=1;//统计次数
while(cin >> a)
{
cout<<a<<endl;
cnt++;
} //while循环结束
cout<<cnt<<endl;
return 0;
}
该代码会将从键盘获取到的标准输入流（即键盘输入的整数）以标准输出流输出(即显示到屏幕终端上)。
知识点2:itoa(grade,ch,10);
VC6.0中，将int转换成string:
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n=65535;
char t[256];
string s;
sprintf(t,"%d",n);
s=t;
cout<<s<<endl;
return 0;
}
#include<iostream>
#include<string>
#include<sstream>
using namespace std;
int main()
{
int n=65535;
stringstream ss;
string ss;
ss<<n;//注意箭头方向
ss>>s;
cout<<s<<endl;
return 0;
}
可以这样理解，stringstream(ss)可以吞下不同的类型，根据s的类型，吐出不同的类型。
使用itoa
char *itoa(int value,char *string,int radix);
value:欲转换的数据
string:目标字符串的地址
radix:转换后的进制数
返回值：指向string这个字符串的指针
#include<iostream>
#include<string>
using namespace std;
int main()
{
int a=30;
char c[8];
itoa(a,c,16);
cout<<c<<endl;//1e
return 0;
}
注意：itoa并不是一个标准的C函数，它是Windows特有的，如果要写跨平台的程序，请用sprintf。
3.约数个数
输入描述：
输入的第一行为N，即数组的个数(N<=1000)
接下来的1行包括N个整数，其中每个数的范围为(1<=Num<=1000000000)
当N=0时输入结束。
输出描述:
可能有多组输入数据，对于每组输入数据，
输出N行，其中每一行对应上面的一个数的约数的个数。
#include<iostream>
#include<vector>
using namespace std;
void Yueshu(long int p[])
{
long int a[1000]={0};
long int count=0;
long int j=0;
while(*p!=0)
{
a[count]=*p;
p=p+1;
count++;
}
while(a[j]!=0)
{
long int ans = 0;
long int l;
for (l = 1; l*l<a[j]; l++)
{
if (a[j]%l == 0)
ans += 2;
}
if (l*l == a[j]) ans++;
cout<<ans<<endl;
j++;
}
}
int main()
{
int N;
long int num[1000]={0};
while(cin>>N)
{
if(N==0) return 0;
for(int i=0;i<N;i++)
cin>>num[i];
Yueshu(num);
}
return 0;
}
知识点1：
如果用普通的遍历求约数的方法，时间复杂度会超。
用以下的方法求约数可以降低时间复杂度
int ans = 0;
int l;
for (l = 1; l*l<a[j]; l++)
{
if (a[j]%l == 0)
ans += 2;
}
if (l*l == a[j])
ans++;
return ans;
知识点2：
数组作为参数传递的时候，会自动退化为指向数组首地址的指针。形参为相应的指针形式，用*访问数组元素。
void Test(int p[])
void Test(int *p)
用p=p+1访问下一个元素。
4.代理服务器
使用代理服务器能够在一定程度上隐藏客户端信息，从而保护用户在互联网上的隐私。我们知道n个代理服务器的IP地址，现在要用它们去访问m个服务器。这 m 个服务器的 IP 地址和访问顺序也已经给出。系统在同一时刻只能使用一个代理服务器，并要求不能用代理服务器去访问和它 IP地址相同的服务器（不然客户端信息很有可能就会被泄露）。在这样的条件下，找到一种使用代理服务器的方案，使得代理服务器切换的次数尽可能得少。
输入描述:
每个测试数据包括 n + m + 2 行。
第 1 行只包含一个整数 n，表示代理服务器的个数。
第 2行至第n + 1行每行是一个字符串，表示代理服务器的 IP地址。这n个 IP地址两两不相同。
第 n + 2 行只包含一个整数 m，表示要访问的服务器的个数。
第 n + 3 行至第 n + m + 2 行每行是一个字符串，表示要访问的服务器的 IP 地址，按照访问的顺序给出。
每个字符串都是合法的IP地址，形式为“xxx.yyy.zzz.www”，其中任何一部分均是0–255之间的整数。输入数据的任何一行都不包含空格字符。
其中，1<=n<=1000，1<=m<=5000。
输出描述:
可能有多组测试数据，对于每组输入数据， 输出数据只有一行，包含一个整数s，表示按照要求访问服务器的过程中切换代理服务器的最少次数。第一次使用的代理服务器不计入切换次数中。若没有符合要求的安排方式，则输出-1。
示例
输入
3
166.111.4.100
162.105.131.113
202.112.128.69
6
72.14.235.104
166.111.4.100
207.46.19.190
202.112.128.69
162.105.131.113
118.214.226.52
输出
1
在
服务器中寻找初次出现最晚的代理服务器的IP地址,为第一次切换。
以当前位置为新的起点，再次在服务器中开始寻找所有的代理服务器的出现最晚的IP地址，为下一次切换。
循环往复，直到遍历完所有服务器
#include<iostream>
#include<string>
using namespace std;
int main()
{
int N,M;
string n[1000];
string m[5000];
while(cin>>N)
{
for(int i=0;i<N;i++)
cin>>n[i];
cin>>M;//这里不用加while()
for(int k=0;k<M;k++)
cin>>m[k];
//唯一不可行的时候：只有一个代理服务器，且服务器有IP相同的
if(N==1)
{
int f=1;
for(int t=0;t<M;t++)
if(n[0]==m[t])
f=0;
if(f)
cout<<0<<endl;
else
cout<<-1<<endl;
continue;
}
int max=0;//选择初次出现最晚的代理IP作为切换的新IP
int begin=0;//断点
int count=0;
int j,i;
while(begin!=M)
{
for(i=0;i<N;i++)
{
for(j=begin;j<M;j++)
{
if(n[i]==m[j])
break;
}
if(j>max)
max=j;
}
begin=max;
count++;
}
cout<<count-1<<endl;//第一次设置不算在内
}
return 0;
}
Tips:没有较为陌生的语法，掌握好思路。
5.手机键盘
按照手机键盘输入字母的方式，计算所花费的时间 如：a,b,c都在“1”键上，输入a只需要按一次，输入c需要连续按三次。 如果连续两个字符不在同一个按键上，则可直接按，如：ad需要按两下，kz需要按6下 如果连续两字符在同一个按键上，则两个按键之间需要等一段时间，如ac，在按了a之后，需要等一会儿才能按c。 现在假设每按一次需要花费一个时间段，等待时间需要花费两个时间段。 现在给出一串字符，需要计算出它所需要花费的时间。
一个很好的思路：
一个数组用
key[]顺序记录26个字母按键次数.
然后判断两个字母是否在同一个按键上 : 如果在同一个按键上，那么下标差（字母间距）就等于按键次数差。
#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;
}
}
6.求质因数的个数
求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=22235，共有5个质因数。
下面是我的代码，时间复杂度较高，未能通过：
#include<iostream>
using namespace std;
int Zhi(long int a)
{
if(a==2)
return 1;
else
for(long int i=2;i<a;i++)
if(a%i==0)
return 0;
return 1;
}
int main()
{
long int num;
while(cin>>num)
{
long int count=0;
//如果输入质数，质因数个数为0；
if(Zhi(num))
{
cout<<0<<endl;
continue;
}
long int k=2;
while(k<=num)
{
if(num%k==0)
{
if(Zhi(k))
count++;
num=num/k;
k=2;
continue;
}
k++;
}
cout<<count<<endl;
}
return 0;
}
N最多只存在一个大于sqrt(N)的质因数，所以只需要把所有小于此范围的质数去除后，剩余的就是大于的了。因此在不断除以质数后，如果N还大于1，说明还有且仅有1个大于sqrt(N)的质因数。
#include <iostream>
#include <cmath>
using namespace std;
int main(){
//这题的关键：
//1、是sqrt,可以极大减少复杂度，若是到方根N仍大于1，则必还有且只还有1个质因数
//2、每次瞬间整除都可帮助减少遍历范围
long M=100;
while(cin>>M)
{
long count=0;
for(long j=2;j<=sqrt(M);j++)
{
while(M%j==0)
{
M=M/j;
count++;
}
if(M<=1)break;
}
if(M>1)count++;
cout<<count<<endl;
}
return 0;
}
Q:为什么不用判断j是不是质数呢？
因为任何一个合数都能被一个比它小的质数整除。所以当我们用小质数去分解这个给定的数时，我们已经把他的合数因子分解了。
或者从反面去说，如果出现了一个合数a能整除这个数M，那显然在j =a之前应该有一个质数p < a 能把a整除，而之前反复地用M去除以p直到p不能再整除M 程序才往下执行，那怎么会后来又出现了M中一个合数因子a能被p整除呢？这显然矛盾了。
从而可以推出，程序中能整除M的数都是质数。
7.整数分解
一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。 用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。
#include <iostream>
#include <vector>
using namespace std;
/*
思路：
1、奇数：f(5)的分解方法为f(4) + 1，1不可再分，f(n) = f(n - 1)
2、偶数：f(4)的分解方法为2 + 1 + 1或2 + 2, f(n) = f(n - 2) + f(n / 2)
*/
int main() {
long long n;
while (cin >> n) {
vector<long long> nums(n + 1);
nums[1] = 1;
nums[2] = 2;
for (int i = 3; i <= n; i++) {
if (i % 2 == 1) {
nums[i] = nums[i - 1] % 1000000000;
}
else {
nums[i] = (nums[i - 2] + nums[i / 2]) % 1000000000;
}
}
cout << nums[n] << endl;
}
return 0;
}
理解无能，且先记下来。
据说是背包问题的变形。
对应的代码：
#include<iostream>
#include<cmath>
using namespace std;
const int MAXLENGTH=10000001;
int F[MAXLENGTH];
int main(){
int V;
int Ci[21];
F[0]=1;
for(int i=1;i<=20;i++){
Ci[i]=(int)pow(2,i-1);
}
while(cin>>V){
for(int i=1;i<=20;i++){
for(int j=Ci[i];j<=V;j++){
F[j]=(F[j]+F[j-Ci[i]])%1000000000;
}
}
cout<<F[V]<<endl;
}
return 0;
}
8.成绩排序
输入描述:
输入第一行包括一个整数N(1<=N<=100)，代表学生的个数。
接下来的N行每行包括两个整数p和q，分别代表每个学生的学号和成绩。
输出描述:
按照学生的成绩从小到大进行排序，并将排序后的学生信息打印出来。
如果学生的成绩相同，则按照学号的大小进行从小到大排序。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct student
{
int num;
int score;
};
bool cmp(const student& a,const student b)
{
if(a.score<b.score)
return true;
else if(a.score==b.score&&a.num<b.num)
return true;
return false;
}
int main()
{
int n;
cin>>n;
vector<student> table(n);
for(int i=0;i<n;i++)
cin>>table[i].num>>table[i].score;
sort(table.begin(),table.end(),cmp);
for(i=0;i<n;i++)
cout<<table[i].num<<" "<<table[i].score<<endl;
return 0;
}
知识点1：
在VC6.0中，数组不可以用变量初始化，但容器可以。
知识点2：
STL的使用
9.二叉树遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入
abc##de#g##f###
输出
c b e g d f a
//这个实际上就是树的遍历的非递归实现，入栈时访问 = 前序， 出栈时访问 = 中序
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main()
{
string pre;
while(cin >> pre)
{
stack<char> s;
for(auto it : pre){
if(it != '#')
s.push(it);
else{
if(!s.empty()){
cout << s.top() << ' ';
s.pop();
}
}
}
cout << '\n'; }
}
-
auto it:pre在VC6.0上不能通过编译，调整如下。
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
string str;
stack<char> s;
while(cin>>str)
{
for(int i=0;str[i]!='\0';i++)
{
if(str[i]!='#')
s.push(str[i]);
else
{
if(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
}
}
cout<<endl;
}
return 0;
}
10.BFS(广度优先搜索)
玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。
典型的BFS，节点就是一个字符串，与它相邻的节点就是由它交换一次所得的字符串。
从初始节点出发，看看它交换一次形成的字符串里哪些没出现过，这些字符串如果有符合要求的就结束BFS返回结果，如果不符合要求那就把它们加入队列。遍历完之后还是没碰到符合要求的字符串就返回-1。
#include<iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;
map<string,int> M; //用来记录交换了多少次位置
queue<string> Q; //广度优先时，用来存储字符串
string swap(string str,int i)
{
char temp = str[i];
str[i] = str[i+1];
str[i+1] = temp;
return str;
}
int BFS(string str)
{
string newStr;
M.clear(); //清空map
//清空队列
while(!Q.empty())
{
Q.pop();
}
Q.push(str);//将字符串加入队列
M[str] = 0; //str作为根节点，高度为0
while(!Q.empty())
{
str = Q.front();//将队列的第一个值赋给str
Q.pop();
//交换str中相邻的两个字符
for(int i=0;i<str.length()-1;i++)
{
newStr = swap(str,i);
if(M.find(newStr) == M.end())//如果该字符串未出现过，说明该字符串是交换过后的字符串
{
M[newStr] = M[str]+1;//交换次数+1
if(newStr.find("2012",0) != string::npos)//从该字符串中找到了2012,返回交换次数
{
return M[newStr];
}
else
{
Q.push(newStr);//如果不符合要求，则继续进行交换
}
}
}
}
return -1;//未找到
}
int main()
{
int length;
string s;
while(cin >> length)
{
cin >> s;
if(length < 4)
{
cout << "-1" << endl;
}
if(s.find("2012",0) != string::npos)//如果字符串中有2012，直接输出交换0次
{
cout << "0" << endl;
}
else
{
cout << BFS(s) << endl;
}
}
return 0;
}
11.求最大最小值
输入N个（N<=10000）数字，求出这N个数字中的最大值和最小值。每个数字的绝对值不大于1000000。
本题较为简单，复习sort()的使用。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int N;
while(cin>>N)
{
vector<long int> a(N);
for(int i=0;i<N;i++)
cin>>a[i];
sort(a.begin(),a.end());
cout<<a[N-1]<<" "<<a[0]<<endl;
}
return 0;
}
(未解决)12.最少邮票数
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。
输入描述:
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
0-1背包问题/动态规划
0-1最小背包问题 求解装满背包的前提下使用物品最少的数量
其中：
邮票总值相当于背包容量，
邮票的面值相当于物品的重量，
邮票的数量相当于物品的总价值，
每张邮票的价值默认为1。
#include <bits/stdc++.h>
using namespace std;
const int MAX = 0x7f7f7f;
int ZeroOnePack(int nPackCap, int nItemNum, vector<int> &weight)
{
vector<int> dp(nPackCap+1, MAX);
dp[0] = 0;
for (int i = 0; i < nItemNum; ++i)
{
int nWeight = weight[i];
for (int j = nPackCap; j >= nWeight; --j)
{
dp[j] = min(dp[j], dp[j-nWeight]+1);
}
}
return dp[nPackCap] < MAX ? dp[nPackCap] : 0;
}
int main()
{
int M = 0;
int N = 0;
while (cin >> M >> N)
{
vector<int> weight(N);
for (int i = 0; i < N; ++i)
{
cin >> weight[i];
}
cout << ZeroOnePack(M, N, weight) << endl;
}
return 0;
}
