算法基础算法

自定义排序

字数统计: 2.7k字   |   阅读时长: 15分
,

$1 自定义排序

$1.1 791. 自定义字符串排序

S 串只含字母 a-z(最长26)，我们要找到的是这26个字母的大小关系。26个字母的大小关系可以通过权重表示，权重越小，该字母在字符串排序后的位置约靠前。而 S 串通过字母的位置告诉了我们一些字母的权重，即：把出现过的字母在S中的下标视为该字母的权重。所以可以用一个长度 26 的 vector 保存 26 个字母的权重，值初始化为 -1，遍历 S，对 S 中的每一个字母将其下标赋值给 vector 的相应位置，这样就得到了从 S 串可以得到的部分字母的权重，权重关系就对应了字母的大小关系。

C++ 中通过给 sort 函数传入自定义的比较函数，可以实现自定义的排序。但是这里的排序需要查遍历 S 串得到的 vector，常用的直接写比较函数的方法不好实现。

还有一种方法是写一个结构体，结构体内部可以持有一个 vector 成员变量，通过初始化的方式将遍历 S 串得到的 vector 传给结构体的对象。重载该结构体的 ()，该结构体创建的对象可以当做函数使用，且内部已经持有了遍历 S 得到的 vector。

即：在 Cmp 中持有状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string customSortString(string S, string T) {
        int n = S.size();
        if(n <= 1) return T;
        vector<int> char_idx(26, -1);
        for(int i = 0; i < n; ++i)
            char_idx[S[i] - 'a'] = i;
        Dictionary_less dictionary_less(char_idx);
        sort(T.begin(), T.end(), dictionary_less);
        return T;
    }

private:
    struct Dictionary_less
    {
        vector<int> char_idx;
        Dictionary_less(vector<int> mapping):char_idx(mapping) {}
        bool operator() (const char& c1, const char& c2)
        {
            return char_idx[c1 - 'a'] < char_idx[c2 - 'a'];
        }
    };
};

$1.2 1329. 将矩阵按对角线排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int> cand;
        vector<vector<int>> result(n, vector<int>(m, -1));
        for(int k = -(n - 1); k <= m - 1; ++k)
        {
            // k = j - i
            cand.clear();
            for(int i = max(0, -k); i <= min(n - 1, m - 1 - k); ++i)
            {
                int j = i + k;
                cand.push_back(mat[i][j]);
            }
            sort(cand.begin(), cand.end());
            int iter = 0;
            for(int i = max(0, -k); i <= min(n - 1, m - 1 - k); ++i)
            {
                int j = i + k;
                result[i][j] = cand[iter++];
            }
        }
        return result;
    }
};

$1.3 1333. 餐厅过滤器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct Restaurant
{
    int id, rate;
    Restaurant(int id, int rate):id(id),rate(rate){}
};

struct Cmp
{
    bool operator()(const Restaurant& r1, const Restaurant& r2) const
    {
        if(r1.rate == r2.rate)
            return r1.id > r2.id;
        return r1.rate > r2.rate;
    }
};

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<Restaurant> vec;
        for(const vector<int> &item: restaurants)
        {
            if(veganFriendly == 1 && item[2] == 0)
                continue;
            if(item[3] > maxPrice)
                continue;
            if(item[4] > maxDistance)
                continue;
            vec.emplace_back(item[0], item[1]);
        }
        sort(vec.begin(), vec.end(), Cmp());
        int m = vec.size();
        vector<int> result(m);
        for(int i = 0; i < m; ++i)
            result[i] = vec[i].id;
        return result;
    }
};

$1.4 1030. 距离顺序排列矩阵单元格

在 Cmp 中持有状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Cmp
{
    int r0, c0;
    Cmp(int r0, int c0):r0(r0),c0(c0){}
    bool operator()(const vector<int>& p1, const vector<int>& p2) const
    {
        return abs(p1[0] - r0) + abs(p1[1] - c0) < abs(p2[0] - r0) + abs(p2[1] - c0);
    }
};

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        vector<vector<int>> result;
        for(int i = 0; i < R; ++i)
            for(int j = 0; j < C; ++j)
                result.push_back({i, j});
        sort(result.begin(), result.end(), Cmp(r0, c0));
        return result;
    }
};

$1.5 524. 通过删除字母匹配到字典里最长单词

