leetcode轮回计划20181204

1. 392 Is Subsequence
   题意：给定两个字符串s和t，判断t是否是s的子序列（s删除一部分字符可以得到t）。
   思路：hashmap
2. 394 Decode String
   题意：s = "3[a2[c]]", return "accaccacc".
   思路：分治，注意细节。

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return decodeString(s,i);
    }
    string decodeString(string& s, int& i){
        string ret;
        while(i < s.size() && s[i] != ']'){
            if(!isdigit(s[i])) ret += s[i++];
            else{
                int n = 0;
                while(i < s.size() && isdigit(s[i])){
                    n = n * 10 + s[i ++] - '0';
                }
                
                ++ i;
                string t = decodeString(s, i);
                ++ i;
                while(n --> 0) ret += t;
            }
        }
        
        return ret;
    }
};

3. 395 Longest Substring with At Least K Repeating Characters
   题意：最大子串，需要满足子串中所有的字符的数量都大于k。
   思路：

def longestSubstring(self, s, k):
    if len(s) < k:
        return 0
    c = min(set(s), key=s.count)
    if s.count(c) >= k:
        return len(s)
    return max(self.longestSubstring(t, k) for t in s.split(c))

c++版本：

class Solution {
public:
    int longestSubstring(string s, int k) {
        if(s.size() < k) return 0;
        int imin = INT_MAX;
        char curr;
        unordered_map<char, int> mp;
        for(auto a : s) mp[a]++;
        for(auto a : mp) if(a.second < imin){
            imin = a.second;
            curr = a.first;
        }
        if(imin >= k) return s.size();
        stringstream ss(s);
        string currstring;
        vector<string> list;
        while(getline(ss, currstring, curr)) list.push_back(currstring);
        int ret = INT_MIN;
        for(auto a : list) ret = max(ret, longestSubstring(a, k));
        
        return ret;
    }
};

4. 396 Rotate Function
5. 397 Integer Replacement
   思路：map
6. 398 Random Pick Index
7. 399 Evaluate Division
   题意：给出一部分算式的结果，求另一部分算式的结果
   思路：图

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, unordered_map<string, double>> m;
        vector<double> ret;
        for(int i = 0;i < values.size();++ i){
            m[equations[i].first].insert(make_pair(equations[i].second, values[i]));
            if(values[i] != 0)
                m[equations[i].second].insert(make_pair(equations[i].first, 1 / values[i]));
        }
        for(auto a : queries){
            unordered_set<string> s;
            double tmp = check(a.first, a.second, m, s);
            if(tmp) ret.push_back(tmp);
            else ret.push_back(-1);
        }
        return ret;
    }
    double check(string up, string down, unordered_map<string, unordered_map<string, double>>& m, unordered_set<string>& s){
        if(m[up].find(down) != m[up].end()) return m[up][down];
        for(auto a : m[up]){
            if(s.find(a.first) == s.end()){
                s.insert(a.first);
                double tmp = check(a.first, down, m, s);
                if(tmp) return a.second * tmp;
            }
        }
        return 0;
    }
};

8. 400 Nth Digit

public int findNthDigit(int n) {
    n -= 1;
    int digits = 1, first = 1;
    while (n / 9 / first / digits >= 1) {
        n -= 9 * first * digits;
        digits++;
        first *= 10;
    }
    return (first + n/digits + "").charAt(n%digits) - '0';
}