常规题 | 昔人已乘黄鹤去此地空余黄鹤楼

1素数回文

描述
现在给出一个素数，这个素数满足两点：

只由1-9组成，并且每个数只出现一次，如13,23,1289。
位数从高到低为递减或递增，如2459，87631。

请你判断一下，这个素数的回文数是否为素数（13的回文数是131,127的回文数是12721）。

输入描述：
输入只有1行。
第1行输入一个整数t，保证t为素数。
数据保证：9<t<109

输出描述：
输出一行字符串，如果t的回文数仍是素数，则输出“prime”，否则输出”noprime”。

解答

#include <iostream>
#include <algorithm>
using namespace std;
bool isPrime(long long num){
    if(num<2) return false;
    for(long long i=2;i*i<=num;i++){
        if(num%i==0) return false;
    }
    return true;
}
int main() {
    string t;
    cin>>t;
    string tmp=t;
    reverse(tmp.begin(),tmp.end());
    tmp.erase(tmp.begin());
    t+=tmp;
    long long ret=atol(t.c_str());
    if (isPrime(ret)) {
        cout<<"prime"<<endl;
    }else {
        cout<<"noprime"<<endl;
    }
    return 0;
}

2活动安排

描述
给定 n 个活动，每个活动安排的时间为[ai,bi)
求最多可以选择多少个活动，满足选择的活动时间两两之间没有重合。

输入描述：
第一行输入一个整数
n (1 ≤ n ≤ 2*10^5)，表示可选活动个数。
接下来的 n 行，每行输入两个整数 ai , bi(0 ≤ ai <bi ≤ 10^ 9 )，表示第 i 个活动的时间。

输出描述：
输出一行一个整数，表示最多可选择的活动数。

解答

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity{
    int start;
    int end;
};
bool compare(Activity a,Activity b){
    return a.end<b.end;
}
int main() {
    int n;
    cin>>n;
    vector<Activity> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i].start>>arr[i].end;
    }
    sort(arr.begin(),arr.end(),compare);
    int count=1;
    int prevEnd=arr[0].end;
    for(int i=1;i<n;i++){
        if(arr[i].start>=prevEnd){
            count++;
            prevEnd=arr[i].end;
        }
    }
    cout<<count<<endl;
    return 0;
}

在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，
所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，
然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。
给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。

测试样例：

1	4,[0,7,1,6],[1,5,0,6]

1	返回：10(解释：可以左手手套取2只，右手手套取8只)

思路：

如果某个颜色没有手套，就必须得把该颜色对应的另一边手套累加起来。
先计算出左手和右手手套的总数，然后减去各自的最少的数再加一
这样就可以保证取出的手套至少每种都有一只
计算总数的时候，要找出手套数量最少的那个颜色
比较两者较小的那个数，决定先取左手还是先取右手
最后再加上另一种手套的一只就行
当左右手中存在手套为零时，可以进行“忽略”

解答

class Gloves {
  public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        // write code here
        int leftsum = 0, leftmin = INT_MAX, rightsum = 0, rightmin = INT_MAX;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (left[i] == 0 || right[i] == 0) {
                ans += left[i] + right[i];
            } else {
                leftsum += left[i];
                leftmin = min(leftmin, left[i]);
                rightsum += right[i];
                rightmin = min(rightmin, right[i]);
            }
        }
        ans += min(leftsum - leftmin + 1, rightsum - rightmin + 1) + 1;
        return ans;
    }
};

4有假币

居然有假币！现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，
结果找来的零钱中有假币！！！可惜nowcoder 一不小心把它混进了一堆真币里面去了。
只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），
请用最快的时间把那个可恶的假币找出来。

输入描述:

1	1≤n≤2^30,输入0结束程序。

输出描述:

1	最多要称几次一定能把那个假币找出来？

思路：
平均分三份是最快的方法，两份进行称重（对比出三个的重量），后对最重的那份再次进行称重，
直到称重的个数不足2个时则结束，获得假币如果无法平均分3分则余数要么是1要么是2，
因为是要最多称几次，n=n/3+1 满足每次取最大分称3份，取两份一样多的过秤，
然后把三份中最多的那份继续分，直到硬币剩余0或1时截至

解答

#include <iostream>
using namespace std;

