目录
- 一、概念
- 二、模板
- 三、例题
- 题:899. 有序队列
- 解:
一、概念
最小表示法是用于解决字符串最小表示问题的方法。
循环同构:
当字符串 S 中可以选定一个位置 i 满足则称 S 与 T 循环同构
最小表示:
字符串 S 的最小表示为与 S 循环同构的所有字符串中字典序最小的字符串
算法流程:
- 初始化指针 i 为 0,j 为 1;初始化匹配长度 k 为 0
- 比较第 k 位的大小,根据比较结果跳转相应指针。若跳转后两个指针相同,则随意选一个加一以保证比较的两个字符串不同
- 重复上述过程,直到比较结束
- 答案为 i, j 中较小的一个
时间复杂度:O(N)
二、模板
int i = 0, j = 1, k = 0, n = s.length();
while(i < n && j < n && k < n) {
int a = chars[(i + k) % n], b = chars[(j + k) % n];
if(a == b) k ++;
else {
if(a > b) i += k + 1; else j += k + 1;
if(i == j) i ++;
k = 0;
}
}
i = Math.min(i, j);
三、例题
题:899. 有序队列
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个,并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后,字典上最小的字符串 。
示例 1:
输入:s = "cba", k = 1
输出:"acb"
解释:
在第一步中,我们将第一个字符(“c”)移动到最后,获得字符串 “bac”。
在第二步中,我们将第一个字符(“b”)移动到最后,获得最终结果 “acb”。
示例 2:
输入:s = "baaca", k = 3
输出:"aaabc"
解释:
在第一步中,我们将第一个字符(“b”)移动到最后,获得字符串 “aacab”。
在第二步中,我们将第三个字符(“c”)移动到最后,获得最终结果 “aaabc”。
提示:
1 <= k <= S.length <= 1000
s 只由小写字母组成。
解:
- 当 k > 1时,我们可以构造出任意的字符方案,所以可直接通过排序得到答案。
- 当 k = 1时,我们共有n种候选方案(将字符串看作一个首尾相接的循环字符串,共有n个起点可枚举)
解题思路:模拟
AC代码:
class Solution {
public String orderlyQueue(String s, int k) {
if(k == 1) {
StringBuilder sb = new StringBuilder(s);
for(int i = 1; i < s.length(); ++ i) {
sb.append(sb.charAt(0)).deleteCharAt(0);
if(sb.toString().compareTo(s) < 0) {
s = sb.toString();
}
}
return s;
} else {
char[] chars = s.toCharArray();
Arrays.sort(chars);
return String.valueOf(chars);
}
}
}
解题思路:最小表示法
AC代码:
class Solution {
public String orderlyQueue(String s, int _k) {
char[] chars = s.toCharArray();
if(_k == 1) {
int i = 0, j = 1, k = 0, n = s.length();
while(i < n && j < n && k < n) {
int a = chars[(i + k) % n], b = chars[(j + k) % n];
if(a == b) k ++;
else {
if(a > b) i += k + 1; else j += k + 1;
if(i == j) i ++;
k = 0;
}
}
i = Math.min(i, j);
return s.substring(i) + s.substring(0, i);
} else {
Arrays.sort(chars);
return String.valueOf(chars);
}
}
}