题解 | #字符串排序#

字符串排序

https://www.nowcoder.com/practice/5190a1db6f4f4ddb92fd9c365c944584

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

bool isletter(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

bool issame(const char a, const char b) {
    
    char a1 = (a>='a'&&a<='z') ? a : a+32;
    char b1 = (b>='a'&&b<='z') ? b : b+32;
    return a1 == b1;
}

bool comp(const char a, const char b) {
    if (issame(a,b))
        return false;
    char a1 = (a>='a'&&a<='z') ? a : a+32;
    char b1 = (b>='a'&&b<='z') ? b : b+32;
    return a1 < b1;
}

void maopao(vector<char>& letters) {
    int len = letters.size();
    for (int i = 1; i < len; i++) {
        for (int j = i; j >= 1; j--) {
            if (comp(letters[j], letters[j-1]))
                swap(letters[j], letters[j-1]);
            else
                break;
        }
    }
}

int main() {
    string s;
    while (getline(cin, s)) {
        vector<char> letters;
        vector<int> poses;
        int len = s.size();
        for (int i = 0; i < len; i++) {
            if (isletter(s[i])) {
                letters.push_back(s[i]);
                poses.push_back(i);
            }
        }
        
        // 冒泡排序
        maopao(letters);
        
        for (int i = 0; i < (int)letters.size(); i++) {
            int pos = poses[i];
            char c = letters[i];
            s[pos] = c;
        }
        cout << s << endl;
    }
}
// 64 位输出请用 printf("%lld")

思路:

  1. 用letters和poses保存所有大小写字母与其下标,对letters进行题目规则排序后,再依次插入原字符串,保证非字母字符的位置不变
  2. 对letters按规则排序,由于要保证A与a的相对位置不变,因此不能用快速排序,只能用插入排序或冒泡排序
  3. 按规则写一个冒泡排序

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
我是没经验的毕业生,这啥情况啊会不会是hr在刷kpi
JamesGosli...:字节boss属于是群发了,我都快入职字节了,其他部门还在和我boss打招呼
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务