[解题报告] 《算法零基础100讲》(第34讲) 排序入门 - 选择排序

[解题报告] 《算法零基础100讲》(第34讲) 排序入门 - 选择排序

目录

• 前言
• 一、有效三角形的个数
• 二、重构字符串
• 三、最多能完成排序的块

---

前言

跟着英雄哥打卡第三十四天
[专题跳转->《算法零基础100讲》]
[万人千题社区跳转]

---

一、有效三角形的个数

跳转力扣：611. 有效三角形的个数
难度：★★☆☆☆

说明：双指针，为方便满足三角形原则【 a + b > c , a + c > b , b + c > a a+b>c,a+c>b,b+c>a a+b>c,a+c>b,b+c>a】，只需将数组从小到大排序后满足【 a + b > c a+b>c a+b>c】即可同时满足后两者；由于题目给出数值范围为非负数，则需排除 n u m [ i ] = = 0 num[i]==0 num[i]==0 此情况；将 n u m [ i ] num[i] num[i] 作为 a a a ， n u m [ j ] num[j] num[j] 作为 b b b， n u m [ k ] num[k] num[k] 作为 c c c，遍历 a a a ，以 b b b 为基地往右拓展 c c c ，若满足 c < a + b c < a + b c c a + b > c a+b>c 的边界情况中最大值 c c c，此时的 k k k 为延伸的最远的下标，遍历每一个 a a a ，累加 （ k − j ） （k - j） （k−j） 即为最终答案。

代码如下（示例）：

class Solution {
public:
    int triangleNumber(vector& nums) {
        int n = nums.size(), ans = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i ++) {
            if (nums[i] == 0) continue;
            int k = i + 1;
            for (int j = i + 1; j < n; j ++) {
                while (k + 1 < n && nums[k + 1] < nums[i] + nums[j])
                    k ++;
                ans += k - j;
            }

        }
        return ans;
    }
};

二、重构字符串

跳转力扣：767. 重构字符串
难度：★★☆☆☆

说明：大根堆，哈希表，首先用哈希表 m s ms ms 记录每一个字母出现的次数，并记录出现次数最大值 m a x n maxn maxn，若要有满足条件结果，需满足 m a x n maxn maxn 大于原字符串长度的一半；大根堆 h e a p heap heap 存放的元素为 p a i r < i n t , c h a r > pair pair （方便排序，所以把int放前面），首先将所有出现的字母放进堆中，然后每次取出出现次数最大与次大的两个元素作为答案并循环 *** 作，每次需将取出的元素的字母次数减一，若扔有次数则重新加入堆中，为保证奇偶的差异，需要在补充最后一个元素。

代码如下（示例）：

typedef pair pic;
class Solution {
public:
    string reorganizeString(string s) {
        int maxn = 0, n = s.size();
        if (n < 2) return s;
        unordered_map ms;
        for (auto &c: s) {
            ms[c] ++;
            maxn = max(ms[c], maxn);
        }
        if (maxn > (n + 1) / 2) return "";

        priority_queue heap;
        for (auto &m: ms) {
            heap.push({m.second, m.first});
        }
        string ans;
        while (heap.size() > 1) {
            auto t1 = heap.top(); heap.pop();
            auto t2 = heap.top(); heap.pop();
            ms[t1.second] --;
            ms[t2.second] --;
            ans += t1.second;
            ans += t2.second;
            if (ms[t1.second] > 0)
                heap.push({t1.first - 1, t1.second});
            if (ms[t2.second] > 0)
                heap.push({t2.first - 1, t2.second});
        }
        if (heap.size() > 0)
            ans += heap.top().second;
        return ans;
    }
};

三、最多能完成排序的块

跳转力扣：769. 最多能完成排序的块

难度：★★☆☆☆

说明：贪心算法，分块最多的情况是升序排序，分块最少的情况是降序排序，因此保证遍历到的每个元素是遍历到的数中的最大值，则可以分块处理。

代码如下（示例）：

class Solution {
public:
    int maxChunksToSorted(vector& arr) {
        int n = arr.size(), maxn = 0, ans = 0;
        for (int i = 0; i < n; i ++) {
            maxn = max(maxn, arr[i]);
            if (i == maxn) ans ++;
        }
        return ans;
    }
};