int main() {
    long long n;
    while(cin>>n){
        int count=0;
        if(n==0){
            break;
        }
        while(n>=2){
            if(n%3){
                n=n/3+1;
                count++;
            }else {
                n/=3;
                count++;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

5逆波兰表达式求值

根据逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

经典后序遍历

class Solution {
public:
    bool isNumber(string ch){
        return !(ch=="+"||ch=="-"||ch=="*"||ch=="/");
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int n=tokens.size();
        for(int i=0;i<n;i++){
            string tmp=tokens[i];
            if(isNumber(tmp)){
                st.push(atoi(tmp.c_str()));
            }else{
                int num2=st.top();
                st.pop();
                int num1=st.top();
                st.pop();
                switch(tmp[0]){
                    case '+':
                        st.push(num1+num2);
                        break;
                    case '-':
                        st.push(num1-num2);
                        break;
                    case '*':
                        st.push(num1*num2);
                        break;
                    case '/':
                        st.push(num1/num2);
                        break;
                }
            }
        }
        return st.top();
    }
};

6电话号码

描述

上图是一个电话的九宫格，如你所见一个数字对应一些字母，因此在国外企业喜欢把电话号码设计成与自己公司名字相对应。
例如公司的Help Desk号码是4357，因为4对应H、3对应E、5对应L、7对应P，因此4357就是HELP。
同理，TUT-GLOP就代表888-4567、310-GINO代表310-4466。
NowCoder刚进入外企，并不习惯这样的命名方式，现在给你一串电话号码列表，请你帮他转换成数字形式的号码，并去除重复的部分。

输入描述：
输入包含多组数据。
每组数据第一行包含一个正整数n（1≤n≤1024）。
紧接着n行，每行包含一个电话号码，电话号码仅由连字符“-”、数字和大写字母组成。
没有连续出现的连字符，并且排除连字符后长度始终为7（美国电话号码只有7位）。

输出描述：
对应每一组输入，按照字典顺序输出不重复的标准数字形式电话号码，即“xxx-xxxx”形式。
每个电话号码占一行，每组数据之后输出一个空行作为间隔符。

注意去重
不采取数组的方式存储数据，采用循环每次处理一个号码 isdigit isupper

解答

#include <cctype>
#include <iostream>
#include <set>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    string alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string num=  "22233344455566677778889999";
    unordered_map<char, char> map;
    for(int i=0;i<26;i++){
        map[alpha[i]]=num[i];
    }
    set<string> set;
    int n;
    while(cin>>n){
        set.clear();
        for(int i=0;i<n;i++){
            string line;
            cin>>line;
            string ans;
            for(auto ch:line){
                if(isdigit(ch)){
                    ans+=ch;
                }else if(isupper(ch)){
                    ans+=map[ch];
                }
            }
            ans=ans.substr(0,3)+"-"+ans.substr(3);
            set.insert(ans);
        }
        for(auto str:set){
            cout<<str<<endl;
        }
        cout<<endl;
    }
    return 0;
}

7查找兄弟单词

描述

定义一个单词的“兄弟单词”为：交换该单词字母顺序（注：可以交换任意次），而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如： ab 和 ba 是兄弟单词。 ab 和 ab 则不是兄弟单词。
现在给定你 n 个单词，另外再给你一个单词 x ，让你寻找 x 的兄弟单词里，按字典序排列后的第 k 个单词是什么？
注意：字典中可能有重复单词。

数据范围： 1≤n≤1000 ，输入的字符串长度满足 1≤len(str)≤10 ， 1≤k<n

输入描述：

输入只有一行。先输入字典中单词的个数n，再输入n个单词作为字典单词。然后输入一个单词x 最后后输入一个整数k

输出描述：

第一行输出查找到x的兄弟单词的个数m 第二行输出查找到的按照字典顺序排序后的第k个兄弟单词，没有符合第k个的话则不用输出。

将字典中的单词先放到 vector 中
将 vector 进行排序
isBrother 函数依次判定每个输入的单词是否是兄弟单词
判定兄弟单词的规则是 : 先判定长度;如果长度相同, 再看是否是完全相同(完全相同不算兄弟);然后将两个单词排序, 排序相同才是真兄弟单词.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isBrother(string str1,string str2){
    if(str1==str2) return false;
    if(str1.length()!=str2.length()) return false;
    sort(str1.begin(),str1.end());
    sort(str2.begin(),str2.end());
    return str1==str2;
}

int main() {
    int n;
    cin>>n;
    vector<string> arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    string dict;
    cin>>dict;
    int k;
    cin>>k;
    int count=0;
    string ans="";
    sort(arr.begin(),arr.end());
    for(int i=0;i<n;i++){
        if(isBrother(arr[i], dict)){
            count++;
            if(count==k){
                ans=arr[i];
            }
        }
    }
    cout<<count<<endl;
    if(count>=k){
        cout<<ans<<endl;
    }
    return 0;
}

模板
一类是有前置或者后置空格的，另一类是没有前置和后置空格的。
1、如果有前后置空格，那么必须判断临时字符串非空才能输出，否则会输出空串

s += " "; //这里在最后一个字符位置加上空格，这样最后一个字符串就不会遗漏
string temp = "";  //临时字符串
vector<string> res; //存放字符串的数组
for (char ch : s)  //遍历字符句子
{
    if (ch == ' ') //遇到空格
    {
        if (!temp.empty()) //临时字符串非空
        {
            res.push_back(temp);
            temp.clear();  //清空临时字符串
        }
    }
    else
        temp += ch; 
}

2、没有前后置的空格不需要判断空串

s += " ";
    string temp = "";
    vector<string> res;
    for (char ch : s)
    {
        if (ch == ' ')
        {
            res.push_back(temp);
            temp.clear();
        }
        else
            temp += ch;
    }

8单词倒排

描述

对字符串中的所有单词进行倒排。

说明：

构成单词的字符只有26个大写或小写英文字母；
非构成单词的字符均视为单词间隔符；
要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
每个单词最长20个字母；

数据范围：字符串长度满足 1≤n≤10000

输入描述：

输入一行，表示用来倒排的句子

输出描述：

输出句子的倒排结果

#include <cctype>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    string str;
    getline(cin,str);
    for(auto& ch:str){
        if(!isalpha(ch)){
            ch=' ';
        }
    }
    stringstream ss;
    ss<<str;
    vector<string> ans;
    while(ss>>str){
        ans.push_back(str);
    }
    for(int i=ans.size()-1;i>0;i--){
        cout<<ans[i]<<" ";
    }
    cout<<ans[0]<<endl;
    return 0;
}

9螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

从左往右从上往下从右往左从下往上

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size()==0){
            return {};
        }
        int l=0,r=matrix[0].size()-1,t=0,b=matrix.size()-1;
        vector<int> ans;
        while(true){
            //从左往右
            for(int i=l;i<=r;i++) ans.push_back(matrix[t][i]);
            if(++t>b) break;
            //从上往下
            for(int i=t;i<=b;i++) ans.push_back(matrix[i][r]);
            if(--r<l) break;
            //从右往左
            for(int i=r;i>=l;i--) ans.push_back(matrix[b][i]);
            if(--b<t) break;
            //从下往上
            for(int i=b;i>=t;i--) ans.push_back(matrix[i][l]);
            if(++l>r) break;
        }
        return ans;
    }
};

10划分数组

给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，剩下的作为右部分。
但是每种划分下都有左部分的最大值和右部分的最大值，请返回最大的，左部分最大值减去右部分最大值的绝对值。

输入描述:

1 2	第一行输入一个整数N(N<100000) 第二行输入N个整数表示arr

输出描述:

1	输出左部分最大值减去右部分最大值的绝对值的最大值

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    int ans=0;
    for(auto x:arr){
        ans=max(ans,x);
    }
    cout<<(ans-min(arr[0],arr[n-1]))<<endl;
    return 0;
}

11最难的问题

NowCoder生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是军团中的一名军官，需要把发送来的消息破译出来、并提
供给你的将军。
消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A 都分别替换成字母F），
其他字符不变，并且消息原文的所有字母都是大写的。密码中的字母与原文中的字母对应关系如下。
密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

输入描述:

1 2	输入包括多组数据，每组数据一行，为收到的密文。密文仅有空格和大写字母组成。

输出描述:

1	对应每一组数据，输出解密后的明文。

密码 > ‘E’
则：原文= 密码 - 5
否则：原文 = 密码 + 21

#include <iostream>
using namespace std;

int main() {
    char c;
    while ((c = getchar()) != EOF) {
        if ('A' <= c && 'Z' >= c) {
            c = (c > 'E') ? (c - 5) : (c + 21);
        }
        putchar(c);
    }
    return 0;
}

12天使果冻

题目描述
有 n 个果冻排成一排。第 i 个果冻的美味度是 𝑎𝑖
天使非常喜欢吃果冻，但她想把最好吃的果冻留到最后收藏。
天使想知道前 x 个果冻中，美味度第二大的果冻有多少美味度？
一共有 𝑞 次询问。
注：如果最大的数有两个以上，默认第二大的等于最大的。例如，
[2,3,4,2,4] 这个序列，第二大的数是4。

输入描述:

第一行一个正整数 𝑛 第二行 n 个正整数 𝑎𝑖 ，用空格隔开。
第三行一个正整数 q 。
接下来的 q 行，每行一个正整数 x ，代表一次询问。
数据范围：1≤q≤1e5，1≤ai≤1e9，2≤x≤n≤1e5

输出描述:

1 2	输出 𝑞 行，每行一个正整数，代表一次询问，输出前 x 个果冻中美味度第二大的值。

