今天的每日一题是简单类别,但还是写了我一会儿。

题目描述

  题目链接,937. 重新排列日志文件,题目截图如下:

image-20220503144139800

题目分析

  首先解读下题目的意思,意思是说,给你一个字符串数组,每个字符串里以空格隔开,第一个字符串为标识符,之后的都是内容。如果内容全部都是数字,那么该日志为数字类型,如果内容全部是小写字母,那么该日志类型为字母类型。现在给你一个字符串数组,需要按照如下的规则进行排序:

  • 所有的字母日志都需要排在字符日志的前面。
  • 对于字母日志,如果内容不同,那就只比较内容的大小(按照字母的字典序比较)。如果内容相同,那么去比较标识符的大小,按照字符的ASCII码进行排序。
  • 对于数字日志来说,需要保证他们原来的相对顺序。

  这道题,我的第一思路就是,首先遍历一遍字符串数组,将字母日志和数字日志分开,分别用不同的数组保存。之后对字母日志进行排序,字母日志排完序之后,将两个数组按照顺序连接起来就是我们最终的答案。虽然写出来了,也通过了,但是在内存消耗和执行效率上却不是很好。代码在下面给出,第一个代码片段是我自己的思考。当然需要注意的是,如果字母日志中,内容相同,去比较标识符的时候,如果存在这样的情况letter1letter12,那肯定是后面那个字符串大,因为多了一位。同理,比较内容的时候,如果全部一样,就是有一个多了字符,那肯定是多了字符的大。

  后面在看了官方给的题解之后,则是发现,这道题其实考察我们自定义排序。对于自定义排序,有如下规则:

  • cmp中返回false,则将参数2放在参数1的前面
  • cmp中返回true,则将参数1放在参数2的前面
  • cmp中第一个参数是后面的元素,第二个参数是前面的元素

  这里对第三点再次解释一下,也就是当序列为[1,2,3,4,5]的时候我们的cmp(x,y),对于第一次传值,x是2,y是1

代码实现

  c++代码实现:

class Solution {
public:
    void swap(string& a,string& b){
        string tmp = a;
        a = b;
        b = tmp;
    }
    vector<string> reorderLogFiles(vector<string>& logs) {
        int n = logs.size();
        vector<string> res;
        vector<string> letter;
        vector<string> digital;
        for(int i = 0;i<n;i++){
            int k = 0;
            while(logs[i][k]!=' '){
                k++;
            }
            if(logs[i][k+1]>='0' && logs[i][k+1]<='9'){
                // 数字日志
                digital.push_back(logs[i]);
            }else{
                // 字母日志
                letter.push_back(logs[i]);
            }
        }
        int len = letter.size();
        // 对字母日志进行排序
        for(int i = 0;i<len;i++){
            for(int j = i+1;j<len;j++){
                string a = letter[i];
                string b = letter[j];
                int start = 0;
                while(a[start]!=' '){
                    start++;
                }
                string a_id = a.substr(0,start+1);
                string a_content = a.substr(start+1,a.length());
                start = 0;
                while(b[start]!=' '){
                    start++;
                }
                string b_id = b.substr(0,start+1);
                string b_content = b.substr(start+1,b.length());
                int m = 0,n = 0;
                while(m<a_content.length() && n<b_content.length()){
                    if(a_content[m]!=b_content[n]){
                        if(a_content[m]>b_content[n]){
                            swap(letter[i],letter[j]);
                        }
                        break;
                    }
                    m++;
                    n++;
                }
                if(m==a_content.length() && n==b_content.length()){
                    // 内容相同 按照标识符排序
                    int u = 0,v = 0;
                    while(u<a_id.length() && v<b_id.length()){
                        if(a_id[u]!=b_id[v]){
                            if(a_id[u]>b_id[v]){
                                swap(letter[i],letter[j]);
                            }
                            break;
                        }
                        u++;
                        v++;
                    }
                    if(v!=a_id.length() && u==b_id.length()){
                        swap(letter[i],letter[j]);
                    }
                }else if(m!=a_content.length() && n==b_content.length()){
                    // a更长
                    swap(letter[i],letter[j]);
                }
            }
        }
        // 结果梳理
        for(int i = 0;i<letter.size();i++){
            res.push_back(letter[i]);
        }
        for(int i = 0;i<digital.size();i++){
            res.push_back(digital[i]);
        }
        return res;
    }
};

  下面这个是按照自定义排序的思路去写的:

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        stable_sort(logs.begin(), logs.end(), [&](const string & log1, const string & log2) {
            int pos1 = log1.find_first_of(" ");
            int pos2 = log2.find_first_of(" ");
            bool isDigit1 = isdigit(log1[pos1 + 1]);
            bool isDigit2 = isdigit(log2[pos2 + 1]);
            if (isDigit1 && isDigit2) {
                return false;
            }
            if (!isDigit1 && !isDigit2) {
                string s1 = log1.substr(pos1);
                string s2 = log2.substr(pos2);
                if (s1 != s2) {
                    return s1 < s2;
                }
                return log1 < log2;
            }
            return isDigit1 ? false : true;
        });
        return logs;
    }
};

结语

  我有一壶酒,足以慰风尘。尽倾江海尔,赠饮天下人!

Q.E.D.


  Java后端开发工程师一名,北漂一族,欢迎大家前来交流