做网站 什么语言,江苏网站建设多少钱,网站制作介绍,负责网站建设推广题目链接
去除重复字母
题目描述 注意点
s 由小写英文字母组成1 s.length 10^4需保证 返回结果的字典序最小#xff08;要求不能打乱其他字符的相对位置#xff09;
解答思路
本题与移掉 K 位数字类似#xff0c;需要注意的是#xff0c;并不是每个字母都能…题目链接
去除重复字母
题目描述 注意点
s 由小写英文字母组成1 s.length 10^4需保证 返回结果的字典序最小要求不能打乱其他字符的相对位置
解答思路
本题与移掉 K 位数字类似需要注意的是并不是每个字母都能被移除而是要移除重复字母保证字符串中每个字母都只出现了一次又因为要保证结果的字典序最小要尽可能保证前面的字母更小所以要尽可能保证字符串是严格递增的没办法保证一定递增部分字母不重复无法去除对于任意一个位置处的字母ch有以下几种情况 如果ch已经加入到结果中因为字母不能重复则不会继续加入到结果中如果ch还未加入到结果中且此时结果末尾处的字母小于ch则直接将ch加入到结果中如果ch还未加入到结果中且此时结果末尾处的字母大于ch且剩余字符串中已经没有末尾处的字母则不能弹出末尾字母保证末尾字母有出现在结果中直接将ch加入到结果中如果ch还未加入到结果中且此时结果末尾处的字母大于ch且剩余字符串中还有末尾处的字母则需要弹出末尾字母直到满足上面两个要求为止再将ch加入到结果中
代码
class Solution {public String removeDuplicateLetters(String s) {// 存储到某个位置时剩余字符串中每个小写字母的数量int[] arr new int[26];// 存储每个小写字母是否已经添加到结果集中boolean[] visited new boolean[26];for (int i 0; i s.length(); i) {arr[s.charAt(i) - a];}StringBuilder sb new StringBuilder();for (int i 0; i s.length(); i) {char ch s.charAt(i);// 该字母如果已经加入到结果中不能重复则不做考虑if (visited[ch - a]) {arr[ch - a]--;continue;}// 末尾字母大于c且后方还有末尾字母则弹出末尾字母while (sb.length() 0 sb.charAt(sb.length() - 1) ch arr[sb.charAt(sb.length() - 1) - a] 0) {visited[sb.charAt(sb.length() - 1) - a] false;sb.deleteCharAt(sb.length() - 1);}sb.append(ch);visited[ch - a] true;arr[ch - a]--;}return sb.toString();}
}关键点
怎么保证结果的字典序最小怎么保证原有字符串中的字母在结果中都出现且只出现了一次
