c++实际应用编程汇总(二)|字符串|数组|向量|输入输出

不念不忘少年蓝@ 2021-11-16 13:12 287阅读 0赞

**目录**

一、一串值的缩约

1.1 会话列表的缩约

解法

二、进制中的分组数

答案

三、最长的N串

四、字符串三道

5.1 字符串的匹配

5.2 频率从大到小输出字符

5.3 substr函数

5.4 翻转单词顺序

五、输入输出

5.1水仙花数

5.2 开根号数列

六、大字符串相乘

七、两道编过的题及思路

7.1 排序二叉树的种数

7.2 不用除号/的除法

--------------------

# 一、一串值的缩约 #

指的是将一系列的值进行缩约，例如如果后面的值出现重复，则只留下前面的值。

## 1.1 会话列表的缩约 ##

oj链接：[https://www.nowcoder.com/questionTerminal/0f52adb3946249f9bb63d964658b2691][https_www.nowcoder.com_questionTerminal_0f52adb3946249f9bb63d964658b2691]

会话列表为显示为一个从上到下的多行控件，其中每一行表示一个会话，每一个会话都可以以一个唯一正整数id表示。

新会话出现时，会出现在列表最上方，如果已有会话也会出现在列表最上方。

输入描述:  
输入的第一行为一个正整数T（T<=10），表示测试数据组数。  
接下来有T组数据。每组数据的第一行为一个正整数N（1<=N<=200），表示接收到信息的次数。第二行为N个正整数，按时间从先到后的顺序表示接收到信息的会话id。会话id不大于1000000000。

输出描述:  
对于每一组数据，输出一行，按会话列表从上到下的顺序，输出会话id。  
相邻的会话id以一个空格分隔，行末没有空格。

输入
    3
    5
    1 2 3 4 5
    6
    1 100 1000 1000 100 1
    7
    1 6 3 3 1 8 1
    输出
    5 4 3 2 1
    1 100 1000
    1 8 3 6

### 解法 ###

开辟了一个新的vector用于从后往前存入ID

#include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    int main(){
    	int times; cin >> times;
    	while (times--){
    		int num; cin >> num;
    		vector<int> id_array;
    		while (num--){
    			int number; cin >> number;
    			id_array.push_back(number);
    		}
    		vector<int> out_array;
    		out_array.push_back(id_array[id_array.size() - 1]);
    		for (int idx = id_array.size() - 2; idx >= 0; idx--){
    			bool exist = false;
    			for (auto item : out_array){
    				if (id_array[idx] == item){
    					exist = true;
    					break;
    				}
    			}
    			if (!exist)out_array.push_back(id_array[idx]);
    		}
    		for (auto item : out_array){
    			cout << item << " ";
    		}
    		cout << endl;
    
    	}
    
    	//int end; cin >> end;
    	return 0;
    }

也可以用map头文件简化运算。

#include <iostream>
    #include <vector>
    #include <map>
    using namespace std;
      
    int main() {
        int T, N;
        cin >> T;
        for (int i = 0; i < T; ++i) {
            cin >> N;
            map<int,int> sessions, res;
            int sessionID;
            for (int j = 0; j < N; ++j) {
                cin >> sessionID;
                if(sessions.count(sessionID) > 0 ){
                    int k = sessions[sessionID];
                    res.erase(k);
                }
                res[N - j] = sessionID;
                sessions[sessionID] = N - j;
            }
      
            auto iter = res.begin();
            while (iter != res.end()){
                cout << iter -> second << " ";
                iter ++;
            }
            cout << endl;
      
        }
      
        return 0;
    }

