痛战！！！华为机试

搜诶符合你

　　本文记录自己的刷题记录，会有自己的代码（第一反应敲出的代码），都是AC过的。会用到别人的算法，在这里做不提名感谢，若有侵权，还望告知。谢谢！！！

格式问题，后续会逐一解决的，菜鸡的我忙着找工作，自用的是


　　2016年9月13日12:57:17
　　=========================================================================================================痛！！！战！！！
　　题目和牛客网上的题目是一样的，顺序不同。
　　=========================================================================================================痛！！！战！！！
　　1、明明的随机数
　　题目：https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0
　　方法一：
　　思路：（第一反应记录）
　　　　读入数组，然后用sort（begin,end）函数排序，输出的时候控制相同的只输出一次。





1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 int main(){
7     int n;
8     while (cin >> n){
9         int nums[n];
10         for (int i = 0; i < n; i++){
11             cin >> nums;
12             //nums = cin;
13         }
14         
15         sort(nums,nums+n);
16         
17         for (int i = 0; i < n; i++){
18             if (i ==0 ) cout << nums << endl;
19             else if ( nums != nums[i-1])
20                 cout << nums << endl;
21         }
22     }
23     return 0;
24 }
View Code　　方法二：大牛码的
　　思路：（666）
　　读入的数存放到对应下标中，并记录为1。即，输入66，存入数组为nums中的方式是：nums[66] = 1。懂了吧？
　　数组的大小是固定的





1 #include <iostream>
2 using namespace std;
3 int main() {
4     int N, n;
5     while (cin >> N) {
6         int a[1001] = { 0 };
7         while (N--) {
8             cin >> n;
9             a[n] = 1;
10         }
11         for (int i = 0; i < 1001; i++)
12             if (a)
13                 cout << i << endl;
14     }
15     return 0;
16 }
View Code　　2、字符串最后一个单词的长度
　　题目：http://www.nowcoder.com/practice/8c949ea5f36f422594b306a2300315da?tpId=37&tqId=21224&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　方法一：
　　思路：
　　把一行的字符串全部读入，保留空格。然后对字符串逆向读取，并将其压入栈中，压栈过程通过空格控制，然后判断栈的大小即可（输出栈也可以做到）
　　纠结癌：
　　想通过cin 控制输入，直接定位到最后一个单词，这样想可以，做不到就别纠结，要不就常规，getline（cin，ss）   GET
　　注意：
　　字符串倒着读取的时候，是从 ss.size() - 1 开始的。
　　知识点：
　　stack 基本操作





1 #include <iostream>
2 #include <stack>
3
4 using namespace std;
5
6 int main(){
7     string s;
8     while(getline(cin,s)){
9         stack<char> st;
10         for (int i = s.size() - 1; i >= 0; i--){
11             if (s == ' ') break;
12             st.push(s);
13         }
14         cout << st.size();
15            
16     }
17     return 0;
18 }
View Code　　方法二：两例都AC了   我哭了
　　思路：
　　感觉和我第一直觉的方法很想，但是，本地调试不通过，在线测试时通过的，代码如下，求解释，求告知测试用例的机制





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




1 //输入流直接会记录最后一个字符串，因为单词之间是用空格隔开的
2 #include<iostream>
3 #include<string>
4 using namespace std;
5 int main(){
6     string str;
7     while(cin>>str);
8     cout<<str.size()<<endl;
9     return 0;
10 }
View Code　　问题补充：
　　有些同学的答案没考虑到末尾有空格的情况，对于末尾有空格的都输出为0了。


　　“hello world     ”依然输出5.






1 // C++
2 //有些同学的答案没考虑到末尾有空格的情况，对于末尾有空格的都输出为0了。
3 //“hello world     ”依然输出5.
4 #include<iostream>
5 #include<string>
6 using namespace std;
7 int main()
8 {
9     string s;
10     while(getline(cin,s)){
11         int n=0,flag=1;
12         for(int i=s.length()-1;i>=0;--i){//倒着计算
13             if(flag && s==' '){//如果末尾有空格，先清除末尾空格
14                 continue;
15             }
16             else if(s!=' '){
17                 flag = 0;
18                 ++n;
19             }
20             else{
21                 break;
22             }
23         }
24         cout << n << endl;
25     }
26     return 0;
27 }
View Code　　3、计算字符个数
　　题目：http://www.nowcoder.com/practice/a35ce98431874e3a820dbe4b2d0508b1?tpId=37&tqId=21225&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　思路：
　　　　分别读入需要读入的数据，然后遍历比较，不区别大小写可以通过ASCIIS的值进行转换比较。
　　问题：
　　初次调试，出现只能获取循环内的输入（cin），只有一次输入，最后在末尾加上cin.ignore()  就解决了
　　知识点：
　　　　cin.ignore() 的作用
　　方法一：





1 #include<iostream>
2 #include<string>
3 #include<cmath>
4 using namespace std;
5  
6 int main(){
7     string str;
8     while (getline(cin,str)){
9         int count = 0;
10         char c;
11         cin >> c;
12         for (int i = 0; i < str.size();i++){
13             if (c == str || abs(str - c) == 'a' - 'A') count++;
14         }
15         cout << count << endl;
16         cin.ignore();
17     }  
18     return 0;
19 }
View Code　　4、字符串分隔
　　方法一：
　　题目：http://www.nowcoder.com/practice/d9162298cb5a437aad722fccccaae8a7?tpId=37&tqId=21227&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　思路：
　　初见题目，是想分开处理两个字符串，应为觉得两个字符串的处理方式一样，定义一个方法，应该很简单，可是后来出问题了，会发现，在控制换行的时候回很头疼。
　　回过头来，想了一个新的办法：
　　将两个字符串分别处理，时期长度达到8的倍数，用零补充。然后将两个字符串拼接，这样在控制输出就简单多了。
　　知识点：
　　字符串的操作，string 可以进行 + 操作 进行拼接





1 #include<iostream>
2 #include<string>
3 #include<cmath>
4  
5 using namespace std;
6
7 int main(){
8     
9     string str1,str2;
10     cin >> str1 >> str2;
11     string z = "0";
12     if (str1.size()%8){
13         for (int i = str1.size()%8; i < 8; i++){
14             str1 += z;
15         }
16     }
17     string str = str1 + str2;
18     int len = str.size();
19     int n = len/8;
20     if (n*8 != len){
21         for (int i = str.size()%8; i < 8; i++) str += z;
22     }
23     for (int i = 0; i < str.size(); i++){
24         if (i != 0 && i % 8 == 0) cout << endl;
25         cout << str;
26     }
27     return 0;
28 }
View Code　　方法二：
　　思路：
　　通过函数substr（起始位置，结束位置）进行截取，然后进行迭代，不够长度的通过 append（个数，填充字符） 补够8位。
　　知识点：
　　substr（起始位置，结束位置）
　　append（个数，填充字符）





1 #include <iostream>
2 #include <string>
3 using namespace std;
4 void fuck(string str) {
5     if (str == "")
6         return;
7     if (str.size() <= 8) {
8         str.append(8 - str.size(), '0');
9         cout << str << endl;
10         return;
11     }
12     cout << str.substr(0, 8) << endl;
13     fuck(str.substr(8, str.size()));
14 }
15 int main() {
16     string str1, str2;
17     cin >> str1 >> str2;
18     fuck(str1);
19     fuck(str2);
20     return 0;
21 }
View Code　　方法三：
　　思路：
　　鸡贼的思路，666
　　给每个字符串都强行添加八个 0 ，然后分别控制输出子串，substr（起始位置，结束位置）
　　知识点：
　　字符串的输出 cout << s.substr(0,8)





