【算法】字典序超详细解析(让你有一种相见恨晚的感觉!)

这篇具有很好参考价值的文章主要介绍了【算法】字典序超详细解析(让你有一种相见恨晚的感觉!)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、前言

二、什么是字典序 ?

✨字典序概念

✨深度理解字典序

✨字典序排序的重要性和应用场景

 三、常考面试题

 ✨ 下一个排列

 ✨ 字典数排序

 ✨ 字典序最小回文串

 四、共勉


一、前言

    经常刷算法题的朋友,肯定会经常看到题目中提到 字典序 这样的字眼,或者需要我们通过字典序来解题,由于之前对字典序了解的不太清楚,导致做题的时候总会卡住,所以收集了一些资料来详解字典序。

二、什么是字典序 ?

 ✨字典序概念

    字典序(dictionary order),又称 字母序(alphabetical order),含义是表示英文单词在字典中的先后顺序,在计算机领域中扩展成两个任意字符串的大小关系。 

 举例:
       在字典中,单词是按照首字母在字母表中的顺序进行排列的,比如 alphabeta 之前。而第一个字母相同时,会去比较两个单词的第二个字母在字母表中的顺序,比如 accountadvanced 之前,以此类推。下列单词就是按照字典序进行排列的:

as

aster

astrolabe

astronomy

astrophysics

at

ataman

attack

baa

✨深度理解字典序

  • 在学习 字符串string 的时候,我们肯定接触过两个字符串之间的比较,比如”abc“ < “acb” < “acbd”, 其规则是先比较第一个字母,如果不相等,就直接得到结果,如果相等,就比较下一个字母。
  • 如果两个字符串的长度不相等,但是长的那个字符串包含了短的那个,那长的那个字符串更大(比如"acb" < “acbd”)
  • 在我们进行比较之前,有一个默认的排序规则,就是‘a' < 'b' < 'c' < ... < 'z'

举例:

对数字 【1,2,3,4,5,6,7,8,9,10,11,12,13】 按照字典序排列:
结果为 :【1,10,11,12,13,2,3,4,5,6,7,8,9】 

总结: 
      对于两个不同的字符串,从左到右逐个比较它们的字符,

  1. 如果在某个位置上它们的字符不同,则将它们按照该位置上的字符的字母顺序进行排序,即较小的字符排在前面,较大的字符排在后面。
  2. 如果一直比较到其中一个字符串结束,则较短的字符串排在前面;
  3. 如果两个字符串完全相同,则它们的字典序相同。可以将它们看作是按照字母表的顺序进行排列的。

 ✨字典序排序的重要性和应用场景

  1. 数据库索引:在数据库中,使用字典序排序可以加快查询速度。例如,对存储了字符串数据的列进行字典序排序,可以使得数据库在执行字符串比较操作时更高效。
  2. 字符串比较:在字符串比较场景中,字典序排序能够方便地判断两个字符串的大小关系。例如,在编程中,可以使用字典序排序来实现字符串的字母顺序排序、查找最大/最小字符串等操作。
  3. 文件系统排序:文件系统通常使用字典序排序来显示文件和目录的顺序。这样可以使得用户在文件浏览器中更容易找到特定的文件或目录。

 三、常考面试题

      通过上面的讲解,相信大家应该对 字典序 有了一个基础的了解,想要深刻的理解它,还是需要通过题目来理解。

 ✨ 下一个排列

链接:31. 下一个排列 - 力扣(LeetCode) 

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

 题目分析:

  • 说实话刚看题目我看了半天不知道在说什么,看到评论里面提到字典序算法才知道题意。我们拿题目中的例子1,2,3 ------> 1,3,2来说明:
  1. 首先本题讨论的范围是数字,数字中有一个规则,就是’0‘ < '1' < '2' < ... < '9',这与上面的a~z是一样的
  2. 然后就是1,2,3这三个数字,我们能够形成6种不同的组合,即123 < 132 < 213 < 231 < 312 < 321。
  3. OK,如果你看懂前面两点,本题已经完成了。我们要做的就是找到当前数 123 在第二点的六种排列中间的下一个位置是什么,即 132,那么 132 就是答案
  4. 如果要找的数字位于排列组合的最后一个一位,即 321,那么按照题目的第二行,我们就返回最小值 123.

上面从直觉上理解了什么是字典序算法,下面说下怎么转化成程序算法。

何时无解 

首先考虑无解情况,即上面所说的321,这种情况带入字典序算法是无解的,而321这种情况,如果我们单独拆分成3,2,1三个数字,其实是一个降序的过程: 

  • 因此如果当前排列是降序的,则字典序算法无解
  • 换而言之,如果不存在后一个数比前一个数大(2<3,1<2),字典序算法无解
  • 比如下图中的54321抽象出来的五个点,不存在后一个点大于前一个点,因此无解。

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

 有解的情况

 下面我们拿51432这个例子,来一步步说明如何通过字典序算法得到 52134 这个答案的

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

 1. 从右往左找,找到第一个右边比左边大的数

  • 首先我们从最右边的2开始,因为2 < 3,因此跳过。然后3 < 4,再跳过。然后发现4 > 1,OK,第一步完成。
  • 然后我们在上图中用黄色点标记这两个数,即1 和 4