来自 <[https://www.nowcoder.com/profile/368591124/test/25652925/147541\#summary][https_www.nowcoder.com_profile_368591124_test_25652925_147541_summary]>

## 二、进制中的分组数 ##

二进制中1的个数分组  
输入一系列数字，问二进制下1的个数。1的个数相同的分为一类。问一共有多少类。  
输入第一个n组数  
第二行每组中数字的个数  
第三行是这些数字

比如
    1
    3
    1 2 3
    输出
    2

### 答案 ###

#include<iostream>
    #include<string.h>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    int bin_num_1(int num){
    	int mask = 0x00000001;
    	int num1 = 0;
    	while (mask){
    		if (num&mask)num1++;
    		mask = mask << 1;
    	}
    	return num1;
    }
    
    int main(){
    	int n_groups; cin >> n_groups;
    	while (n_groups--){
    		int nums; cin >> nums;
    		vector<int> binary_num;
    		for (int idx = 0; idx < nums; idx++){
    			int current; cin >> current;
    			int current_1_num = bin_num_1(current);
    			binary_num.push_back(current_1_num);
    		}
    		vector<int> dict;
    		dict.push_back(binary_num[0]);
    		for (int idx = 1; idx < nums; idx++){
    			bool exist = false;
    			for (auto item : dict){
    				if (item == binary_num[idx]){
    					exist = true;
    				}
    			}
    			if (!exist)dict.push_back(binary_num
    
    				[idx]);
    		}
    		cout << dict.size() << endl;
    	}
    
    	//int end; cin >> end;
    	return 0;
    }

# 三、最长的N串 #

没有找到oj，

最多改变string中两个位置的值，使得剩下的N最长是多长？

例如

NTNN，输出4

NNTNNTN，输出7

下面这个程序存在算法复杂度过高的问题，只能通过70%

#include<iostream>
    #include<string>
    #include<algorithm>
    #include<vector>
    using namespace std;
    
    int num_of_N(string str_1){
    	int str_len = str_1.size();
    	int max_N = 0;
    	int current_N = 0;
    	for (int idx = 0; idx < str_len; idx++){
    		if (str_1[idx] == 'N'){
    			current_N++;
    			if (idx == str_len - 1){
    				max_N = (max_N>current_N) ? max_N
    
    					: current_N;
    			}
    		}
    		else{
    			max_N = (max_N>current_N) ? max_N :
    
    				current_N;
    			current_N = 0;
    		}
    	}
    	return max_N;
    }
    
    int main(){
    	int T; cin >> T;
    	while (T--){
    		string str;
    		cin >> str;
    		int strlen = str.size();
    		string str_cp;
    
    		int max_N = num_of_N(str);
    
    		for (int loc_1 = 0; loc_1 < strlen; loc_1++){
    			for (int loc_2 = 0; loc_2 < strlen;
    
    				loc_2++){
    				if (str[loc_1] != 'N' && str
    
    					[loc_2] != 'N'){
    					str_cp = str;
    					str_cp[loc_1] = 'N';
    					str_cp[loc_2] = 'N';
    					int changed_N = num_of_N
    
    						(str_cp);
    					max_N = (max_N>changed_N)
    
    						? max_N : changed_N;
    				}
    			}
    		}
    		cout << max_N << endl;
    	}
    
    	return 0;
    }

# 四、字符串三道 #

zoom笔试题，选择题较难，但是编程题oj全对。

## 5.1 字符串的匹配 ##

判断一个字符串与另一个字符串是否匹配，即第一个字符串经过倒序之后能组成第二个字符串。

例如 第一个 abcabc，第二个， aabbcc，则第一个经过改变顺序则可以组成第二个字符串。

思路就是，第一个与第二个中的进行match，如果能够match上，则说明可以组成第二个字符串。

直观的想到有下面这种方法，但是算法复杂度较高，为O(N\*N)，其实有另一种O(N)的方法来更好的解决这个问题。

即针对char实现一个256大小的哈希表。两个哈希表匹配上，则说明字符串匹配上。

