|
精品推薦：
《征服數(shù)據(jù)結(jié)構(gòu)》專(zhuān)欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服 《經(jīng)典圖論算法》專(zhuān)欄：50多種經(jīng)典圖論算法全部掌握 最近在網(wǎng)上看到一篇文章，列出了華為的校招薪資，從學(xué)歷來(lái)看，要求還挺高的，不過(guò)薪資給的也高。校招最多都能給到53.2萬(wàn)(無(wú)線算法)，所以如果學(xué)歷好的話，還是建議大家學(xué)算法，下面我們就來(lái)看一道華為的算法題。 --------------下面是今天的算法題-------------- 來(lái)看下今天的算法題，這題是LeetCode的第316題：去除重復(fù)字母。也是華為?？嫉囊坏浪惴}。 給你一個(gè)字符串 s ，請(qǐng)你去除字符串中重復(fù)的字母，使得每個(gè)字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最?。ㄒ蟛荒艽騺y其他字符的相對(duì)位置）。 輸入：s = "cbacdcbc" 輸出："acdb"
1 <= s.length <= 104 s 由小寫(xiě)英文字母組成
這題是讓刪除字符串 s 中的重復(fù)字符，使每個(gè)字符只出現(xiàn)一次，需要保證返回結(jié)果的字典序最小，并且還不能打亂字符的相對(duì)位置。
解決思路就是使用一個(gè)棧，然后遍歷字符串中的每個(gè)字符，如果當(dāng)前字符在棧中出現(xiàn)了就不用管了，因?yàn)槊總€(gè)字符只能出現(xiàn)一次。如果當(dāng)前字符在棧中沒(méi)有出現(xiàn)，我們就需要把它添加到棧中，添加的時(shí)候因?yàn)橐ＷC字典序最小，所以要和棧頂元素比較，如果當(dāng)前字符比棧頂元素小并且棧頂元素在后面還會(huì)出現(xiàn)，就把棧頂元素給刪除，接著繼續(xù)重復(fù)上面的步驟。
舉個(gè)例子，比如棧中元素是[a,b,e]（右邊是棧頂），當(dāng)我們添加字符 c 的時(shí)候，因?yàn)闂ｍ斪址?e 比當(dāng)前字符 c 大：1，假設(shè)字符串后面還有 e ，這個(gè)時(shí)候我們就可以把 e 給移除掉，在后面的時(shí)候可以在加 e 。2，假設(shè)字符串后面沒(méi)有 e 了，就不能把字符 e 給移除，因?yàn)橐瞥?，后面沒(méi)有了就沒(méi)法在添加了。
這里的關(guān)鍵點(diǎn)是怎么判斷后面還有沒(méi)有待移除的字符呢？很簡(jiǎn)單，我們只需要在開(kāi)始的時(shí)候計(jì)算每個(gè)字符的個(gè)數(shù)即可，用掉一個(gè)就減去一個(gè)。最后棧中的字符就是需要返回的結(jié)果，我們還需要把他轉(zhuǎn)化為字符串。public String removeDuplicateLetters(String s) {
Stack<Character> stk = new Stack<>();// 棧
int[] count = new int[128];// 統(tǒng)計(jì)每個(gè)字符的數(shù)量
for (int i = 0; i < s.length(); i++)
count[s.charAt(i)]++;
// 記錄對(duì)應(yīng)的字符有沒(méi)有添加到棧中
boolean[] add = new boolean[128];
for (char ch : s.toCharArray()) {
count[ch]--;// 遍歷到當(dāng)前字符，數(shù)量要減1
if (add[ch])// 如果當(dāng)前字符已經(jīng)添加到棧中就跳過(guò)
continue;
// 如果當(dāng)前字符沒(méi)有添加到棧中，棧頂字符比當(dāng)前字符大
// 并且棧頂字符在后面還有，就讓棧頂字符出棧。
while (!stk.isEmpty() && stk.peek() > ch
&& count[stk.peek()] > 0) {
add[stk.pop()] = false;// 標(biāo)記為false
}
stk.push(ch);// 把當(dāng)前字符添加到棧中
add[ch] = true;
}
// 這里是把棧中的字符轉(zhuǎn)化為字符串。
StringBuilder sb = new StringBuilder();
while (!stk.isEmpty())
sb.append(stk.pop());
return sb.reverse().toString();
}
public:
string removeDuplicateLetters(string s) {
stack<char> stk;// 棧
vector<int> count(128);// 統(tǒng)計(jì)每個(gè)字符的數(shù)量
for (char ch: s)
count[ch]++;
// 記錄對(duì)應(yīng)的字符有沒(méi)有添加到棧中
vector<bool> add(128, false);
for (char ch: s) {
count[ch]--;// 遍歷到當(dāng)前字符，數(shù)量要減1
if (add[ch])// 如果當(dāng)前字符已經(jīng)添加到棧中就跳過(guò)
continue;
// 如果當(dāng)前字符沒(méi)有添加到棧中，棧頂字符比當(dāng)前字符大
// 并且棧頂字符在后面還有，就讓棧頂字符出棧。
while (!stk.empty() && stk.top() > ch && count[stk.top()] > 0) {
add[stk.top()] = false;
stk.pop();
}
stk.push(ch);// 把當(dāng)前字符添加到棧中
add[ch] = true;
}
// 這里是把棧中的字符轉(zhuǎn)化為字符串。
string str;
while (!stk.empty()) {
str.push_back(stk.top());
stk.pop();
}
reverse(str.begin(), str.end());
return str;
}
def removeDuplicateLetters(self, s: str) -> str:
stk = [] # 棧
count = Counter(s) # 統(tǒng)計(jì)每個(gè)字符的數(shù)量
# 記錄對(duì)應(yīng)的字符有沒(méi)有添加到棧中
add = [0] * 128
for ch in s:
count[ch] -= 1 # 遍歷到當(dāng)前字符，數(shù)量要減1
if add[ord(ch)]: # 如果當(dāng)前字符已經(jīng)添加到棧中就跳過(guò)
continue
'''
如果當(dāng)前字符沒(méi)有添加到棧中，棧頂字符比當(dāng)前字符大
并且棧頂字符在后面還有，就讓棧頂字符出棧。
'''
while stk and stk[-1] > ch and count[stk[-1]] > 0:
add[ord(stk[-1])] = 0 # 標(biāo)記為false
stk.pop()
stk.append(ch) # 把當(dāng)前字符添加到棧中
add[ord(ch)] = 1
# 這里是把棧中的字符轉(zhuǎn)化為字符串。
return ''.join(stk)
博哥，真名：王一博，畢業(yè)十多年，《算法秘籍》作者，專(zhuān)注于數(shù)據(jù)結(jié)構(gòu)和算法的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫(xiě)算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以下載我整理的1000多頁(yè)的PDF算法文檔。數(shù)組，稀疏表(Sparse Table)，單向鏈表，雙向鏈表，塊狀鏈表，跳表，隊(duì)列和循環(huán)隊(duì)列，雙端隊(duì)列，單調(diào)隊(duì)列，棧，單調(diào)棧，雙端棧，散列表，堆，字典樹(shù)(Trie樹(shù))，ArrayMap，SparseArray，二叉樹(shù)，二叉搜索樹(shù)(BST)，笛卡爾樹(shù)，AVL樹(shù)，樹(shù)堆(Treap)，FHQ-Treap，哈夫曼樹(shù)，滾動(dòng)數(shù)組，差分?jǐn)?shù)組，LRU緩存，LFU緩存 …… 《經(jīng)典圖論算法》專(zhuān)欄 圖的介紹，圖的表示方式，鄰接矩陣轉(zhuǎn)換，廣度優(yōu)先搜索(BFS)，深度優(yōu)先搜索(DFS)，A*搜索算法，迭代深化深度優(yōu)先搜索(IDDFS)，IDA*算法，雙向廣度優(yōu)先搜索，迪杰斯特拉算法(Dijkstra)，貝爾曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓?fù)渑判?/span>，約翰遜算法(Johnson) ……
|