Cmp 持有状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct Cmp
{
    string origin;
    Cmp(const string& origin):origin(origin){}
    bool operator()(const string& word1, const string& word2) const
    {
        bool flag1 = check(word1), flag2 = check(word2);
        if(!flag2) return false;
        if(!flag1) return true;
        if(word1.size() == word2.size())
            return word1 > word2;
        return word1.size() < word2.size();
    }
    bool check(const string& word) const
    {
        // word 是否可以通过 origin 删除某些字符得到
        int n = origin.size();
        int m = word.size();
        if(m > n) return false;
        int i = 0, j = 0;
        while(i < n && j < m)
        {
            if(origin[i] == word[j])
                ++j;
            ++i;
            if(m - j > n - i)
                return false;
        }
        return j == m;
    }
};

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        if(s.empty() || d.empty()) return "";
        Cmp cmp(s);
        auto it = max_element(d.begin(), d.end(), cmp);
        if(cmp.check(*it))
            return *it;
        return "";
    }
};

$1.6 179. 最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        if(nums.empty()) return "";
        int n = nums.size();
        if(n == 1) return to_string(nums[0]);
        vector<string> nums_str(n, "");
        for(int i = 0; i < n; ++i)
            nums_str[i] = to_string(nums[i]);
        sort(nums_str.begin(), nums_str.end(), dictionary_order_greater);
        if(nums_str[0] == "0") return "0";
        string result = "";
        for(string item: nums_str)
            result += item;
        return result;
    }

private:
    static bool dictionary_order_greater(const string& s1, const string& s2)
    {
        return s1 + s2 > s2 + s1;
    }
};

$1.7 406. 根据身高重建队列

先排序再插入，排序 $O(N\log N)$，插入 $O(N^{2})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        if(people.empty()) return vector<vector<int> >();
        int n = people.size();
        sort(people.begin(), people.end(), Cmp());
        vector<vector<int> > result;
        for(int i = 0; i < n; ++i)
            result.insert(result.begin() + people[i][1], people[i]);
        return result;
    }

private:
    struct Cmp
    {
        bool operator()(const vector<int>& vec1, const vector<int>& vec2)
        {
            if(vec1[0] == vec2[0])
                return vec1[1] < vec2[1];
            return vec1[0] > vec2[0];
        }
    };
};

2.8 1366. 通过投票对团队排名

持有状态的自定义排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes.size();
        int m = votes[0].size();
        Cmp cmp(m);
        for(const string& vote: votes)
        {
            for(int i = 0; i < m; ++i)
                ++cmp.polls[vote[i] - 'A'][i];
        }
        string result = votes[0];
        sort(result.begin(), result.end(), cmp);
        return result;
    }

private:
    struct Cmp
    {
        vector<vector<int> > polls;
        Cmp(int m)
        {
            polls = vector<vector<int> >(26, vector<int>(m, 0));
        }
        bool operator()(const char& a, const char& b)
        {
            for(int i = 0; i < (int)polls[0].size(); ++i)
            {
                if(polls[a - 'A'][i] > polls[b - 'A'][i])
                    return true;
                else if(polls[a - 'A'][i] < polls[b - 'A'][i])
                    return false;
            }
            return a < b;
        }
    };
};

2.9 1057. 校园自行车分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct Pair
{
    int x1, y1, x2, y2;
    int d;
    int id1, id2;
    Pair(int x1, int y1, int x2, int y2, int id1, int id2):x1(x1),y1(y1),x2(x2),y2(y2),id1(id1),id2(id2)
    {
        d = abs(x1 - x2) + abs(y1 - y2);
    }
};

struct Cmp
{
    bool operator()(const Pair& p1, const Pair& p2) const
    {
        if(p1.d == p2.d)
        {
            if(p1.id1 == p2.id1)
                return p1.id2 < p2.id2;
            return p1.id1 < p2.id1;
        }
        return p1.d < p2.d;
    }
};

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int n = workers.size(), m = bikes.size();
        vector<bool> used1(n, false), used2(m, false);
        vector<Pair> pairs;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                pairs.emplace_back(workers[i][0], workers[i][1], bikes[j][0], bikes[j][1], i, j);
        sort(pairs.begin(), pairs.end(), Cmp());
        vector<int> result(n, -1);
        for(const Pair& p: pairs)
        {
            if(used1[p.id1] || used2[p.id2])
                continue;
            result[p.id1] = p.id2;
            used1[p.id1] = true;
            used2[p.id2] = true;
        }
        return result;
    }
};