#include<vector>
    #include<iostream>
    #include<string>
    using namespace std;
    int main(){
    	string string_A, string_B;
    	cin >> string_A >> string_B;
    	int str_size = string_A.size();
    	if (str_size < 1 || str_size != string_B.size()){
    		cout << "0" << endl;
    		return 0;
    	}
    	vector<bool> matched(str_size, false);
    	for (int idx_A = 0; idx_A < str_size; idx_A++){
    		int idx_B;
    		for (idx_B = 0; idx_B < str_size; idx_B++){
    			if (string_A[idx_A] == string_B[idx_B] && !matched[idx_B]){
    				matched[idx_B] = true;
    				break;
    			}
    		}
    		if (idx_B == str_size){
    			cout << "0" << endl;
    			return 0;
    		}
    	}
    	cout << "1" << endl;
    	//int end; cin >> end;
    	return 0;
    
    }

## 5.2 频率从大到小输出字符 ##

输出字符在字符串中出现的频率,按照从大到小输出。例如 cbbaaa就输出abc

这个相当于字符存一个vector，出现次数存一个vector，然后选择排序。AC 100%

#include<vector>
    #include<iostream>
    #include<string>
    using namespace std;
    
    int main(){
    	string string_A;
    	cin >> string_A;
    	int str_size = string_A.size();
    	if (str_size < 1)return 0;
    
    	vector<char> char_vector;
    	vector<int> times_vector;
    	char_vector.push_back(string_A[0]);
    	times_vector.push_back(1);
    
    	// input all values
    	for (int idx = 1; idx < str_size; idx++){
    		bool if_exist=false;
    		for (int vector_idx = 0; vector_idx < char_vector.size(); vector_idx++){
    			if (string_A[idx] == char_vector[vector_idx]){
    				if_exist = true;
    				times_vector[vector_idx]++;
    				break;
    			}
    		}
    		if (!if_exist){
    			char_vector.push_back(string_A[idx]);
    			times_vector.push_back(1);
    		}
    	}
    
    	for (int idx = 0; idx < char_vector.size()-1; idx++){
    		for (int next_idx = idx+1; next_idx < char_vector.size(); next_idx++){
    			if (times_vector[idx] < times_vector[next_idx]){
    				char temp_c = char_vector[idx];
    				char_vector[idx] = char_vector[next_idx];
    				char_vector[next_idx] = temp_c;
    
    				int temp = times_vector[idx];
    				times_vector[idx] = times_vector[next_idx];
    				times_vector[next_idx] = temp;
    			}
    		}
    
    	}
    	for (auto item : char_vector){
    		cout << item;
    	}
    	cout << endl;
    	int end; cin >> end;
    	return 0;
    }

## 5.3 substr函数 ##

注意需要加上\#include<string>头文件。

int main(){
    	string a = "whats your problem";
    	string b = a.substr(1);
    	string c = a.substr(1,3);
    	cout << a << endl;
    	cout << b << endl;
    	cout << c << endl;
    	int end; cin >> end;
    	return 0;
    }

第一个参数是开始位置，第二个参数是子字符串的长度，如果不加第二个参数，则返回最终的位置。

输出：

whats your problem
    hats your problem
    hat

## 5.4 翻转单词顺序 ##

肯定有更简单的方法，此法时间复杂度较高。但是此法可以更好的找到相应的位置映射。

*  先对字符串做一次倒序，需要颠倒顺序的是 idx<length/2的量，即中间位置之前
 *  字符串内倒序，中间位置idx<(fast-slow)/2 +slow
 *  鲁棒性判断一定要加

