从零学算法2810

2810.你的笔记本键盘存在故障，每当你在上面输入字符 ‘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” 。

• 最直观的想法就是直接翻译题意，遍历字符串，遇到 i 就翻转已经遍历的部分，否则加上字符。

•   public String finalString(String s) {StringBuilder sb = new StringBuilder();for(int i=0;i<s.length();i++){char c = s.charAt(i);if(c == 'i')sb.reverse();else sb.append(c);}return sb.toString();}
  

• 而如果有大量 i，大量的翻转操作会使得时间复杂度较高，其实当一个字符串被翻转时，就相当于我们逆序读取它，所以当遇到 i 后，我们把 i 之后的字符加到字符串头部即可，比如 string，我们会得到 gnistr，然后逆序输出得到 rtsing。
• 而如果再遇到一个 i，我们再换回正序读取即可，这时又从尾部拼接字符，比如 abicdief 我们会得到 ab，然后遇到 i 开始从头部拼接得到 dcab，并且最终要逆序读取来输出它即 bacd；但是最后又遇到了 i，此时如果后面没有字符了，我们只需要再换成正序读取它其实就是我们要的结果即 dcab，后面还有字符就继续往尾部添加字符串即可得到 dcabef，最后正序输出它就是最终结果，所以使用双端队列即可，用一个变量记录我们是否要逆序拼接并逆序读取。

•   public String finalString(String s) {Deque<Character> dq = new LinkedList<>();  // 是否要逆序boolean isReverse = false;for(int i=0;i<s.length();i++){char c = s.charAt(i);if(c == 'i')isReverse=!isReverse;// 逆序就拼接到头部else if(isReverse)dq.offerFirst(c);// 正常是添加到末尾else dq.offerLast(c);}StringBuilder sb = new StringBuilder();for(char c:dq)sb.append(c);if(isReverse)sb.reverse();return sb.toString();}