目标
你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
示例 1：
输入：s = "string"
输出："rtsng"
解释：
输入第 1 个字符后，屏幕上的文本是："s" 。
输入第 2 个字符后，屏幕上的文本是："st" 。
输入第 3 个字符后，屏幕上的文本是："str" 。
因为第 4 个字符是 'i' ，屏幕上的文本被反转，变成 "rts" 。
输入第 5 个字符后，屏幕上的文本是："rtsn" 。
输入第 6 个字符后，屏幕上的文本是： "rtsng" 。
因此，返回 "rtsng" 。示例 2：
输入：s = "poiinter"
输出："ponter"
解释：
输入第 1 个字符后，屏幕上的文本是："p" 。
输入第 2 个字符后，屏幕上的文本是："po" 。
因为第 3 个字符是 'i' ，屏幕上的文本被反转，变成 "op" 。
因为第 4 个字符是 'i' ，屏幕上的文本被反转，变成 "po" 。
输入第 5 个字符后，屏幕上的文本是："pon" 。
输入第 6 个字符后，屏幕上的文本是："pont" 。
输入第 7 个字符后，屏幕上的文本是："ponte" 。
输入第 8 个字符后，屏幕上的文本是："ponter" 。
因此，返回 "ponter" 。说明：
- 1 <= s.length <= 100
- s 由小写英文字母组成
- s[0] != 'i'
思路
当输入i的时候，之前所有的输入都需要反转，i字符本身不显示。使用split无法处理连续为i以及结尾为i的情况。
最直接的做法就是模拟操作，但是反转字符串的复杂度较高。考虑使用双端队列，当反转时，相当于从队首加入字符，从队尾开始读取。
代码
/**
* @date 2024-04-01 8:42
*/
public class FinalString2810 {
public String finalString_v1(String s) {
StringBuilder res = new StringBuilder();
Deque<Character> q = new ArrayDeque<>();
boolean reverse = false;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if ('i' == ch) {
reverse = !reverse;
} else if (reverse) {
q.push(ch);
} else {
q.offer(ch);
}
}
Iterator<Character> it;
if (reverse) {
it = q.descendingIterator();
} else {
it = q.iterator();
}
while (it.hasNext()) {
res.append(it.next());
}
return res.toString();
}
public String finalString(String s) {
StringBuilder res = new StringBuilder();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if ('i' == chars[i]) {
res.reverse();
} else {
res.append(chars[i]);
}
}
return res.toString();
}
}性能
按道理来说应该是finalString_v1更快一些，res.reverse()时间复杂度是 O(n/2)，会将元素左右互换。但是leetcode显示的用时分布反而finalString更快，耗时是finalString_v1的一半2ms，应该与数据规模有关吧，字符串长度最大才100。finalString_v1有更多的流程控制，还体现不出性能。