#include<vector>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<stdio.h>
    using namespace std;
    
    class Solution {
    public:
    	string ReverseSentence(string str) {
    		int length = str.size();
    		if (length < 1){
    			string empty;
    			return empty;
    		}
    		for (int idx = 0; idx < length / 2; idx++){
    			swap(str[idx],str[length-idx-1]);
    		}
    
    		int slow = 0; int fast = 1;
    		while (fast != length){
    			if (str[fast]== ' '){
    				for (int idx = slow; idx < (fast - slow) / 2 +slow; idx++){
    					swap(str[idx], str[fast - 1 - idx+slow]);
    				}
    				slow = fast + 1;
    			}
    			fast++;
    		}
    		for (int idx = slow; idx < (fast - slow) / 2+slow; idx++){
    			swap(str[idx], str[fast - 1 - idx + slow]);
    		}
    		return str;
    	}
    };
    
    int main(){
    	string A = "I am a student!";
    	Solution s1;
    	cout << s1.ReverseSentence(A) << endl;
    	string B = "Its a dog!";
    	cout << s1.ReverseSentence(B) << endl;
    	int end; cin >> end;
    	return 0;
    }

# 五、输入输出 #

有时候输入会告诉几组数据，从而制造输入，但是经常考试时会遇到不告诉输入组数的情况，即只要有输入就需要一直运行下去。这时候就不能用iostream头文件来处理信息了。

*  用scanf函数来读取信息，用!=EOF来判断是否结束
 *  VS2013为scanf\_s函数，即安全输入函数，但是oj里面需要改为scanf

样例两道；

## 5.1水仙花数 ##

**题目描述：**

春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的： “水仙花数”是指一个三位数，它的各位数字的立方和等于其本身，比如：153=1^3+5^3+3^3。 现在要求输出所有在m和n范围内的水仙花数。

输入 输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。

输出 对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开; 如果给定的范围内不存在水仙花数，则输出no; 每个测试实例的输出占一行。

样例输入

100 120

300 380

样例输出

370 371

来自 <[https://beike.acmcoder.com/cand/index?.r=0.627767842878423&\#/main/onlinecode/5c7e35140bd91403fbc00bb3/0/1][https_beike.acmcoder.com_cand_index_.r_0.627767842878423_main_onlinecode_5c7e35140bd91403fbc00bb3_0_1]>

#include<stdio.h>
    int main(){
        int m,n;
        while(scanf("%d%d",&m,&n)!=EOF){
                int t=0;
            for(int i=m; i<=n; i++){
                int a=i/100;
                int b=i%100/10;
                int c=i%10;
                
                if(i==a*a*a+b*b*b+c*c*c && t==0){
                    printf("%d ",i);
                    t++;
                }
                else if(i==a*a*a+b*b*b+c*c*c && t==1){
                    printf("%d ",i);
                }
            }
            if(t!=0){ printf("\n"); }
            if(t==0){ printf("no\n"); }
        }
        return 0;
    }

## 5.2 开根号数列 ##

求数列的和

**题目描述：**

数列的定义如下： 数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。

输入

输入数据有多组，每组占一行，由两个整数n（n<10000）和m(m<1000)组成，n和m的含义如前所述。

输出

对于每组输入数据，输出该数列的和，每个测试实例占一行，要求精度保留2位小数。

样例输入

81 4

2 2

样例输出

94.73

3.41

#include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<math.h>
    using namespace std;
    
    int main(){
    	double n;
    	int  m;
    	while (scanf("%lf %d", &n, &m) != EOF){
    		double sum = 0;
    		for (int idx = 0; idx < m; idx++){
    			sum += n;
    			n = sqrt(n);
    		}
    		printf("%.2lf\n", sum);
    	}
    
    	return 0;
    
    }

需要注意几点，

*  首先sqrt需要包含 math.h头文件
 *  scanf到double之中的时候 %lf
 *  读取的时候，用scanf("%lf %d",&n,&m)!=EOF
 *  EOF相当于ctrl+z

# 六、大字符串相乘 #

作业帮二面面试题，也是 Leetcode43，可能因为实现有bug，因此没过。类似这种题应该把映射找好，争取一遍编全对。

#include<string>
    #include<iostream>
    #include<vector>
    #include<set>
    #include<list>
    using namespace std;
    
    class Solution {
    public:
    	char int_to_char(int a){
    		char c = '0';
    		c += a;
    		return c;
    	}
    	int char_to_int(char c){
    		int a;
    		a = c - '0';
    		return a;
    	}
    	string multiply(string num1, string num2) {
    		if (num1 == "0" || num2 == "0")return "0";
    		int num1_size = num1.size();
    		int num2_size = num2.size();
    		int max_count = num1_size + num2_size;
    		string result;
    		int next = 0;
    		for (int idx = 0; idx < max_count; idx++){
    			int current = 0;
    			for (int idx_a = 0; idx_a <= idx; idx_a++){
    				int idx_b = idx - idx_a;
    				int n1 = (num1_size - 1 - idx_a >= 0) ? char_to_int(num1[num1_size - 1 - idx_a]) : 0;
    				int n2 = (num2_size - idx_b - 1 >= 0) ? char_to_int(num2[num2_size - idx_b - 1]) : 0;
    				current += n1*n2;
    			}
    			current += next;
    			next = current / 10;
    			result += int_to_char(current % 10);
    		}
    		int idx = result.size()-1;
    		while (result[idx] == '0'){
    			idx--;
    		}
    		string reverse;
    		for (; idx >= 0; idx--){
    			reverse += result[idx];
    		}
    		return reverse;
    	}
    };
    
    int main(){
    
    	string num1 = "1111";
    	string num2 = "1111";
    	Solution s;
    	cout << s.multiply(num1,num2) << endl;
    	int end; cin >> end;
    	return 0;
    }

# 七、两道编过的题及思路 #

## 7.1 排序二叉树的种数 ##

作业帮一面题，1，2，3.。。n能构成多少种排序二叉树

#include<vector>
    #include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    int main(){
    
    	int n; cin >> n;
    	vector<int> methods;
    	methods.push_back(1);// 0 nodes
    	methods.push_back(1);// 1 nodes
    	methods.push_back(2);// 2 nodes
    	for (int idx = 3; idx <= n; idx++){//idx nodes
    		int idx_methods = 0;
    		for (int left_nodes = 0; left_nodes <= idx - 1; left_nodes++){
    			int mult = methods[left_nodes] * methods[idx - left_nodes - 1];
    			idx_methods += mult;
    		}
    		methods.push_back(idx_methods);
    	}
    	cout << methods[n] << endl;
    
    	int end; cin >> end;
    	return 0;
    }

