字典序最小问题(贪心)
字典序是指从前到后比较两个字符串大小的方法。首先比较第1个字符,如果不同则第1个字符较小的字符串更小,一直这样子比较下去。比如:s1:ABCDE 和 s2:ABCCE 两个字符串,s1的 D 比 s2的 C要更加大一点,所以s1 > s2。现在有这样一个问题,给定长度为N的字符串S,要构造一个长度为 N 的字符串 T。起初 ,T 是一个空串,随后反复进行下列任意操作,从 S 的...
字典序是指从前到后比较两个字符串大小的方法。首先比较第1个字符,如果不同则第1个字符较小的字符串更小,一直这样子比较下去。
比如:
s1:ABCDE
和 s2:ABCCE
两个字符串,s1的 D 比 s2的 C要更加大一点,所以s1 > s2。
现在有这样一个问题,
给定长度为N的字符串S,要构造一个长度为 N 的字符串 T。起初 ,T 是一个空串,随后反复进行下列任意操作,
- 从 S 的头部删除一个字符,加到 T 的尾部。
- 从 S 的尾部删除一个字符,加到 T 的尾部。
目标是构造字典序最小的字符串 T。
这类题型一般利用贪心来做,贪心就是就是遵循某种规则,不断贪心地选取当前的最优策略的算法。
每做出的一步选择都是当前的最优策略,并不需要考虑整体,但难点就在于当前最优策略的选择,拿上面那道题继续分析,
要创建字典序最小的字符串T,我们只需要保证字符串的前面尽量较小,所以每次从字符串 S 的首尾取相对较小的加入到字符串 T 中,这就是策略,但这个策略还可能遇到一个问题,如果当首尾的字符此时相等的话,该如何选择?这时候就要比较下一个了,选择下一个字符里面相对较小的加入到字符串 T 中。这两者结合就是我们的贪心策略。
有点懵?
不急,我们来看看图解。
假定给定的字符串 S = “ACDBCB”,
一开始,两指针指向字符串 S 的首尾,比较两者的大小,将小的一位加入到字符串 T 中,
此时两指针对应的字符相等,这时候要判断下一位的大小,
B < D,所以将右侧的先加入,
应该够清晰了吧,那么我们可以写一下伪代码了,伪代码主要是总结以上思路,以便更好的转换成最终代码。
# String S;
# String T;
# left, right
while(left <= right) {
如果左边较小,将左边加入T;
如果右变较小,将右边加入T;
if(相等) {
i = left + 1;
j = right - 1;
while(i <= j) {
如果左边较小,将左边加入T;
如果右变较小,将右边加入T;
if(相等)
i++;
j--;
}
}
}
好,以上应该都比较好理解了,那可以直接转成我们的代码了。
class Solution {
public String bestCowLine(String S) {
String T = "";
int left = 0;
int right = S.length() - 1;
char[] temp = S.toCharArray();
//左右两指针,向中间移动
while(left <= right) {
//标记左边是否小过右边
boolean l = false;
//如果左右两边一致,就跳出循环,不一致就一直寻找
for(int i = 0; left + i <= right; i++) {
//如果左边小于右边,标记并跳出
if(temp[left + i] < temp[right - i]) {
l = true;
break;
}
//如果右边小于左边,标记并跳出
else if(temp[left + i] > temp[right - i]) {
l = false;
break;
}
}
//加入到字符串 T 中
if(left == true)
T += temp[left++];
else
T += tempS[right--];
}
return T;
}
}
整理于 2020.4.19
更多推荐
所有评论(0)