字符串的一些关键点
//大小写的转换
transform(str_1.begin(),str_1.end(),str_1.begin(),::tolower);//字符串
tolower(str_1[i-1])；//字符
//寻找字符和字符串
str_2.find(temp_str)!=string::npos;//找到返回位置，否则返回npos
str_2.find(temp_char)!=string::npos;//找到返回位置，否则返回npos
//下面写法是跟容器类的find函数一样的（但只是寻找字符）
find(str_2.begin(),str_2.end(),temp_char)!=str_2.end();//找到返回位置，否则返回end
//寻找某个字符的索引位置
int index=input_str.find('/');
//输出double的小数点（#include <iomanip>）
//fixed 操作符与 setprecision 操作符一起使用时。将指定浮点数字的小数点后要显示的位数，而不是要显示的总有效数位数
std::cout<<fixed <<setprecision(1)<<average;//固定一位小数（必须要有fixed）
std::cout<<setw(9)<<setfill('0')<<value;//前导0，总共9位
//平时sort是从小到大排列，如果想从大到小排列，可以这样
sort(nums.begin(),nums.end(),greater<int>());//从大到小排列，当然也可以自定义函数来实现～
有时做最大最小值记录的时候，可以选择初始化为INT_MIN和INT_MAX！必须，特别是数组或者vector类别的，没有初始化就用地址值会报错。
注意每次对比最值都应该check最后一个！
采用"//"来代替'/'，因为'/'是转义字符，会出现问题
int n; cin>>n;
cin.ignore(); // 忽略 cin>>n 后的换行符
string input_str; getline(cin,input_str);
//转换为string
to_string(123);//转换为字符串
stoi("123");//转换为int
stol("123");//转换为long int
n进制转10进制都是pow（n，第几位）逢n进位
map<int,int>对应的是有序的（从小到大），unordered_map<int,int>对应的是无序的
map<int, string, greater<int>> group;//从大到小排列
set<int>对应的是有序的（从小到大），unordered_set<int>对应的是无序的（用insert放入元素）
//将map转换为vector
vector<pair<int,int>> vec(group.begin(),group.end());
整数与罗马数字的转换
class Solution {
public:
// 通过vector穷举了所有的可能性(由于不同的千百十位对应不同的字符,故此穷举最直接)
vector<pair<int, string>> group = {
{1000, "M"},
{900, "CM"},
{500, "D"},
{400, "CD"},
{100, "C"},
{90, "XC"},
{50, "L"},
{40, "XL"},
{10, "X"},
{9, "IX"},
{5, "V"},
{4, "IV"},
{1, "I"},
};//顺序很重要!
string intToRoman(int num) {
string output_str;
// 遍历这个group
for(int i=0;i<group.size();i++)//长度固定因此复杂度为O(1)
{
// 注意遍历是从大到小减的~
while(num>=group[i].first)//通过while循环,取完了,i再变
{
output_str+=group[i].second;
num=num-group[i].first;
}
if(num==0)
break;
}
return output_str;
}
};
穷举的时候，用map也可以，但是map默认是按key从小到大排列了的，改一下即可~
class Solution {
public:
// 穷举了所有的可能性(由于不同的千百十位对应不同的字符,故此穷举最直接)
map<int, string, greater<int>> group = {
{1000, "M"},
{900, "CM"},
{500, "D"},
{400, "CD"},
{100, "C"},
{90, "XC"},
{50, "L"},
{40, "XL"},
{10, "X"},
{9, "IX"},
{5, "V"},
{4, "IV"},
{1, "I"},
};//顺序很重要!
string intToRoman(int num) {
string output_str;
// 遍历这个group
for(auto it=group.begin(); it!=group.end();it++)//长度固定因此复杂度为O(1)
{
// 注意遍历是从大到小减的~
while(num>=it->first)//通过while循环,取完了,i再变
{
output_str+=it->second;
num=num-it->first;
}
if(num==0)
break;
}
return output_str;
}
};
跟上面很类似，只是反过来由罗马变为阿拉伯数字而已~
class Solution {
public:
unordered_map<char, int> define_group=//注意是从小到大
{
{'I',1},
{'V',5},
{'X',10},
{'L',50},
{'C',100},
{'D',500},
{'M',1000}
};
int romanToInt(string s) {
int num_value=0;
for(int i=0;i<s.size();i++)
{
// 若字符串的当前位对应的数字小于下一位对应的数字(对应特殊的4,9等等)
if(define_group[s[i]]<define_group[s[i+1]])
{
//逐个遍历，逐个相加即可~
num_value+=define_group[s[i+1]]-define_group[s[i]];
i=i+1;//当前位和下一位都算了，可以跳过
}
else//反之,则是当前位和下一位相同
num_value+=define_group[s[i]];//直接获取值
}
// num_value=num_value+define_group[s[s.size()-1]];//最后一个加上
return num_value;
}
};
人民币的转换比罗马数字难多了，主要是还要考虑不同位的念法不一样。此处单纯给出代码，还没理思路～
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const vector<string> helper1 = {"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"};
const vector<string> helper2 = {"元", "万", "亿"};
const vector<string> helper3 = {"", "拾", "佰", "仟"};
string parts(int num){
string str;
if(num > 0 && num <= 9)
str += helper1[num];
else if(num >= 10 && num <= 19){
if(num % 10 == 0)
str += helper3[1];
else
str += helper3[1] + helper1[num%10];
}else if(num >= 20 && num <= 99){
if(num % 10 == 0)
str += helper1[num/10] + helper3[1];
else
str += helper1[num/10] + helper3[1] + helper1[num%10];
}else if(num >= 100 && num <= 999){
if(num % 100 == 0)
str += helper1[num/100] + helper3[2];
else if(num % 100 <= 9)
str += helper1[num/100] + helper1[0] + helper1[num%100];
else
str += helper1[num/100] + helper3[2] + parts(num % 100);
}else if(num >= 1000 && num <= 9999){
if(num % 1000 == 0)
str += helper1[num/1000] + helper3[3];
else if(num % 1000 <= 99)
str += helper1[num/1000] + helper3[3] + helper1[0] + parts(num % 1000);
else
str += helper1[num/1000] + helper3[3] + parts(num % 1000);
}
return str;
}
int main(){
double money;
while (cin >> money){
money += 0.0001; // 此处+0.0001防止double转换int产生误差
// 分两步，第一步处理整数
int data = static_cast<int>(money);
vector<int> vec;
string res = "人民币";
while (data){
vec.push_back(data % 10000);
data /= 10000;
}
for (int i = vec.size() - 1; i >= 0; --i){
res += parts(vec[i]);
res += helper2[i];
if (i != 0 && i - 1 >= 0 && vec[i - 1] <= 999 && vec[i - 1] != 0)
res += helper1[0];
}
// 第二步处理小数
int deci = static_cast<int>((money - static_cast<int>(money)) * 100);
if (deci == 0)
res += "整";
else if (deci < 10)
res += helper1[deci] + "分";
else if (deci % 10 == 0)
res += helper1[deci / 10] + "角";
else
res += helper1[deci / 10] + "角" + helper1[deci % 10] + "分";
cout << res << endl;
}
return 0;
}
进制转换
进制转换是非常经典的题目，其实关键点都是十进制与其他进制相互转换而已～
注意16进制就是要乘16次幂（pow(16,n)）。输入的为字符串，每次对比是字符’0’和’9’
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
string input_str;
cin>>input_str;
int output_result=0;
for(int i=input_str.size()-1;i>=0;i--)//从最后一位开始吧
{
if(input_str[i]>='0' && input_str[i]<='9')//注意要对比的是字符
output_result+=(input_str[i]-'0')*pow(16,input_str.size()-1-i);//16的i次方对应16进制
else if(input_str[i]>='A' && input_str[i]<='F')
output_result+=(input_str[i]-'A'+10)*pow(16,input_str.size()-1-i);
else//忽略“0x”前缀
break;//跳出
}
std::cout<<output_result<<std::endl;
}
二进制求和
要用string来解题才可以，如果先转换为十进制然后相加可能出现越界情况.时间复杂度, O(Max(M,N))
class Solution {
public:
int binarytoten(string input_str)
{
int output_value=0;
for(int i=input_str.size()-1;i>=0;i--)//倒序
{
output_value+=(input_str[i]=='1'? 1:0)*pow(2,input_str.size()-1-i);
}
return output_value;
}
string tentobinary(int input_value)
{
if(input_value==0)
return "0";
string output_str;
while(input_value!=0)
{
output_str+=to_string(input_value%2);//获取余数
input_value=input_value/2;//整除
}
reverse(output_str.begin(), output_str.end());//倒序输出
return output_str;
}
string addBinary(string a, string b) {
//先转换为十进制然后相加再转二进制（但是如果输入长度很长就会越界~）
// string output_str=tentobinary(binarytoten(a)+binarytoten(b));
string output_str;
//先将输入进行倒序
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if(b.size()>a.size())
swap(a,b);//确保a是长序列
int jinwei=0;
for(int i=0;i<b.size();i++)
{
int temp=(a[i]=='1'? 1:0)+ (b[i]=='1'? 1:0)+jinwei;
if(temp>1)
{
jinwei=1;
output_str+=to_string((temp-2));//进位了
}
else
{
jinwei=0;
output_str+=to_string((temp));//没有进位
}
}
//计算完b剩余的a序列
for(int i=b.size();i<a.size();i++)
{
int temp=(a[i]=='1'? 1:0)+jinwei;
if(temp>1)
{
jinwei=1;
output_str+=to_string((temp-2));//进位了
}
else
{
jinwei=0;
output_str+=to_string((temp));//没有进位
}
}
//不要漏了最后一个进位
if(jinwei!=0)
output_str+='1';
reverse(output_str.begin(), output_str.end());//倒序输出（前面倒序处理了，不要漏了！）
return output_str;
}
};
在内存中存储时1个数
此题实际上就是转换为二进制
#include <iostream>
#include <string>
using namespace std;
int main() {
int input_value;
cin>>input_value;
int num_result=0;
//转换为二进制
while(input_value!=0)//还没除尽
{
if(input_value%2==1)//余数
num_result++;
input_value=input_value/2;//整除的结果，下次再继续用
}
std::cout<<num_result;
}
求最大连续bit数
跟上一题是很像的，主要是要注意设计循环迭代求最值都需要对比一下最后一个
#include <iostream>
using namespace std;
int main() {
int input_value;
cin>>input_value;//输入数字
//直接计算，而不是先转二进制再算
int max_num=0;
int temp=0;
while(input_value)//整除不为0还可以继续计算
{
if(input_value%2==1)//是1
{
temp++;
}
else //为0，那么就相当于1中断了，需要重新计算
{
if(temp>max_num)
max_num=temp;
temp=0;
}
input_value=input_value/2;//整除后的结果下次再继续算
}
//最后一个算一下（注意每次对比最值都应该check最后一个）
if(temp>max_num)
max_num=temp;
std::cout<<max_num;
}
整数与ip地址之间的转换
此题包含了十进制转2进制；2进制转10进制。注意n进制转10进制都是pow（n，第几位）逢n进位，故此满一位就是要乘n。细节的地方主要是分组+0的讨论。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
string tenTobrinary(long int value)
{
if(value==0)
return "0";//若一开始就为0，就返回0
string result;
while(value!=0)//还没除尽
{
int yushu=value%2;//余数
result+=to_string(yushu);
value=value/2;//整除，下一次继续算
}
reverse(result.begin(),result.end());//注意存放顺序发生了变化也要倒序
return result;
}
long int brinaryToten(string input_str)
{
long int result=0;
for(int i=input_str.size()-1;i>=0;i--)//注意是倒序
{
result+=(input_str[i]=='1'? 1:0)*pow(2,input_str.size()-1-i);//二进制应该是乘2，满2就递增一位
}
return result;
}
int main() {
string input_str1;
long int input_value;
getline(cin,input_str1);
cin>>input_value;
vector<string> group;
string temp;
for(int i=0;i<input_str1.size();i++)
{
if(input_str1[i]=='.')
{
group.push_back(temp);
temp.clear();
}
else {
temp+=input_str1[i];
}
}
//不要漏掉最后一个
group.push_back(temp);
string output_str;
for(int i=0;i<group.size();i++)
{
int temp_value=stoi(group[i]);
string temp_str=tenTobrinary(temp_value);
// 进行加0的操作
int num_zero=8-temp_str.size();
while(num_zero!=0)
{
temp_str='0'+temp_str;
num_zero--;
}
output_str+=temp_str;//全部累加
}
long int result_value=brinaryToten(output_str);
std::cout<<result_value<<std::endl;
//先转为二进制
string input_str2=tenTobrinary(input_value);
int num_zero=32-input_str2.size();
while(num_zero!=0)
{
input_str2='0'+input_str2;//在前面补0
num_zero--;
}
vector<string> group_out;
//然后每8位输出一个group
// 正确处理每8位分组
for(int i = 0; i < input_str2.size(); i += 8)
{
string temp_str = input_str2.substr(i, 8);
group_out.push_back(temp_str);
}
//四组二进制的值
string result_str;
for(int i=0;i<group_out.size();i++)
{
int value=brinaryToten(group_out[i]);
result_str+=to_string(value)+'.';
}
std::cout<<result_str.substr(0,result_str.size()-1);//去掉最后一个点
}
Hash Table相关题目
unordered_map内部的元素是无序的，即插入的顺序和输出的顺序不一定相同。而map内部的元素是有序的，它是按照元素的键值大小进行排序，所以它的内部元素是有序的。
定义
合并表记录
#include <iostream>
#include <map>
using namespace std;
int main() {
int row;
cin>>row;
// 定义一个hash table
// unordered_map<int, int> result_group;//里面存储是无序的
map<int, int> result_group;
int index, value;
while(cin>>index>>value)
{
result_group[index]+=value;
}
for(auto it=result_group.begin();it!=result_group.end();it++)
{
std::cout<<it->first<<" "<<it->second<<std::endl;
}
}
简单密码
关键在于hash table的初始化
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
//初始化定义
unordered_map<char, int> group{
{'a', 2}, {'b', 2}, {'c', 2}, {'d', 3},
{'e', 3}, {'f', 3}, {'g', 4}, {'h', 4},
{'i', 4}, {'j', 5}, {'k', 5}, {'l', 5},
{'m', 6}, {'n', 6}, {'o', 6}, {'p', 7},
{'q', 7}, {'r', 7}, {'s', 7}, {'t', 8},
{'u', 8}, {'v', 8}, {'w', 9}, {'x', 9},
{'y', 9}, {'z', 9}
};
//或者定义两个一一对应的密码表
const string dict1="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string dict2="bcdefghijklmnopqrstuvwxyza22233344455566677778889999";
int main() {
//赋值操作必须放到 main 函数中
// group['a']=2;
// group['b']=2;
// group['c']=2;
// group['d']=3;
// group['e']=3;
// group['f']=3;
// group['g']=4;
// group['h']=4;
// group['i']=4;
// group['j']=5;
// group['k']=5;
// group['l']=5;
// group['m']=6;
// group['n']=6;
// group['o']=6;
// group['p']=7;
// group['q']=7;
// group['r']=7;
// group['s']=7;
// group['t']=8;
// group['u']=8;
// group['v']=8;
// group['w']=9;
// group['x']=9;
// group['y']=9;
// group['z']=9;
string input_str;
getline(cin,input_str);
string out_str;
for(int i=0;i<input_str.size();i++)
{
if(input_str[i]>='A' && input_str[i]<='Z')
{//大写字母则变成小写之后往后移一位
if(input_str[i]=='Z')
{
out_str+='a';
}
else {
out_str+=char ('a'+(input_str[i]-'A'+1));
}
}
else if(input_str[i]>='a' && input_str[i]<='z')
{
out_str+=to_string(group[input_str[i]]);//注意要转换为字符串
}
else
out_str+=input_str[i];//数字和其它的符号都不做变换。
}
std::cout<<out_str;
}
称砝码
一开始是想着用回溯算法去解的，但是复杂度比较高，且剪枝策略不正确，改为hash table来算吧～
#include <iostream>
#include <vector>
#include<unordered_set> //无序集合， 每次加构成的新重量加入集合，集合会自动去重
using namespace std;
int main() {
int num;//多少种砝码
cin >> num;
vector<int> weight;//每种的重量
for (int i = 0; i < num; i++) {
int value;
cin >> value;
weight.push_back(value);
}
vector<int> num_each_wight;//每种重量的个数
for (int i = 0; i < num; i++) {
int value;
cin >> value;
num_each_wight.push_back(value);
}
unordered_set<int> result_set;//hash table用于去重
result_set.insert(0);//先插入0，0也是一种结果
//遍历各种砝码
for(int n=0;n<num;n++)
{
int num_of_current_weight=num_each_wight[n];
int currrent_weight=weight[n];
//当前重量的数量用完前
for(int i=1;i<=num_of_current_weight;i++)
{
auto temp=result_set;//注意由于下面要使用，此处应该copy一份来遍历
for(auto it=temp.begin();it!=temp.end();it++)
{
result_set.insert(*it+currrent_weight);//遍历当前插入的结果，分别加当前的砝码。反正去重了
}
}
}
std::cout<<result_set.size()<<std::endl;
}
hash table的思维，vector的解法：名字的漂亮度
此题是hash table的思维，但是hash table不好进行排序，因此用vector代替，对应位置each_string[each_char-'a']填入即可实现计数
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int num;
cin>>num;
string temp;
vector<string> input_group;
for(int i=0;i<num;i++)
{
cin>>temp;
input_group.push_back(temp);
}
for(int i=0;i<num;i++)
{
//采用hash table计算每个字母的数目，但是不好进行排序
// 且仅由小写字母组成。为此可以用vector代替
vector<int> each_string (26,0);
string input_str=input_group[i];
for(auto each_char:input_str)
{
each_string[each_char-'a']++;
}
sort(each_string.begin(),each_string.end());
int result_value=0;
for(int i=25;i>=0;i--)
{
if(each_string[i]==0)
break;//由于是递减，后续都为空的啦
result_value+=each_string[i]*(i+1);//分数就是最大26，依次跟着i递减
}
std::cout<<result_value<<std::endl;
}
}
set与map自动升值排列：整型数组合并
两种解法均可～
#include <iostream>
#include <map>
#include <set>
using namespace std;
int main() {
// map<int, int>input_group;//自动按照key排序了
set<int> input_group;//也是按key顺序排序的
int n1,n2;
int temp;
cin>>n1;
while(n1--)
{
cin>>temp;
// input_group[temp]++;
input_group.insert(temp);
}
cin>>n2;
while(n2--)
{
cin>>temp;
// input_group[temp]++;
input_group.insert(temp);
}
for(auto it=input_group.begin();it!=input_group.end();it++)
std::cout<<*it;
}
set通过.count(each_str)来代替find寻值：字符串字符匹配
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
string str1,str2;
cin>>str1>>str2;
// 注意是均出现过，而不是寻找一样顺序的
set<char> gruop;
for(auto each_str:str1)
gruop.insert(each_str);
for(auto each_str:str2)
{
if(find(gruop.begin(),gruop.end(),each_str)!=gruop.end())
gruop.erase(each_str);//能找到就删掉
}
if(gruop.empty())
std::cout<<"true";//都能找到
else
std::cout<<"false";
}
// 64 位输出请用 printf("%lld")
,第二种解法其实就是换个思路，感觉差不多～
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int main() {
string str1,str2;
cin>>str2>>str1;
if(str1.size()<str2.size())
swap(str1,str2);//保证1为长序列。
// 注意是均出现过，而不是寻找一样顺序的
set<char> gruop;
for(auto each_str:str1)
gruop.insert(each_str);
//若短序列中出现了长序列没有出现的字符，那么就是短字符串的有字符未在长字符串中出现过
bool flag=true;
for(auto each_str:str2)
{
if(!gruop.count(each_str))//没找到
{
flag=false;
break;
}
}
if(flag)
std::cout<<"true";//都能找到
else
std::cout<<"false";
}
将map转换为vector进行排序：字符统计
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
bool comparefunction(pair<char,int>a, pair<char,int>b)
{
if (a.second == b.second) { //当出现次数相同时
return a.first < b.first; //输出ASCII码较小的字符
}
return a.second > b.second;
}
int main() {
string input_str;
cin>>input_str;
map<char,int> group;//map会自动按照key值排序
for(int i=0;i<input_str.size();i++)
{
group[input_str[i]]++;
}
// 将 map 的内容复制到 vector 中
vector<pair<char, int>> copy_group(group.begin(), group.end());//初始化一个vector数组
sort(copy_group.begin(),copy_group.end(),comparefunction);
for(auto each:copy_group)
{
std::cout<<each.first;
}
}
其他string相关的题目
字符串最后一个单词的长度
，trick：输入为空格的时候就停止输入
#include <iostream>
#include <string>
using namespace std;
int main() {
string input_str;
while (cin >> input_str) { //不停的输入，遇到空格会中断，下次再输入，因此最终保留是最后一个
}
std::cout<<input_str.size()<<std::endl;
}
// 64 位输出请用 printf("%lld")
计算某字符出现次数
注意不区分大小写，需要调用tolower（）函数转换成小写。时间复杂度为O（N），空间复杂度为O（1）
#include <iostream>
#include <string>
using namespace std;
int main() {
string input_str;
getline(cin,input_str);//获取一整行
char target;
cin >> target;
target=tolower(target);//不区分大小写
int num_result=0;
for(char _str:input_str)
{
if(tolower(_str)==target)//不区分大小写
num_result++;
}
std::cout<< num_result<<std::endl;
}
下面方法采用hash table，也可以，但是空间复杂度应该是O（N），时间复杂度一样
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
string input_str;
getline(cin,input_str);//获取一整行
char target;
cin >> target;
target=tolower(target);//不区分大小写
unordered_map<char, int> input_group;
for(char _str:input_str)
{
input_group[tolower(_str)]++;
}
std::cout<< input_group[target]<<std::endl;
}
明明的随机数
此题的关键是set的使用
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> input_group;//set默认自动排序，从小到大
int totally_num;
cin>>totally_num;//输入的总的数字数目
int input_value;
while (cin >> input_value) {
input_group.insert(input_value);//插入，自动排序
}
// 注意set的使用是需要指针取值的
for(auto it=input_group.begin();it!=input_group.end();it++)
std::cout<<*it<<std::endl;
}
// 更多关于set容器的使用：
// begin() ,返回set容器的第一个元素
// end() ,返回set容器的最后一个元素
// clear() ,删除set容器中的所有的元素
// empty() ,判断set容器是否为空
// max_size() ,返回set容器可能包含的元素最大个数
// size() ,返回当前set容器中的元素个数
字符串分隔
#include <iostream>
#include <string>
using namespace std;
int main() {
string input_str;
while(cin>> input_str)
{
string temp;
for(int i=0;i<input_str.size();i++)
{
if(temp.size()==8)//等于8
{
std::cout<<temp<<std::endl;//输出
temp.clear();//清空
}
temp+=input_str[i];
}
if(temp.size()!=0)//也就是最后还有
{
while(temp.size()!=8)
temp+='0';//一直添加0
std::cout<<temp<<std::endl;//输出
}
}
}
// 64 位输出请用 printf("%lld")
提取不重复的整数
#include <iostream>
#include <string>
using namespace std;
int main() {
string input_str, result_str;
getline(cin,input_str);
int a[10]={0};//用于记录当前值是否出现（用数组代替set或map）
for(int i=input_str.size()-1;i>=0;i--)//注意从右到左阅读
{
if(a[(input_str[i]-'0')]==0)
{
result_str+=input_str[i];
a[(input_str[i]-'0')]++;
}
}
std::cout<<result_str;
}
string颠倒：数字颠倒
#include <iostream>
#include <string>
#include <algorithm> //调用reverse
using namespace std;
int main() {
string input_str;
cin>>input_str;
reverse(input_str.begin(),input_str.end());
std::cout<<input_str;
}
字符串排序
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string input_str;
vector<string> group;
int row;
cin>>row;
while(cin>>input_str)
{
group.push_back(input_str);
}
sort(group.begin(),group.end());
for(auto temp:group)
{
std::cout<<temp<<std::endl;
}
}
这题难度要大很多，关键是构建一个vector，先按字母的顺序存放字母。然后当遇到字母的时候，再次从vector中拿出来（对于同字母的大小写，按输入的顺序进行放入，也按输入的顺序进行取出）。注意通过处理原输入，可以避免处理其他不变的情况
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string input_str;
getline(cin,input_str);
vector<char> group;//存放着26个字母
for(int i=0;i<26;i++)//对应26个字母，按先后顺序存放
{
for(int j=0;j<input_str.size();j++)
{
//不区分大小写，进而实现了先出现，先存放
if((input_str[j]-'a'==i) || (input_str[j]-'A'==i))//对应的位置上存字母
group.push_back(input_str[j]);
}
}
for(int i=0, k=0; i<input_str.size(), k<group.size();i++)
{
//对应字母的位置取值，其他位置不变~
if(
(input_str[i]>='a' && input_str[i]<='z')
||(input_str[i]>='A' && input_str[i]<='Z')
)
{
// 是字母，则优先填上面i值小的，也就是位于更前的字母
input_str[i]=group[k];
k++;//下次就填下一个
}
}
std::cout<<input_str;//直接在输入的基础上修改，这样就可以只处理字母的情况
}
字符串：坐标移动
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string input_str;
getline(cin,input_str);
vector<string> group;
string temp_str;
for(int i=0;i<input_str.size();i++)
{
if(input_str[i]==';')//分割
{
//判断是否合法
if(temp_str.size()<=3)//三位以内
{
group.push_back(temp_str);
}
temp_str.clear();
continue;//当前跳过
}
temp_str+=input_str[i];
}
int x=0,y=0;//也可以用一个数组来存。int XY[2] = {0, 0};
for(int i=0;i<group.size();i++)
{
string temp_str=group[i];
int temp_value=0;
if (temp_str.size()==2 && temp_str[1]>='0' && temp_str[1]<='9')
{
temp_value=temp_str[1]-'0';
}
else if(temp_str.size()==3 && temp_str[1]>='0' && temp_str[1]<='9' && temp_str[2]>='0' && temp_str[2]<='9')
{
temp_value=(temp_str[1]-'0')*10+(temp_str[2]-'0');
}
if(temp_value!=0)
{
if(temp_str[0]=='A')
x=x-temp_value;
else if(temp_str[0]=='D')
x=x+temp_value;
else if(temp_str[0]=='W')
y=y+temp_value;
else if(temp_str[0]=='S')
y=y-temp_value;
}
}
std::cout<<x<<","<<y;
}
密码验证合格程序
#include <iostream>
#include <string>
using namespace std;
int main() {
string input_str;
while(cin>>input_str)
{
//条件1:长度超过8位
if(input_str.size()<=8)
{
std::cout<<"NG"<<std::endl;
continue;//长度小于8直接跳出，执行下一次
}
// 条件2：包括大小写字母.数字.其它符号,以上四种至少三种
int big=0, small=0, num=0, other=0;
for(int i=0;i<input_str.size();i++)
{
if(input_str[i]>='a' && input_str[i]<='z')
small=1;
else if(input_str[i]>='A' && input_str[i]<='Z')
big=1;
else if(input_str[i]>='0' && input_str[i]<='9')
num=1;
else if (input_str[i]!=' ')
other=1;////其他情况且不为空格
if((big+small+num+other)>=3)
break;//满足就退出当前循环
}
if((big+small+num+other)<3)
{
std::cout<<"NG"<<std::endl;
continue;//不满足条件2，执行下一次
}
// 条件3:不能有长度大于2的包含公共元素的子串重复
bool repeat_flag=false;
// 下面更直接简单
// for(int i=0;i<input_str.size()-3;i++)
// {
// string sub_1=input_str.substr(i,3);
// string sub_2=input_str.substr(i+3,input_str.size()-(i+3));
// if(sub_2.find(sub_1)!=string::npos)
// {
// repeat_flag=true;
// break;
// }
// }
for(int i=0;i<input_str.size()-6;i++)
{
string sub_i=input_str.substr(i,3);
for(int j=i+3;j<input_str.size()-3;j++)
{
string sub_j=input_str.substr(j,3);
if(sub_i==sub_j)
{
repeat_flag=true;
break;
}
}
// string sub_str=input_str.substr(i,3);//大于2，就是3啦～
// if(input_str.find(sub_str)!=input_str.npos)//找到了。不能用find因为全部找必然找到。。。。
// {
// repeat_flag=true;
// break;
// }
}
if(repeat_flag)
{
std::cout<<"NG"<<std::endl;
continue;//不满足条件2，执行下一次
}
std::cout<<"OK"<<std::endl;
}
}
删除字符串中出现次数最少的字符
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
string input_str;
cin>>input_str;
unordered_map<char, int> group;
for(int i=0;i<input_str.size();i++)
{
group[input_str[i]]++;
}
int min_value=input_str.size();
//要用迭代器来遍历
for(auto it=group.begin();it!=group.end();it++)
{
min_value=min(min_value,it->second);
}
string result;
for(int i=0;i<input_str.size();i++)
{
if(group[input_str[i]]!=min_value)
result+=input_str[i];
}
std::cout<<result;
}
查找兄弟单词
时间复杂度：O(nlogm)，其中n为单词总数，m为最大单词的长度。logm为排序算法的复杂度。空间复杂度是O（N）注意最后一个单词才是目标，审题最重要！！！
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin>>N;
string temp_str;
int i=0;
vector<string> input_group;
while(cin>>temp_str)//遇到空格会停下来
{
input_group.push_back(temp_str);
i++;
if (i==N+1)
break;//字符满了
}
int index;
cin>>index;//按照字典顺序排序后的第k个兄弟单词
string target=input_group[N];//最后一个就是target
string sort_target=input_group[N];
sort(sort_target.begin(),sort_target.end());
vector<string> result_group;
//遍历
for(int i=0;i<input_group.size()-1;i++)//不找最后一个
{
string temp=input_group[i];
if(temp==target)
continue;//一模一样的，不是兄弟词
if(temp.size()!=target.size())//size不一样的也不是
continue;
string sort_temp=input_group[i];
sort(sort_temp.begin(),sort_temp.end());
if(sort_temp==sort_target)//排序后一样
result_group.push_back(temp);
}
std::cout<<result_group.size()<<std::endl;
if(index<result_group.size())
{
sort(result_group.begin(),result_group.end());
std::cout<<result_group[index-1];
}
}
字符串加解密
注意循环中用else if不然就会一直处理，一直叠加。
#include <iostream>
#include <string>
using namespace std;
int main() {
string input_str1, input_str2;
cin>>input_str1;
cin>>input_str2;
for(int i=0;i<input_str1.size();i++)
{
if(input_str1[i]>='0' && input_str1[i]<='9')
{
if(input_str1[i]=='9')
input_str1[i]='0';
else
input_str1[i]=char( (input_str1[i]-'0'+1)+'0');
}
else if(input_str1[i]>='a' && input_str1[i]<='z')
{
if(input_str1[i]=='z')
input_str1[i]='A';
else
input_str1[i]=char( (input_str1[i]-'a'+1)+'A');
}
else if(input_str1[i]>='A' && input_str1[i]<='Z')
{
if(input_str1[i]=='Z')
input_str1[i]='a';
else
input_str1[i]=char( (input_str1[i]-'A'+1)+'a');
}
}
for(int i=0;i<input_str2.size();i++)
{
if(input_str2[i]>='0' && input_str2[i]<='9')
{
if(input_str2[i]=='0')
input_str2[i]='9';
else
input_str2[i]=char( (input_str2[i]-'0'-1)+'0');
}
else if(input_str2[i]>='a' && input_str2[i]<='z')
{
if(input_str2[i]=='a')
input_str2[i]='Z';
else
input_str2[i]=char( (input_str2[i]-'a'-1)+'A');
}
else if(input_str2[i]>='A' && input_str2[i]<='Z')
{
if(input_str2[i]=='A')
input_str2[i]='z';
else
input_str2[i]=char( (input_str2[i]-'A'-1)+'a');
}
}
std::cout<<input_str1<<std::endl<<input_str2;//直接返回就避免了其他字符的改变了
}
字符串反转
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string input_str;
getline(cin,input_str);
vector<string> group_str;
string temp="";
for(int i=0;i<input_str.size();i++)
{
if(input_str[i]>='a' && input_str[i]<='z'
|| input_str[i]>='A' && input_str[i]<='Z' )
{
temp+=input_str[i];
}
else if(!temp.empty())//且不为空
{
group_str.push_back(temp);
temp.clear();
}
}
//最后一个也放入
if(!temp.empty())//且不为空
{
group_str.push_back(temp);
temp.clear();
}
for(int i=group_str.size()-1;i>=0;i--)
std::cout<<group_str[i]<<" ";
}
字符串相乘
这个解法相对比较直接，就是把乘法的计算过程跟加的过程用代码实现了～
class Solution {
public:
string addstring(string num1, string num2) {
if(num1.size()<num2.size())
swap(num1,num2);//确保1为最长的
// 倒序
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
int temp=0;//记录进位
string output_str;
for(int i=0;i<num1.size();i++)
{
if(i<num2.size())
{
int num1_val=int (num1[i]-'0');
int num2_val=int (num2[i]-'0');
int value=num1_val+num2_val+temp;
temp=value/10;//整除10记录进位
output_str+=('0'+value%10);//余数为个位
}
else if(temp!=0)
{
int num1_val=int (num1[i]-'0');
int value=num1_val+temp;
temp=value/10;//整除10记录进位
output_str+=('0'+value%10);//余数为个位
}
else
output_str+=num1[i];
}
if(temp != 0)
output_str += ('0' + temp); // 处理最高位的进位
reverse(output_str.begin(),output_str.end());//最后记得倒序
return output_str;
}
string multiply(string num1, string num2) {
if(num1.size()<num2.size())
swap(num1,num2);//确保2为短的
// 倒序
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end());
int temp=0;//记录进位
string output_str="0";
for(int i=0;i<num2.size();i++)
{
if(num2[i]!='0')
{
string current_result;
for(int j=0;j<num1.size();j++)
{ //num1*num2
int num2_val=int (num2[i]-'0');
int num1_val=int (num1[j]-'0');
int value=num1_val*num2_val+temp;
temp=value/10;//整除10记录进位
current_result+=('0'+value%10);//余数为个位
}
while(temp!=0)//若进位不为0
{
int value=temp;
temp=value/10;//整除10记录进位
current_result+=('0'+value%10);//余数为个位
}
reverse(current_result.begin(),current_result.end());
int num_zero=i;
while(num_zero)
{
current_result+='0';
num_zero--;
}
output_str=addstring(output_str,current_result);
}
}
return output_str;
}
};
也可以采用下图所示的双指针法的思路解题。时间复杂度为O（n*m），空间复杂度为O（n+m）
|
|
class Solution {
public:
string multiply(string num1, string num2) {
int size_1=num1.size();
int size_2=num2.size();
vector<int> result(size_1+size_2,0);//两数相乘的结果最大位数为num1.size()+num2.size()
for(int i=num1.size()-1;i>=0;i--)//从最小位开始
{
for(int j=num2.size()-1;j>=0;j--)
{
int temp_value=(num1[i]-'0')*(num2[j]-'0');
//存放的位置应该也是逆着看的，为此小的是十位，大的是个位
int shiwei=i+j;
int gewei=i+j+1;
temp_value+=result[gewei];//当前的值+当前个位处的值
result[gewei]=temp_value%10;//进位后剩余的（此处的个位已经用了～）
result[shiwei]+=temp_value/10; //进位的数目+当前十位的值
}
}
// 接下来将result转为string
bool flag=false;//直到遇到第一个非零
string result_str;
for(int i=0;i<result.size();i++)
{
if(result[i]!=0 && flag==false)//去掉第一个0
flag=true;
if(flag==true)
result_str+=to_string(result[i]);
}
if (result_str.empty())//那么结果就是0
return "0";
return result_str;
}
};
用python的eval函数求解就无敌简单😱
class Solution:
def multiply(self, num1: str, num2: str) -> str:
str_all=num1+'*'+num2
return str(eval(str_all))
python求解字符串的四则运算
此题如果用cpp去解的话有点繁琐，为此改为用python，几句代码即可！
# Python2
# raw_input( ) 将所有输入作为字符串看待，返回字符串类型。
# input( ) 只能接收"数字"的输入，在对待纯数字输入时具有自己的特性，它返回所输入的数字的类型（ int, float ）。
# 在 Python3.x 中 raw_input( ) 和 input( ) 进行了整合，去除了 raw_input( )，仅保留了 input( ) 函数，其接收任意任性输入，将所有输入默认为字符串处理，并返回字符串类型。
input_str = input()
# 把其中的不规则括号都变为普通括号
input_str.replace("[", "(")
input_str.replace("{", "(")
input_str.replace("]", ")")
input_str.replace("}", ")")
# eval是Python的一个内置函数，功能十分强大，这个函数的作用是，返回传入字符串的表达式的结果。就是说：将字符串当成有效的表达式 来求值 并 返回计算结果。
result=eval(input_str)#返回传入字符串的表达式的结果
print(result)
# print(str(result))
同理，上面字符串相乘也是可以类似的用
用python解题，三行代码即可！
input_str=input()
result=eval(input_str)
print(str(result))
高精度整数加法
最简单就是采用python解题～
str1=input()
str2=input()
str3=str1+'+'+str2
result=eval(str3)
print(str(result))
此处也给出cpp的解法,处理好进位以及字符串的反转即可～
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int main() {
string str1, str2, result_str;
cin>>str1>>str2;
if(str1.size()<str2.size())
swap(str1,str2);//保证str1是最长的
//先反转过来
reverse(str1.begin(),str1.end());
reverse(str2.begin(),str2.end());
int temp_jinwei=0;
for(int i=0;i<str2.size();i++)
{
int temp_value=(str1[i]-'0')+(str2[i]-'0')+temp_jinwei;
result_str+=('0'+temp_value%10);//进位后余值
temp_jinwei=temp_value/10;//进位
}
if(str1.size()>str2.size())
{
for(int i=str2.size();i<str1.size();i++)
{
int temp_value=(str1[i]-'0')+temp_jinwei;
result_str+=('0'+temp_value%10);//进位后余值
temp_jinwei=temp_value/10;//进位
}
}
while(temp_jinwei!=0)
{
int temp_value=+temp_jinwei;
result_str+=('0'+temp_value%10);//进位后余值
temp_jinwei=temp_value/10;//进位
}
reverse(result_str.begin(),result_str.end());
std::cout<<result_str;
}
蛇形矩阵
关键是如何填矩阵的思路～
#include <iostream>
#include <vector>
using namespace std;
int main() {
int input_value;
cin>>input_value;
//直接创建一个矩阵来遍历
vector< vector <int>> matrix (input_value,vector<int>(input_value,0));
int value=1;
for(int k=0;k<input_value;k++)//k决定了每次x从哪里开始
{
int y=0;
for(int x=k;x>=0;x--)//每次x减小
{
matrix[x][y]=value;
value++;
y++;//每次y必然增加
}
}
for(int i=0;i<input_value;i++)
{
for(int j=0;j<input_value;j++)
{
if(matrix[i][j]!=0)
std::cout<<matrix[i][j]<<" ";
}
std::cout<<std::endl;
}
}
挑7
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int range;
cin>>range;
int result_num=0;
for(int i=1;i<=range;i++)//注意从1开始
{
if(i%7==0)//可以整除7，注意不要考虑0的情况
result_num++;
else
{
string temp=to_string(i);
if(find(temp.begin(),temp.end(),'7')!=temp.end())//找到了
result_num++;
}
}
std::cout<<result_num;
}
查找两个字符串a,b中的最长公共子串
关键点是字符串中找子字符串的用法str_2.find(temp_str)!=string::npos
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
string str_1, str_2;
cin>>str_1>>str_2;
if(str_1.size()>str_2.size())
swap(str_1,str_2);//确保str_1是短的序列
string result_str;
//从最长的开始选（要用size_t而不是int）
for(size_t len=str_1.size(); len>=0; len--)
{
for(int i=0;i<=(str_1.size()-len);i++)
{
string temp_str=str_1.substr(i,len);
if(str_2.find(temp_str)!=string::npos)//找到了,注意找字符串与找字节不一样
// find(str_2.begin(),str_2.end(),char);
{
std::cout<<temp_str;
return 0;
}
}
}
}
成绩排序
stable_sort 和 sort的区别在于 前者作排序可以使原来的”相同”的值在序列中的相对位置不变
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool high_to_low(pair<string, int> g1, pair<string, int> g2) {
return g1.second > g2.second;
}
bool low_to_high(pair<string, int> g1, pair<string, int> g2) {
return g1.second < g2.second;
}
int main() {
int n, flag;
vector<pair<string, int>> group;
while (cin >> n >> flag) {
for (int i = 0; i < n; i++) {
string name;
// getline(cin, name);//获取一整行，所以出错了
int value;
// cin >> value;
cin >> name >> value;
auto temp=make_pair(name, value);
group.push_back(temp);
}
if (flag) //1表示从低到高
//要用stable_sort,不然分数相同可能排序不对：
// stable_sort 和 sort的区别在于 前者作排序可以使原来的"相同"的值在序列中的相对位置不变
stable_sort(group.begin(), group.end(), low_to_high);
else
stable_sort(group.begin(), group.end(), high_to_low);
for (int i = 0; i < n; i++) {//输出成绩单
cout << group[i].first << " " << group[i].second << endl;
}
}
}
// #include<iostream>
// #include<string>
// #include<vector>
// #include<algorithm>
// using namespace std;
// struct user {//用户结构
// string name;//姓名
// int score;//分数
// };
// bool compare0(user a, user b) {
// return a.score > b.score ;
// }
// bool compare1(user a, user b) {
// return a.score < b.score;
// }
// int main() {
// int n, flag;
// while (cin >> n >> flag) {
// vector<user> userForm;
// for (int i = 0; i < n; i++) {//输入成绩单
// user temp;
// cin >> temp.name >> temp.score ;
// userForm.push_back(temp);
// }
// if (flag) { //从低到高排序
// stable_sort(userForm.begin(), userForm.end(), compare1);//重载稳定排序
// } else { //从高到低排序
// stable_sort(userForm.begin(), userForm.end(), compare0);//重载稳定排序
// }
// for (int i = 0; i < n; i++) {//输出成绩单
// cout << userForm[i].name << " " << userForm[i].score << endl;
// }
// }
// return 0;
// }
在字符串中找出连续最长的数字串
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool Comparefunction(string a, string b)
{
return a.size()>b.size();
}
int main() {
string input_str;
while(cin>>input_str)
{
vector<string> group;
string temp;
for(int i=0;i<input_str.size();i++)
{
if(input_str[i]>='0' && input_str[i]<='9')//为数字
{
temp+=input_str[i];
}
else//不为数字
{
if(!temp.empty())//且不为空
{
group.push_back(temp);
temp.clear();//清空
}
}
}
//不要漏掉最后一个
if(!temp.empty())//且不为空
{
group.push_back(temp);
temp.clear();//清空
}
sort(group.begin(),group.end(),Comparefunction);//排序
for(int i=0;i<group.size();i++)
{
if(group[i].size()==group[0].size())//长度一样
std::cout<<group[i];
}
std::cout<<","<<group[0].size()<<std::endl;
}
}
自守数
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int N;
cin>>N;
int num_count=0;
for(int i=0;i<=N;i++)
{
int temp_value=pow(i,2);//获取它的平方
string str_i=to_string(i);//当前数转换为字符
string str_temp=to_string(temp_value);//平方数转换为字符
//判断尾数是否相同
bool flag=true;
for(int i=0;i<str_i.size();i++)
{
if(str_i[i]!=str_temp[str_temp.size()-str_i.size()+i])
{
flag=false;//有不等就是false
}
}
if(flag)//最终都是相同的
num_count++;
}
std::cout<<num_count;
}