1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 void diu(string s){
6     if (s.size()%8 != 0) s += "00000000";
7     while (s.size() >= 8){
8         cout << s.substr(0,8) << endl;
9         s = s.substr(8);
10     }
11 }
12
13 int main() {
14     string str1, str2;
15     cin >> str1 >> str2;
16     diu(str1);
17     diu(str2);
18
19     return 0;
20 }
View Code　　5、进制转换
　　方法一：
　　思路：
　　常规的思路，自己实现的转换过程。
　　从低位处理，每一位换算成十进制，然后在乘以当前所在的位即可。





1 #include<iostream>
2 #include<string>
3 using namespace std;
4 int main(){
5     string s;
6     while(cin>>s){
7         int length = s.size();
8         if(length  <= 2)
9             continue;
10         if(s[0]!='0' || s[1]!='x')
11             continue;
12         
13         int res =0;
14         int flag =1;
15         for(int i=length-1;i>1;--i){
16             char cur = s;
17             if(cur>='A'&&cur<='F'){
18                 res+=(cur-'A'+10)*flag;
19             }
20             else if(cur>='0' && cur<='9'){
21                 res+=(cur-'0')*flag;
22             }
23             else
24                 continue;
25             flag*=16;
26         }   
27         cout<<res<<endl;   
28     }
29     return 0;
30 }
View Code　　方法二：
　　思路：
　　是通过库函数实现的





1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 int main()
5 {
6     char str[100];
7     int i=0,count,sum;
8     while(gets(str))//用于多次输入
9     {
10         count=strlen(str);//计算字符串的长度
11         sum=0;
12         for(i=count-1;i>=0;i--)//从十六进制个位开始，每位都转换成十进制
13         {
14         if(str>='0'&&str<='9')//数字字符的转换
15         {
16             sum+=(str-48)*pow(16,count-i-1);
17         }
18         else if(str>='A'&&str<='F')//字母字符的转换
19         {
20             sum+=(str-55)*pow(16,count-i-1);
21         }
22         }
23         printf("%d\n",sum);
24     }
25     return 0;
26  }
View Code　　再来一发





1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6     int a;
7     while(cin>>hex>>a){
8     cout<<a<<endl;
9     }
10 }
View Code　　问题拓展：
　　十进制转换2进制
　　递归方式、压数组





1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 void BinaryRecursion(int n) {
6     int a;
7     a = n % 2;
8     n = n >> 1;
9     if (n == 0) ;
10     else
11         BinaryRecursion(n);
12     cout<<a;
13 }  
14
15 void BinaryVector(int n){
16     int a;
17     vector<int> nums;
18     vector<int>::iterator it;
19     while(n){
20         a = n % 2;
21         n = n >> 1;
22         nums.push_back(a);
23     }
24     for (it = nums.end() - 1; it >= nums.begin(); it--){
25         cout << *it;
26     }
27 }
28
29 int main(){
30     int b;
31     cin >> b;
32     BinaryRecursion(b);
33     cout << endl;
34     BinaryVector(b);
35 }
View Code　　6、质数因子
　　题目：http://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607?tpId=37&tqId=21229&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　方法一：
　　思路：
　　每次从2开始，递增寻找能整除的数。找到后输出，重复上述步骤，直到找到可以整除的数等于要找的数。
　　这里会想，没次找的数就一定是质数么？因为没次都是从2开始，所以可以保证找到的数就是质数。
　　知识点：
　　整除  取余  质数
　　补充：
　　本方法是不是迭代的思想？
　　质数的新求法？





1 #include <iostream>
2 #include <cmath>
3
4 using namespace std;
5
6 int main(){
7     long n;
8     while(cin >> n){
9         bool f = true;
10         if (n == 1){
11             cout << n << " ";
12             continue;
13         }
14         if (n < 0) continue;
15         while (f){
16             for (long i = 2; i <= n; i++){
17                 if (i == n) f = false;
18                 if (n%i == 0){
19                     cout << i << " ";
20                     n = n / i;
21                     break;
22                 }
23             }
24         }
25         
26     }
27     return 0;
28 }
View Code　　7、取近视值
　　题目：http://www.nowcoder.com/practice/3ab09737afb645cc82c35d56a5ce802a?tpId=37&tqId=21230&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　方法一：
　　思路：
　　扩大十倍，对10取模 判断这个小数点的大小进行输出
　　知识点：
　　强制类型转换





1 #include <iostream>
2 #include <cmath>
3
4 using namespace std;
5
6 int main(){
7     float n;
8     while(cin >> n){
9         int a = (int) n;
10         int b = (int)(n*10) % 10;
11         if (b < 5) cout << a;
12         else cout << a + 1;
13     }
14     return 0;
15 }
View Code　　方法二：
　　思路：
　　好巧妙的思路





1 #include <iostream>
2 using namespace std;
3 int main()
4 {
5 float a;
6 cin>>a;
7 cout<<int(a+0.5);
8 return 0;
9 }
View Code　　8、合并表记录
　　题目：http://www.nowcoder.com/practice/de044e89123f4a7482bd2b214a685201?tpId=37&tqId=21231&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　方法一：
　　思路：
　　键值对的合并， 把数组的下标作为键值，然后对其进行操作。
　　缺点，不知道输入键值大小，存在数组越界的情况
　　知识点：
　　迭代器 it 可以实现加减法，下标的表示可以通过 it - nums.begin() 实现





1 #include <iostream>
2
3 using namespace std;
4
5 int main(){
6     int n;
7     vector<int> nums(1000,0);
8     while(cin >> n){
9         for (int i =0; i < n; i++){
10             int a,b;
11             cin >> a >> b;
12             nums[a] += b;
13         }
14         for (int i = 0; i < 1000; i++){
15             if (nums != 0) cout << i << " " << nums << endl;
16         }
17     }
18     return 0;
19 }
View Code　　方法二：
　　思路：
　　利用STL中的map函数实现的，这个想法方法一要理想。
　　知识点：
　　STL中的map函数





1 #include<iostream>
2 #include<map>
3 using namespace std;
4  
5 int main()
6 {
7     int n;
8     while(cin >> n){
9         map<int,int> m;
10         while(n--){
11             int key,value;
12             cin >> key >> value;
13             m[key] += value;
14         }
15         //map内部本身就是按照key的大小顺序进行存储的
16         for(map<int,int>::iterator it=m.begin();it!=m.end();++it){
17             cout << it->first << " "<< it->second << endl;
18         }
19     }
20     return 0;
21 }
View Code　　9、提取不重复的整数
　　题目：
　　http://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?tpId=37&tqId=21232&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking
　　方法一：
　　思路：
　　把输入的整数读成字符串，然后把字符串倒着进行处理。处理的时候，借用到一个长度为10的数组用来去重。（哈希去重）
　　知识点：
　　本题用到的数组初始化有点小题大做，简单的数组初始化 int a[10]={0};
　　注意：
　　数组以及字符串的下标，都是冲0开始的，倒着读的时候，是从 nums.size() - 1 开始。





