查询公司信息的网站,制作广告的软件,精品设计网站,自己怎么创建一个网站目录
一、前言
二、什么是字典序 #xff1f;
✨字典序概念
✨深度理解字典序
✨字典序排序的重要性和应用场景 三、常考面试题 ✨ 下一个排列 ✨ 字典数排序 ✨ 字典序最小回文串 四、共勉 一、前言 经常刷算法题的朋友#xff0c;肯定会经常看到题目中提到 字典序 这样…目录
一、前言
二、什么是字典序
✨字典序概念
✨深度理解字典序
✨字典序排序的重要性和应用场景 三、常考面试题 ✨ 下一个排列 ✨ 字典数排序 ✨ 字典序最小回文串 四、共勉 一、前言 经常刷算法题的朋友肯定会经常看到题目中提到 字典序 这样的字眼或者需要我们通过字典序来解题由于之前对字典序了解的不太清楚导致做题的时候总会卡住所以收集了一些资料来详解字典序。 二、什么是字典序 ✨字典序概念 字典序dictionary order又称 字母序alphabetical order含义是表示英文单词在字典中的先后顺序在计算机领域中扩展成两个任意字符串的大小关系。 举例 在字典中单词是按照首字母在字母表中的顺序进行排列的比如 alpha 在 beta 之前。而第一个字母相同时会去比较两个单词的第二个字母在字母表中的顺序比如 account 在 advanced 之前以此类推。下列单词就是按照字典序进行排列的
asasterastrolabeastronomyastrophysicsatatamanattackbaa
✨深度理解字典序
在学习 字符串string 的时候我们肯定接触过两个字符串之间的比较比如”abc“ “acb” “acbd”, 其规则是先比较第一个字母如果不相等就直接得到结果如果相等就比较下一个字母。如果两个字符串的长度不相等但是长的那个字符串包含了短的那个那长的那个字符串更大比如acb “acbd”在我们进行比较之前有一个默认的排序规则就是‘a b c ... z
举例
对数字 【12345678910111213】 按照字典序排列
结果为 【11011121323456789】 总结 对于两个不同的字符串从左到右逐个比较它们的字符 如果在某个位置上它们的字符不同则将它们按照该位置上的字符的字母顺序进行排序即较小的字符排在前面较大的字符排在后面。如果一直比较到其中一个字符串结束则较短的字符串排在前面如果两个字符串完全相同则它们的字典序相同。可以将它们看作是按照字母表的顺序进行排列的。 ✨字典序排序的重要性和应用场景 数据库索引在数据库中使用字典序排序可以加快查询速度。例如对存储了字符串数据的列进行字典序排序可以使得数据库在执行字符串比较操作时更高效。字符串比较在字符串比较场景中字典序排序能够方便地判断两个字符串的大小关系。例如在编程中可以使用字典序排序来实现字符串的字母顺序排序、查找最大/最小字符串等操作。文件系统排序文件系统通常使用字典序排序来显示文件和目录的顺序。这样可以使得用户在文件浏览器中更容易找到特定的文件或目录。 三、常考面试题 通过上面的讲解相信大家应该对 字典序 有了一个基础的了解想要深刻的理解它还是需要通过题目来理解。 ✨ 下一个排列 链接31. 下一个排列 - 力扣LeetCode 题目分析 说实话刚看题目我看了半天不知道在说什么看到评论里面提到字典序算法才知道题意。我们拿题目中的例子1,2,3 ------ 1,3,2来说明
首先本题讨论的范围是数字数字中有一个规则就是’0‘ 1 2 ... 9,这与上面的a~z是一样的然后就是123这三个数字我们能够形成6种不同的组合即123 132 213 231 312 321。OK如果你看懂前面两点本题已经完成了。我们要做的就是找到当前数 123 在第二点的六种排列中间的下一个位置是什么即 132那么 132 就是答案如果要找的数字位于排列组合的最后一个一位即 321那么按照题目的第二行我们就返回最小值 123. 上面从直觉上理解了什么是字典序算法下面说下怎么转化成程序算法。 何时无解
首先考虑无解情况即上面所说的321这种情况带入字典序算法是无解的而321这种情况如果我们单独拆分成321三个数字其实是一个降序的过程
因此如果当前排列是降序的则字典序算法无解换而言之如果不存在后一个数比前一个数大23,12字典序算法无解比如下图中的54321抽象出来的五个点不存在后一个点大于前一个点因此无解。 有解的情况 下面我们拿51432这个例子来一步步说明如何通过字典序算法得到 52134 这个答案的 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 实际上就是432中间的最小值因此这一步我们要做的就是找到左边黄点1右边的所有数432中间最小的一个数2然后我们用 红点标记下来。之所以要交换1和2而不是1和3或者1和4是因为我们现在是要把千位的1换成一个更大中的最小的情况因此要选2. 3.交换左边的黄点和红点 上面我们找到了红点2因此这一步我们需要讲红点跟左边的黄点2进行交换得到52431 4. 对红点右边的数进行升序排序 此时我们交换了千位的1和个位2变成了52431.但是距离我们的最终答案52134还差了一步52134 52143 52314 52341 52413 52431,由这个规则可以看到我们的千位和万位已经相同了但是个十百位还未相同了而因为我们要找的答案要尽可能小因此需要进行升序排序得到52134大功告成 代码 class Solution {
public:void nextPermutation(vectorint nums) {// 用于判断是否无解 -- 开始默认无解bool flag 0;for(int i nums.size()-1;i0;i--){if(nums[i]nums[i-1]){// 有解flag 1;// 初始化最小值 为右边断点 int min nums[i],idx i;// 向后找最小值for(int j i1;jnums.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 class Solution {
public:static bool cmp(int a,int b){string s1 to_string(a);string s2 to_string(b);// 字典升序return s1s2;}vectorint lexicalOrder(int n) {vectorint res;while(n!0){res.push_back(n);n--;}sort(res.begin(),res.end(),cmp);return res;}
}; ✨ 字典序最小回文串 链接2697. 字典序最小回文串 - 力扣LeetCode 题目分析 对于两个中心对称的字母 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(beginend){if(s[begin]!s[end]){s[begin] s[end] min(s[begin],s[end]);}begin;end--;}return s;}
}; 四、共勉 以下就是我对 字典序 的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对 C 的更新请持续关注我哦