不采取排序的方式如果数组过大程序会超时

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> first_max(n + 1), second_max(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 预处理每个前缀的最大值和次大值
    for (int i = 1; i <= n; ++i) {
        if (a[i] > first_max[i - 1]) {
            second_max[i] = first_max[i - 1];
            first_max[i] = a[i];
        } else if (a[i] > second_max[i - 1]) {
            second_max[i] = a[i];
            first_max[i] = first_max[i - 1];
        } else {
            first_max[i] = first_max[i - 1];
            second_max[i] = second_max[i - 1];
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << second_max[x] << endl;
    }

    return 0;
}

13dd爱旋转

题目描述

读入一个
n∗n的矩阵，对于一个矩阵有以下两种操作
1:顺时针旋 180°
2:关于行镜像
如

给出 q个操作，输出操作完的矩阵

输入描述:

第一行一个数n(1≤n≤1000)，表示矩阵大小
接下来n行，每行n个数，描述矩阵，其中数字范围为[1,2000]
一下来一行一个数q(1≤q≤100000)，表示询问次数
接下来q行，每行一个数x(x=1或x=2)，描述每次询问

输出描述:

1	n行，每行n个数，描述操作后的矩阵

简单模拟即可
解答

#include <iostream>
#include <vector>
using namespace std;
// 矩阵旋转180度
void rotate180(vector<vector<int>> &matrix, int n) {
    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < n; ++j) {
            swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
        }
    }
    if (n % 2 != 0) {
        for (int j = 0; j < n / 2; ++j) {
            swap(matrix[n / 2][j], matrix[n / 2][n - 1 - j]);
        }
    }
}

// 矩阵关于行镜像
void mirrorRows(vector<vector<int>> &matrix, int n) {
    for (int i = 0; i < n / 2; ++i) {
        swap(matrix[i], matrix[n - 1 - i]);
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }
    int q;
    cin >> q;
    int rotate180_count = 0, mirror_count = 0;
    while (q--) {
        int x;
        cin >> x;
        if (x == 1) {
            rotate180_count++;
        } else if (x == 2) {
            mirror_count++;
        }
    }
    // 奇数次的旋转180度
    if (rotate180_count % 2 == 1) {
        rotate180(matrix, n);
    }
    // 奇数次的行镜像
    if (mirror_count % 2 == 1) {
        mirrorRows(matrix, n);
    }
    // 输出最终矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

14因子个数

一个正整数可以分解成一个或多个数组的积。例如36=223*3，即包含2和3两个因子。
NowCoder最近在研究因子个数的分布规律，现在给出一系列正整数，他希望你开发一个程序输出每个正整数的因子个数。

输入描述:

1 2	输入包括多组数据。每组数据仅有一个整数n (2≤n≤100000)。

输出描述:

1	对应每个整数，输出其因子个数，每个结果占一行。

思路:
从最小因子2到数字的最大因子数（数字的平方根）开始判断是否能够取余
可以则循环取余直到取余不为0，因子个数+1;否则使用下一个因子计算；
最终整除了各个因子数之后剩余的数字不为1则本身也是一个因子，因此因子数+1
注意：因子个数而不是一共有几个因子

解答

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        int k=0;
        for(int i=2;i<=sqrt(n);i++){
            if(n%i==0){
                while(n%i==0){
                    n/=i;
                }
                k++;
            }
        }
        if(n!=1) k++;
        cout<<k<<endl;
    }
    return 0;
}

14分解因子

所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × … × an,
并且 1 < a1 ≤ a2 ≤ a3 ≤ … ≤ an。其中a1、a2、…、an均为素数。先给出一个整数a，请输出分解后的因子。

输入描述:

1	输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。

输出描述:

1	对应每组数据，以“a = a1 * a2 * a3...”的形式输出因式分解后的结果。

简单素数判断

解答

#include <iostream>
#include <vector>
using namespace std;
// 函数：分解素因子
void primeFactorization(int n) {
    cout << n << " = ";
    bool first = true;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            if (!first) {
                cout << " * ";
            }
            cout << i;
            n /= i;
            first = false;
        }
    }
    // 如果 n 仍然大于 1，那么它本身就是一个素数
    if (n > 1) {
        if (!first) {
            cout << " * ";
        }
        cout << n;
    }
    cout << endl;
}

int main() {
    int a;
    while (cin >> a) {
        primeFactorization(a);
    }
    return 0;
}

15剪花布条

描述

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。
对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入描述：
输入包含多组数据。
每组数据包含两个字符串s,t，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，
可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。

输出描述：

对应每组输入，输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就输出0，每个结果占一行。

字符查找 str.find

解答

#include <iostream>
using namespace std;
int countSubstrings(const string& s,const string& t){
    int count=0;
    size_t pos=0;
    while((pos=s.find(t,pos))!=string::npos){
        count++;
        pos+=t.length();
    }
    return count;
}
int main() {
    string s,t;
    while(cin>>s>>t){
        cout<<countSubstrings(s,t)<<endl;
    }
    return 0;
}

16收件人列表

描述

NowCoder每天要给许多客户写电子邮件。正如你所知，如果一封邮件中包含多个收件人，
收件人姓名之间会用一个逗号和空格隔开；如果收件人姓名也包含空格或逗号，则姓名需要用双引号包含。
现在给你一组收件人姓名，请你帮他生成相应的收件人列表。

输入描述：

输入包含多组数据。
每组数据的第一行是一个整数n (1≤n≤128)，表示后面有n个姓名。
紧接着n行，每一行包含一个收件人的姓名。姓名长度不超过16个字符。

输出描述：

对应每一组输入，输出一行收件人列表。

字符串查找对应的字符

解答

#include<iostream>
#include<string>
using namespace std;
int main() {
    int n = 0;
    while (cin >> n) {
        string str;
        getchar();//数字后面有个换行符不要忘了
        for (int i = 0; i < n; i++) {
            getline(cin, str);
            if (str.find(' ') != str.npos || str.find(',') != str.npos)
                cout << '"' << str << '"';
            else
                cout << str;
            (i + 1 != n) ? cout << ", " : cout << endl; //最后一个不用输出逗号空格按要求输出换行
        }
    }
    return 0;
}

17抄送列表

NowCoder每天要处理许多邮件，但他并不是在收件人列表中，有时候只是被抄送。
他认为这些抄送的邮件重要性比自己在收件人列表里的邮件低，因此他要过滤掉这些次要的邮件，优先处理重要的邮件。
现在给你一串抄送列表，请你判断目标用户是否在抄送列表中。

输入描述:

输入有多组数据，每组数据有两行。
第一行抄送列表，姓名之间用一个逗号隔开。如果姓名中包含空格或逗号，
则姓名包含在双引号里。总长度不超过512个字符。
第二行只包含一个姓名，是待查找的用户的名字（姓名要完全匹配）。长度不超过16个字符。

输出描述:

1 2	如果第二行的名字出现在收件人列表中，则输出“Ignore”，表示这封邮件不重要；否则，输出“Important!”，表示这封邮件需要被优先处理。

截取字符串 substr

通过getiine(cin, names)方法获取第一行中的所有名字
解析出第一行中的所有名字保存在unordered_set中
获取第二行中的名字，检测该名字是否存在，并按照题目的要求进行输出

