营销型网站应用,今天热搜榜前十名,品牌型网站开发,wordpress免费汉化2810.你的笔记本键盘存在故障#xff0c;每当你在上面输入字符 ‘i’ 时#xff0c;它会反转你所写的字符串。而输入其他字符则可以正常工作。 给你一个下标从 0 开始的字符串 s #xff0c;请你用故障键盘依次输入每个字符。 返回最终笔记本屏幕上输出的字符串。 示例 1每当你在上面输入字符 ‘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 i0;is.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) {DequeCharacter dq new LinkedList(); // 是否要逆序boolean isReverse false;for(int i0;is.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();}
