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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//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++] 纯文本查看 复制代码

?

01

02

03

04

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的变体而且变更简单了

at No comments:

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.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//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;
    }
};
at No comments:

Wednesday, October 28, 2015

MJ [47] CSV Parser


at No comments:

Monday, October 26, 2015

LeetCode [297] Serialize and Deserialize Binary Tree


297. Serialize and Deserialize Binary Tree
Hard

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

 

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

 

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
    void serialize(TreeNode* node, stringstream &ss){
        if(!node)
        {
            ss<<"# ";
        }
        else
        {
            ss<<node->val<<" ";
            serialize(node->left, ss);
            serialize(node->right, ss);
        }
    }
    
    TreeNode* deserialize(stringstream &ss)
    {
        string s;
        ss>>s;
        if(s=="#"){
            return NULL;
        }else{
            TreeNode* node = new TreeNode(stoi(s));
            node->left = deserialize(ss);
            node->right = deserialize(ss);
            return node;
        }
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        serialize(root, ss);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss<<data;
        return deserialize(ss);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    String str;
    String[] strs;
    int index = 0;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        str = "";
        sh(root);
        return str;
    }
    
    void sh(TreeNode node){
        if(str.length()>0) str += ",";
        if(node==null){
            str += "#";
        }else{
            str += node.val;
            sh(node.left);
            sh(node.right);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        strs = data.split(",");
        index = 0;
        return dh();
    }
    
    TreeNode dh(){
        TreeNode node;
        String s = strs[index++];
        if(s.equals("#")){
            node = null;
        }else{
            node = new TreeNode(Integer.parseInt(s));
            node.left = dh();
            node.right = dh();
        }
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
at No comments: