当前位置：首页 > news >正文

力扣字典序问题详解

news 来源：原创 2024/9/28 12:07:31

1.字典序大小比较方法

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

2.力扣例题

①：386. 字典序排数

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。 示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]示例 2：
输入：n = 2
输出：[1,2]

// 字典序排序问题比较适合于DFS
// 所以本题采用DFS+递归的方式解决
class Solution {private List<Integer> res=new ArrayList<>();private int n;public List<Integer> lexicalOrder(int n) {this.n=n;for (int i = 1; i <= 9; i++) {dfs(i);}return res;}private void dfs(int n) {if(n>this.n){return;}res.add(n);for (int i = 0; i <= 9; i++) {dfs(n*10+i);}}
}

②：2697. 字典序最小回文串

给你一个由 小写英文字母 组成的字符串 s ，你可以对其执行一些操作。在一步操作中，你可以用其他小写英文字母 替换  s 中的一个字符。
请你执行 尽可能少的操作 ，使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种，则只需选取 字典序最小 的方案。
对于两个长度相同的字符串 a 和 b ，在 a 和 b 出现不同的第一个位置，如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早，则认为 a 的字典序比 b 的字典序要小。
返回最终的回文字符串。示例 1：
输入：s = "egcfe"
输出："efcfe"
解释：将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。示例 2：
输入：s = "abcd"
输出："abba"
解释：将 "abcd" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。示例 3：
输入：s = "seven"
输出："neven"
解释：将 "seven" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "neven" 。

class Solution {public String makeSmallestPalindrome(String s) {StringBuilder sb=new StringBuilder(s);int len=sb.length();for (int i = 0; i <len/2 ; i++) {if(sb.charAt(i)!=sb.charAt(len-i-1)){char c=(char) Math.min(sb.charAt(i),sb.charAt(len-i-1));sb.setCharAt(i,c);sb.setCharAt(len-i-1,c);}}return sb.toString();}
}