leetcode解题: Count and Say (38)

发表于 2017-01-03 | 分类于刷题总结

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

解法1： Recursive

用递归求得n-1的字符串，然后一位位遍历，每当得到和前一位不一样的字符时，保存前一位的字符的计数和字符。要注意的是最后一位的结果要在扫描结束后保存。
C++
C++ 里从1个char转换到string可以用string(1, character)

class Solution {
public:
    string countAndSay(int n) {
        if (n <= 0) {
            return "";
        }
        if (n == 1) {
            return "1";
        }
        
        string prev = countAndSay(n - 1);
        string res = "";
        int count = 1;
        char cur = prev[0];
        for (int i = 1; i < prev.size(); ++i) {
            if (prev[i] == prev[i - 1]) {
                count++;
            } else {
                res += to_string(count) + string(1, cur);
                cur = prev[i];
                count = 1;
            }
        }
        res += to_string(count) + string(1, prev[prev.size() - 1]);
        return res;
    }
};

Java

leetcode解题: Bulls and Cows (299)

发表于 2017-01-03 | 分类于刷题总结

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.

For example:

Secret number: “1807”
Friend’s guess: “7810”
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
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. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

Secret number: “1123”
Friend’s guess: “0111”
In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.
You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

解法1： O（N) Time , 一次遍历

参考了[这个][1]的解法，只需要一次遍历即可。思路是按位一个个遍历，如果碰到一样的字符则bull加1。如果碰到不一样的字符，secret的字符对应的+1， guess对应的减1。这样就同时保存了secret和guess出现的字符的情况。如果后续碰到如果secret字符对应的次数为负，则证明在guess中出现过；如果guess字符对应的次数为正，则说明在secret中出现过。这样的话就能记录一次cow。
C++

class Solution {
public:
    string getHint(string secret, string guess) {
        vector<int> map(10, 0);
        int bulls, cows;
        bulls = cows = 0;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) {
                ++bulls;
            } else {
                if (map[secret[i] - '0'] < 0) {
                    ++cows;
                }
                if (map[guess[i] - '0'] > 0) {
                    ++cows;
                }
                map[secret[i] -'0']++;
                map[guess[i] - '0']--;
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

Java

class Solution {
    public String getHint(String secret, String guess) {
        int[] map = new int[10];
        int bull = 0, cow = 0;
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                bull++;
            } else {
                if (map[secret.charAt(i) - '0'] < 0) {
                    cow++;
                }
                if (map[guess.charAt(i) - '0'] > 0) {
                    cow++;
                }
                map[secret.charAt(i) - '0']++;
                map[guess.charAt(i) - '0']--;
            }
        }
        return Integer.toString(bull) + "A" + Integer.toString(cow) + "B";
    }
}

leetcode解题: Implement Trie (Prefix Tree) (208)

发表于 2017-01-03 | 分类于刷题总结

Implement a trie with insert, search, and startsWith methods.

解法1：

本题主要是考察Trie树的基本概念，可以参考Wiki的解释。实现的时候，每一个node的children可以用一个map来实现，做insert或者是search的时候可以用一个current的指针从root开始不停的往下搜索。
比较直观，并没有难度。
C++

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() {
        isWord = false;
    }
    
    unordered_map<char, TrieNode*> children;
    bool isWord;
};
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* cur = root;
        for (char c: word) {
            if (!cur->children.count(c)) {
                cur->children[c] = new TrieNode();
            }
            cur = cur->children[c];
        }
        cur->isWord = true;
    }
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* cur = root;
        for (char c: word) {
            if (!cur->children.count(c)) {
                return false;
            }
            cur = cur->children[c];
        }
        return cur->isWord;
    }
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* cur = root;
        for (char c: prefix) {
            if (!cur->children.count(c)) {
                return false;
            }
            cur = cur->children[c];
        }
        return true;
    }
private:
    TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

Java

class TrieNode {
    Map<Character, TrieNode> map;
    boolean isWord;
    public TrieNode() {
        this.map = new HashMap<Character, TrieNode>();
    }
};
public class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            if (!current.map.containsKey(c)) {
                current.map.put(c, new TrieNode());
            }
            current = current.map.get(c);
        }
        current.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            if (!current.map.containsKey(c)) {
                return false;
            }
            current = current.map.get(c);
        }
        return current.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c: prefix.toCharArray()) {
            if (!current.map.containsKey(c)) {
                return false;
            }
            current = current.map.get(c);
        }
        return true;
    }
}
/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

