暴力、最小表示法及其变形最大表示法 2 种算法，双指针技巧，求解《899. 有序队列》和《 1163. 按字典序排在最后的子串》
例题
899. 有序队列
给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
示例 1：
输入：s = "cba", k = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
答案
暴力比较
var orderlyQueue = function(s, k) {
let r = s
if (k === 1) {
const n = s.length
for (let i = 1; i < n; i++) {
const t = s.substring(i, n) + s.substring(0, i)
if (r > t) r = t
}
} else {
return s.split('').sort().join('')
}
return r
};class Solution {
function orderlyQueue($s, $k) {
if ($k === 1) {
$r = $s;
$n = strlen($s);
for ($i = 1; $i < $n; $i++) {
$t = substr($s, $i, $n) . substr($s, 0, $i);
if ($r > $t) $r = $t;
}
return $r;
} else {
$a = str_split($s);
sort($a);
return join('', $a);
}
}
}func orderlyQueue(s string, k int) string {
if k == 1 {
n, r := len(s), s
for i := 1; i < n; i++ {
t := s[i:] + s[:i]
if t < r {
r = t
}
}
return r
}
t := []byte(s)
sort.Slice(t, func(i, j int) bool {
return t[i] < t[j]
})
return string(t)
}class Solution {
public String orderlyQueue(String s, int k) {
if (k == 1) {
String r = s;
int n = s.length();
for (int i = 1; i < n; i++) {
String t = s.substring(i, n) + s.substring(0, i);
if (t.compareTo(r) < 0) r = t;
}
return r;
} else {
char[] t = s.toCharArray();
Arrays.sort(t);
return new String(t);
}
}
}public class Solution {
public string OrderlyQueue(string s, int k) {
if (k == 1) {
string r = s;
int n = s.Length;
for (int i = 1; i < n; i++) {
string t = s.Substring(i, n - i) + s.Substring(0, i);
if (t.CompareTo(r) < 0) r = t;
}
return r;
} else {
char[] t = s.ToCharArray();
Array.Sort(t);
return new string(t);
}
}
}static inline int cmp (const void *pa, const void *pb) {
return *(char *)pa - *(char *)pb;
}
char * orderlyQueue(char * s, int k){
int n = strlen(s);
if (k == 1) {
char* r = malloc(sizeof(char) * (n + 1));
strcpy(r, s);
for (int i = 1; i < n; i++) {
char t = s[0];
for (int j = 0; j < n - 1; j++) {
s[j] = s[j + 1];
}
s[n - 1] = t;
if (strcmp(s, r) < 0) strcpy(r, s);
}
return r;
}
qsort(s, n, sizeof(char), cmp);
return s;
}class Solution {
public:
string orderlyQueue(string s, int k) {
if (k == 1) {
string r = s;
int n = s.size();
for (int i = 1; i < n; i++) {
string t = s.substr(i, n - i) + s.substr(0, i);
if (t < r) r = t;
}
return r;
}
sort(s.begin(), s.end());
return s;
}
};class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
return min(s[i:] + s[:i] for i in range(len(s))) if k == 1 else ''.join(sorted(s))class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
return min(s[i:] + s[:i] for i, _ in enumerate(s)) if k == 1 else ''.join(sorted(s))最小表示法
function orderlyQueue(s: string, k: number): string {
if (k === 1) {
const n = s.length
let i = k = 0, j = 1
while (i < n && j < n && k < n) {
if (s[(i + k) % n] === s[(j + k) % n]) k++
else {
if (s[(i + k) % n] > s[(j + k) % n]) i++
else j++
k = 0
if (i === j) i++
}
}
if (i > j) i = j
return s.substring(i, n) + s.substring(0, i)
} else {
return s.split('').sort().join('')
}
};class Solution {
function orderlyQueue($s, $k) {
if ($k === 1) {
$i = $k = 0;
$j = 1;
$n = strlen($s);
while ($i < $n && $j < $n && $k < $n) {
$a = $s[($i + $k) % $n];
$b = $s[($j + $k) % $n];
if ($a === $b) $k++;
else {
if ($a > $b) $i += $k + 1;
else $j += $k + 1;
$k = 0;
if ($i === $j) $i++;
}
}
if ($i > $j) $i = $j;
return substr($s, $i, $n) . substr($s, 0, $i);
} else {
$a = str_split($s);
sort($a);
return join('', $a);
}
}
}func orderlyQueue(s string, k int) string {
if k == 1 {
i, j, k, n := 0, 1, 0, len(s)
for i < n && j < n && k < n {
a, b := s[(i + k) % n], s[(j + k) % n]
if a == b {
k++
} else {
if a > b {
i += k + 1
} else {
j += k + 1
}
k = 0
if i == j {
i++
}
}
}
if i > j {
i = j
}
return s[i:] + s[:i]
}
t := []byte(s)
sort.Slice(t, func(i, j int) bool {
return t[i] < t[j]
})
return string(t)
}class Solution {
public String orderlyQueue(String s, int k) {
if (k == 1) {
int i = 0, j = 1, len = 0, n = s.length();
while (i < n && j < n && len < n) {
int a = s.charAt((i + len) % n), b = s.charAt((j + len) % n);
if (a == b) len++;
else {
if (a > b) i += len + 1;
else j += len + 1;
len = 0;
if (i == j) i++;
}
}
if (i > j) i = j;
return s.substring(i, n) + s.substring(0, i);
} else {
char[] t = s.toCharArray();
Arrays.sort(t);
return new String(t);
}
}
}public class Solution {
public string OrderlyQueue(string s, int k) {
if (k == 1) {
int i = 0, j = 1, n = s.Length;
k = 0;
while (i < n && j < n && k < n) {
int a = s[(i + k) % n], b = s[(j + k) % n];
if (a == b) k++;
else {
if (a > b) i += k + 1;
else j += k + 1;
k = 0;
if (i == j) i++;
}
}
if (i > j) i = j;
return s.Substring(i, n - i) + s.Substring(0, i);
} else {
char[] t = s.ToCharArray();
Array.Sort(t);
return new string(t);
}
}
}static inline int cmp (const void *pa, const void *pb) {
return *(char *)pa - *(char *)pb;
}
char * orderlyQueue(char * s, int k){
int n = strlen(s);
if (k == 1) {
int i = 0, j = 1, len = 0;
while (i < n && j < n && len < n) {
int a = s[(i + len) % n], b = s[(j + len) % n];
if (a == b) len++;
else {
if (a > b) i += len + 1;
else j += len + 1;
len = 0;
if (i == j) i++;
}
}
if (i > j) i = j;
char* r = malloc(sizeof(char) * (n + 1));
for (int j = 0; j < n; j++) {
r[j] = s[i++ % n];
}
r[n] = '\0';
return r;
}
qsort(s, n, sizeof(char), cmp);
return s;
}class Solution {
public:
string orderlyQueue(string s, int k) {
if (k == 1) {
int i = 0, j = 1, len = 0, n = s.size();
while (i < n && j < n && len < n) {
char a = s[(i + len) % n], b = s[(j + len) % n];
if (a == b) len++;
else {
if (a > b) i += len + 1;
else j += len + 1;
len = 0;
if (i == j) i++;
}
}
if (i > j) i = j;
return s.substr(i, n - i) + s.substr(0, i);
}
sort(s.begin(), s.end());
return s;
}
};class Solution:
def orderlyQueue(self, s: str, k: int) -> str:
if k == 1:
i, j, k, n = 0, 1, 0, len(s)
while i < n and j < n and k < n:
a, b = s[(i + k) % n], s[(j + k) % n]
if a == b: k += 1
else:
if a > b: i += k + 1
else: j += k + 1
k = 0
if i == j: i += 1
if i > j: i = j
return s[i:] + s[:i]
return ''.join(sorted(s))1163. 按字典序排在最后的子串
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。
示例 1：
输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
答案
最大表示法
var lastSubstring = function(s) {
let i = 0, j = 1, k = 0, n = s.length
while (j + k < n) {
const a = s[i + k], b = s[j + k]
if (a === b) k++
else {
if (a > b) j += k + 1
else i += k + 1
k = 0
if (i == j) j++
}
}
return s.substring(i)
};function lastSubstring(s: string): string {
let i = 0, j = 1, k = 0, n = s.length
while (j + k < n) {
const a = s[i + k], b = s[j + k]
if (a == b) k++
else {
if (a > b) j += k + 1
else i += k + 1
k = 0
if (i == j) j++
}
}
return s.substring(i)
};class Solution {
function lastSubstring($s) {
$n = strlen($s);
$i = 0;
$j = 1;
$k = 0;
while ($j + $k < $n) {
$a = $s[$i + $k];
$b = $s[$j + $k];
if ($a == $b) $k++;
else {
if ($a > $b) $j += $k + 1;
else $i += $k + 1;
$k = 0;
if ($i == $j) $j++;
}
}
return substr($s, $i);
}
}func lastSubstring(s string) string {
i, j, k, n := 0, 1, 0, len(s)
for j + k < n {
a, b := s[i + k], s[j + k]
if a == b {
k++
} else {
if a > b {
j += k + 1
} else {
i += k + 1
}
k = 0
if i == j {
j++
}
}
}
return s[i:]
}class Solution {
public String lastSubstring(String s) {
int i = 0, j = 1, k = 0, n = s.length();
while (j + k < n) {
char a = s.charAt(i + k), b = s.charAt(j + k);
if (a == b) k++;
else {
if (a > b) j += k + 1;
else i += k + 1;
k = 0;
if (i == j) j++;
}
}
return s.substring(i);
}
}public class Solution {
public string LastSubstring(string s) {
int i = 0, j = 1, k = 0, n = s.Length;
while (j + k < n) {
char a = s[i + k], b = s[j + k];
if (a == b) k++;
else {
if (a > b) j += k + 1;
else i += k + 1;
k = 0;
if (i == j) j++;
}
}
return s.Substring(i);
}
}char * lastSubstring(char * s){
int i = 0, j = 1, k = 0, n = strlen(s);
while (j + k < n) {
char a = s[i + k], b = s[j + k];
if (a == b) k++;
else {
if (a > b) j += k + 1;
else i += k + 1;
k = 0;
if (i == j) j++;
}
}
char * r = malloc(sizeof(char) * (n + 1 - i));
strncpy(r, s + i, n + 1 - i);
return r;
}class Solution {
public:
string lastSubstring(string s) {
int i = 0, j = 1, k = 0, n = s.size();
while (j + k < n) {
char a = s[i + k], b = s[j + k];
if (a == b) k++;
else {
if (a > b) j += k + 1;
else i += k + 1;
k = 0;
if (i == j) j++;
}
}
return s.substr(i);
}
};class Solution:
def lastSubstring(self, s: str) -> str:
i, j, k, n = 0, 1, 0, len(s)
while j + k < n:
a, b = s[i + k], s[j + k]
if a == b: k += 1
else:
if a > b: j += k + 1
else: i += k + 1
k = 0
if i == j: j += 1
return s[i:]