2. 找到断点右边所有数中最小的一个 (包括断点)

  • 如果我们直接交换两个黄点,得到 54132,虽然也比 51432 大,但是它不符合字典序算法中的规则,因为这两个数中间还夹杂着别的数 51432 < 52134 < 52143 < 52314 < ...... < 54132,字典序算法中必须满足两个数之间不能夹杂其他数才行。
  • 而根据上面列举的,我们知道 52134 才是我i们想要的答案,它的特点就是我们需要把 1 换成2,而不是 4。
  • 而 2 实际上就是4,3,2中间的最小值,因此这一步我们要做的就是找到左边黄点(1)右边的所有数(4,3,2)中间最小的一个数(2),然后我们用 红点标记下来。
  • 之所以要交换1和2,而不是1和3或者1和4,是因为我们现在是要把千位的1换成一个更大中的最小的情况,因此要选2.

3.交换左边的黄点和红点 

  •  上面我们找到了红点(2),因此这一步我们需要讲红点跟左边的黄点(2)进行交换,得到52431

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

4. 对红点右边的数进行升序排序 

  • 此时,我们交换了千位的1和个位2,变成了52431.但是距离我们的最终答案52134还差了一步,52134 < 52143 < 52314 < 52341 < 52413 < 52431,👈由这个规则可以看到我们的千位和万位已经相同了,但是个十百位还未相同了,而因为我们要找的答案要尽可能小,因此需要进行升序排序,得到52134,大功告成!

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

 代码:

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        // 用于判断是否无解  -- 开始默认无解
          bool flag = 0;
        for(int i = nums.size()-1;i>0;i--)
        {
            if(nums[i]>nums[i-1])
            {
                // 有解
                flag = 1;
                // 初始化最小值 为右边断点 
                int min = nums[i],idx = i;
                // 向后找最小值
                for(int j = i+1;j<nums.size();j++)
                {
                    if(nums[j]<min && nums[j] > nums[i-1])
                    {
                        // 更新最小值
                        min = nums[j];
                        // 存储小标,便于后续交换
                        idx = j;
                    }
                }

                // 将右边最小值 和 左边最小值交换  (左右区分,以断点为界线)
                nums[i - 1]^= nums[idx];
                nums[idx]^= nums[i - 1];      // 小技巧  位运算  不用第三个参数来交换两个数
                nums[i - 1]^= nums[idx];

                // 将左边的数据 包括断点进行升序排序
                sort(nums.begin()+i,nums.end());
                break;
            }
        }
        // 确定误解  将动态数组全部进行 升序排序
        if(flag == 0)
        {
            sort(nums.begin(),nums.end());
        }
    }
};

 ✨ 字典数排序

 链接:386. 字典序排数 - 力扣(LeetCode)

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

class Solution {
public:
    static bool cmp(int a,int b)
    {
        string s1 = to_string(a);
        string s2 = to_string(b);
        // 字典升序
        return s1<s2;
    }
    vector<int> lexicalOrder(int n) 
    {
         vector<int> res;
         while(n!=0)
         {
            res.push_back(n);
            n--;
         }
         sort(res.begin(),res.end(),cmp);
         return res;
    }
};

 ✨ 字典序最小回文串

 链接:2697. 字典序最小回文串 - 力扣(LeetCode)

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言

 题目分析:

     对于两个中心对称的字母 x = s[i] 和 y = s[ n - 1 - i ] , 如果 x != y ,那么只需要修改一次,就可以让这两个字母相同:把 x 改成 y 或者 把 y 改成 x。

  • 如果 x > y , 那么把 x 修改成 y 更好 , 这样字典序更小
  • 如果 x < y , 那么把 y 修改成 x 更好 , 这样字典序更小

 代码:

class Solution {
public:
    string makeSmallestPalindrome(string s) 
    {
        // 双指针 分别指向 头部和尾部
        int begin = 0,end = s.size()-1;

        while(begin<end)
        {
            if(s[begin]!=s[end])
            {
                s[begin] = s[end] = min(s[begin],s[end]);
            }
            begin++;
            end--;
        }
        return s;
    }
};

 四、共勉

  以下就是我对 字典序 的理解,如果有不懂和发现问题的小伙伴,请在评论区说出来哦,同时我还会继续更新对 C++ 的更新,请持续关注我哦!!! 

【算法】字典序超详细解析(让你有一种相见恨晚的感觉!),算法面试题,# 排序,算法,c++,c语言,面试,开发语言文章来源地址https://www.toymoban.com/news/detail-845646.html