解答

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    string name;
    while(getline(cin,name)){
        unordered_set<string> set;
        size_t pos=0;
        while(pos<name.length()){
            if(name[pos]=='\"'){
                //名字中包含""
                size_t end=name.find('\"',pos+1);
                set.insert(name.substr(pos+1,end-pos-1));
                pos=end+2;//跳过""和,
            }else {
                size_t end=name.find(',',pos);
                if(end==-1){
                    //最后一个名字
                    set.insert(name.substr(pos));
                    break;
                }
                set.insert(name.substr(pos,end-pos));
                pos=end+1;
            }
        }
        //接受第二个名字
        getline(cin,name);
        if(set.find(name)==set.end()){
            cout<<"Important!"<<endl;
        }else {
            cout<<"Ignore"<<endl;
        }
    }
    return 0;
}

18养兔子

一只成熟的兔子每天能产下一胎兔子。每只小兔子的成熟期是一天。某人领养了一只小兔子，请问第N天以后，他将会得到多少只兔子。

输入描述:

1	测试数据包括多组，每组一行，为整数n(1≤n≤90)。

输出描述:

1	对应输出第n天有几只兔子(假设没有兔子死亡现象)。

斐波那契数列

#include <iostream>
using namespace std;

int main() {
    long long n[91] = { 1, 2 };
    for (int i = 2; i <= 90; i++) {
        n[i] = n[i - 1] + n[i - 2];
    }
    int d;
    while (std::cin >> d) {
        printf("%lld\n", n[d - 1]);
    }
}

19mkdir

描述
工作中，每当要部署一台新机器的时候，就意味着有一堆目录需要创建。
例如要创建目录“/usr/local/bin”，就需要此次创建“/usr”、“/usr/local”以及“/usr/local/bin”。
好在，Linux下mkdir提供了强大的“-p”选项，只要一条命令“mkdir -p /usr/local/bin”就能自动创建需要的上级目录。
现在给你一些需要创建的文件夹目录，请你帮忙生成相应的“mkdir -p”命令。

输入描述：

输入包含多组数据。
每组数据第一行为一个正整数n(1≤n≤1024)。
紧接着n行，每行包含一个待创建的目录名，目录名仅由数字和字母组成，长度不超过200个字符。

输出描述：

对应每一组数据，输出相应的、按照字典顺序排序的“mkdir -p”命令。
每组数据之后输出一个空行作为分隔。

判断字符串是否相等，字串问题

解答

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        vector<string> path(n);
        for(int i=0;i<n;i++){
            cin>>path[i];
        }
        vector<bool> flag(n,true);
        sort(path.begin(),path.end());
        for(int i=0;i<n-1;i++){
            //判断两个路径是否相等
            if(path[i]==path[i+1]){
                flag[i]=false;
            }
            //判断两个路径是否是字串关系
            if(path[i+1].length()>path[i].length()&&path[i+1].substr(0,path[i].length())==path[i]&&path[i+1][path[i].length()]=='/'){
                flag[i]=false;
            }
        }
        //输出结果
        for(int i=0;i<n;i++){
            if(flag[i]){
                cout<<"mkdir -p "<<path[i]<<endl;
            }
        }
        cout<<endl;
    }
    return 0;
}

20找出字符串中第一个只出现一次的字符

描述

找出字符串中第一个只出现一次的字符
数据范围：输入的字符串长度满足 1≤n≤1000

输入描述：

输入一个非空字符串

输出描述：

输出第一个只出现一次的字符，如果不存在输出-1

注意是字符(256)而不是字母(26)

解答

#include <iostream>
#include <unordered_map>
using namespace std;
char getFirstOneChar(string str) {
    int hash[256]={0};
    for (auto ch : str) {
        hash[ch]++;
    }
    for (auto ch : str) {
        if (hash[ch] == 1) {
            return ch;
        }
    }
    return -1;
}

int main() {
    string str;
    cin >> str;
    char res=getFirstOneChar(str);
    if(res==-1){
        cout<<-1<<endl;
    }else{
        cout<<res<<endl;
    }
    return 0;
}

21微信红包

描述

春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。
请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。
若没有金额超过总数的一半，返回0。
数据范围：1≤n≤1000 ,红包金额满足 1≤gift≤100000

超过数组一半的元素->如果存在，一定在数组正中间

解答

class Gift {
  public:
    int getValue(vector<int> gifts, int n) {
        map<int, int> map;
        int middle = n / 2;
        for (auto x : gifts) {
            map[x]++;
        }
        for (auto x : map) {
            if (x.second > middle) {
                return x.first;
            }
        }
        return 0;
    }
};

22猴子分桃

描述

老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。
第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。
第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。

输入描述：

输入包括多组测试数据。
每组测试数据包括一个整数n(1≤n≤20)。
输入以0结束，该行不做处理。

输出描述：

每组测试数据对应一行输出。
包括两个整数a，b。
分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。

数学分析题：
因为每次分5堆都会多出来1个，所以我们借给猴子们4个，以致每次都可以刚好分成5堆
并且，每次给老猴子的桃子都不在我们借出的那4个中，这样最后减掉4就可以得到结果。
假设最初由x个桃子，我们借给猴子4个，则此时有x+4个，
第一个猴子得到（x+4）/5，剩余（x+4）（4/5）个
第二个猴子分完后剩余（x+4） (4/5)^2个
第三个猴子分完后剩余（x+4） (4/5)^3个
依次类推，第n个猴子分完后剩余（x+4）（4/5）^n 要满足最后剩余的为整数，
并且x最小，则当 x+4=5^n时，满足要求；此时，x=5^n - 4;
老猴子得到的数量为：（x+4）*（4/5）^n + n - 4 = 4^n + n - 4
最后的 +n是因为每个小猴子都会多出一个给老猴子，-4是还了借的4个

解答

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        if(n==0) break;
        long total=pow(5,n)-4;
        long left=pow(4,n)+n-4;
        cout<<total<<" "<<left<<endl;
    }
    return 0;
}

23游游的字母串

对于一个小写字母而言，游游可以通过一次操作把这个字母变成相邻的字母。
‘a’和’b’相邻，’b’和’c’相邻，以此类推。特殊的，’a’和’z’也是相邻的。可以认为，小写字母的相邻规则为一个环。
游游拿到了一个仅包含小写字母的字符串，她想知道，使得所有字母都相等至少要多少次操作？

输入描述:

1	一个仅包含小写字母，长度不超过100000的字符串。

输出描述:

1	一个整数，代表最小的操作次数。

思路：
26个字母依次进行枚举

解答

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt = 1e9;
    for (char i = 'a'; i <= 'z'; i++) {
        int sum = 0;
        for (int j = 0; j < s.size(); j++) {
            sum += min(abs(s[j] - i), 26 - abs(s[j] - i)); //从左去或从右去
        }
        cnt = min(cnt, sum);
    }
    cout << cnt;
    return 0;
}

24合唱队形

描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，
则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述：

输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。

输出描述：

可能包括多组测试数据，对于每组数据，输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

思考:

