LIKE CODING

Monday, July 25, 2016

LeetCode [341] Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,4,6].

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
    stack<vector<NestedInteger>::iterator> its, ends;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        its.push(nestedList.begin());
        ends.push(nestedList.end());
    }

    int next() {
        auto it = its.top();
        int v = it->getInteger();
        its.top()++;
        return v;
    }

    bool hasNext() {
        while(!its.empty())
        {
            if(its.top() == ends.top())
            {
                its.pop();
                ends.pop();
            }
            else
            {
                auto it = its.top();
                if(it->isInteger()) return true;
                its.top()++;//current "it" is a list, and the list to stack and move to the next
                its.push(it->getList().begin());
                ends.push(it->getList().end());
            }
        }
        return false;
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

Monday, July 11, 2016

LeetCode [340] Longest Substring with At Most K Distinct Characters

340. Longest Substring with At Most K Distinct Characters

Hard

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int counts[256] = {0};
        int sz = s.size(), start = 0, distincts = 0, ret = 0;
        for(int e=0; e<sz; ++e)
        {
            if(counts[s[e]]==0) distincts++;
            counts[s[e]]++;
            if(distincts>k)
            {
                while(counts[s[start]])
                {
                    if(--counts[s[start]] == 0) break;   
                    start++;
                }
                start++;
                distincts--;
            }
            ret = max(ret, e-start+1);
        }
        return ret;
    }
};

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length(), i = 0, j = 0, longest = 0, d = 0;
        Map<Character, Integer> map = new HashMap<>();
        while(j<n){
            char cur = s.charAt(j++);
            if(map.getOrDefault(cur, 0)==0) d++;
            map.put(cur, (map.getOrDefault(cur, 0)+1));
            while(d>k){
                char last = s.charAt(i++);
                map.put(last, map.get(last)-1);
                if(map.get(last)==0) d--;
            }
            longest = Math.max(longest, j-i);
        }
        return longest;
    }
}

LeetCode [339] Nested List Weight Sum

LeetCode [338] Counting Bits

LeetCode [337] House Robber III

337. House Robber III

Medium

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

//C++
/**
 * 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> dfs(TreeNode *node) {
    if (node == nullptr) return {0, 0};
    vector<int> rv1 = dfs(node->left);
    vector<int> rv2 = dfs(node->right);
    vector<int> rv(2, 0);
    rv[0] = rv1[1] + rv2[1] + node->val;
    rv[1] = max(rv1[0], rv1[1]) + max(rv2[0], rv2[1]);
    return rv;
  }
  int rob(TreeNode *root) {
    vector<int> rv = dfs(root);
    return max(rv[0], rv[1]);
  }

};
//Java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = helper(root);
        return Math.max(res[0], res[1]);
    }
    
    int[] helper(TreeNode node){
        if(node==null){
            return new int[]{0,0};
        }
        int[] l = helper(node.left);
        int[] r = helper(node.right);
        int[] res = new int[2];
        res[0] = l[1] + r[1] + node.val;
        res[1] = Math.max(l[0],l[1]) + Math.max(r[0], r[1]);
        return res;
    }
}

LeetCode [336] Palindrome Pairs

336. Palindrome Pairs

Hard

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

class Solution {
    bool isPalindrome(string s){
        int n = s.size();
        int l = 0, r = n-1;
        while(l<r){
            if(s[l++]!=s[r--]) return false;
        }
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        set<vector<int>> ret;
        map<string, int> mp;//word, index;
        for(int i=0; i<words.size(); ++i){
            mp[words[i]] = i;
        }
        
        for(int i=0; i<words.size(); ++i){
            string w = words[i];
            for(int l=0; l<=w.size(); ++l){
                string ls = w.substr(0, l);
                string rs = w.substr(l);
                string rls(ls);
                reverse(rls.begin(), rls.end());
                string rrs(rs);
                reverse(rrs.begin(), rrs.end());
                
                if(mp.count(rls) && mp[rls]!=i && isPalindrome(rs)){
                    ret.insert(vector<int>{i, mp[rls]});
                }
                
                if(mp.count(rrs) && mp[rrs]!=i && isPalindrome(ls)){
                    ret.insert(vector<int>{mp[rrs], i});
                }
            }
        }
        return vector<vector<int>>(ret.begin(), ret.end());
    }
};

LeetCode [335] Self Crossing

335. Self Crossing

Hard

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

┌───┐
│   │
└───┼──>
    │

Input: [2,1,1,2]
Output: true

Example 2:

┌──────┐
│      │
│
│
└────────────>

Input: [1,2,3,4]
Output: false

Example 3:

┌───┐
│   │
└───┼>

Input: [1,1,1,1]

Output: true

class Solution {
public:
  bool isSelfCrossing(vector<int>& x) {
    for (int i = 3; i < x.size(); i++) {
      // last four
      if (x[i-3] >= x[i-1] && x[i] >= x[i-2]) return true;
      // last five
      if (i >= 4 && x[i-1] == x[i-3] && (x[i]+x[i-4] >= x[i-2])) return true;
      // last six
      if (i >= 5 && x[i-1] <= x[i-3] && (x[i-1]+x[i-5] >= x[i-3]) &&
          x[i-4] <= x[i-2] && (x[i]+x[i-4] >= x[i-2]))
        return true;
    }
    return false;
  }
};