1 #include<iostream>
2 #include <string>
3 #include <vector>
4  
5 using namespace std;
6  
7 int main()
8 {
9     string n;
10     while(cin >> n){
11         vector<int> nums(10,0);
12         for (int i = n.size() - 1; i >= 0; i--){
13            
14             if (nums[(int) n - 48] == 0) cout << n;
15             nums[(int) n - 48] = 1;
16         }
17     }
18     return 0;
19 }
View Code　　方法二：
　　思路：
　　整个过程都是按照数字进行处理的（我第一感觉也是，本人不是很熟练这一波操作，就换了想法），出的过程简洁明了。
　　知识点：
　　%  /





1 #include<iostream>
2 using namespace std;
3 int main()
4 {
5     int n;
6     int a[10]={0};
7     int num=0;
8     cin>>n ;
9     while(n)
10     {
11         if(a[n%10]==0)
12         {
13             a[n%10]++;//这一步是更新，遇到下次相同的数会跳过
14             num=num*10+n%10;
15         }
16         n/=10;
17     }
18     cout<<num<<endl;
19     return 0;
20 }
View Code　　10、字符个数统计
　　题目：





http://www.nowcoder.com/practice/eb94f6a5b2ba49c6ac72d40b5ce95f50?tpId=37&tqId=21233&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking

题目描述
编写一个函数，计算字符串中含有的不同字符的个数。字符在ACSII码范围内(0~127)。不在范围内的不作统计。
输入描述:
输入N个字符，字符在ACSII码范围内。

输出描述:
输出范围在(0~127)字符的个数。
输入例子:
abc
输出例子:
3
View Code　　方法一：
　　思路：
　　按行读入字符串，然后对每个字符串进行ascii码验证，并且检查是否已经统计过次字符。





1 #include<iostream>
2 #include <string>
3 #include <vector>
4  
5 using namespace std;
6  
7 int main()
8 {
9     string n;
10     while(getline(cin,n)){
11         int nums[127] = {0};
12         int count = 0;
13         for (int i = 0; i < n.size(); i++){
14             int a = (int) n;
15             if (a > 0 && a < 127 && nums[a] == 0 ){
16                 count++;
17                 nums[a] += 1;
18             }
19         }
20         cout << count << endl;
21     }
22     return 0;
23 }
View Code　　方法二：
　　思路：
　　这个方法是倒着验证的，就是在字符串中找在0-127范围内的字符。厉害呐！！！！
　　知识点：
　　利用字符串的方法 find（a），可以是char 也可以是整数（整数会自动转换成对应的  ACSII）





1 #include <iostream>
2 #include <string>
3 using namespace std;
4  
5 int main()
6     {
7     string b;
8     getline(cin,b);
9     int count=0;
10     for(int i=0;i<=127;i++)
11         if(b.find(i)!=string::npos)
12         count++;
13     cout<<count;
14 }
View Code　　11、字符串翻转 （12、字符串反转 类似题）
　　题目：





http://www.nowcoder.com/practice/e45e078701ab4e4cb49393ae30f1bb04?tpId=37&tqId=21235&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking

题目描述
描述：
输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001

输入描述:
输入一个int整数

输出描述:
将这个整数以字符串的形式逆序输出
输入例子:
1516000
输出例子:
0006151
View Code　　方法一：
　　思路：
　　把输入的数字当字符串的处理





1 #include <iostream>
2 #include <string>
3 using namespace std;
4  
5 int main(){
6     string b;
7     while (getline(cin,b)){
8         for (int i = b.size() - 1; i >= 0; i--){
9             cout << b;
10         }
11     }
12 }
View Code　　13、句子逆序
　　题目：





http://www.nowcoder.com/practice/48b3cb4e3c694d9da5526e6255bb73c3?tpId=37&tqId=21236&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述
将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”
所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
入描述:
将一个英文语句以单词为单位逆序排放。

输出描述:
得到逆序的句子
输入例子:
I am a boy
输出例子:
boy a am I
View Code　　方法一：
　　思路：
　　找（find（“ ”）） 空格 的为止，来截取字符串（substr（开始为止，结束位置）），然后把找到的单词放到数组中。（或者压入栈中）





1 #include <iostream>
2 #include <string>
3 #include <vector>
4 using namespace std;
5  
6 int main(){
7     
8     string s;
9     while (getline(cin,s)){
10         vector<string> nums;
11         while (s.find(" ") != string::npos){
12             string tmp = s.substr(0,s.find(" "));
13             nums.push_back(tmp);
14             s = s.substr(s.find(" ")+1,s.size());
15         }
16         nums.push_back(s);
17         
18         for (int i = nums.size() - 1; i >= 0; i--){
19             cout << nums;
20             if (i != 0) cout << " ";
21         }
22     }
23 }
View Code　　入栈





1 #include <iostream>
2 #include <string>
3 #include <stack>
4 using namespace std;
5  
6 int main(){
7     
8     string s;
9     while (getline(cin,s)){
10         stack<string> nums;
11         while(s.find(" ") != string::npos){
12             string tmp = s.substr(0,s.find(" "));
13             nums.push(tmp);
14             s = s.substr(s.find(" ") + 1,s.size());//语句末尾不能有空格
15         }
16         nums.push(s);
17         while(!nums.empty()){
18             cout << nums.top();
19             nums.pop();
20             if(!nums.empty()) cout << " ";
21         }
22         cout << endl;
23     }
24 }
View Code　　方法二：
　　思路：
　　和上边的思路一样的。
　　这是牛客网上的别人提交的代码，个人感觉，这个只能做一个测试用例 BUT 他通过了 ，这样的现象在牛客网上挺多见的。。。。一度怀疑，牛客网有的试题的用例只有一个
　　问题：
　　他这个while怎么跳出的，本地调试是通不过的，为什么牛客网上是可以通过的，求教========求告知===========求指正 ^-^





1 #include<iostream>
2 #include<stack>
3 #include<string>
4 using namespace std;
5 int main()
6 {
7     stack<string> ss;
8     string s;
9     while(cin>>s)
10     {
11         ss.push(s);
12     }
13     while(!ss.empty())
14     {
15         cout<<ss.top();
16         ss.pop();
17         if(!ss.empty())
18             cout<<' ';
19     }
20     cout<<endl;
21 }
View Code　　14、字串的连接最长路径查找
　　题目：





题目描述
给定n个字符串，请对n个字符串按照字典序排列。
输入描述:
输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。

输出描述:
数据输出n行，输出结果为按照字典序排列的字符串。
输入例子:
9
cap
to
cat
card
two
too
up
boat
boot
输出例子:
boat
boot
cap
card
cat
to
too
two
up
View Code　　方法一：
　　思路：
　　读入到数组中，然后排序即可。这里排序是用到算法头文件中的sort（）函数，也可以通过字符串比较大小来进行排序。
　　知识点：
　　sort（nums.begin(),nums.end()）
　　sort函数的实现也是通过字符串大小比较实现排序的





1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 int main(){
9     int n;
10     while(cin >> n){
11         vector<string> nums;
12         vector<string>::iterator it;
13         while(n--){
14             string s;
15             cin >> s;
16             nums.push_back(s);
17         }
18         sort(nums.begin(),nums.end());
19         for (it = nums.begin(); it != nums.end(); it++){
20             cout << *it << endl;
21         }
22         
23     }
24     
25     return 0;
26 }
View Code




1 #include<iostream>
2 #include<string>
3 using namespace std;
4 int main()
5 {
6     int String_Number,i,j;
7     string Input_String[1000],Temp;
8     cin>>String_Number;
9     for(i=0;i<String_Number;i++)
10         cin>>Input_String;
11     for(i=0;i<String_Number-1;i++)
12     {
13         for(j=0;j<String_Number-1-i;j++)
14         {
15             if(Input_String[j]>Input_String[j+1])
16             {
17                 Temp=Input_String[j];
18                 Input_String[j]=Input_String[j+1];
19                 Input_String[j+1]=Temp;
20             }
21         }
22     }
23     for(i=0;i<String_Number;i++)
24         cout<<Input_String<<endl;
25     return 0;
26 }
View Code　　15、求int型正整数在内存中存储时1的个数
　　题目：





http://www.nowcoder.com/practice/440f16e490a0404786865e99c6ad91c9?tpId=37&tqId=21238&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking

题目描述
输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。
输入描述:
输入一个整数（int类型）

输出描述:
这个数转换成2进制后，输出1的个数
输入例子:
5
输出例子:
2
View Code　　方法一：
　　思路：
　　通过右移实现的
　　知识点：
　　移位 >>  移位满了以后质的变化





1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <algorithm>
5
6 using namespace std;
7
8 int main(){
9     int n;
10     while(cin >> n){
11         int count = 0;
12         while(n > 0){
13            
14             if(n & 1) count++;
15             n = n >> 1;
16         }
17         cout << count << endl;
18     }
19     
20     return 0;
21 }
View Code　　方法二：
　　思路：
　　a&=a-1;//判断二进制有多少个1
　　硬生生的不懂原理  不好意思 智商捉急





1 #include<iostream>
2 using namespace std;
3 int main()
4 {
5     int a;
6     while(cin>>a){
7         int count=0;
8         while(a){
9             a&=a-1;//判断二进制有多少个1
10             count++;
11         }
12         cout<<count<<endl;
13     }
14     return 0;
15 }
View Code　　16、购物单（背包问题）
　　题目：





http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4?tpId=37&tqId=21239&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking

题目描述
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件    附件
电脑    打印机，扫描仪
书柜    图书
书桌    台灯，文具
工作椅    无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
请你帮助王强设计一个满足要求的购物单。

输入描述:
输入的第 1 行，为两个正整数，用一个空格隔开：N m
（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）


输出描述:
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
输入例子:
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
输出例子:
2200
View Code　　方法二：
　　思路：
　　背包问题，详见：http://blog.csdn.net/liang5630/article/details/8030108





1 #include <iostream>
2 #include <string>
3 using namespace std;
4  
5 int getMax(int x, int y){
6     return (x > y ? x : y);
7 }
8  
9 int main(){
10     int N;  //总钱数
11     int m;  //希望购买的物品个数
12     int weight[60][3]={0};  //价格（成本）
13     int value[60][3]={0};   //价值（重要度*价格）
14     int f[60][3200];        //第i个物品在j容量下可以获得的最大价值
15     int i,j;
16  
17     cin >> N >> m;
18     N/=10;  //都是10的整数，先除以10，减少循环次数
19     //存储清单
20     for(int i=1;i<=m;i++){
21         int v;  //该物品价格
22         int p;  //该物品价值
23         int q;  //该物品主件还是附件
24         cin >> v >> p >> q;
25         v/=10;
26  
27         if(q==0){               //主件
28             weight[0]=v;
29             value[0]=p*v;
30         }
31         else{                   //附件
32             if(weight[1]==0){    //第一个附件
33                 weight[1]=v;
34                 value[1]=p*v;   
35             }
36             else{                   //第二个附件
37                 weight[2]=v;
38                 value[2]=p*v;
39             }
40         }
41     }
42     //遍历计算
43     for(i=1;i<=m;i++)
44         for(j=N;j>0;j--){
45             if(j>=weight[0])      //可以容下第i个主件时,比较放第i个或者不放第i个物品的价值
46                 f[j]=getMax(f[i-1][j],f[i-1][j-weight[0]]+value[0]);
47             if(j>=weight[0]+weight[1]) //可以容下第i个主件和此主件的第1个附件时
48                 f[j]=getMax(f[i-1][j],f[i-1][j-weight[0]-weight[1]]+value[0]+value[1]);
49             if(j>=weight[0]+weight[2]) //可以容下第i个主件和此主件的第2个附件时
50                 f[j]=getMax(f[i-1][j],f[i-1][j-weight[0]-weight[2]]+value[0]+value[2]);
51             if(j>=weight[0]+weight[1]+weight[2])        //可以容下第i个主件和此主件的第1个附件和第2个附件时
52                 f[j]=getMax(f[i-1][j],f[i-1][j-weight[0]-weight[1]-weight[2]]+value[0]+value[1]+value[2]);
53         }
54     cout << f[m][N]*10 << endl;
55 }
View Code　　14、坐标移动
　　题目：





http://www.nowcoder.com/practice/119bcca3befb405fbe58abe9c532eb29?tpId=37&tqId=21240&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述
开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。
输入：
合法坐标为A(或者D或者W或者S) + 数字（两位以内）
坐标之间以;分隔。
非法坐标点需要进行丢弃。如AA10;  A1A;  $%$;  YAD; 等。
下面是一个简单的例子 如：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
处理过程：
起点（0,0）
+   A10   =  （-10,0）
+   S20   =  (-10,-20)
+   W10  =  (-10,-10)
+   D30  =  (20,-10)
+   x    =  无效
+   A1A   =  无效
+   B10A11   =  无效
+  一个空 不影响
+   A10  =  (10,-10)

结果 （10， -10）

输入描述:
一行字符串

输出描述:
最终坐标，以,分隔
输入例子:
A10;S20;W10;D30;X;A1A;B10A11;;A10;
输出例子:
10,-10
View Code　　方法一：
　　思路：
　　通过find()函数定位“；”的位置，然后求子串，对子串做进一步的处理。
　　知识点：
　　字符串某个字符定位find（），求子串s.substr(起始位置，结束位置)





1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 int stringToNum(string n,int len){
7     int num;
8     for(int i = 1; i < len; i++){
9         int a = n-'0';
10         if( a > 9 || a < 0) return 0;
11     }
12     if (len == 3) num = (n[1] - '0') * 10 + (n[2] - '0');
13     if (len == 2) num = (n[1] - '0');
14     return num;
15 }
16
17 void move(string s, int &x, int &y){
18     int len = s.size();
19     if(len < 4 && len > 1){
20         if(s[0] == 'A'){
21             x -= stringToNum(s,len);
22         }
23         if(s[0] == 'D'){
24             x += stringToNum(s,len);
25         }
26         if(s[0] == 'W'){
27             y += stringToNum(s,len);
28         }
29         if(s[0] == 'S'){
30             y -= stringToNum(s,len);
31         }
32     }
33     
34 }
35 void move2(string s, int &x, int &y){
36     int len = s.size();
37     if(len < 4 && len > 1){
38         switch(s[0]){
39             case 'A':{x -= stringToNum(s,len); break;}
40             case 'D':{x += stringToNum(s,len); break;}
41             case 'W':{y += stringToNum(s,len); break;}
42             case 'S':{y -= stringToNum(s,len); break;}
43         }
44     }
45 }
46 int main(){
47     string s;
48     while(getline(cin,s)){
49         
50         int x=0,y=0;
51         while(s.find(";") != string::npos){
52             string temp = s.substr(0,s.find(";"));
53             //判断移动
54            
55             s = s.substr(s.find(";")+1,s.size());   
56             //move(temp,x,y);
57             move2(temp,x,y);
58         }
59         cout << x << "," << y << endl;
60     }
61     
62     return 0;
63 }
View Code　　15、别有效的IP地址和掩码并进行分类统计 （不懂）
　　题目：