leetcode解题: House Robber III (337)

发表于 2017-01-01 | 分类于刷题总结

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:

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:

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

解法1：

参考了这个帖子的解法3。对于每一个节点，存在两种可能，取或者不取。那么可以用一个帮助函数，每一次计算的时候保存这两种情况的值。
用一个vector保存，v[0]表示从这个点出发，不包含这个点最大的可取值， v1表示从这个点出发并且包含这个点可取的最大值。
那么对于一个root，分别计算left和right的vector，再按取或者不取的情况计算出root的vector。
如果取root的值，那一定不能取left和right的值，所以最大取值是left1 + right1 + val
如果不取root的值，那可以取left和right的值，这也等价于两颗树，对这两颗树取这个问题的最大值，就是left两种情况的最大值+right两种情况的最大值。
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:
    int rob(TreeNode* root) {
        vector<int> temp = helper(root);
        return max(temp[0], temp[1]);
    }
    vector<int> helper(TreeNode* root) {
        if (!root) {
            return vector<int>(2, 0);
        }
        vector<int> left = helper(root->left);
        vector<int> right = helper(root->right);
        vector<int> res(2,0);
        res[0] = max(left[0], left[1]) + max(right[0], right[1]);
        res[1] = left[0] + right[0] + root->val;
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class MarkedTreeNode {
        int take;
        int notake;
        public MarkedTreeNode(int take, int notake) {
            this.take = take;
            this.notake = notake;
        }
    };
    public int rob(TreeNode root) {
        if (root == null) return 0;
        MarkedTreeNode res = helper(root);
        return Math.max(res.take, res.notake);
    }
    private MarkedTreeNode helper(TreeNode root) {
        if (root == null) return new MarkedTreeNode(0,0);
        MarkedTreeNode left = helper(root.left);
        MarkedTreeNode right = helper(root.right);
        int take = root.val + left.notake + right.notake;
        int notake = Math.max(left.notake, left.take) + Math.max(right.notake, right.take);
        return new MarkedTreeNode(take, notake);
    }
}

leetcode解题: Implement Stack using Queues (225)

发表于 2016-12-31 | 分类于刷题总结

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Notes:
You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

解法1：

基本思路是当执行top或者是pop的时候，我们需要取出最后一个元素。那么前面的元素放哪里？可以直接push回当前的queue。这样，当除最后一个元素被重新push后，第一个就是我们要求的元素。
要注意的是，top是不改变数据的，所以执行完top之前，要把第一个元素push回queue
C++

class Stack {
public:
    // Push element x onto stack.
    void push(int x) {
        q.push(x);
    }
    // Removes the element on top of the stack.
    void pop() {
        int s = q.size();
        for (int i = 0; i < s - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
        q.pop();
    }
    // Get the top element.
    int top() {
        int s = q.size();
        for (int i = 0; i < s - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
        int res = q.front();
        q.push(res);
        q.pop();
        return res;
    }
    // Return whether the stack is empty.
    bool empty() {
        return q.empty();
    }
private:
    queue<int> q;
};

Java

leetcode解题: Intersection of Two Linked Lists (160)

发表于 2016-12-31 | 分类于刷题总结

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

解法1： O（M + N） Time + O（1） Space

很巧妙的一个方法是如果我们将其中一个list的尾巴和另一个list的头部连接，那么就变成了求这个长list中是否有circle，如果有那么他们的交点是什么的题目。
要注意求交点的算法是：

slow，fast pointer
slow = head， fast = head.next
找到slow和fast相等的点
把slow挪到head， fast往下移一格

一步一步走直到slow和fast相等
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) {
            return NULL;
        }
        ListNode *a = headA;
        while (a ->next) {
            a = a->next;
        }
        a->next =headB;
        ListNode* temp = circle(headA);
        a->next = NULL;
        return temp;
    }
    ListNode* circle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (!fast || !fast->next) {
                return NULL;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        slow = head;
        fast = fast->next;
        while (slow != fast) {
            slow =slow->next;
            fast =fast->next;
        }
        return slow;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tailA = headA;
        while (tailA.next != null) {
            tailA = tailA.next;
        }
        tailA.next = headB;
        // A -> B
        ListNode slow = headA, fast = headA.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                tailA.next = null;
                return null;    // no cycle found
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = headA;
        fast = fast.next;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        tailA.next = null;  // restore the original linked List
        return slow;
    }
}

