痛战！！！华为机试
本文记录自己的刷题记录，会有自己的代码（第一反应敲出的代码），都是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;
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)
20 cout << nums << endl;
21 }
22 }
23 return 0;
24 }
View Code 方法二：大牛码的
思路：（666）
读入的数存放到对应下标中，并记录为1。即，输入66，存入数组为nums中的方式是：nums = 1。懂了吧？
数组的大小是固定的
1 #include <iostream>
2 using namespace std;
3 int main() {
4 int N, n;
5 while (cin >> N) {
6 int a = { 0 };
7 while (N--) {
8 cin >> n;
9 a = 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.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' || s!='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;
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 += 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 += 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={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={0};
7 int num=0;
8 cin>>n ;
9 while(n)
10 {
11 if(a==0)
12 {
13 a++;//这一步是更新，遇到下次相同的数会跳过
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 = {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 == 0 ){
16 count++;
17 nums += 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,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>Input_String)
16 {
17 Temp=Input_String;
18 Input_String=Input_String;
19 Input_String=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 ，重要度为 w ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v*w+v*w+ … +v*w 。（其中 * 为乘号）
请你帮助王强设计一个满足要求的购物单。
输入描述:
输入的第 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={0};//价格（成本）
13 int value={0}; //价值（重要度*价格）
14 int f; //第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=v;
29 value=p*v;
30 }
31 else{ //附件
32 if(weight==0){ //第一个附件
33 weight=v;
34 value=p*v;
35 }
36 else{ //第二个附件
37 weight=v;
38 value=p*v;
39 }
40 }
41 }
42 //遍历计算
43 for(i=1;i<=m;i++)
44 for(j=N;j>0;j--){
45 if(j>=weight) //可以容下第i个主件时,比较放第i个或者不放第i个物品的价值
46 f=getMax(f,f]+value);
47 if(j>=weight+weight) //可以容下第i个主件和此主件的第1个附件时
48 f=getMax(f,f-weight]+value+value);
49 if(j>=weight+weight) //可以容下第i个主件和此主件的第2个附件时
50 f=getMax(f,f-weight]+value+value);
51 if(j>=weight+weight+weight) //可以容下第i个主件和此主件的第1个附件和第2个附件时
52 f=getMax(f,f-weight-weight]+value+value+value);
53 }
54 cout << f*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 - '0') * 10 + (n - '0');
13 if (len == 2) num = (n - '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 == 'A'){
21 x -= stringToNum(s,len);
22 }
23 if(s == 'D'){
24 x += stringToNum(s,len);
25 }
26 if(s == 'W'){
27 y += stringToNum(s,len);
28 }
29 if(s == '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){
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={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++;
18 return;
19 }
20 }
21 if(flag&&a<256)
22 vec=a;
23 else{
24 p++;
25 return;
26 }
27 b++;
28 }
29 if(vec>0){
30 if(vec<127){
31 p++;
32 if(vec==10)
33 p++;
34 }else if(vec<192&&vec>127){
35 p++;
36 if(vec==172&&vec>=16&&vec<=31)
37 p++;
38 }else if(vec>191&&vec<224){
39 p++;
40 if(vec==192&&vec==168)
41 p++;
42 }else if(vec>223&&vec<240)
43 p++;
44 else if(vec>239)
45 p++;
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==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++;
91 }
92 cout<<p<<" "<<p<<" "<<p<<" "<<p<<" "<<p<<" "<<p<<" "<<p<<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 --- 砝码数(范围)
第二行：m1 m2 m3 ... mn --- 每个砝码的重量(范围)
第三行：x1 x2 x3 .... xn --- 每个砝码的数量(范围)
输出描述:
利用给定的砝码可以称出的不同的重量数
输入例子:
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={0};//每个砝码的质量
10 int x={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;i++)
20 weights.push_back(i*m);//将第一个砝码能称出的质量入队
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+j*m;//将该质量的砝码数依次与前面所有的砝码数相加
27 //去重操作
28 if(find(weights.begin(),weights.end(),w)==weights.end())//如果之前没有这个质量的砝码就将其入队
29 weights.push_back(weights+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的基础上，对Q个不同的重量，分别添加k个砝码i，再添加的过程中除去重复情况。
9 //假设：w表示N个不同重量的砝码（例子中N=6），w。
10 // c表示N个不同砝码相应的数量，c。
11 //则：Q = (Q + k*w)-添加过程中重复的个数。其中0=<k<=c。网上博客搜的解题思路*/
12
13 int n ;//砝码数
14 int m = { 0 };//每个砝码的质量
15 int x = { 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; i++)
31 {
32 weigths.push_back(i*m);//将第一个砝码能称出的所有质量入队。
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 + j*m;//将该质量的砝码数依次与前面所有的砝码数相加
44 if (find(weigths.begin(), weigths.end(), wei) == weigths.end())//如果之前没有这个质量的砝码就将其入队
45 weigths.push_back(weigths + 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]);
35 result.push_back("hundred");
36
37 if (inners == 0)
38 {
39 if (inners > 0)
40 {
41 result.push_back("and");
42 result.push_back(zeroToNine]);
43 }
44 }
45 else if (inners == 1)
46 {
47 result.push_back("and");
48 result.push_back(tenToNineteen]);
49 }
50 else
51 {
52 result.push_back("and");
53 result.push_back(tenToNinety - 1]);
54 if (inners > 0)
55 {
56 result.push_back(zeroToNine]);
57 }
58 }
59 }
60 // 两位数
61 else if (inners.size() == 2)
62 {
63 if (inners == 1)
64 {
65 /*
66 if (! isBegin)
67 {
68 result.push_back("and");
69 }
70 */
71 result.push_back(tenToNineteen]);
72 }
73 else
74 {
75 /*
76 if (! isBegin)
77 {
78 result.push_back("and");
79 }*/
80 result.push_back(tenToNinety - 1]);
81 if (inners > 0)
82 {
83 result.push_back(zeroToNine]);
84 }
85 }
86 }
87 // 一位数
88 else
89 {
90 if (! isBegin)
91 {
92 if (inners > 0)
93 {
94 // result.push_back("and");
95 result.push_back(zeroToNine]);
96 }
97 }
98 else
99 {
100 result.push_back(zeroToNine]);
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, result, true);
135 result.push_back(thousandToBillion);
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);
144 }
145 }
146
147 // 最后小于1000的部分
148 processThousand(thousands, result, false);
149 }
150
151 for (int i = 0; i < result.size() - 1; ++i)
152 {
153 cout << result << " ";
154 }
155 cout << result << 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 = {
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为,既第一空格是可以走的路。
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*;
for(int i =0; i<N; i++){
a =new int;
}
for(int i =0; i<N; i++){
for(int j =0; j<M; j++){
cin >> a;
}
}
int dir = { {0,1}, {1,0}, {0,-1}, {-1,0} };//点的四个方向：下，右，上，左
int visit = {0}; //判定该点是否走过
bool flag =0; //是否走完
stack<pair<int,int>> stk;
stk.push(make_pair(0,0));
stk.push(make_pair(0,0));
visit =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;
int dy = j + dir;
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 ==0&& visit ==0){//未被访问过且有路径
stk.push(make_pair(dx, dy));
visit =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 voidaddNum(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-'0';
44 }else if(s!='('&&s!='['&&s!='{'){
45 addNum(Q,pre);
46 string ss;
47 ss+=s;
48 Q.push_back(ss);
49 pre=0;
50 }else{
51 int* bra=NULL;
52 bra=value(s,i+1);
53 pre=bra;
54 i=bra+1;
55 }
56 }
57 addNum(Q,pre);
58 int *R=new int;
59 R=getNum(Q);
60 R=i;
61 return R;
62 }
63 int main(){
64 string s;
65 while(cin>>s){
66 int *R=value(s,0);
67 cout<<R<<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=='('||strExpression=='['||strExpression=='{'))
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;
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;
24 }
25 }
26 int main()
27 {
28 int num=0,k=0;
29 int arr={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)//比堆顶元素小 ，调整堆
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;
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;
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]++;
12 for(int i=0;!flag && i<s.size();++i){
13 if(hasTable] == 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
页:
[1]