http://www.nowcoder.com/practice/de538edd6f7e4bc3a5689723a7435682?tpId=37&tqId=21241&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述
请解析IP地址和对应的掩码，进行分类识别。要求按照A/B/C/D/E类地址归类，不合法的地址和掩码单独归类。
所有的IP地址划分为 A,B,C,D,E五类
A类地址1.0.0.0~126.255.255.255;
B类地址128.0.0.0~191.255.255.255;
C类地址192.0.0.0~223.255.255.255;
D类地址224.0.0.0~239.255.255.255；
E类地址240.0.0.0~255.255.255.255

私网IP范围是：
10.0.0.0～10.255.255.255
172.16.0.0～172.31.255.255
192.168.0.0～192.168.255.255

子网掩码为前面是连续的1，然后全是0。（例如：255.255.255.32就是一个非法的掩码）
本题暂时默认以0开头的IP地址是合法的，比如0.1.1.2，是合法地址

输入描述:
多行字符串。每行一个IP地址和掩码，用~隔开。

输出描述:
统计A、B、C、D、E、错误IP地址或错误掩码、私有IP的个数，之间以空格隔开。
输入例子:
10.70.44.68~255.254.255.0
1.0.0.1~255.0.0.0
192.168.0.2~255.255.255.0
19..0.~255.255.255.0
输出例子:
1 0 1 0 0 2 1
View Code　　方法一：
　　思路：
　　暂无    划分的好细





1 #include <iostream>
2 #include <string>
3 #include <vector>
4 using namespace std;
5 int p[7]={0};
6 void is(string s){
7     int a=0,b=0,flag;
8     vector<int> vec(4);
9     for(int i=0;i<s.length();i++){
10         a=0;
11         flag=0;
12         for(;i<s.length()&&s!='.';i++){
13             flag=1;
14             if(s>='0'&&s<='9')
15                 a=a*10+s-'0';
16             else{
17                 p[5]++;
18                 return;
19             }
20         }
21         if(flag&&a<256)
22             vec=a;
23         else{
24             p[5]++;
25             return;
26         }
27         b++;
28     }
29     if(vec[0]>0){
30         if(vec[0]<127){
31             p[0]++;
32             if(vec[0]==10)
33                 p[6]++;
34         }else if(vec[0]<192&&vec[0]>127){
35             p[1]++;
36             if(vec[0]==172&&vec[1]>=16&&vec[1]<=31)
37                 p[6]++;
38         }else if(vec[0]>191&&vec[0]<224){
39             p[2]++;
40             if(vec[0]==192&&vec[1]==168)
41                 p[6]++;
42         }else if(vec[0]>223&&vec[0]<240)
43             p[3]++;
44         else if(vec[0]>239)
45             p[4]++;
46     }
47 }
48 int isvalid(string s){
49     int a,b=0,flag,flag2=0;
50     vector<int> vec(4);
51     for(int i=0;i<s.length();i++){
52         a=0;flag=0;
53         for(;i<s.length()&&s!='.';i++){
54             flag=1;
55             if(s>='0'&&s<='9')
56                 a=a*10+s-'0';
57             else
58                 return 0;
59         }
60         if(flag&&(a==255||a==254||a==252||a==248||a==240||a==224||a==192||a==128||a==0))
61             vec=a;
62         else
63             return 0;
64         b++;
65     }
66     for(int i=0;i<4;i++){
67         if(flag2==0){
68             if(vec<255)
69                 flag2=1;
70         }else{
71             if(vec!=0)
72                 return 0;  
73         }
74     }
75     if(vec[3]==255)
76         return 0;
77     return 1;
78 }
79 int main(){
80     string s;
81     int i;
82     while(cin>>s){
83         string ss,sss;
84         for(i=0;i<s.length()&&s!='~';i++);
85         ss=s.substr(0,i);
86         sss=s.substr(i+1,s.length()-i);
87         if(isvalid(sss))
88             is(ss);
89         else
90             p[5]++;      
91     }
92     cout<<p[0]<<" "<<p[1]<<" "<<p[2]<<" "<<p[3]<<" "<<p[4]<<" "<<p[5]<<" "<<p[6]<<endl;
93     return 0;
94 }
View Code　　16、简单错误记录
　　题目：





http://www.nowcoder.com/practice/2baa6aba39214d6ea91a2e03dff3fbeb?tpId=37&tqId=21242&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述
开发一个简单错误记录功能小模块，能够记录出错的代码所在的文件名称和行号。
处理：
1、 记录最多8条错误记录，循环记录，对相同的错误记录（净文件名称和行号完全匹配）只记录一条，错误计数增加；
2、 超过16个字符的文件名称，只记录文件的最后有效16个字符；
3、 输入的文件可能带路径，记录文件名称不能带路径。

输入描述:
一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。

输出描述:
将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开，如：
输入例子:
E:\V1R2\product\fpgadrive.c   1325
输出例子:
fpgadrive.c 1325 1
View Code　　方法一：
　　17、砝码
　　题目：





http://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c?tpId=37&tqId=21264&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述
现有一组砝码，重量互不相等，分别为m1,m2,m3…mn；
每种砝码对应的数量为x1,x2,x3...xn。现在要用这些砝码去称物体的重量，问能称出多少中不同的重量。
注：
称重重量包括0
方法原型：public static int fama(int n, int[] weight, int[] nums)

输入描述:
输入包含多组测试数据。
对于每组测试数据：
第一行：n --- 砝码数(范围[1,10])
第二行：m1 m2 m3 ... mn --- 每个砝码的重量(范围[1,2000])
第三行：x1 x2 x3 .... xn --- 每个砝码的数量(范围[1,6])

输出描述:
利用给定的砝码可以称出的不同的重量数
输入例子:
2
1 2
2 1
输出例子:
5
View Code　　方法一：
　　思路：





1 #include<iostream>
2 #include<vector>
3 #include<set>
4 #include<algorithm>
5 using namespace std;
6 int main()
7 {
8      int n;//砝码数
9      int m[10]={0};//每个砝码的质量
10      int x[10]={0};//每个砝码的数量
11      while(cin>>n){
12         for(int i=0;i<n;i++)
13             cin>>m;
14         for(int i=0;i<n;i++)
15             cin>>x;
16         vector<int>weights; //存所有已经称出的砝码的质量。
17         /*先将第一个砝码称出的质量入队。*/
18         weights.push_back(0);//初始化weights数组
19         for(int i=1;i<=x[0];i++)
20             weights.push_back(i*m[0]);//将第一个砝码能称出的质量入队
21         for(int i=1;i<n;i++){//前多少个砝码
22             //weights.push_back(m);
23             int len=weights.size();//记录已经称出砝码质量便于下面for循环
24             for(int j=1;j<=x;j++){//遍历该质量的砝码数
25                 for(int k=0;k<len;k++){
26                     int w=weights[k]+j*m;//将该质量的砝码数依次与前面所有的砝码数相加
27                         //去重操作
28                     if(find(weights.begin(),weights.end(),w)==weights.end())//如果之前没有这个质量的砝码就将其入队
29                         weights.push_back(weights[k]+j*m);
30                 }
31             }
32         }
33         cout<<weights.size()<<endl;
34      }
35 }
View Code