左侧递增子序列：计算每个位置 i，以该位置为结尾的最长递增子序列的长度。
右侧递减子序列：计算每个位置 i，以该位置为起点的最长递减子序列的长度。
然后对于每个位置 i，我们计算出当 i 是峰顶时的合唱队形长度，
即 left[i] + right[i] - 1，最后取最大的长度，再用 N 减去这个长度即可得到最少需要出列的同学人数。

解答

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minStudentsToRemove(int N, const vector<int>& heights) {
    vector<int> left(N, 1);  // 记录左侧递增子序列的长度
    vector<int> right(N, 1); // 记录右侧递减子序列的长度

    // 计算左侧递增子序列的长度
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (heights[i] > heights[j]) {
                left[i] = max(left[i], left[j] + 1);
            }
        }
    }

    // 计算右侧递减子序列的长度
    for (int i = N - 2; i >= 0; --i) {
        for (int j = N - 1; j > i; --j) {
            if (heights[i] > heights[j]) {
                right[i] = max(right[i], right[j] + 1);
            }
        }
    }

    // 计算最长的合唱队形的长度
    int maxLength = 0;
    for (int i = 0; i < N; ++i) {
        maxLength = max(maxLength, left[i] + right[i] - 1);
    }

    // 需要移除的同学数量
    return N - maxLength;
}

int main() {
    int N;
    while (cin >> N) {
        vector<int> heights(N);
        for (int i = 0; i < N; ++i) {
            cin >> heights[i];
        }
        cout << minStudentsToRemove(N, heights) << endl;
    }
    return 0;
}

25另类加法

描述

给定两个int A和B。编写一个函数返回A+B的值，但不得使用+或其他算数运算符。

解答

class UnusualAdd {
public:
    int addAB(int A, int B) {
        // write code here
        if(A==0) return B;
        if(B==0) return A;
        int a=A^B;
        int b=(A&B)<<1;
        return addAB(a, b);
    }
};

26井字棋

描述

给定一个二维数组board，代表棋盘，其中元素为1的代表是当前玩家的棋子，0表示没有棋子，-1代表是对方玩家的棋子。
当一方棋子在横竖斜方向上有连成排的及获胜（及井字棋规则），返回当前玩家是否胜出。

解答

#include <iostream>
using namespace std;
#include <vector>
class Board {
  public:
    bool checkWon(vector<vector<int>> board) {
        int n=board.size();
        bool winMainDiag=true,winAntiDiag=true;
        for(int i=0;i<n;i++){
            bool winRow=true,winCol=true;
            for(int j=0;j<n;j++){
                if(board[i][j]!=1) winRow=false;
                if(board[j][i]!=1) winCol=false;
            }
            if(winRow||winCol) return true;
            if(board[i][i]!=1) winMainDiag=false;
            if(board[i][n-i-1]!=1) winAntiDiag=false;
        }
        return winMainDiag||winAntiDiag;
    };
};

27密码强度等级

描述

密码按如下规则进行计分，并根据不同的得分为密码进行安全等级划分。

一、密码长度:
5 分: 小于等于4 个字符
10 分: 5 到7 字符
25 分: 大于等于8 个字符

二、字母:
0 分: 没有字母
10 分: 密码里的字母全都是小（大）写字母
20 分: 密码里的字母符合”大小写混合“

三、数字:
0 分: 没有数字
10 分: 1 个数字
20 分: 大于1 个数字

四、符号:
0 分: 没有符号
10 分: 1 个符号
25 分: 大于1 个符号

五、奖励（只能选符合最多的那一种奖励）:
2 分: 字母和数字
3 分: 字母、数字和符号
5 分: 大小写字母、数字和符号

最后的评分标准:

= 90: 非常安全
= 80: 安全（Secure）
= 70: 非常强
= 60: 强（Strong）
= 50: 一般（Average）
= 25: 弱（Weak）
= 0: 非常弱（Very_Weak）

对应输出为：

VERY_SECURE
SECURE
VERY_STRONG
STRONG
AVERAGE
WEAK
VERY_WEAK

请根据输入的密码字符串，进行安全评定。

