[LeetCode] 525. Contiguous Array

https://leetcode.com/contest/leetcode-weekly-contest-20/problems/contiguous-array/

Solution:
The straightforward way is of O(n2) time complexity, which is not what the OJ wants. There are only two elements in the vectors: 0 and 1. So we can define one variable to record the number difference of 0 and 1: sum. When it is 0, --sum; and when it is 1, ++sum. A hashmap is needed to connect the sum to the current position from which we can calculate the length of the subarray with the same number of 0 and 1. Then we need find the one with the maximum length.

In short, we will use map[sum] = i to record the position of i when the difference of the 0's and 1's number is sum. When the same sum appears again, let's say at position of j, then the subarray between i and j must contain the same number of 0 and 1.

Further thinking: how about there are three different elements in the array, and ask for the maximum subarray with the same number of each of them?

Code:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res = 0, sum = 0, n = nums.size();
        unordered_map<int, int> m;
        m[0] = 0;
        for(int i=0; i<n; ++i){
            if(nums[i] == 0) --sum;
            else ++sum;
            if(m.find(sum) != m.end()) res = max(res, i+1-m[sum]);
            else m[sum] = i+1;
        }
        return res;
    }
}; 

  

[LeetCode] 387. First Unique Character in a String

https://leetcode.com/contest/warm-up-contest/problems/first-unique-character-in-a-string/

Solution:
This is an easy level question. We may use the hash map to count the time of appearances for  each element. Then find the first element with count number of 1 (or the total number of this kind of element is 1). Since all the letters are in lower case, we can use a 26-letter long vector, instead of a hashmap. See code below.

Code:

class Solution {
public:
    int firstUniqChar(string s) {
        int res = -1, n = s.size();
        vector<int> count(26, 0);
        for(auto a:s) ++count[a-'a'];
        for(int i=0; i<n; ++i){
            if(count[s[i]-'a'] == 1) {
                res = i;
                break;
            }
        }
        return res;
    }
};

[LeetCode] 508. Most Frequent Subtree Sum

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/most-frequent-subtree-sum/

Solution:
first step to find all the sums of the subtrees; then save the ones appearing mostly. So the first step is the key for this question.
Using the properties of Tree, we can recursively find the sums of all the subtrees in a "bottom-up" fashion. See code below.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> m;
        int count = -1;
        findFTS(root, 0, m, count);
        for(auto a:m){
            if(a.second == count)
                res.push_back(a.first);
        } 
        return res;
    }
private: 
    int findFTS(TreeNode *r, int s, unordered_map<int, int> &m, int &ct){
        if(!r) return 0;
        int lt = findFTS(r->left, s, m, ct);
        int rt = findFTS(r->right, s, m, ct);
        s = lt + rt + r->val;
        ++m[s];
        ct = max(ct, m[s]);
        return s;
    }
};

[LeetCode] 500. Keyboard Row

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/keyboard-row/

Solution:
may use a hashmap to label the letters in the same row. Also need to pay attention to the upper or lower letters.

Code:

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> res;
        string v1="qwertyuiop", v2="asdfghjkl", v3="zxcvbnm";
        unordered_map<char, int> m;
        for(auto a:v1) m[a]=0;
        for(auto a:v2) m[a]=1;
        for(auto a:v3) m[a]=2;
        for(auto a:words){
            if(a.size()){
                int t = -1;
                if(m.find(a.front())!=m.end()) t = m[a.front()];
                else t = m[(a.front()+32)];
                bool flag = true;
                for(auto b:a){
                    if((m.find(b)!=m.end()&&m[b]==t) || (m.find(b+32)!=m.end()&&m[b+32]==t)) continue;
                    else{
                        flag = false;
                        break;
                    }
                }
                if(flag) res.push_back(a);
            }
        }
        return res;
    }
};

[LeetCode] 501. Find Mode in Binary Tree

https://leetcode.com/contest/leetcode-weekly-contest-17/problems/find-mode-in-binary-tree/
Find all the elements that appears mostly.

Solution:
Use a hashmap to count the time of duplicates. Then save the elements with the highest appearing time into the output.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        unordered_map<int, int> m;
        int ct = 0;
        findM(root, m, ct);
        for(auto a:m){
            if(a.second == ct) res.push_back(a.first);
        }
        return res;
    }
private:
    void findM(TreeNode* root, unordered_map<int, int> &m, int &c){
        if(!root) return;
        c = max(c, ++m[root->val]);
        findM(root->left, m, c);
        findM(root->right, m, c);
    }
};

[LeetCode] 316. Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/

