LIKE CODING

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;
  }
};

Tuesday, March 22, 2016

MJ [56] Longest String Chain

Given a set of strings, find the longest string chain. Two strings are chained if
1. both strings belong to the given set
2. the second string is generated by remove one letter in the first string
For example:
Given vector<string> w = {a,ba,bca,bda,bdca}, the longest string chain is bdca->bda->ba->a.

Solution:
Represent the string chain by a Trie like structure. Record the depth while building Trie.

bdca
| |
bda bca
| |
ba ba
|
a

=============
===============

Ref
[1] http://www.1point3acres.com/bbs/thread-131978-1-1.html