LeetCode 899.有序队列|字符串最小表示法的使用|求循环字符串的最小值
2022/8/5 23:22:46
本文主要是介绍LeetCode 899.有序队列|字符串最小表示法的使用|求循环字符串的最小值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题:899.Orderly Queue
Tags: #String
For a string s
, each time you can choose one of first k
letters and put it the end of string s
. What is the lexicographically smallest string you can obtain?
Example1:
Input: s="dbbca", k=1 Output: s="adbbc" Explanation: Continuously put the first letter to end of s till 'a' is the first letter.
Example2:
Input: s="baaca", k=3 Output: s="aaabc" Explanation: First move: 'b' to end, now s="aacab" Second move: 'c' to end, now s="aaabc"
Let's divide this problem into two situations:
- k>1
- k=1
k>1(Simple)
Let's consider k=2, we can move either the first letter or second letter to the end. If we move the second letter to the end, that is equal to move the letter advance one space in the string cycle: "bacc"
, move "a"
, then the string becomes "bcca"
, which is equal to "abcc
"(just cycle 3 times). So that means we can move any character to any where in the string. Then we can always obtain a sorted lexicographically smallest string.
Any other case where k>2 is also the same.
// if k>1 char[] arr=s.toCharArray(); Arrays.sort(arr); return String.valueOf(arr);
k=1(Interesting)
Each time we can only move one character to string end. That is Cyclic isomorphism(循环同构):
\[S_i=S[i,n]+S[0,i]=T \]\(S\) and \(T\) are called cyclic isomorphism.
To find the smallest cyclic isomorphism, we just need to index where the answer string starts in the string s
. So we need to compare those n=s.length()
strings.
Choose the i=0
, j=1
as two strings' beginning, compare them.
how to compare two string efficiently?
Compare each letter at same position of them. If s[i+k]<s[j+k]
, \(k\in(0,n)\), them string \(S_j\) must bigger than string \(S_i\). For example:
s="aaabc", i=0, j=1
:
k=0,1
,s[i+k]=s[j+k]='a'
k=2
,s[i+k]='a' < s[j+k]='b'
, so string \(S_i\) start withi=0: "aaabc"
is smaller than \(S_j\)"aabca"
which is start withj=1
.
So string \(S_j\) j=1
must not be the answer. Then we should j
start next?
where to start next?
Consider string \(A\) and \(B\), they are \(S_i\) and \(S_j\) of string s
, which means they start at \(i\) and \(j\). The first \(k\) letters of them are equal:
W.o.l.g, consider \(S[i+k]<S[j+k]\), then all string \(S_{j+m}\) where \(0\leq m\leq k\) can't be the answer. If \(S_{j+m}\) is the smallest answer, then \(S_{i+m}\) can be even smaller, cause \(S[i+k]<S[j+k]\).
So next j
should be \(j+k+1\).
complexity?
We only need to go through the string one time(till the bigger one of i
or j
reach the end). So the time complexity is \(O(n)\), that's quick!
Code:
public String orderlyQueue(String s, int m) { if (m == 1) { int i = 0, j = 1, k = 0, n = s.length(); while (i < n && j < n && k < n) { char iCh = s.charAt((i + k) % n), jCh = s.charAt((j + k) % n); if (iCh == jCh) k++; else { if (iCh > jCh) { 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 { char[] arr = s.toCharArray(); Arrays.sort(arr); return String.valueOf(arr); } }
Reference:
OI Wiki-最小表示法
宫水三叶的题解
这篇关于LeetCode 899.有序队列|字符串最小表示法的使用|求循环字符串的最小值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升