Solution:
The hard part is the smallest in lexicographical order. So in addition to a hashmap, we also need an extra vector to label each elements for the status of visiting. First to count the appearance times for each letters in the input string. Then when scan the input string, for each new element, we need to compare it with the last letter in the output string. If the new element is smaller than the last letter in the string and also the counting for the last element is larger than 0 (which means there is still more than 0 elements in the rest part of the input string), we need to set the status of the last letter to be un-visited and remove it. Otherwise, we can add the new elements in the back of the output string and set the visiting status as true. See code below.

Code:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "0";
        vector<int> m(26, 0), visit(26, 0);
        for(auto a:s) ++m[a-'a'];
        for(auto a:s){
            int t = a-'a';
            --m[t];
            if(visit[t]) continue;
            while(a<res.back() && m[res.back()-'a']){
                visit[res.back()-'a'] = 0;
                res.pop_back();
            }
            res.push_back(a);
            visit[t] = 1;
        }
        return res.substr(1);
    }
}; 

Further thinking:
How about the largest lexicographical order?
Ans: set the res to be "~" or some others that are larger than 'z'; and then change the "a<res.back()" inside the while condition into "a>res.back()". Done.

http://www.cnblogs.com/grandyang/p/5085379.html

290. Word Pattern

https://leetcode.com/problems/word-pattern/

Solution:
Use double hash maps to build up one-to-one relationship.

Code:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> v(26, "");
        unordered_map<string, char> m;
        int i = 0, j = 0, l1 = pattern.size(), l2 = str.size();
        for(; i<l1 && j<l2; ++i){
            while(j<l2 && str[j] == ' ') ++j;
            int t = j;
            while(t<l2&&str[t] != ' ') ++t;
            string s = str.substr(j, t-j);
            if(v[pattern[i]-'a'] == "" && m.find(s) == m.end()){ 
                v[pattern[i]-'a'] = s;
                m[s] = pattern[i];
            }
            else{ 
                if(v[pattern[i]-'a'] != s || m[s] != pattern[i]) return false;
            }
            j = t;
        }
        return i == l1 && j == l2;
    }
};

187. Repeated DNA Sequences

https://leetcode.com/problems/repeated-dna-sequences/

Solution:

It is straightforward to use the "brute force" hash map method plus a sliding window with size of 10-letter. But something else can be applied to reduce the space complexity since it is too expensive when using string as the hash key.

We just need to distinguish four letters, so bitwise operation may be used and two bits are enough for four, i.e. 'A' can be 00, 'C' for 01, 'G' for 10, and 'T' for 11.

Two details need to consider:

1) : a mask may need to set all the bits beyond the first 20 from the left to be 0. (since we only need to consider the "10-letter" sub-sequences and each letter need 2 bits). 0xFFFFF represents the first 20 bits from the left are 1s, and all the rest are 0s. (F in hexadecimal is equivalent to 1111 in binary);

2): need to remove the possible duplicates. Can use set, but actually can also use hash map, see below.

Code:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        unordered_map<char, int> m1{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        unordered_map<int, int> m2;
        int i = 0, t = 0, mask = 0xfffff;  // the lower 20 bits are 1s;
        while(i<9) t = (t<<2) + m1[s[i++]];
        while(i<s.size()){
            t = ((t<<2) & mask) | m1[s[i++]];
            if(m2.find(t) == m2.end()) m2[t] = 1;
            else{ 
                if(m2[t] == 1){
                    res.push_back(s.substr(i-10, 10));
                    m2[t] = 0;
                }
            }
        }
        return res;
    }
};

128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

Solution:
My first response is to sort the array first, but this question requests time complexity of O(n). So we may need some help from data structures, like hash table, set, ... Will use hash table, first to built up hash table; then scan the array again, for each element, will check the existence its neighbor in value with the help of hash table built.  Then find the longest one to return.

Code:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_map<int, bool> m;
        for(auto i:nums) m[i] = true;//built up hash table (or map);
        for(auto i:nums){
            if(m[i]){
                int len = 1;
                int j = 1;
                while(m[i+j]){//search larger direction in value;
                    ++len;
                    m[i+j] = false;
                    ++j;
                }
                j = 1;
                while(m[i-j]){//search smaller direction in value;
                    ++len;
                    m[i-j] = false;
                    ++j;
                }
                m[i] = false;
                res = max(res, len);
            }
        }
        return res;
    }
}; 

1: Two Sum

https://leetcode.com/problems/two-sum/

solution:
不用hash table的话，需要double pointers. 这样的就 O(n2) 了。
使用hash table的话， 就很直观的 O(n) 了。 然后需要注意一些细节， 比如不要重复计入了， 还有就是可以扫一遍就行了 （hash的同时就可以判断了）。

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int, int> map;
        for(int i=0; i<nums.size(); ++i){
            if(map.find(target-nums[i])!=map.end()&&i>map[target-nums[i]]){
                res.push_back(map[target-nums[i]]);
                res.push_back(i);
                return res;
            }
            else map[nums[i]]=i;
        }
        return res;
    }
};