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

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

[解题报告] 《算法零基础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;
    }
};

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/zaji/5593963.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-12-15
下一篇2022-12-15

随机推荐

  • 全包装修也叫什么装修

    导读:房屋交易买卖完成后,业主一般就开始计划装修事宜,如果担心怕麻烦的情况下可能会选择找装修公司并全包,那么全包装修也叫什么装修?全包装修也叫包工包料装修,也就是说所有材料采购和施工都由施工方负责,对于业主来说这是最省心的一种装修方式,同时

    2022-12-29
    1800
  • 机舱电胶布可以在网上买吗

    机舱电胶布可以在网上买,也可以在实体店购买,注意区分产品质量,尽量选择可靠的店铺进行购买。电胶布是指电工胶带,全名为聚氯乙烯电气绝缘胶粘带,适用于电线的缠绕,以及变压器、马达、电容器、稳压器等各类电机、电子零件的绝缘固定用。有红、黄、蓝、白

    2022-12-29
    2000
  • 生猪饲料价格最近新闻报道,生猪及饲料价格行情的影响

    猪肉价格持续下跌,“带崩”了温氏股份的业绩。近日,南都记者透过温氏股份披露的2021年财报注意到,该公司去年全年净亏损达134.04亿元,相比2020年同期的盈利74.25亿元大跌280.51%,这意味着温氏股份在去年一年,亏掉了2020

    2022-12-29
    1600
  • 台湾的特产有哪些

    台湾是我国的特别行政区,很多人喜欢到台湾游玩,既然要到台湾,那就一定要知道台湾有哪些特产,那么台湾的特产有哪些呢?台湾的特产有哪些1、冻顶乌龙茶:产地为台湾鹿谷乡凤凰村永隆村彰雅村(冻顶巷),茶区海拔约600-1000公尺,依以上三点为核心

    2022-12-29
    1700
  • 新手号原神200抽能出限定吗

    新手号原神200抽能出限定。原神200抽必获得当期UP的所有武器和圣痕,是可以抽到限定的。200抽如果全抽角色池,能抽出3个五星角色;如果全抽武器池,能抽出将近4把五星武器。《原神》是由上海米哈游网络科技股份有限公司制作发行的一款开放世界冒

  • 物业服务费用是怎么算的

    导读:如今交房之后业主是要缴纳物业服务费的,当然除了特殊情况之后,是可以不缴纳的,比如说物业公司违约,那么物业服务费用是怎么算的?物业费是根据政府指导价以及产权面积计算。一级收费标准每月1元每平米;二级收费标准每月0.75元每平米;三级收费

    2022-12-29
    2300
  • 网站推广团队_品牌产品校园推广方式

    校园营销是在产品市场营销推广过程中,扩大学校竞争力的一个重要手段。通过对营销手段,营销工具以及营销策略进行有机整合,从而形成有效的营销系统,且将这种营销方案运用到学校市场之中,最终达到部分效果之和大于整体的效果。而且校园营销不仅可以把学生发

    2022-12-29
    1200
  • 如何查看买的房被开发商抵押没_如何查询房产证是否解压贷款

    我们们买房时不管是楼盘还是二手房都要查看房间产权证,关于新闻曾报道业主购房,后来发现房间产权证被开发商抵押给了银行,那么我们们要怎么查询房产附近抵押?楼盘查验房产是不是被开发商抵押我国《担保法》中明确规范,房地产开发商将购买土地在建期房的

  • 外贸soho操作流程_soho外贸怎么样

    前几天发了个文章《 工厂自营自销环境下,外贸公司还有生存空间吗?》,在评论中,有不少人表示了他们的看法与担忧。“ 最后说说小单的问题,一旦工厂的贸易部起来,你们还会认为工厂会做贸易商手头的小单吗?!而原本工厂就对小单并不感冒的情况,贸易商

    2022-12-29
    1600

发表评论

登录后才能评论

评论列表(0条)

    保存