14070: 【原4070】字符串删除与排序

题目

题目描述

author: 程序设计思想与方法助教组蒋永康 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4070

问题描述

输入若干个字符串(每个字符串的长度不超过30个字符，字符串总数不超过30)，和一个英文字符ch。 要求： - 删除每个字符串中的字符ch(区分大小写)，得到新的字符串 - 将新的字符串按照字典逆序排序后输出

输入输出描述

输入

• 第一行输入英文字符ch
• 每一行输入一个字符串
• 最后一行单独输入特殊字符@做为结束标志

输出

• 删除ch的新字符串按字典逆序输出
• 每行输出一个字符串

程序运行示例

Sample Input 1

e
shangejiao
fudean
teongji
shangcai
@

Sample Output 1

tongji
shangjiao
shangcai
fudan

注意

• 不要显示多余的提示信息，避免输出判定错误。
• 输出结束后不要输出任何内容，包括空格和换行。
• 注意判断输出信息是否符合要求。

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/29.
//

//
// Created by BugenZhao on 2019/5/12.
//

#ifndef SBL_BQSORT_H
#define SBL_BQSORT_H

#ifndef SBL_BSORT_H
#define SBL_BSORT_H

namespace bsort {
    template<typename Item>
    struct greater {
        bool operator()(const Item &a, const Item &b) {
            return a > b;
        }
    };

    template<typename Item>
    struct less {
        bool operator()(const Item &a, const Item &b) {
            return a < b;
        }
    };
}

#endif //SBL_BSORT_H


template<typename Item, typename Comparator=bsort::less<Item>>
class BQSort {
    static Comparator comparator;

private:
    static bool less(Item v, Item w) {
        return comparator(v, w);
    }

    static void exch(Item *a, int i, int j) {
        Item t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

public:
    static inline void sort(Item *a, int n) {
        sort(a, 0, n - 1);
    }

    static inline void sort(Item *a, int lo, int hi) {
        if (hi <= lo) return;
        int mid = partition(a, lo, hi);
        sort(a, lo, mid - 1);
        sort(a, mid + 1, hi);
    }

    static int partition(Item *a, int lo, int hi) {
        Item v = a[lo];
        while (true) {
            while (lo < hi && less(v, a[hi])) --hi;
            if (lo < hi) a[lo] = a[hi], ++lo;
            while (lo < hi && less(a[lo], v)) ++lo;
            if (lo < hi) a[hi] = a[lo], --hi;
            if (lo >= hi) break;
        }
        a[lo] = v;
        return lo;
    }
};

template<typename Item, typename Comparator>
Comparator BQSort<Item, Comparator>::comparator = Comparator();

#endif //SBL_BQSORT_H


#include <iostream>
#include <cstring>

using std::ios, std::cin, std::cout, std::endl;
using ll = long long;

struct cmp {
    bool operator()(char *a, char *b) {
        return strcmp(a, b) > 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    char **strs = new char *[35];
    for (int i = 0; i < 35; ++i) {
        strs[i] = new char[35];
    }
    char tmp[35];
    char ch;
    cin >> ch;
    int i = 0;
    for (i = 0; i < 35; ++i) {
        cin >> tmp;
        if (tmp[0] == '@') break;
        int len = strlen(tmp);
        int q = 0;
        for (int p = 0; p <= len; ++p) {
            if (tmp[p] == ch) continue;
            strs[i][q++] = tmp[p];
        }
    }
    BQSort<char *, cmp>::sort(strs, i);
    for (int j = 0; j < i; ++j) {
        cout << strs[j];
        if (j != i - 1) cout << '\n';
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int main() {


}

skyzh's solution

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

struct String {
    char x[50];
};

bool operator<(const String& a, const String& b) {
    return strcmp(a.x, b.x) < 0;
}

int partition(String *x, int l, int r) {
    String pivot = x[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (x[j] < pivot) {
            swap(x[j], x[i++]);
        }
    }
    swap(x[r], x[i]);
    return i;
}

void _quicksort(String *x, int l, int r) {
    if (l >= r) return;
    int mid = partition(x, l, r);
    _quicksort(x, l, mid - 1);
    _quicksort(x, mid + 1, r);
}

void shuffle(String *x, int N) {
    for (int i = N - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        swap(x[i], x[j]);
    }
}


void quicksort(String *x, int N) {
    shuffle(x, N);
    _quicksort(x, 0, N - 1);
}

const int MAX_BUF = 100000;
String buffer[MAX_BUF];
int N = 0;

int main() {
    char ch;
    char tmp[50];
    cin >> ch; cin.get();
    while(true) {
        cin.getline(tmp, 50);
        if (strcmp(tmp, "@") == 0) break;
        else {
            const int size = strlen(tmp);
            int j = 0;
            for(int i = 0; i < size; i++) {
                if (tmp[i] != ch) buffer[N].x[j++] = tmp[i];
            }
            buffer[N].x[j] = 0;
            ++N;
        }
    }
    quicksort(buffer, N);
    for (int i = N - 1; i >= 0; i--) {
        cout << buffer[i].x;
        if (i != 0) cout << endl;
    }
    return 0;
}