注：
字母：a-z, A-Z
数字：0-9
符号包含如下： (ASCII码表可以在UltraEdit的菜单view->ASCII Table查看)
!”#$%&’()*+,-./ (ASCII码：0x210x2F)
:;<=>?@ (ASCII码：0x3A0x40)
[]^_` (ASCII码：0x5B0x60)
{|} (ASCII码：0x7B~0x7E)

提示:
1 <= 字符串的长度<= 300

输入描述：

输入一个string的密码

输出描述：

输出密码等级

判断是否是字符 ispunct

解答

#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;
int getLengthScore(const string& password) {
    int len = password.length();
    if (len <= 4) return 5;
    if (len <= 7) return 10;
    return 25;
}

int getLetterScore(const string& password) {
    bool hasLower = false, hasUpper = false;
    for (auto ch : password) {
        if (islower(ch)) hasLower = true;
        if (isupper(ch)) hasUpper = true;
    }
    if (hasLower && hasUpper) return 20;
    if (hasLower || hasUpper) return 10;
    return 0;
}

int getDigitScore(const string& password) {
    int digitcount = 0;
    for (auto ch : password) {
        if (isdigit(ch)) digitcount++;
    }
    if (digitcount == 1) return 10;
    if (digitcount > 1) return 20;
    return 0;
}

int getSymbolScore(const string& password) {
    int symbolcount = 0;
    for (auto ch : password) {
        if (ispunct(ch)) symbolcount++;
    }
    if (symbolcount == 1) return 10;
    if (symbolcount > 1) return 20;
    return 0;
}

int getBonusScore(const string& password) {
    bool hasLower = false, hasUpper = false, hasDigit = false, hasSymbol = false;
    for (char ch : password) {
        if (islower(ch)) hasLower = true;
        if (isupper(ch)) hasUpper = true;
        if (isdigit(ch)) hasDigit = true;
        if (ispunct(ch)) hasSymbol = true;
    }
    if (hasLower && hasUpper && hasDigit && hasSymbol) return 5;
    if ((hasLower || hasUpper) && hasDigit && hasSymbol) return 3;
    if ((hasLower || hasUpper) && hasDigit) return 2;
    return 0;
}

string getPasswordStrength(int score) {
    if (score >= 90) return "VERY_SECURE";
    if (score >= 80) return "SECURE";
    if (score >= 70) return "VERY_STRONG";
    if (score >= 60) return "STRONG";
    if (score >= 50) return "AVERAGE";
    if (score >= 25) return "WEAK";
    return "VERY_WEAK";
}

int main() {
    string password;
    cin >> password;

    int score = 0;
    score += getLengthScore(password);
    score += getLetterScore(password);
    score += getDigitScore(password);
    score += getSymbolScore(password);
    score += getBonusScore(password);

    cout << getPasswordStrength(score) << endl;

    return 0;
}

28求最大连续bit数

描述

求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1

数据范围：数据组数： 1≤t≤5 ， 1≤n≤500000
进阶：时间复杂度： O(logn) ，空间复杂度： O(1)

输入描述：

输入一个int类型数字

输出描述：

输出转成二进制之后连续1的个数

求一个二进制数有几个连续的1，用n与n<<1作&

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int count=0;
    while(n){
        n=n&(n<<1);
        count++;
    }
    cout<<count<<endl;
    return 0;
}

求一个二进制数有几个1，用n与n-1作&

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int count=0;
    while(n){
        n=n&(n-1);
        count++;
    }
    cout<<count<<endl;
    return 0;
}

29二进制插入

描述

给定两个32位整数n和m，同时给定i和j，将m的二进制数位插入到n的二进制的第j到第i位,保证n的第j到第i位均为零，
且m的二进制位数小于等于i-j+1，其中二进制的位数从0开始由低到高。

测试样例：

1 2	1024，19，2，6 返回：1100

解答

class BinInsert {
public:
    int binInsert(int n, int m, int j, int i) {
        // write code here
        m=m<<j;
        return n|m;
    }
};

30查找组成一个偶数最接近的两个素数

描述

任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。

数据范围：输入的数据满足 4≤n≤1000

输入描述：

输入一个大于2的偶数

输出描述：

从小到大输出两个素数

#include <iostream>
using namespace std;
bool isPrime(int num){
    if(num<2) return false;
    for(int i=2;i*i<=num;i++){
        if(num%i==0) return false;
    }
    return true;
}

int main() {
    int n;
    cin>>n;
    int half=n/2;
    int i=0;
    for(i=half;i>1;i--){
        if(isPrime(i)&&isPrime(n-i)){
            break;
        }
    }
    cout<<i<<endl;
    cout<<n-i<<endl;
    return 0;
}

31参数解析

描述

在命令行输入如下命令：

xcopy /s c:\ d:\e，

各个参数如下：

参数1：命令字xcopy

参数2：字符串/s

参数3：字符串c:\

参数4: 字符串d:\e

请编写一个参数解析程序，实现将命令行各个参数解析出来。

解析规则：

1.参数分隔符为空格

2.对于用””包含起来的参数，如果中间有空格，不能解析为多个参数。比如在命令行输入xcopy /s “C:\program files” “d:"时，参数仍然是4个，第3个参数应该是字符串C:\program files，而不是C:\program，注意输出参数时，需要将””去掉，引号不存在嵌套情况。

3.参数不定长

4.输入由用例保证，不会出现不符合要求的输入

数据范围：字符串长度： 1≤s≤1000
进阶：时间复杂度： O(n) ，空间复杂度： O(n)

输入描述：

输入一行字符串，可以有空格

输出描述：

输出参数个数，分解后的参数，每个参数都独占一行

#include <iostream>
#include <vector>
using namespace std;
void cmdLineParse(const string& str){
    vector<string> param;
    string tmp="";
    bool flag=false;
    for(auto ch:str){
        if(ch=='"'){
            flag=!flag;
        }else if(ch==' '&&!flag){
            param.push_back(tmp);
            tmp.clear();
        }else {
            tmp+=ch;
        }
    }
    if(!tmp.empty()){
        param.push_back(tmp);
    }
    cout<<param.size()<<endl;
    for(auto s:param){
        cout<<s<<endl;
    }
}
int main() {
    string str;
    getline(cin,str);
    cmdLineParse(str);
    return 0;
}

32神奇数

给出一个区间[a, b]，计算区间内“神奇数”的个数。
神奇数的定义：存在不同位置的两个数位，组成一个两位数（且不含前导0），且这个两位数为质数。
比如：153，可以使用数字3和数字1组成13，13是质数，满足神奇数。同样153可以找到31和53也为质数，只要找到一个质数即满足神奇数。

输入描述:

1	输入为两个整数a和b，代表[a, b]区间 (1 ≤ a ≤ b ≤ 10000)。

输出描述:

1	输出为一个整数，表示区间内满足条件的整数个数

解答

#include <iostream>
#include <unordered_set>
using namespace std;
bool isPrime(int num){
    if(num<2) return false;
    for(int i=2;i*i<=num;i++){
        if(num%i==0) return false;
    }
    return true;
}

bool isMagicNumber(int num){
    string str=to_string(num);
    int len=str.length();
    unordered_set<int> set;
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            if(i!=j){
                int num=(str[i]-'0')*10+(str[j]-'0');
                if(num>10){
                    set.insert(num);
                }
            }
        }
    }

    for(auto x:set){
        if(isPrime(x)) return true;
    }
    return false;
}

int main() {
    int a,b;
    cin>>a>>b;
    int count=0;
    for(int i=a;i<=b;i++){
        if(isMagicNumber(i)) count++;
    }
    cout<<count<<endl;
    return 0;
}

33进制转换

描述

给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数

输入描述：

输入为一行，M(32位整数)、N(2 ≤ N ≤ 16)，以空格隔开。

输出描述：

为每个测试实例输出转换后的数，每个输出占一行。如果N大于9，则对应的数字规则参考16进制（比如，10用A表示，等等）

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int M,N;
    cin>>M>>N;
    string str="0123456789ABCDEF";
    string ans="";
    bool flag=false;
    if(M<0){
        flag=true;
        M=-M;
    }else if(M==0){
        cout<<0<<endl;
        return 0;
    }

    while(M){
        ans+=str[M%N];
        M/=N;
    }
    if(flag){
        ans+='-';
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    return 0;
}

34Fibonacci数列

描述

Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。
给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

输入描述：

输入为一个正整数N(1 ≤ N ≤ 1,000,000)

输出描述：

输出一个最小的步数变为Fibonacci数”

解答

#include <iostream>
using namespace std;

int main() {
    int N,f0=0,f1=1,l=0,r=0;
    cin>>N;
    while(1){
        int f=f0+f1;
        f0=f1;
        f1=f;
        if(f<N){
            l=N-f;
        }else{
            r=f-N;
            break;
        }
    }
    cout<< min(l,r) <<endl;
    return 0;
}

35两种排序方法

描述

考拉有n个字符串字符串，任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法：

1.根据字符串的字典序排序。例如：
“car” < “carriage” < “cats” < “doggies < “koala”

2.根据字符串的长度排序。例如：
“car” < “cats” < “koala” < “doggies” < “carriage”

考拉想知道自己的这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以需要你来帮忙验证。

输入描述：

输入第一行为字符串个数n(n ≤ 100) 接下来的n行,每行一个字符串,字符串长度均小于100，均由小写字母组成

输出描述：

如果这些字符串是根据字典序排列而不是根据长度排列输出”lexicographically”,
如果根据长度排列而不是字典序排列输出”lengths”,
如果两种方式都符合输出”both”，否则输出”none”

思路：长度，字典序如何比较 lambda表达式

解答

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<string> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<string> arr_copy=arr;
    sort(arr.begin(),arr.end());
    bool lexicographically=true;
    for(int i=0;i<n;i++){
        if(arr[i]!=arr_copy[i]){
            lexicographically=false;
            break;
        }
    }
    sort(arr.begin(),arr.end(),[](const string&str1,const string&str2){
        return str1.length()<str2.length();
    });
    bool lengths=true;
    for(int i=0;i<n;i++){
        if(arr[i]!=arr_copy[i]){
            lengths=false;
            break;
        }
    }
    if(lexicographically&&lengths){
        cout<<"both"<<endl;
    }else if(lexicographically&&!lengths){
        cout<<"lexicographically"<<endl;
    }else if(!lexicographically&&lengths){
        cout<<"lengths"<<endl;
    }else {
        cout<<"none"<<endl;
    }
    return 0;
}

36重构字符串

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 “” 。

思路: m>n−m+1，那么无法重排，返回空字符串;从偶数下标开始填，如果单个字母出现的次数过多，则不能进行重构

class Solution {
public:
    string reorganizeString(string s) {
        int n=s.length();
        unordered_map<char,int> mp;
        for(auto ch:s) mp[ch]++;

        vector<pair<char,int>> v(mp.begin(),mp.end());

        sort(v.begin(),v.end(),[](const auto&p,const auto&q){
            return p.second>q.second;
        });

        int m=v[0].second;
        if(m>n-m+1){
            return "";
        }
        string ans(n,0);
        int i=0;
        for(auto[ch,cnt]:v){
            while(cnt--){
                ans[i]=ch;
                i+=2;
                if(i>=n){
                    i=1;
                }
            }
        }
        return ans;
    }
};

37mari和shiny

题目描述

mari每天都非常shiny。她的目标是把正能量传达到世界的每个角落！
有一天，她得到了一个仅由小写字母组成的字符串。
她想知道，这个字符串有多少个”shy”的子序列？
（所谓子序列的含义见样例说明）

输入描述:

1 2	第一行一个正整数n，代表字符串的长度。（1≤n≤300000）第二行为一个长度为n，仅由小写字母组成的字符串。

输出描述:

1	一个正整数，代表子序列"shy"的数量。

需要注意数值的范围

解答

#include <iostream>
using namespace std;
 int main(){
     long long n;
     cin>>n;
     string str;
     cin>>str;
     long long counts=0,countsh=0,countshy=0;
     for(auto ch:str){
         if(ch=='s') counts++;
         else if(ch=='h') countsh+=counts;
         else if(ch=='y') countshy+=countsh;
     }
     cout<<countshy<<endl;
     return 0;
 }

进阶版本

38不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的子序列中 t 出现的个数，结果需要对 10^9 + 7 取模。

解答

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.length(),m=t.length();
        vector<vector<int>> cache(n,vector<int>(m,-1));//-1表示没有被访问过
        function<long long(int,int)> dfs=[&](int i,int j)->long long{
            if(j<0) return 1;
            if(i<0) return 0;
            int& res=cache[i][j];
            if(res!=-1){
                return res;
            }
            if(s[i]==t[j]){
                return res=dfs(i-1,j-1)+dfs(i-1,j);
            }
            return res=dfs(i-1,j);
        };
        return dfs(n-1,m-1);
    }
};

39游游的水果大礼包

游游有 n个苹果， m个桃子。她可以把2个苹果和1个桃子组成价值 a元的一号水果大礼包，
也可以把1个苹果和2个桃子组成价值 b元的二号水果大礼包。游游想知道，自己最多能组成多少价值总和的大礼包？

输入描述:

1 2	四个正整数 n,m,a,b，用空格隔开。分别代表苹果的数量、桃子的数量、一号大礼包价值、二号大礼包价值。 1≤n,m,a,b≤10^6

输出描述:

1	一个整数，代表大礼包的最大价值总和。

贪心算法

解答

#include <iostream>
using namespace std;

int main() {
    long long n,m,a,b;
    cin>>n>>m>>a>>b;
    long long max_value=0;
    for(int i=0;i<=n/2;i++){
        if(i<=n/2&&i<=m){
            int left_n=n-2*i;
            int left_m=m-i;
            int j=min(left_n,left_m/2);
            max_value=max(max_value,i*a+j*b);
        }
    }
    cout<<max_value<<endl;
    return 0;
}

40字符串替换

请你实现一个简单的字符串替换函数。原串中需要替换的占位符为”%s”,请按照参数列表的顺序一一替换占位符。若参数列表的字符数大于占位符个数。则将剩下的参数字符添加到字符串的结尾。

给定一个字符串A，同时给定它的长度n及参数字符数组arg，请返回替换后的字符串。保证参数个数大于等于占位符个数。保证原串由大小写英文字母组成，同时长度小于等于500。

class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m)
    {
        size_t pos=0;
        size_t paramindex=0;
        while((pos=A.find("%s",pos))!=string::npos){
            if(paramindex<arg.size()){
                string tmp=string(1,arg[paramindex++]);
                A.replace(pos,2,tmp);
                pos++;
            }else {
                break;
            }
        }
        while(paramindex<arg.size()){
            A+=arg[paramindex++];
        }
        return A;
    }
};

41洗牌

描述

洗牌在生活中十分常见，现在需要写一个程序模拟洗牌的过程。现在需要洗2n张牌，从上到下依次是第1张，第2张，第3张一直到第2n张。
首先，我们把这2n张牌分成两堆，左手拿着第1张到第n张（上半堆），右手拿着第n+1张到第2n张（下半堆）。接着就开始洗牌的过程，
先放下右手的最后一张牌，再放下左手的最后一张牌，接着放下右手的倒数第二张牌，再放下左手的倒数第二张牌，直到最后放下左手的第一张牌。
接着把牌合并起来就可以了。例如有6张牌，最开始牌的序列是1,2,3,4,5,6。首先分成两组，左手拿着1,2,3；右手拿着4,5,6。
在洗牌过程中按顺序放下了6,3,5,2,4,1。把这六张牌再次合成一组牌之后，我们按照从上往下的顺序看这组牌，就变成了序列1,4,2,5,3,6。
现在给出一个原始牌组，请输出这副牌洗牌k次之后从上往下的序列。

输入描述：

第一行一个数T(T ≤ 100)，表示数据组数。对于每组数据，第一行两个数n,k(1 ≤ n,k ≤ 100)，接下来有2n行个数a1,a2,…,a2n(1 ≤ ai ≤ 1000000000)。表示原始牌组从上到下的序列。

输出描述：

对于每组数据，输出一行，最终的序列。数字之间用空格隔开，不要在行末输出多余的空格。

思考:
如果当前数小于等于n（即在左手），则他下次出现的位置是 2当前位置
与之对应的当前位置小于n（即在右手）的牌,则他下次出现的位置是 2当前位置+1

解答

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> cache(2 * n);
        for(int i=0;i<2*n;i++){
            cin>>cache[i];
        }
        for (int j = 0; j < k; j++) {
            vector<int> tmp(cache.begin(), cache.end());
            for (int m=0;m<n;m++){
                cache[2*m]=tmp[m];
                cache[2*m+1]=tmp[m+n];
            }
        }
        for(auto x:cache){
            cout<<x <<" ";
        }
        cout<<endl;
    }
    return 0;
}

42过桥

题目描述

dd被困在了一个迷幻森林，现在她面前有一条凶险的大河，河中央有 n个神奇的浮块，浮块按 1∼n顺序标号，但两两并不相接，第
i个浮块上有一个数字 a[i]，可能是正数，也可能是负数,每块浮块都附带一个魔法结界用于传送，当 a[i]为正数时，
dd可以选择传送到第 i+k(1≤k≤a[i])个浮块上,当 dd抵达 n号浮块时才可以顺利脱身，显然不管 a[n]是多少，都没有任何意义，当
a[i]为负时， dd只能选择标号小于等于[i]的任意一块浮块进行传送，当 i+a[i]<1时，默认只能传送到
1的位置，每次传送都会花费 1s的时间，随着时间的流逝，迷雾森林的空气会被逐渐榨干，她现在在
1号浮块，她想知道，她最快多久能顺利脱身，如果始终无法逃脱，请输出 −1

输入描述:

1 2	第一行一个数n(2≤n≤2000) 接下来一行n个数a[i](1≤\|a[i]\|≤2000)表示浮块上的数字

输出描述:

1	输出一行，表示对应的答案

思路:

我们从第1个浮块开始，使用BFS逐层遍历每一个浮块。
对于每一个浮块，计算它可以传送到的其他浮块。
如果浮块上的数字是正数，我们可以向后传送，最多传送 a[i] 步。
如果浮块上的数字是负数，我们可以向前传送，最多传送 -a[i] 步。
传送的目标如果超过范围，按照题意处理。
BFS的过程中，每传送一次，记录时间 +1。
如果在BFS过程中到达第 n 个浮块，则输出对应的时间；如果BFS完成后仍未到达，则返回 -1。

解答

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);  // 浮块上的数字
    vector<int> dist(n + 1, -1);  // 到达每个浮块的最短时间
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    queue<int> q;
    q.push(1);  // 从第1个浮块开始
    dist[1] = 0;

    while (!q.empty()) {
        int i = q.front();
        q.pop();

        if (a[i] > 0) {  // 可以向后传送
            for (int k = 1; k <= a[i] && i + k <= n; ++k) {
                int next = i + k;
                if (dist[next] == -1) {  // 未访问过
                    dist[next] = dist[i] + 1;
                    q.push(next);
                }
            }
        } else {  // 可以向前传送
            for (int k = 1; k <= -a[i]; ++k) {
                int next = i - k;
                if (next < 1) {
                    next = 1;  // 传送到第1个浮块
                }
                if (dist[next] == -1) {  // 未访问过
                    dist[next] = dist[i] + 1;
                    q.push(next);
                }
            }
        }
    }

    cout << dist[n] << endl;

    return 0;
}

43小红的数字串

小红拿到了一个数字串（由’1’~’9’组成，不含’0’），她准备截取一段连续子串，使得该子串表示的正整数小于
k。你能帮她求出有多少种截取方案吗？

输入描述:

1 2	第一行输入一个数字串，长度不超过200000。第二行输入一个正整数 k。 1≤k≤10^9

输出描述:

1	小于k的截取方案数。

双指针

解答

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    long long k;
    cin >> s >> k;

    int n = s.size();
    int count = 0;

    for (int i = 0; i < n; ++i) {
        long long num = 0;
        for (int j = i; j < n; ++j) {
            num = num * 10 + (s[j] - '0');
            if (num < k) {
                count++;
            } else {
                break;
            }
        }
    }

    cout << count << endl;
    return 0;
}

44kotori和n皇后

题目描述

kotori最近在研究n皇后的问题。

所谓n皇后问题是这样的：一个n*n的地图，上面一共放n个皇后，保证任意两个皇后都不能互相攻击（每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后）。

kotori思考了很久都无法得出答案，整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟，按照次序一共放了k个皇后。

但是，皇后的站位太复杂了，kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你，在第i个皇后放置在棋盘上之后，是否存在两个皇后可以互相攻击？

输入描述:

第一行输入一个正整数k，代表总共放置的皇后的个数。（1<=k<=1e5）
接下来的k行，每行两个正整数xi和yi，代表每个皇后的坐标。（1<=xi,yi<=1e9）
之后输入一个正整数t，代表t次询问。（1<=t<=1e5）
接下来的t行，每行一个正整数i，代表询问第i个皇后放置后，是否存在互相攻击的情况。（1<=i<=k）
保证不存在两个皇后放置的位置相同。

输出描述:

1	共t行。每行对应当前的询问是否存在两个皇后可以互相攻击，若是则输出“Yes”，否则输出“No”

思考
代码逻辑分析
初始化四个 unordered_map 来追踪每个皇后所在的行 (row)、列 (col)、45度对角线 (diag1) 和 135度对角线 (diag2)。
对于每一个皇后的位置 (x, y)：
检查在该皇后所在的行、列或对角线上是否已经有其他皇后。
如果检测到冲突（即 row[x], col[y], diag1[x - y], diag2[x + y] 中任一项已经为 true），
记录当前的索引 i 为 conflict_index。此后，所有查询只需比较 i 是否大于或等于 conflict_index 即可判断是否存在冲突。
对于每个查询 i，如果 i 大于或等于 conflict_index，则输出 “Yes” 表示存在冲突；否则输出 “No”。

解答

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int k;
    cin >> k;

    unordered_map<int, bool> row, col, diag1, diag2;
    int conflict_index = -1;

    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;

        if (conflict_index == -1 && (row[x] || col[y] || diag1[x - y] || diag2[x + y])) {
            conflict_index = i;
        }

        row[x] = true;
        col[y] = true;
        diag1[x - y] = true;
        diag2[x + y] = true;
    }

    int t;
    cin >> t;
    while (t--) {
        int i;
        cin >> i;
        if (conflict_index != -1 && i >= conflict_index) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

45接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例

计算每个木桶左右壁的高度选择最短的木板

解答

class Solution {
public:
    int trap(vector<int>& height) {
        //双向双指针
        //优化
        int n=height.size();
        int left=0,right=n-1;
        int pre_max=0,suf_max=0;
        int ans=0;
        while(left<right){
            pre_max=max(pre_max,height[left]);
            suf_max=max(suf_max,height[right]);
            if(pre_max>suf_max){
                ans+=suf_max-height[right--];
            }else{
                ans+=pre_max-height[left++];
            }
        }
        return ans;
    }
};

1素数回文

2活动安排

3手套

4有假币

5逆波兰表达式求值

6电话号码

7查找兄弟单词

8单词倒排

9螺旋矩阵

10划分数组

11最难的问题

12天使果冻

13dd爱旋转

14因子个数

14分解因子

15剪花布条

16收件人列表

17抄送列表

18养兔子

19mkdir

20找出字符串中第一个只出现一次的字符

21微信红包

22猴子分桃

23游游的字母串

24合唱队形

25另类加法

26井字棋

27密码强度等级

28求最大连续bit数

29二进制插入

30查找组成一个偶数最接近的两个素数

31参数解析

32神奇数

33进制转换

34Fibonacci数列

35两种排序方法

36重构字符串

37mari和shiny

38不同的子序列

39游游的水果大礼包

40字符串替换

41洗牌

42过桥

43小红的数字串

44kotori和n皇后

45接雨水