Leetcode summary of 20200223-20200301

Posted by chunyang on March 1, 2020

Summary

Solved problems list

  • 187. Repeated DNA Sequences
  • 201. Bitwise AND of Numbers Range
  • 166. Fraction to Recurring Decimal
  • 146. LRU Cache
  • 131. Palindrome Partitioning
  • 91. Decode Ways
  • 498. Diagonal Traverse
  • 518. Coin Change 2
  • 133. Clone Graph
  • 1361. Validate Binary Tree Nodes
  • 264. Ugly Number II
  • 236. Lowest Common Ancestor of a Binary Tree

Highlight

Bitwise AND of Numbers Range

It is similar to the problem of counting the number of 1s in a number. For any number n, the way to remove the last bit of 1 in n is:

n = n & (n-1)

The largest number by performing AND is the number itself. So we keep repeating this process until we can no no more. The remained n is the final result.

Coin change

It is one kind of knapsack problem. You can refer to knapsack

Code Section

The sequence of code is the same with the problem list.

// 187. Repeated DNA Sequences
// https://leetcode.com/problems/repeated-dna-sequences/
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int size = s.size();
        unordered_map<string, int> m;
        set<string> ss;
        for (int i = 0; i < size; ++i) {
            auto sub = s.substr(i, 10);
            if (ss.find(sub) != ss.end()) continue;
            if (m.find(sub) == m.end()) {
                m[sub] = i;
            } else {
                ss.insert(sub);
            }
        }
        return vector<string>(ss.begin(), ss.end());
    }
};
// 201. Bitwise AND of Numbers Range
// https://leetcode.com/problems/bitwise-and-of-numbers-range/
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if (m == n) return m;
        if (m == 0 || n == 0) return 0;
        while (true) {
            if (n > m) n &= (n-1);
            else break;
        }
        return n;
    }
};
// 166. Fraction to Recurring Decimal
// https://leetcode.com/problems/fraction-to-recurring-decimal/
class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        map<int, int> pos;
        string result;
        long long n = numerator;
        long long d = denominator;
        bool flag = false;
        if (n < 0 && d < 0) {
            n = -n;
            d = -d;
        } else if (n < 0) {
            flag = true;
            n = -n;
        } else if (d < 0) {
            flag = true;
            d = -d;
        }
        if (n == 0) return "0";
        bool add_dot = false;
        int p = -1;
        while (n) {
            if (n % d == 0) {
                result += to_string(n / d);
                break;
            } else {
                if (n < d) {
                    if (!add_dot) {
                        if (result.empty()) result += "0";
                        result += ".";
                        add_dot = true;
                        p = result.size();
                    }
                    if (pos[n] != 0) {
                        // find repeat pattern
                        result += ")";
                        result.insert(pos[n], "(");
                        break;
                    }
                    pos[n] = p;
                    n *= 10;
                    auto div = n / d;
                    auto r = n % d;


                    n = r;
                    result += to_string(div);
                    ++p;
                } else {
                    result += to_string(n/d);
                    n = n % d;
                }
            }
        }
        return flag ? "-" + result : result;
    }
};
// 146. LRU Cache
// https://leetcode.com/problems/lru-cache/
struct MyNode {
    MyNode* prev;
    MyNode* next;
    int val;
    int key;
    MyNode(int key, int val):key(key), val(val), prev(nullptr), next(nullptr) {}
};
class LRUCache {
    unordered_map<int, MyNode*> _indexer;
    int size;
    int cap;
    MyNode* head;
    MyNode* tail;
public:
    LRUCache(int capacity): size(0), head(nullptr), tail(nullptr), cap(capacity) {
    }

    int get(int key) {
        if (_indexer.empty() || _indexer.find(key) == _indexer.end()) {
            return -1;
        }
        auto pos = _indexer[key];
        if (pos == head) return head->val;
        if (pos == tail) tail = pos->prev;
        auto next = head;
        auto prev = pos->prev;
        if (prev) {
            prev->next = pos->next;
            if (pos->next) pos->next->prev = prev;
        }
        pos->next = next;
        next->prev = pos;
        head = pos;
        auto t = head;
        /*
        cout << "----------getting: " << key << endl;
        while (t) {
            cout << "key: " << t->key << " val: " << t->val << endl;
            t = t->next;
        }
        cout << "head: " << head->key << " tail: " << tail->key << endl;
        if (tail->prev) {
            cout << "tail->prev: " << tail->prev->key << endl;
        } else {
            cout << "tail->prev is nullptr" << endl;
        }
        */
        return head->val;
    }