## 7.2 不用除号/的除法 ##

用移位的方法，用移位来实现除法。

#include<vector>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<stdlib.h>
    using namespace std;
    
    int main(){
    
    	// m/n
    	int m; int n; cin >> m >> n;
    	if (n == 0){
    		cout << "Input error!" << endl;
    		return 1;
    	}
    	bool minus_result = (m*n < 0) ? true : false;
    	m = abs(m);
    	n = abs(n);
    
    	if (m < n){
    		cout << 0 << endl;
    		return 0;
    	}
    
    	int idx = 0;
    	int minus = n;
    	while (minus < m){
    		idx++;
    		minus = n << idx;
    	}
    	int result = 0;
    	int mask = 0x00000001;
    	for (; idx >= 0; idx--){
    		if (m>=(n << idx)){
    			m -= n << idx;
    			result += mask << idx;
    		}
    	}
    	cout << result << endl;
    
    	int end; cin >> end;
    	return 0;
    }

[https_www.nowcoder.com_questionTerminal_0f52adb3946249f9bb63d964658b2691]: https://www.nowcoder.com/questionTerminal/0f52adb3946249f9bb63d964658b2691
[https_www.nowcoder.com_profile_368591124_test_25652925_147541_summary]: https://www.nowcoder.com/profile/368591124/test/25652925/147541#summary
[https_beike.acmcoder.com_cand_index_.r_0.627767842878423_main_onlinecode_5c7e35140bd91403fbc00bb3_0_1]: https://beike.acmcoder.com/cand/index?.r=0.627767842878423&#/main/onlinecode/5c7e35140bd91403fbc00bb3/0/1