(哈希表，滑动窗口，栈) lintcode 646

class Solution {
public:
    /**
     * @param s: a string
     * @return: it's index
     */
    int firstUniqChar(string &s) {
        // write your code here
        vector<int> cnt(256, 0);
        for(int i=0; i<s.size(); i++)
            cnt[s[i]] ++;
        
        for(int i=0; i<s.size(); i++){
            if(cnt[s[i]] == 1)
                return i;
        }
        return -1;
    }
};

 

 A 和 B 互为 anagram 的充分必要条件是 ： A中每个字符出现的次数 = B中每个字符出现的次数

class Solution {
public:
    /**
     * @param s: a string
     * @param p: a string
     * @return: a list of index
     */
     //sliding window + hash
    vector<int> findAnagrams(string &s, string &p) {
        // write your code here
        // 返回所有同构串的首地址
        vector<int> ans;
        vector<int> cnt(256, 0), cnp(256, 0);
        
        if(s.size() < p.size())
            return ans;
            
        for(int i=0; i<p.size(); i++){
            //统计每个字符出现的次数
            cnt[s[i]] ++;
            cnp[p[i]] ++;
        }
        
        if(cnt == cnp)
            ans.push_back(0);
            
        //sliding window
        for(int i=p.size(); i<s.size(); i++){
            cnt[s[i]]++;  //增加右边
            cnt[s[i-p.size()]] --;   //减少左边
            if(cnt == cnp)
                ans.push_back(i-p.size()+1);
        }
        
        return ans;
    }
};

 

 

class ValidWordAbbr {
public:
    /*
    * @param dictionary: a list of words
    */
    unordered_map<string, int> abbr;
    unordered_map<string, int> dict;
    
    ValidWordAbbr(vector<string> dictionary) {
        // do intialization if necessary
        for(int i=0; i<dictionary.size(); i++){
            string w = dictionary[i];
            dict[w]++;   //统计字符串的个数
            
            //abbr dictionary 统计每个字符串缩写的个数
            if(w.size() <= 2)
                abbr[w]++;   
            else
                abbr[w.front()+to_string(w.size()-2)+w.back()]++;
        }
    }

    /*
     * @param word: a string
     * @return: true if its abbreviation is unique or false
     */
    bool isUnique(string &word) {
        // write your code here
        if(word.size()<=2)
            return abbr[word]==dict[word];
        else
            return abbr[word.front()+to_string(word.size()-2)+word.back()]==dict[word];
    }
};

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * bool param = obj.isUnique(word);
 */

 要求O(n)的时间复杂度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> map(nums.begin(), nums.end());
        int ans = 0;
        for(int i=0; i<nums.size(); i++){
            if(map.find(nums[i]) != map.end()){
                map.erase(nums[i]);
                int pre = nums[i]-1;
                int next = nums[i]+1;
                while(map.find(pre) != map.end()){
                    map.erase(pre);
                    pre--;
                }
                while(map.find(next) != map.end()){
                    map.erase(next);
                    next++;
                }
                ans = max(ans, next-pre-1);
            }
        }
        return ans;
    }
};

 

 解法：栈

 首先在栈中加入空串，这样可以将b和c情况合为一种情况，如：()) 这样会判断为 ‘ ’ 和 ) 不匹配，返回false

class Solution {
public:
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    bool isValidParentheses(string &s) {
        // write your code here
        //栈
        vector<char> stack;
        stack.push_back(' ');  //压入空字符，作为dummy 0
        for(char w : s){
            if(w == '(' || w == '[' || w == '{')
                stack.push_back(w);
            else if(w == ')'){
                if(stack.back() != '(')
                    return false;
                else
                    stack.pop_back();
            }
            else if(w == ']'){
                if(stack.back() !='[')
                    return false;
                else
                    stack.pop_back();
            }
            else if(w == '}'){
                if(stack.back() !='{')
                    return false;
                else
                    stack.pop_back();
            }
        }
        if(stack.back() != ' ')
            return false;
        return true;
    }
};

 

 

class LoadBalancer {
public:
    int p;
    vector<int> array;
    unordered_map<int, int> mp;
    
    LoadBalancer() {
        // do intialization if necessary
        p = 0;
        srand((unsigned)time(NULL));
    }

    /*
     * @param server_id: add a new server to the cluster
     * @return: nothing
     */
    void add(int server_id) {
        // write your code here
        if(mp.find(server_id) == mp.end()){
            //mp中没找到对应元素，插入
            array.push_back(server_id);
            mp[server_id] = p;
            p++;
        }
    }

    /*
     * @param server_id: server_id remove a bad server from the cluster
     * @return: nothing
     */
    void remove(int server_id) {
        // write your code here
        if(mp.find(server_id) != mp.end()){
            mp[array[p-1]] = mp[server_id];  //将mp里array最后一个元素,对应的位置更新为mp中key为server_id对应的位置
            array[mp[server_id]] = array[p-1];   //将array中server_id的位置用array的最后一个元素替换
            array.pop_back();    //删掉array的最后一个元素
            mp.erase(server_id);  //删掉mp中的 server_id
            p--;
        }
    }

    /*
     * @return: pick a server in the cluster randomly with equal probability
     */
    int pick() {
        // write your code here
        return array[rand()%p];
    }
};