1112 字符串
题目大意： 坏的键盘可能会连续打出K个字母。给你一个字符串(由a-z, 0-9 和 '_' 组成，不超过1000个字符)， 指出可能坏了的键，以及原始的字符串。
思路： 两次遍历字符串。第一次遍历，统计每次每个字符连续出现的次数，用map<char , vector<int> >存储。然后遍历这个map，若发现某个字符有一次连续出现的次数不是k, 则是没错的字符。第二次遍历，若遍历到错误的字符，若还未输出，则输出（这样就可以按照原次序输出了，map和set里存储的是排序的），然后删除不正确的字符。
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
using namespace std;
int main(){
int k;
cin>>k;
string s;
cin>>s;
map<char, vector<int> > mp;
for(int i=0;i<s.length(); ){
int count = 0;
while( i+ count < s.length() && s[i] == s[i+count]) count++;
mp[s[i]].push_back(count);
i += count;
}
set<char> wrong; //记录错误字母
map<char, vector<int> >::iterator iter;
for(iter = mp.begin(); iter != mp.end(); iter++){
bool flag = true;
for(int j=0; j < mp[iter->first].size(); j++){
if(mp[iter->first][j] % k != 0){ //但凡有一个值不为k都不是错的
flag = false;
break;
}
}
if(flag) wrong.insert(iter->first);
}
set<char> exist; //记录已输出字母
for(int i = 0;i<s.length();i++){
if(wrong.find(s[i]) != wrong.end()){ //若是错误字母
s.erase(i+1,k-1); //删除后面k-1个
if(exist.find(s[i]) == exist.end()){
cout<<s[i];
exist.insert(s[i]);
}
}
}
cout<<endl<<s;
return 0;
}
1113 逻辑题
题目大意： 给n个正整数，分成两个不相交集合；记集合的元素数量分别为n1和n2，元素和为s1,s2；首先使得|n1 - n2|最小，其次使得|s1-s2|最大
思路： 要使得|n1 - n2|最小，若n为偶数，则均分，若n为奇数，则给较大集合多一个元素让他变得更大。要使使得|s1-s2|最大 ，则对n个数进行排序，较大的数给较大集合，小数给小集合即可。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n; // 2<= n <= 10^5
cin>>n;
vector<int> v(n); //后面有sort，就不能初始化为n+1
for(int i=0;i<n;i++){
cin>>v[i];
}
sort(v.begin(), v.end());
if( n % 2 == 0){
cout<<"0 ";
}else{
cout<<"1 ";
}
int sum1 = 0;
for(int i=0;i<n/2;i++){
sum1+=v[i];
}
int sum2=0;
for(int i=n/2;i<n;i++){
sum2+=v[i];
}
cout<<sum2-sum1<<endl;
return 0;
}
1114 并查集
题目大意： 已知每个人的家庭成员、名下房产 。求每个家庭的总人数，以及平均拥有房产
思路： 这题考察并查集，好麻烦。
1115 二叉搜索树 DFS
题目大意： 二叉搜索树 (可插入重复节点，重复加点插入在左子树)。给你二叉搜索树节点的插入顺序，求最低两层的节点总数 。结点数范围：[1,1000],结点值范围：[-1000,1000]
思路： 先建树，然后遍历求得每层结点数，输出最后两层结点数即可。但是测试点3过不去，不知道为什么。
#include<iostream>
#include<vector>
#include<map>
using namespace std;
typedef struct node{
int val;
int left,right;
}node;
map<int ,node> tree;
map<int, int> height;
int maxh = 0;
int n;
int root;
void insert(int r, int val, int h){
if(val <= r && tree[r].left == -1){
tree[r].left = val;
node temp;
temp.val = val; temp.left = -1; temp.right = -1;
tree[val] = temp;
height[h+1]++;
if(h+1>maxh){
maxh = h+1;
}
return;
}else if(val > r && tree[r].right == -1){
tree[r].right = val;
node temp;
temp.val = val; temp.left = -1; temp.right = -1;
tree[val] = temp;
height[h+1]++;
if(h+1>maxh){
maxh = h+1;
}
return;
}else if(val > r && tree[r].right != -1){
insert(tree[r].right, val, h+1);
}if(val <= r && tree[r].left != -1){
insert(tree[r].left, val, h+1);
}
}
int main(){
cin>>n;
cin>>root;
node temp;
temp.val = root; temp.left = -1; temp.right = -1;
tree[root] = temp;
height[0] = 1;
for(int i=1;i<n;i++){
int x;
cin>>x;
insert(root, x, 0);
}
cout<<height[maxh]<<" + "<<height[maxh-1]<<" = "<<height[maxh] + height[maxh-1]<<endl;
return 0;
}
