資訊專欄INFORMATION COLUMN
摘要：首先要求就是得保證在原來(lái)的字符串中存在當(dāng)前字符的順序，即要保證每次的字符的次數(shù)大于。讀字符的過(guò)程中，把字符存到里，當(dāng)發(fā)現(xiàn)之前存的字符中比當(dāng)前字符大而且頻率還大于就可以把那個(gè)字符出去。基本思想就是在一定的限制條件下出比當(dāng)前選擇差的元素。
Remove Duplicate Letters
分析 方法一Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given "bcabc"
Return "abc"Given "cbacdcbc"
Return "acdb"
這道題可以采用Greedy的思想，因?yàn)樽詈笙胍慕Y(jié)果是最小值，所以我們?cè)跐M足要求的情況下把不斷append最小的字符, 最后便可得到最小的字符串.
關(guān)鍵點(diǎn)就是要滿足什么要求以及怎么樣去滿足。首先要求就是得保證在原來(lái)的字符串中存在當(dāng)前字符append的順序，即要保證每次append的字符的次數(shù)大于0。我們可以用一個(gè)數(shù)組記錄每個(gè)字符出現(xiàn)的次數(shù)，用一個(gè)指針從左到右掃，過(guò)程中減小對(duì)應(yīng)字符次數(shù)，找當(dāng)前最小字符, 找的過(guò)程中終止條件是發(fā)現(xiàn)某個(gè)字符次數(shù)等于0，因?yàn)槔^續(xù)掃的話最終結(jié)果很有可能缺那個(gè)字符.
方法二其實(shí)跟上個(gè)方法差不多，但是可以優(yōu)化下，用stack的話，最多每個(gè)字符過(guò)兩遍就可以了。讀字符的過(guò)程中，把字符存到stack里，當(dāng)發(fā)現(xiàn)stack之前存的字符中比當(dāng)前字符大而且頻率還大于0就可以把那個(gè)字符pop出去。類(lèi)似這種題目都可以用stack解決。基本思想就是在一定的限制條件下pop出比當(dāng)前選擇差的元素。
復(fù)雜度 方法一time: O(kn), space: O(k), k表示原字符串中unique字符的個(gè)數(shù)
方法二time: O(n), space: O(k)
代碼 方法一public class Solution {
public String removeDuplicateLetters(String s) {
if (s == null ||s.length() == 0)
return s;
// 記錄每個(gè)字符出現(xiàn)的次數(shù)
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - "a"]++;
}
// 找出當(dāng)前最小字符
int pos = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) < s.charAt(pos))
pos = i;
// 避免無(wú)字符可用
if (--cnt[s.charAt(i) - "a"] == 0)
break;
}
// 除去字符串中已經(jīng)append的字符的所有重復(fù)值
return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
}
}
方法二
public class Solution {
public String removeDuplicateLetters(String s) {
int[] freqs = new int[256];
// 統(tǒng)計(jì)字符頻率
for (int i = 0; i < s.length(); i++) {
freqs[s.charAt(i)]++;
}
boolean[] visited = new boolean[256]; // 用來(lái)標(biāo)記存在stack里的字符
Deque q = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
freqs[c]--;
if (visited[c]) continue;
// pop出stack當(dāng)中比當(dāng)前字符大但后面還存在的的字符，
while (!q.isEmpty() && q.peek() > c && freqs[q.peek()] > 0) {
visited[q.pop()] = false;
}
q.push(c);
visited[c] = true;
}
StringBuilder sb = new StringBuilder();
for (char c : q) {
sb.append(c);
}
return sb.reverse().toString();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65332.html
摘要：復(fù)雜度思路用一個(gè)每次考慮當(dāng)前的字符大小和的頂端字符的大小，如果當(dāng)前字符比較小的話，則可以出頂端的字符，將當(dāng)前的字符放進(jìn)中。需要維持了一個(gè)判斷當(dāng)前字符在剩余字符串中的出現(xiàn)次數(shù)，考慮能否將這個(gè)字符從棧中彈出。 LeetCode[316] Remove Duplicate Letters Given a string which contains only lowercase letter...
Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...
摘要：以及枚舉的做法，因?yàn)檫@題只有個(gè)字母，枚舉的復(fù)雜度是，參考博客還有先把排序，然后從小到大取字母的寫(xiě)法，參考 316. Remove Duplicate Letters 題目鏈接：https://leetcode.com/problems... 用一個(gè)stack來(lái)做，stack里面的字母按增序來(lái)排，出現(xiàn)top>cur的時(shí)候要把top給pop出來(lái)，注意一點(diǎn)是如果后面沒(méi)有top的話，就不能po...
摘要：每個(gè)字母只留一個(gè)，而且保證字典序最小。從前往后掃描，還要往前看一個(gè)檢出是否刪除的，要用解。需要一個(gè)數(shù)據(jù)結(jié)構(gòu)記錄是否使用這個(gè)字母，可以用。結(jié)構(gòu)也可以用數(shù)組加頂點(diǎn)指針模擬。 316 Remove Duplicate Given a string which contains only lowercase letters, remove duplicate letters so that e...
Problem Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms o...
閱讀 1441·2021-11-25 09:43
閱讀 2044·2021-07-26 23:38
閱讀 751·2019-08-30 15:53
閱讀 2289·2019-08-30 15:43
閱讀 1180·2019-08-29 18:40
閱讀 1981·2019-08-26 13:28
閱讀 1983·2019-08-23 18:20
閱讀 555·2019-08-23 15:07