2.10 1029. 两地调度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct Person
{
    int a, b;
    Person(int a, int b):a(a),b(b){}
};

struct Cmp
{
    bool operator()(const Person& p1, const Person& p2) const
    {
        return (p1.a - p1.b) < (p2.a - p2.b);
    }
};

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<Person> persons;
        for(int i = 0; i < n; ++i)
        {
            persons.push_back(Person(costs[i][0], costs[i][1]));
        }
        sort(persons.begin(), persons.end(), Cmp());
        int ans = 0;
        for(int i = 0; i < n / 2; ++i)
            ans += persons[i].a;
        for(int i = n / 2; i < n; ++i)
            ans += persons[i].b;
        return ans;
    }
};

2.11 1094. 拼车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct Event
{
    int idx;
    // 右端点排前面，先下
    bool side; // false: 右，true: 左
    int num; // 涉及的乘客数，根据 side 决定是上还是下
    Event(int idx, bool side, int num):idx(idx),side(side),num(num){}
};

struct Cmp
{
    bool operator()(const Event& e1, const Event& e2) const
    {
        if(e1.idx == e2.idx)
            return e1.side < e2.side;
        return e1.idx < e2.idx;
    }
};

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<Event> events;
        for(const vector<int>& trip: trips)
        {
            // trip[0,1,2] : num, start, end
            events.push_back(Event(trip[1], true, trip[0]));
            events.push_back(Event(trip[2], false, trip[0]));
        }
        sort(events.begin(), events.end(), Cmp());
        int sum = 0;
        for(const Event &e : events)
        {
            if(e.side)
                sum += e.num;
            else
                sum -= e.num;
            if(sum > capacity)
                return false;
        }
        return true;
    }
};

2.12 1058. 最小化舍入误差以满足目标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct Cmp
{
    bool operator()(const double& a, const double& b) const
    {
        return a - (int)a > b - (int)b;
    }
};

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        const double EPS = 1e-4;
        int n = prices.size();
        vector<double> ps(n);
        for(int i = 0; i < n; ++i)
        {
            const string &p = prices[i];
            stringstream ss;
            ss << p;
            ss >> ps[i];
        }
        int sum = 0;
        int integer = 0;
        for(double p: ps)
        {
            sum += (int)p;
            if(p - (int)p < EPS)
                ++integer;
        }
        int gap = target - sum; // 需要上取整的个数: gap
        if(gap < 0 || gap > n - integer) // 可以上取整的个数: n - integer
            return "-1";
        sort(ps.begin(), ps.end(), Cmp());
        double ans = 0.0;
        for(int i = 0; i < gap; ++i)
        {
            ans += ((int)ps[i] + 1) - ps[i];
        }
        for(int i = gap; i < n - integer; ++i)
        {
            ans += ps[i] - (int)ps[i];
        }
        stringstream ss;
        ss << setiosflags(ios::fixed) << setprecision(3);
        ss << ans;
        string result;
        ss >> result;
        return result;
    }
};

2.13 1090. 受标签影响的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct Item
{
    int val;
    int label;
    Item(int v, int l):val(v),label(l){}
    Item():val(-1),label(-1){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.val > i2.val;
    }
};

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        int n = values.size();
        vector<Item> items(n);
        int max_label = -1;
        for(int i = 0; i < n; ++i)
        {
            items[i].val = values[i];
            items[i].label = labels[i];
            max_label = max(max_label, labels[i]);
        }
        vector<int> labels_record(max_label + 1, use_limit);
        sort(items.begin(), items.end(), Cmp());
        int cnt = 0;
        int ans = 0;
        for(const Item& i: items)
        {
            if(labels_record[i.label] == 0)
                continue;
            ans += i.val;
            ++cnt;
            --labels_record[i.label];
            if(cnt == num_wanted)
                break;
        }
        return ans;
    }
};

2.14 1356. 根据数字二进制下 1 的数目排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct Cmp
{
    bool operator()(const int& n1, const int& n2) const
    {
        int ones1 = ones(n1);
        int ones2 = ones(n2);
        if(ones1 == ones2)
            return n1 < n2;
        return ones1 < ones2;
    }

    int ones(int x) const
    {
        int cnt = 0;
        while(x)
        {
            x = x & (x - 1);
            ++cnt;
        }
        return cnt;
    }
};

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<int> result(arr.begin(), arr.end());
        sort(result.begin(), result.end(), Cmp());
        return result;
    }
};
Share