leetcode解题: Construct Binary Tree from Inorder and Postorder Traversal (106)

发表于 2016-12-31 | 分类于刷题总结

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

解法1：

首先回想一下inorder和postorder的遍历顺序是什么样的。 inorder是left，root，right。 postorder是left，right，root。那么发现postorder对应的最后一个数就是tree的root，当我们找到乐root之后就可以在inorder里面找到root的位置，假设为i。
按照inorder的顺序，在i左面的都是root的左节点，而在i右面的都是root的右节点。
对于左右子树，我们只要在运行一次同样的算法，只是更新一下取值的范围（左右边界）就可以了。
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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty()) {
            return NULL;
        }
        
        return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    }
    
    TreeNode* helper(vector<int>& inorder, int istart, int iend, vector<int>& postorder, int pstart, int pend) {
        if (istart > iend) {
            return NULL;
        }
        if (istart == iend) {
            TreeNode* node = new TreeNode(inorder[istart]);
            return node;
        }
        int val = postorder[pend];
        TreeNode* root = new TreeNode(val);
        auto iter = find(inorder.begin(), inorder.end(), val);
        int index = iter - inorder.begin();
        int leftNum = index - istart;
        int rightNum = iend - index;
        
        // Find left tree
        TreeNode* left = helper(inorder, istart, index - 1, postorder, pstart, pstart + leftNum - 1);
        // Find right tree
        TreeNode* right = helper(inorder, index + 1, iend, postorder, pstart + leftNum, pstart + leftNum + rightNum - 1);
        root->left = left;
        root->right = right;
        return root;
    }
};

Java

leetcode解题: Remove Linked List Elements (203)

发表于 2016-12-30 | 分类于刷题总结

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6
Return: 1 –> 2 –> 3 –> 4 –> 5

解法1： O(N) One Pass

要注意的是因为可能头指针会被删除或者整条list会被删，要用dummy node。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        while (head->next) {
            if (head->next->val == val) {
                ListNode* temp = head->next;
                head->next = head->next->next;
                delete temp;
            } else {
                head = head->next;
            }
        }
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

Java

leetcode solution: Remove Nth Node From End of List (19)

发表于 2016-12-30 | 分类于刷题总结

Given a linked list, remove the nth node from the end of list and return its head.

For example,

1
2
3

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

解法1： Two pointers, One Pass, O(N) Time

头node不确定，上dummy node大法。然后用双指针向前移动，找到Nth node的前一个node，删除后返回dummy->next
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* left = dummy;
        head = dummy;
        for (int i = 0; i < n; ++i) {
            head = head->next;
        }
        
        while (head->next) {
            left = left->next;
            head = head->next;
        }
        ListNode* temp = left->next;
        left->next = left->next->next;
        ListNode* res = dummy->next;
        delete temp;
        delete dummy;
        return res;
    }
};

Java

Leetcode解题: Path Sum II (113)

发表于 2016-12-30 | 分类于刷题总结

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return
[
[5,4,11,2],
[5,8,4,5]
]

解法1： DFS

关于求所有的路径之类的题目，首先想到的都是DFS。这道题也不例外。用DFS遍历tree，每一次往下一个node，就把当前的sum减去node的val，如果碰到叶子并且叶子的val和所剩的val相等，则加入paths中。
C++

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int> > paths;
        vector<int> path;
        helper(root, sum, path, paths);
        return paths;  
    }
private:
    void helper(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
        if (!node) {
            return;
        }
        path.push_back(node->val);
        if (!node->left && !node->right && sum == node->val) {
            paths.push_back(path);
        }
        helper(node->left, sum - node->val, path, paths);
        helper(node->right, sum - node->val, path, paths);
        
        path.pop_back();
    }
};

Java