【05-03】力扣每日一题

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

题目描述

题目分析

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

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

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

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

当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;
    }
};