LIKE CODING

Sunday, November 8, 2015

LeetCode [302] Smallest Rectangle Enclosing Black Pixels

Ref
[1] https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/
[2] https://leetcode.com/discuss/68246/c-java-python-binary-search-solution-with-explanation

Saturday, November 7, 2015

MJ [48] Compute combinations

Question:
Given a 2-D vector of strings [[Hello, Hi], [world, girl, boy]]
print:
Hello world
Hello girl
Hello boy
Hi world
Hi girl
Hi boy
=============== =================
Ref
[1] http://www.mitbbs.com/article_t/JobHunting/32972467.html

Thursday, November 5, 2015

LeetCode [301] Remove Invalid Parentheses

301. Remove Invalid Parentheses

Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

class Solution {
    bool isvalid(string s){
        int cnt = 0;
        for(auto c:s){
            cnt += c=='(';
            cnt -= c==')';
            if(cnt<0) return false;
        }
        return cnt==0;
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for(auto c:s){
            if(c=='(') l++;
            else{
                if(l==0) r += (c==')');
                else l -= (c==')');                
            }
        }      
        vector<string> ret;
        dfs(s, ret, 0, l, r);
        return ret;
    }
    
    void dfs(string s, vector<string>&ret, int pos, int l, int r){
        if(l==0 && r==0 && isvalid(s)){
            ret.push_back(s);
            return;
        }
        
        for(int i=pos; i<s.size(); ++i){
            if(i>pos && s[i]==s[i-1]) continue;
            if(!(s[i]=='(' && l>0 || s[i]==')' && r>0)) continue;
            string s1 = s;
            
            s1.erase(i, 1);
            if(s[i]=='(' && l>0) dfs(s1, ret, i, l-1, r);
            else if(s[i]==')' && r>0) dfs(s1, ret, i, l, r-1);
        }
    }
};

http://zxi.mytechroad.com/blog/string/leetcode-301-remove-invalid-parentheses/

Monday, November 2, 2015

LeetCode [300] Longest Increasing Subsequence

300. Longest Increasing Subsequence