    void put(int key, int value) {
        if (_indexer.find(key) != _indexer.end()) {
            get(key);
            head->val = value;
        } else {
            auto n = new MyNode(key, value);
            ++size;
            if (size > cap) {
                auto pos = tail;
                tail = tail->prev;
                if (tail == nullptr) head = tail = nullptr;
                else tail->next = nullptr;
                --size;
                _indexer.erase(pos->key);
                delete pos;
            }
            n->next = head;
            if (head) {
                head->prev = n;
            } else {
                tail = n;
            }
            head = n;
            _indexer[key] = n;
        }
        /*
        cout << "----------Putting: " << key << " val: " << value << endl;
        auto t = head;
        while (t) {
            cout << "key: " << t->key << " val: " << t->val << endl;
            t = t->next;
        }
        cout << "head: " << head->key << " tail: " << tail->key << endl;
        */
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// 131. Palindrome Partitioning
// https://leetcode.com/problems/palindrome-partitioning/
class Solution {
public:
    vector<vector<string>> partition(string s) {
        function<bool(int, int)> is_palindrome = [&](int start, int end) {
            while (start < end && s[start] == s[end]) {
                ++start;
                --end;
            }
            return start >= end;
        };
        vector<vector<string>> result;
        vector<string> path;
        int size = s.size();
        function<void(int)> dfs = [&](int start) {
            if (start == size) {
                result.push_back(path);
            }
            for (int i = start; i < size; ++i) {
                if (is_palindrome(start, i)) {
                    path.push_back(s.substr(start, i-start+1));
                    dfs(i+1);
                    path.pop_back();
                }
            }
        };
        dfs(0);
        return result;
    }
};
// 91. Decode Ways
// https://leetcode.com/problems/decode-ways/
class Solution {
public:
    int numDecodings(string s) {
        int size = s.size();
        vector<int> dp(size+1);
        dp[0] = 1;
        dp[1] = 1;
        if (s[0] == '0') return 0;
        for (int i = 2; i <= size; ++i) {
            bool good = false;
            if (s[i-1] != '0') {
                dp[i] = dp[i-1];
                good = true;
            }
            if (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6')) {
                dp[i] += dp[i-2];
                good = true;
            }
            if (!good) return 0;
        }
        return dp[size];
    }
};
// 498. Diagonal Traverse
// https://leetcode.com/problems/diagonal-traverse/
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int m = matrix.size();
        if (m == 0) return result;

        int n = matrix[0].size();
        result.reserve(m*n);
        bool reversed = true;
        for (int i = 0; i < n; ++i) {
            vector<int> mid;
            for (int r = 0, c = i; r < m && c >= 0; ++r, --c) {
                mid.push_back(matrix[r][c]);
            }
            if (reversed) {
                copy(mid.rbegin(), mid.rend(), back_inserter(result));
            } else {
                copy(mid.begin(), mid.end(), back_inserter(result));
            }
            reversed = !reversed;

        }
        for (int i = 1; i < m; ++i) {
            vector<int> mid;
            for (int r = i, c = n-1; r < m && c >= 0; ++r, --c) {
                mid.push_back(matrix[r][c]);
            }
            if (reversed) {
                copy(mid.rbegin(), mid.rend(), back_inserter(result));
            } else {
                copy(mid.begin(), mid.end(), back_inserter(result));
            }
            reversed = !reversed;

        }
        return result;
    }
};
// 518. Coin Change 2
// https://leetcode.com/problems/coin-change-2/
class Solution {
public:
  int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (const int coin : coins)
      for (int i = 0; i <= amount - coin; ++i)
        dp[i + coin] += dp[i];
    return dp[amount];
  }
};
/**
 * 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<TreeNode*> generateTrees(int n) {
        unordered_map<string, vector<TreeNode*>> cache;
        function<vector<TreeNode*>(int, int )> gen = [&](int s, int e) {
            vector<TreeNode*> result;
            if (s > e) result.push_back(nullptr);
            else if (s == e) result.push_back(new TreeNode(s));
            else {
                for (int i = s; i <= e; ++i) {
                    auto l = gen(s, i-1);
                    auto r = gen(i+1, e);
                    for (auto ll : l) {
                        for (auto rr : r) {
                            TreeNode* node = new TreeNode(i);
                            node->left = ll;
                            node->right = rr;
                            result.push_back(node);
                        }
                    }
                }
            }
            return result;
        };
        if (n == 0) return vector<TreeNode*>();
        return gen(1, n);
    }
};
// 133. Clone Graph
// https://leetcode.com/problems/clone-graph/
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<int, Node*> cloned;
        function<Node*(Node*)> clone_one = [&](Node* node) {
            if (!node) return node;
            if (cloned.find(node->val) != cloned.end()) return cloned[node->val];
            Node* cloned_node = new Node(node->val);
            cloned[node->val] = cloned_node;
            for (Node* n : node->neighbors) {
                cloned_node->neighbors.push_back(clone_one(n));
            }
            return cloned_node;
        };
        return clone_one(node);
    }
};
// 1361. Validate Binary Tree Nodes
// https://leetcode.com/problems/validate-binary-tree-nodes/
class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        // more than one root
        // more than two child
        // more than two parent
        unordered_set<int> roots;
        unordered_set<int> children;
        function<bool(int)> be_child = [&](int n) {
            if (n == -1) return true;
            auto b = children.find(n) == children.end();
            if (b) {
                children.insert(n);
            }
            return b;
        };
        function<void(int)> del = [&](int n) {
            if (n == -1) return;
            if (roots.find(n) != roots.end()) {
                roots.erase(n);
            }
        };
        for (int i = 0; i < n; ++i) {
            auto l = leftChild[i];
            auto r = rightChild[i];
            auto b1 = be_child(l); auto b2 = be_child(r);
            del(l); del(r);
            if (!b1 || !b2) return false;
            /*
            cout << "for i = " << i << " root: ";
            copy(begin(roots), end(roots), ostream_iterator<int>(cout, ","));
            cout << endl;
            cout << "children: ";
            copy(begin(children), end(children), ostream_iterator<int>(cout, ","));
            cout << endl;
            */

            if (children.find(i) == children.end()) {
                roots.insert(i);
            } else {
                if (roots.find(i) != roots.end()) {
                    roots.erase(i);
                }
            }
        }
        // cout << "roots.size(): " << roots.size() << endl;
        return roots.size() == 1;
    }
};
// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> l(n); // initialize the squence.
        int p_2, p_3, p_5; // initialize the pointer
        l[0] = 1;
        p_2 = 0;
        p_3 = 0;
        p_5 = 0;
        for (int i = 1; i < n; ++i) {
            l[i] = min({l[p_2] * 2, l[p_3] * 3, l[p_5] * 5});
            if (l[p_2] * 2 == l[i]) ++p_2;
            if (l[p_3] * 3 == l[i]) ++p_3;
            if (l[p_5] * 5 == l[i]) ++p_5;
        }
        return l[n - 1];
    }
public:
    bool isUglyNumber(int num) {
        if (num <= 0) return false;
        while (num % 6 == 0) num /= 6;
        while (num % 10 == 0) num /= 10;
        while (num % 15 == 0) num /= 15;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;

    }
    int nthUglyNumberSlow(int n) {
        int cnt = 0;
        int i = 1;
        while (cnt < n) {
            if (isUglyNumber(i)) ++cnt;
            ++i;
        }
        return i-1;
    }
};
// 236. Lowest Common Ancestor of a Binary Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (root->val == p->val || root->val == q->val) return root;
        auto n = lowestCommonAncestor(root->left, p, q);
        auto m = lowestCommonAncestor(root->right, p, q);
        if (m && n) return root;
        else if (m) return m;
        else if (n) return n;
        else return nullptr;
    }
};

Creative Commons License
This work is licensed under a CC A-S 4.0 International License.