1 #include<iostream>
2 #include<vector>
3 #include<set>
4 #include<algorithm>
5 using namespace std;
6 int main()
7 {
8     /*从砝码1开始分析，假设前i个砝码能称出的不同重量为Q,那么Q一定是这样计算出来的：在Q[i-1]的基础上，对Q[i-1]个不同的重量，分别添加k个砝码i，再添加的过程中除去重复情况。
9 //假设：w[N]表示N个不同重量的砝码（例子中N=6），w[0~N-1]。
10 //      c[N]表示N个不同砝码相应的数量，c[1~N]。
11 //则：Q = (Q[i-1] + k*w)-添加过程中重复的个数。其中0=<k<=c。网上博客搜的解题思路*/
12  
13     int n ;//砝码数
14     int m[10] = { 0 };//每个砝码的质量
15     int x[10] = { 0};//每个砝码的数量
16     while (cin >> n)
17     {
18         for (int i = 0; i < n; i++)
19         {
20             cin >> m;
21         }
22         for (int i = 0; i < n; i++)
23         {
24             cin >> x;
25         }
26  
27         vector<int>weigths;//存所有已经称出的砝码的质量。
28         /*先将第一个砝码称出的质量入队。*/
29         weigths.push_back(0);//初始化weigths数组
30         for (int i = 1; i <= x[0]; i++)
31         {
32             weigths.push_back(i*m[0]);//将第一个砝码能称出的所有质量入队。
33         }
34         for (int i = 1; i < n; i++)//前多少个砝码
35         {
36             //weigths.push_back(m);
37             int len = weigths.size();//记录已经称出的砝码质量便于下面for循环使用
38             for (int j = 1; j <= x; j++)//遍历该质量的砝码数
39             {
40                  
41                 for (int z = 0; z < len; z++)
42                 {
43                     int wei = weigths[z] + j*m;//将该质量的砝码数依次与前面所有的砝码数相加
44                     if (find(weigths.begin(), weigths.end(), wei) == weigths.end())//如果之前没有这个质量的砝码就将其入队
45                         weigths.push_back(weigths[z] + j*m);
46                 }
47             }
48  
49         }
50         //set<int>wi(weigths.cbegin(), weigths.cend());//这一步是为了将weigths中的数字进一步去重保证正确性。
51         cout << weigths.size() << endl;
52         //cout << wi.size() << endl;
53     }
54     //system("pause");
55     return 0;
56 }
View Code　　18、学英语
　　题目：





http://www.nowcoder.com/practice/1364723563ab43c99f3d38b5abef83bc?tpId=37&tqId=21265&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题目描述
Jessi初学英语，为了快速读出一串数字，编写程序将数字转换成英文：
如22：twenty two，123：one hundred and twenty three。
说明：
数字为正整数，长度不超过九位，不考虑小数，转化结果为英文小写；
输出格式为twenty two；
非法数据请返回“error”；
关键字提示：and，billion，million，thousand，hundred。
方法原型：public static String parse(long num)


输入描述:
输入一个long型整数

输出描述:
输出相应的英文写法
输入例子:
2356
输出例子:
two thousand three hundred and fifty six
View Code　　方法一：





  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4  
  5 using namespace std;
  6  
  7 const vector<string> zeroToNine = {"zero", "one", "two", "three", "four",
  8                                    "five", "six", "seven", "eight", "nine"};
  9  
10 const vector<string> tenToNineteen = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen",
11                                       "sixteen", "seventeen", "eighteen", "nineteen"};
12  
13 const vector<string> tenToNinety = {"ten", "twenty", "thirty", "forty", "fifty",
14                                     "sixty", "seventy", "eighty", "ninety"};
15  
16 const vector<string> thousandToBillion = {"thousand", "million", "billion"};
17  
18 // 处理小于1000的部分
19 // isBegin用来表示当前的3位数是否位于数字的最高位部分
20 // 如果是则某些两位数或一位数之前不用加and
21 void processThousand(int N, vector<string> &result, bool isBegin)
22 {
23     vector<int> inners;
24     while (N >= 10)
25     {
26         inners.push_back(N % 10);
27         N /= 10;
28     }
29     inners.push_back(N);
30  
31     // 三位数
32     if (inners.size() == 3)
33     {
34         result.push_back(zeroToNine[inners[2]]);
35         result.push_back("hundred");
36  
37         if (inners[1] == 0)
38         {
39             if (inners[0] > 0)
40             {
41                 result.push_back("and");
42                 result.push_back(zeroToNine[inners[0]]);
43             }
44         }
45         else if (inners[1] == 1)
46         {
47             result.push_back("and");
48             result.push_back(tenToNineteen[inners[0]]);
49         }
50         else
51         {
52             result.push_back("and");
53             result.push_back(tenToNinety[inners[1] - 1]);
54             if (inners[0] > 0)
55             {
56                 result.push_back(zeroToNine[inners[0]]);
57             }
58         }
59     }
60     // 两位数
61     else if (inners.size() == 2)
62     {
63         if (inners[1] == 1)
64         {
65             /*
66             if (! isBegin)
67             {
68                 result.push_back("and");
69             }
70              */
71             result.push_back(tenToNineteen[inners[0]]);
72         }
73         else
74         {
75             /*
76             if (! isBegin)
77             {
78                 result.push_back("and");
79             }*/
80             result.push_back(tenToNinety[inners[1] - 1]);
81             if (inners[0] > 0)
82             {
83                 result.push_back(zeroToNine[inners[0]]);
84             }
85         }
86     }
87     // 一位数
88     else
89     {
90         if (! isBegin)
91         {
92             if (inners[0] > 0)
93             {
94                 // result.push_back("and");
95                 result.push_back(zeroToNine[inners[0]]);
96             }
97         }
98         else
99         {
100             result.push_back(zeroToNine[inners[0]]);
101         }
102     }
103 }
104  
105 int main()
106 {
107  
108     int N;
109  
110     while (cin >> N)
111     {
112         int thousandPart = 0;
113         vector<int> thousands;
114  
115         vector<string> result;
116  
117         while (N >= 1000)
118         {
119             thousands.push_back(N % 1000);
120             N /= 1000;
121             ++thousandPart;
122         }
123  
124         thousands.push_back(N);
125  
126         if (thousandPart == 0)
127         {
128             // 1000以下
129             processThousand(N, result, true);
130         }
131         else
132         {
133             // 按1000分 最高位的部分
134             processThousand(thousands[thousandPart], result, true);
135             result.push_back(thousandToBillion[thousandPart - 1]);
136  
137             // 中间部分
138             for (int i = thousandPart - 1; i >= 1; --i)
139             {
140                 processThousand(thousands, result, false);
141                 if (thousands > 0)
142                 {
143                     result.push_back(thousandToBillion[i - 1]);
144                 }
145             }
146  
147             // 最后小于1000的部分
148             processThousand(thousands[0], result, false);
149         }
150  
151         for (int i = 0; i < result.size() - 1; ++i)
152         {
153             cout << result << " ";
154         }
155         cout << result[result.size() - 1] << endl;
156     }
157  
158     return 0;
159 }
View Code　　19、迷宫
　　题目：





http://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&rp=&ru=/ta/huawei&qru=/ta/huawei/question-ranking

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
Input
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)


输入描述:
输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述:
左上角到右下角的最短路径，格式如样例所示。
输入例子:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出例子:
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
View Code　　方法二：





#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main(){
int N, M;
while(cin >> N >> M){
int **a =new int*[N];
for(int i =0; i<N; i++){
a =new int[M];
}
for(int i =0; i<N; i++){
for(int j =0; j<M; j++){
cin >> a[j];
}
}
int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };//点的四个方向：下，右，上，左
int visit[11][11] = {0}; //判定该点是否走过
bool flag =0; //是否走完
stack<pair<int,int>> stk;
stk.push(make_pair(0,0));
stk.push(make_pair(0,0));
visit[0][0] =1;
while(!flag){   //深度优先搜索思想，往该点四个方向探查，若有则从这点继续探寻，若没有则回溯到上一个点
pair<int,int> p = stk.top();   //回退路径的点
            stk.pop();
int i = p.first, j= p.second;
for(int k =0; k <4;k++){  //对四个方向进行探查
int dx = i + dir[k][0];
int dy = j + dir[k][1];
if(dx == N-1&&dy == M-1){ //到达终点
stk.push(make_pair(N-1, M-1));
flag =true;
break;
}
if(dx>=0&& dx<=N-1&& dy>=0&& dy<=M-1&& a[dx][dy] ==0&& visit[dx][dy] ==0){  //未被访问过且有路径
                    stk.push(make_pair(dx, dy));
visit[dx][dy] =1;
i = dx;     //从该点继续探查
j = dy;
k=-1;
}
}
}
stack<pair<int,int>> outputStk;  //把栈的先后顺序换一下输出
while(!stk.empty()){
outputStk.push(stk.top());
stk.pop();
}
while(!outputStk.empty()){
pair<int,int> p = outputStk.top();
outputStk.pop();
cout <<"("<<p.first<<","<<p.second<<")"<< endl;
}
}
return0;
}
View Code　　20、四则运算





1 //利用了递归求解，程序十分简短
2 #include <iostream>
3 #include <string>
4 #include <sstream>
5 #include <deque>
6 using namespace std;
7 void  addNum(deque<string>& Q,int num){
8     if(!Q.empty()){
9         int cur=0;
10         if(Q.back()=="*"||Q.back()=="/"){
11             string top=Q.back();
12             Q.pop_back();
13             stringstream ss(Q.back());
14             ss>>cur;
15             Q.pop_back();
16             num=top=="*"?(cur*num):(cur/num);
17         }
18     }
19     stringstream ss;
20     ss<<num;
21     Q.push_back(ss.str());
22 }
23 int getNum(deque<string>& Q){
24     int num=0,R=0;
25     string f("+");
26     while(!Q.empty()){     
27         stringstream ss(Q.front());
28         ss>>num;
29         Q.pop_front();
30         R=(f=="+")?(R+num):(R-num);
31         if(!Q.empty()){
32             f=Q.front();
33             Q.pop_front();
34         }
35     }
36     return R;
37 }
38 int* value(string& s,int i){
39     deque<string> Q;
40     int pre=0;
41     while(i<s.length()&&s!=')'&&s!=']'&&s!='}'){
42         if(s>='0'&&s<='9'){
43             pre=pre*10+s[i++]-'0';
44         }else if(s!='('&&s!='['&&s!='{'){
45             addNum(Q,pre);
46             string ss;
47         ss+=s[i++];
48             Q.push_back(ss);
49             pre=0;         
50         }else{
51             int* bra=NULL;
52             bra=value(s,i+1);
53             pre=bra[0];
54             i=bra[1]+1;
55         }      
56     }
57     addNum(Q,pre);
58     int *R=new int[2];
59     R[0]=getNum(Q);
60     R[1]=i;
61     return R;
62 }
63 int main(){
64     string s;
65     while(cin>>s){  
66         int *R=value(s,0);
67         cout<<R[0]<<endl;
68     }
69     return 0;
70 }
View Code




  1 #include <iostream>
  2 #include <stack>
  3 #include <string>
  4  
  5 using namespace std;
  6 string pucExpression = "0123456789+-*/()[]{}";
  7  
  8 int Priority(char a1, char a2)
  9 {
10     int index1 = pucExpression.find(a1);
11     int index2 = pucExpression.find(a2);
12     if (index1>=14 && index1<=19)
13     {
14         if (index1 == (index2-1))
15             return 3;
16         else if ((index2-index1)>=2)
17             return -1;
18         else if (index2 <= index1)
19             return 2;
20     }
21     else if (index1==12 || index1==13)
22     {
23         if (index2==14 || index2==16 || index2==18)
24             return 2;
25         else
26             return 1;
27     }
28     else if (index1==10 || index1==11)
29     {
30         if ((index2>=12&&index2<=14) || (index2==16) || (index2==18))
31             return 2;
32         else
33             return 1;
34     }
35     return -1;
36 }
37  
38 int calculate(string strExpression)
39 {
40     stack<int> data_stack;
41     stack<char> operation_stack;
42     for(int i=0; strExpression!='\0'; i++)
43     {
44         int value = 0;
45         char operation;
46         
47         char ch = strExpression;
48         int flag = 1;
49         if (ch=='-' && (strExpression[i-1]=='('||strExpression[i-1]=='['||strExpression[i-1]=='{'))
50         {
51             flag = 2;
52             i++;
53         }
54         if (pucExpression.find(ch)<=9 || flag==2)
55         {
56             int sum = 0;
57             int nextIsdata;
58             while (1)
59             {
60                 if (strExpression!='\0')
61                 {
62                     nextIsdata = pucExpression.find(strExpression);
63                     if (nextIsdata>=0 && nextIsdata<=9)
64                         sum = 10*sum + (strExpression - '0');
65                     else
66                     {
67                         i--;
68                         break;
69                     }
70                 }
71                 else
72                 {
73                     i--;
74                     break;
75                 }
76                 i++;
77             }
78             if (flag == 2)
79                 data_stack.push(-1*sum);
80             else
81                 data_stack.push(sum);
82             //value = 10*value + strExpression-'0';
83             //data_stack.push(value);
84         }
85         else
86         {
87             if (operation_stack.size() == 0)
88                 operation_stack.push(ch);
89             else
90             {
91                 operation = operation_stack.top();
92                 int a1,a2;
93                 switch(Priority(operation,ch))
94                 {
95                 case 1://operation>=ch
96                     a1 = data_stack.top();
97                     data_stack.pop();
98                     a2 = data_stack.top();
99                     data_stack.pop();
100                     switch(pucExpression.find(operation))
101                     {
102                     case 10: data_stack.push(a2+a1);
103                         break;
104                     case 11:data_stack.push(a2-a1);
105                         break;
106                     case 12: data_stack.push(a2*a1);
107                         break;
108                     case 13:data_stack.push(a2/a1);
109                         break;
110                     }
111                     operation_stack.pop();
112                     i--;
113                     break;
114                 case 2://operation<ch
115                     operation_stack.push(ch);
116                     break;
117                 case 3://() [] {}
118                     operation_stack.pop();
119                     break;
120                 }
121             }
122         }
123     }
124     while(operation_stack.size() !=0)
125     {
126         int a1,a2;
127         char op1 = operation_stack.top();
128         operation_stack.pop();
129         if (operation_stack.size() == 0)
130         {
131             a1 = data_stack.top();
132             data_stack.pop();
133             a2 = data_stack.top();
134             data_stack.pop();
135             switch(pucExpression.find(op1))
136             {
137             case 10: data_stack.push(a2+a1);
138                 break;
139             case 11:data_stack.push(a2-a1);
140                 break;
141             case 12: data_stack.push(a2*a1);
142                 break;
143             case 13:data_stack.push(a2/a1);
144                 break;
145             }
146             break;
147         }
148         char op2 = operation_stack.top();
149         
150         switch(Priority(op1,op2))
151         {
152         case 1://operation>=ch
153             a1 = data_stack.top();
154             data_stack.pop();
155             a2 = data_stack.top();
156             data_stack.pop();
157             switch(pucExpression.find(op1))
158             {
159             case 10: data_stack.push(a2+a1);
160                 break;
161             case 11:data_stack.push(a2-a1);
162                 break;
163             case 12: data_stack.push(a2*a1);
164                 break;
165             case 13:data_stack.push(a2/a1);
166                 break;
167             }
168             break;
169         case 2://operation<ch
170             operation_stack.push(op1);
171             break;
172         case 3://() [] {}
173             operation_stack.pop();
174             break;
175         }
176     }
177     return data_stack.top();
178 }
179  
180 int main(void)
181 {
182     string str;
183     while(cin >> str)
184     {
185         printf("%d\n", calculate(str));
186     }
187     return 0;
188 }
View Code　　21、输入n个数，输出k个最小的数
　　问题：
　　是不是可以用二分查找





1 //我是忆水寒
2 //代码提交了几次，都是错误的，原因是格式错误。
3 //在输出结果的时候，先输出前k-1个，cout<<arr<<" ";
4 //最后输出最后一个数字不带空格就行。cout<<arr[k];
5 //c++代码如下：
6 #include<iostream>
7 #include <algorithm>
8 using namespace std;
9  
10 void Print_k_Of_arr(int* arr,int num,int k_Number)
11 {
12     if(k_Number>num)
13     {
14         return ;
15     }
16     else
17     {
18         sort(arr,arr+num);
19         for(int i=0;i<k_Number-1;i++)
20         {
21             cout<<arr<<" ";
22         }
23         cout<<arr[k_Number-1];
24     }  
25 }
26 int main()
27 {
28     int num=0,k=0;
29     int arr[1000]={0};
30     while(scanf("%d %d",&num,&k)!=EOF)
31     {
32         for(int i=0;i<num;i++)
33         {
34             cin>>arr;
35         }
36         Print_k_Of_arr(arr,num,k);
37     }
38     return 0;
39 }
40 //方法2：采用最大堆。
41 //（注意这个题目的测试用例答案要升序输出，所以这个题目出的不好） #include<iostream>
42 #include<vector>
43 #include<stdlib.h>
44 #include<algorithm>
45 using namespace std;
46  
47 void Heap_K_Number(vector<int>& temp,int N,int k)
48 {
49     if(k>N) return;
50     //将前K个元素（下标为0~k-1）导入vector容器中，下面要制作堆
51     vector<int> heap(temp.begin(),temp.begin()+k);
52     //初始化最大堆
53     make_heap(heap.begin(),heap.end());
54      
55     //从K+1个元素（下标就是k~N-1）
56     for(int i=k;i<N;i++)
57     {
58         if(temp<heap[0])//比堆顶元素小 ，调整堆
59         {
60             pop_heap(heap.begin(),heap.end());
61             heap.pop_back();
62              
63             heap.push_back(temp);
64             push_heap(heap.begin(),heap.end());
65         }
66     }
67      
68     //输出堆
69     for(int i=0;i<k-1;i++)
70         cout<<heap<<" ";
71     cout<<heap[k-1];
72 }
73  
74 int main()
75 {
76     int n,k,temp;
77     vector<int> vec;
78     while(cin>>n>>k)
79     {
80         for(int i=0;i<n;i++)
81         {
82             cin>>temp;
83             vec.push_back(temp);
84         }
85         Heap_K_Number(vec,n,k);
86     }
87 }
View Code　　22、字符串中只出现一次的字符
　　知识点：
　　find（）和rfind（）





1 #include <iostream>
2 #include <string>
3  
4 int main()
5     {
6     using namespace std;
7     string str;
8     while(getline(cin,str))
9         {
10          unsigned int i;
11         for (i=0;i<str.size();i++)
12         {
13             if(str.find(str)==str.rfind(str))
14             {
15                 cout<<str<<endl;
16                     break;
17             }
18         }
19         if(i==str.size())
20             cout<<"-1";
21     }
22     return 0;
23 }
View Code　　哈希统计：
　　知识点：
　　ascii码 256 个





1 #include<iostream>
2 #include<string>
3 using namespace std;
4 const int tableSize = 256;
5 int hasTable[tableSize];
6 int main(){
7     string s;
8     while(cin>>s){
9         bool flag = false;
10         for(int i=0;i<tableSize;++i) hasTable=0;
11         for(int i=0;i<s.size();++i) hasTable[s]++;
12         for(int i=0;!flag && i<s.size();++i){
13             if(hasTable[s] == 1){
14                 cout<<s<<endl;
15                 flag = true;
16                 break;
17             }
18         }
19         if(!flag)
20             cout<<'.'<<endl;
21     }
22     return 0;
23 }
View Code　　23、判断偶数最近的两个素数
　　知识点：
　　　判断素数（比我之前自己写的判断素数好多了）





1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 using namespace std;
5  
6 bool isPrime(int i)
7 {
8     for (int j = 2; j <= sqrt(i * 1.0); j++) {
9         if (i % j == 0)
10             return false;
11     }
12     return true;
13 }
14  
15 int main() {
16     int n;
17     int Prime1, Prime2;
18     while (cin >> n) {
19         if (n < 2)
20             return 1;
21         else {
22             for (int i = 1; i <= n / 2;i++) {
23                 if (isPrime(i) && isPrime(n - i)) {
24                     Prime1 = i;
25                     Prime2 = n - i;
26                 }
27             }
28             cout << Prime1 << endl;
29             cout << Prime2 << endl;
30             }
31     }
32     return 0;
33 }
View Code　　24、最小公倍数
　　知识点：
　　递归
　　最小公倍数
　　最大公约数





1 #include<iostream>
2 using namespace std;
3  
4 int gcd(int a, int b) // greatest common divisor
5 {
6     while(a%b){
7         int tmp = a;
8         a = b;
9         b = tmp%b;
10     }
11     return b;
12  
13 }
14 int main()
15 {
16     int a,b;
17     while(cin >> a >> b){
18         cout << a*b/gcd(a,b) <<endl;
19     }
20     return 0;
21 }
View Code