思路

這道題讓我們從一個字符串數字中刪除 k 個數字，使得剩下的數最小。也就說，我們要保持原來的數字的相對位置不變。

以題目中的 num = 1432219， k = 3 為例，我們需要返回一個長度為 4 的字符串，問題在于： 我們怎么才能求出這四個位置依次是什么呢？

這里有一個前置知識：對于兩個數 123a456 和 123b456，如果 a > b， 那么數字 123a456 大于 數字 123b456，否則數字 123a456 小于等于數字 123b456。也就說，兩個相同位數的數字大小關系取決于第一個不同的數的大小。

因此我們的思路就是：
1、從左到右遍歷。
2、對于遍歷到的元素，我們選擇保留。
3、但是我們可以選擇性丟棄前面相鄰的元素。

以題目中的 num = 1432219， k = 3 為例的圖解過程如下：
1、

由于沒有左側相鄰元素，因此沒辦法丟棄。

2、

由于 4 比左側相鄰的 1 大。如果選擇丟棄左側的 1，那么會使得剩下的數字更大（開頭的數從 1 變成了 4）。因此我們仍然選擇不丟棄。

3、

由于 3 比左側相鄰的 4 小。 如果選擇丟棄左側的 4，那么會使得剩下的數字更小（開頭的數從 4 變成了 3）。因此我們選擇丟棄。

然而需要注意的是，如果給定的數字是一個單調遞增的數字，那么我們的算法會永遠選擇不丟棄。這個題目中要求的，我們要永遠確保丟棄 k 個矛盾。

題目要求我們丟棄 k 個。反過來說，不就是讓我們保留 n - k個元素么？其中 n 為數字長度。 那么我們只需要按照上面的方法遍歷完成之后，再截取前n - k個元素即可。

class Solution { public:string removeKdigits(string num, int k) {int size=num.size();if(size==k) return "0";int need=size-k;//要求刪掉k個元素，則最后需要保留size-k個元素//stack<string> st;string res;for(int ii=0;ii<size;ii++){char temp=num[ii];//還需要丟棄并且棧內還有元素供我們丟棄并且棧頂元素比當前遍歷的元素大，那么就需要丟棄棧頂元素，使得整體變小while(k>0&&!res.empty()&&res[res.size()-1]>temp){res.pop_back();k--;}res+=temp;}res=res.substr(0,need);//循環刪除前導0 如"0","001"while(*res.begin()=='0'&&res.size()!=1){res.erase(res.begin());//順序容器內部刪除一個元素用erase,這個函數會返回下一個有效的迭代器}return res;} };

TX筆試:
我們定義兩個長度相等的字符串比較最優時，字典序大的那個是更優的。

現在給你一個字符串s,字符串的元素全是小寫英文字母a~z，你可以在這個字符串中按順序選擇一個長度為k的子序列(可以不連續)，現在想問你最優子序列是什么。

兩個長度相等的字符串的字典序的比較規則如下:
比較它們第一次出現的不相等的字母，該字母大的那個字符串字典序更大，例如: “abac” 大于"aazy",因為第一次出現的不等字母是第2個，且’b’ 大于’a’。

#include <string> #include <vector> #include <iostream> using namespace std;int main(){int n,k;//序列長度和選擇元素的個數cin>>n>>k;string s;cin>>s;int size=s.size();int KK=size-k;//需要刪除的元素個數int need=k;//最后需要的元素個數string res;for(int ii=0;ii<size;ii++){char temp=s[ii];while(KK>0&&!res.empty()&&res[res.size()-1]<temp){res.pop_back();KK--;}res+=temp;}res=res.substr(0,need);cout<<res<<endl;}

總結

以上是生活随笔為你收集整理的402.移掉K位数字，使得剩下数字最小的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。