Medium

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        vector<int> dp(n, 1); 
        int ret = 1;
        for(int i=0; i<n; ++i){
            for(int j=0; j<i; ++j){
                if(nums[i]>nums[j]) dp[i] = max(dp[i], dp[j]+1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

//https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
class Solution1 {
public:
    int lengthOfLIS(vector<int>& nums) {
        //al[L-1] is the last element of the min L-length sequence
        //for each number n in nums, find the first element al[L-1] in al greater (or equal) than n
        //replace al[L-1] by n (so we can keep the min property of the L-length subsequence)
        vector<int> al;
        for(auto n:nums){
            if(al.size()==0 || n>al.back()) al.push_back(n);
            else{
                int l = 0, r = al.size()-1;
                while(l<=r){
                    int m = l+(r-l)/2;
                    if(n<=al[m] && (m==l || al[m-1]<n)){
                        al[m] = n;
                        break;
                    }else if(n<al[m]){
                        r = m-1;
                    }else{
                        l = m+1;
                    }
                }
            }
        }
        return al.size();
    }
};

class Solution2 {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> al;
        for(auto n:nums){
            auto it = lower_bound(al.begin(), al.end(), n);
            if(it==al.end()) al.push_back(n);
            else *it = n;
        }
        return al.size();
    }
};

Saturday, October 31, 2015

LeetCode [299] Bulls and Cows

299. Bulls and Cows

Easy

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows.

Please note that both secret number and friend's guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.

Note: You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

//C++: two pass, 8 ms
class Solution {
public:
    string getHint(string secret, string guess) {
        int n = secret.size();
        int b = 0, c = 0;
        int nums[10] = {0};
        for(int i=0; i<n; ++i){
            if(secret[i]==guess[i]){
                b++;
            }else{
                nums[secret[i]-'0']++;
            }
        }
        for(int i=0; i<n; ++i){
            if(secret[i]!=guess[i]){
                if(nums[guess[i]-'0']>0){                        
                    c++;
                    nums[guess[i]-'0']--;
                }
            }
        }
        return to_string(b)+"A"+to_string(c)+"B";
    }
};

//C++: one pass, 4 ms
class Solution {
public:
    string getHint(string secret, string guess) {
        int n = secret.size();
        int b = 0, c = 0;
        int nums[10] = {0};
        for(int i=0; i<n; ++i){
            if(secret[i]==guess[i]){
                b++;
            }else{
                if(nums[secret[i]-'0']<0) c++;
                if(nums[guess[i]-'0']>0) c++;
                nums[secret[i]-'0']++;
                nums[guess[i]-'0']--;
            }
        }
        return to_string(b)+"A"+to_string(c)+"B";
    }
};

//Java
class Solution {
    public String getHint(String secret, String guess) {
        int[] numbers = new int[256];
        int n = secret.length();
        int b=0, c=0;
        for(int i=0; i<n; ++i){
            if(secret.charAt(i)!=guess.charAt(i)){
                numbers[secret.charAt(i)]++;
            }
        }
        for(int i=0; i<n; ++i){
            if(secret.charAt(i)==guess.charAt(i)) b++;
            else{
                if(numbers[guess.charAt(i)]>0){
                    c++;
                    numbers[guess.charAt(i)]--;
                }
            }
        }
        return b+"A"+c+"B";
    }
}

YMSF

第五轮，白人小哥，刷题网没刷到过（题刷太少了我。。），给两个长度为4的都是数字0-9的字符串A和B，如果B对应A的位置数字相同就是一个correct，如果对应数字不同，但是存在与A别的位置，就算是一个miss，设计个函数求最后correct和miss的数量。比方A=1166，B=1116，结果是3 correct，0 miss （因为A只有俩1，B第三个1不算miss），再比方A=2780，B=0782，就是2 correct，2 miss。 Followup是如何用这个函数把B最后修改成为A，assume一定能把B改成A，时间不够了，写的伪代码，大概思路是每个位置都放0-9测试，如果放的数字使correct+miss总和比上次的情况好，说明猜对了那个数字，就往下一个位置走，结束条件是correct+miss的总和等于4，最后再permute这4个数字的位置然后使用函数，直到correct=4，miss=0，大概率也不是最优解，说了下时间空间复杂度，小哥只是点了点头，问我还有啥问题没有就拜拜了

感觉第五题的 follow up 有点像843

第五轮是刷题网原题，楼上有人回复了，follow up可能是面试官临时想出来的，也没让我写代码，就口述

第五题的typo，

但是存在与A别的位置 =》但是存在于A别的位置

题目有点绕，第一步是不是可以这么解？

strA, strB，用countA[] 和countB[] 分别count出现数字的个数。

[C++] 纯文本查看复制代码

if strA[i][i] == strB[i]

correct ++;

else if countA[strA[i]] != countB[strB[i]]

miss ++

差不多这个思路，可能是我解释得不清楚，如果B(i) 不存在A里，那这个既不算correct也不算miss，就continue就行, 比如A: 1234, B: 7890, 结果就是(0,0)

YMSF

1. 给两个长度一样string S和T，如果在同一个位置上，两个string的字符不同，就是一个diff。比如“abc”和"abd"，最后一个字符分别是'c'和'd'，这两个string的diff就是1。现在我们要在S里交换两个字符的位置，使把S和T之间的diff尽量减到最小，返回两个被交换的字符的位置。面试官应该要求的是O（n）

请问群主如何在O(n)时间使用map找到S和T中是否存在一对相同的 character pair呢，尤其在有重复character的情况下

前面一道题简单，维护一个 Map<Character,List<Integer>> 对象，保存所有没有找到match的t 的character以及位置，任何时候看到一个不匹配的character，去找这个map里面有没有现成的t 的character，如果有，查一下list，看看list里面这些位置s上有没有正好是当前t的char，如果有调换这两个，如果没有选择第一个调换，然后更新map

第一题的解法看的不太明白。如果这样做最坏情况下的时间复杂度不是O(n^2) 吗

是的，正常情况下是O(n)的复杂度类似2Sum的算法

但是在找这个dif-2调换的时候，要做一个循环，但是再怎样应该每次找的时候到不了O(n)的复杂度，当然理论上还是得说这是个O(n)的循环

如果有调换这两个，如果没有选择第一个调换，然后更新map

请问这句是什么意思呀，会存在调换一次只减少一个diff的情况吗

这个第一种情况可以严格O(n)

建立一个Map<String, Integer>，然后当我遇见两个字符是a和b时，存入string "ab" 作为key，index作为value，生成这个String key的时候，总是把小的字符放在前面。

这样当我又遇见ab的时候，我只需要查一下Map里的index，看看是不是ab还是ba就可以了，如果是a都在同一个字符里，就无视，如果是a分别在两个字符里，就找到答案

啊是这个意思我理解错题了以为是t和s里的字符相互调换。。谢谢！

第一题就是bulls and cows的变体而且变更简单了

LeetCode [298] Binary Tree Longest Consecutive Sequence

298. Binary Tree Longest Consecutive Sequence

Medium

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

Example 1:

Input:

   1
    \
     3
    / \
   2   4
        \
         5

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input:

   2
    \
     3
    / 
   2    
  / 
 1

Output: 2 

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

//C++: 40ms dfs recursive
/**
 * 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:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        int ret = 1;
        lc(root, ret, root->val, 1);
        return ret;
    }
    void lc(TreeNode* root, int &ret, int parent, int len){
        if(!root) return;
        if(root->val == parent+1){
            ret = max(ret, len+1);
        }else{
            len = 0;            
        }
        lc(root->left, ret, root->val, len+1);
        lc(root->right, ret, root->val, len+1);        
    }
};

//C++: 48ms dfs iterative
/**
 * 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:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        stack<pair<TreeNode*, int>> stk;
        stk.push(pair<TreeNode*, int>(root, 1));
        int ret = 1;
        while(!stk.empty()){
            TreeNode* t = stk.top().first;
            int cur = stk.top().second;
            stk.pop();
            if(t->left){
                if(t->left->val == t->val+1){
                    stk.push(pair<TreeNode*, int>(t->left, cur+1));
                    ret = max(ret, cur+1);
                }else{
                    stk.push(pair<TreeNode*, int>(t->left, 1));
                }
            }
            if(t->right){
                if(t->right->val == t->val+1){
                    stk.push(pair<TreeNode*, int>(t->right, cur+1));
                    ret = max(ret, cur+1);
                }else{
                    stk.push(pair<TreeNode*, int>(t->right, 1));
                }
            }            
        }
        return ret;
    }
};

//C++: 44ms bfs iterative
/**
 * 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:
    int longestConsecutive(TreeNode* root) {
        if(!root) return 0;
        queue<pair<TreeNode *, int>> que;
        que.push(pair<TreeNode *, int>(root, 1));
        int ret = 1;
        while(!que.empty()){
            TreeNode * t = que.front().first;
            int cur = que.front().second;
            que.pop();
            if(t->left){
                if(t->left->val == t->val+1){
                    ret = max(ret, cur+1);
                    que.push(pair<TreeNode *, int>(t->left, cur+1));
                }else{
                    que.push(pair<TreeNode *, int>(t->left, 1));
                }
            }
            if(t->right){
                if(t->right->val == t->val+1){
                    ret = max(ret, cur+1);
                    que.push(pair<TreeNode *, int>(t->right, cur+1));
                }else{
                    que.push(pair<TreeNode *, int>(t->right, 1));
                }
            }
        }
        return ret;
    }
};