首页 > 其他 > 详细

Remove Duplicate Letters

时间:2015-12-24 11:54:31      阅读:192      评论:0      收藏:0      [点我收藏+]

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"

 

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int ahead[256] = {};    //直接定义256,不用减‘a’了
        for (char c : s)
            ahead[c]++;        //统计每个数出现的次数
    
        string result = " ";
        bool inresult[256] = {};    //记录是否出现过这个值了
    
        for (char c : s) {    //从头开始扫描
            ahead[c]--;        //每出现一次就--
            if (inresult[c])        //如果已经记录过了就跳过
                continue;
    //如果当前值,比结果的最后一个值小,并且结果的最后值的计数大于0(后面还有)
    //则把最后一个值弹出,并把它的状态变为false
            while (c < result.back() && ahead[result.back()]) {
                inresult[result.back()] = false;
                result.pop_back();
            }
            result += c;
            inresult[c] = true;
        }
    
        return result.substr(1);    //第一个为空格;使用一个空格的原因是back()函数必须里面有值
    }
};
  • 使用一个栈,先把东西都扔进去,如果发现后面的数比前面的小,并且前面的值计数还不为0则弹出该值

Remove Duplicate Letters

原文:http://www.cnblogs.com/dylqt/p/5072568.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!