到了这里,关于【算法】字典序超详细解析(让你有一种相见恨晚的感觉!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 测量鼠标DPI的三种方法,总有一种适合你

    DPI(dots per inch)代表每英寸点数,是一种用于各种技术设备(包括打印机)的测量方法,但对于鼠标来说,指的是鼠标在桌面上移动1英寸的距离的同时,鼠标光标能够在屏幕上移动多少“点”。 许多游戏鼠标都有按钮,可以让你在玩游戏时动态切换DPI,但如果你不知道鼠标

    2024年01月16日
    浏览(43)
  • 有一种新型病毒在 3Ds Max 环境中传播,如何避免?

    3ds Max渲染慢,可以使用渲云渲染农场: 渲云渲染农场解决本地渲染慢、电脑配置不足、紧急项目渲染等问题,可批量渲染,批量出结果,速度快,效率高。 此外3dmax支持的 CG MAGIC插件专业版正式上线, CG MAGIC是一款基于3ds Max深度开发的免费智能化辅助插件,上千项实用功能

    2024年02月12日
    浏览(40)
  • 解决电脑无故自动关机或重启的15种方法,总有一种适合你

    你的Windows PC是否在没有警告的情况下关闭或重新启动?这背后有几个潜在的原因。例如,它可能是软件/硬件冲突、过热或硬盘驱动器错误。本故障排除指南将概述在Windows 10/11中修复自动关闭和重新启动的多个解决方案。 如果你的计算机经常关闭,则必须在安全模式下启动计

    2024年04月23日
    浏览(35)
  • 懒人必备!Python代码帮你自动发送会议纪要,让你有更多时间做更重要的事情

    目录 痛点: 应用场景: 源代码: 代码说明: 效果如下所示: 在传统的工作中,发送会议纪要是一个比较繁琐的任务,需要手动输入邮件内容、收件人、抄送人等信息,每次发送都需要重复操作,不仅费时费力,而且容易出现疏漏和错误。 但是,有了这个程序,员工们就可

    2023年04月18日
    浏览(73)
  • CT重建概念和算法详细解析

    Radon变换与逆变换的提出奠定CT图像重建的数学基础(1917) 卷积反投影算法/滤波反投影算法的提出开启了图像精确重建的大门(1971-1974) Feldkamp等人提出的FDK算法开启了图像三维重建的新纪元(1980) Katsevich解决了锥形束螺旋CT图像精确重建的轴向截断问题(2002) Pan等人提出

    2024年02月01日
    浏览(37)
  • 十分详细的diff算法原理解析

    本文我们总结一下有关 diff算法 的相关内容和实现原理 开门见山,直接先给出大家 diff算法 的概念 diff算法 可以看作是一种对比算法,对比的对象是 新旧虚拟Dom 。顾名思义, diff算法 可以找到 新旧虚拟Dom 之间的差异,但 diff算法 中其实并不是只有对比 虚拟Dom ,还有根据对

    2023年04月08日
    浏览(34)
  • 快速排序算法C++实现(超详细解析!!!!)

    目录 一、前言 (1)分治算法 (2)分治算法解题方法     1.分解:     2.治理:     3.合并: 二、快速排序 1.问题分析 2.算法设计     (1)分解:     (2)治理 :     (3)合并:     (4)基准元素的选取: 3.算法分析 三、AC代码  四、共勉     快速排序,其实是一种

    2024年02月03日
    浏览(41)
  • git回退--使用TortoiseGit小乌龟【我有一颗后悔药,服用说明图文详细,请对症下药】

    hi~ 你好!见到你很开心 ^ ^ 我听到你的呼唤啦 你说你一不小心做错事了,我这刚好有一颗后悔药 说不定等你吃完,就能回到事情发生前啦!祝你好运o! 下面我给大家 介绍 此款后悔药功效,请对症下药 药效: 可穿越回到 之前某一次提交的时刻 ( 本地与远端分支,均回退

    2024年02月08日
    浏览(46)
  • 银行家算法——C++实现 [ 开源代码 + 详细解析 ]

    ✅ (原创,纯手敲,开源免费,2021的最后一篇) Banker Algorithm 🏦 ◆ 说明 :上述算法的核心实现采用了 “DFS + 回溯” 的方法,详见后文的源代码。另外,如果把 C++ 代码里面的 “ p_num=1; ” 注释掉,得到的是另一个结果。我虽然输入是“0”,但代码里后面我直接把 p_num 赋值

    2023年04月26日
    浏览(74)
  • D* 算法完全解析(应该是全网最详细的吧)

    转载请注明出处,谢谢! 花了几天时间学习了下 D* 算法,只能说熟悉了一下流程,远不能说掌握,算法实在是非常巧妙 《制造车间无人搬运系统调度方法研究》 《基于D*Lite算法的移动机器人路径规划研究》 人工智能: 自动寻路算法实现(四、D、D*算法) D* 算法 D*路径规划算法

    2024年04月25日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包