Techinpad

[LintCode] Add and Search Word

2015-12-23T01:53:00.001-08:00

Design a data structure that supports the following two operations:addWord(word) and search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or ..

A . means it can represent any one letter.

Example

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

Note

You may assume that all words are consist of lowercase letters a-z.

class Trie {
    unordered_map<char,Trie*> _map;
    bool _end;
public:
    Trie() {
        _end = false;
    }
    void add(string &s,int n) {
        if(!_map.count(s[n])) {
            _map[s[n]] = new Trie();
        }
        if(n == s.length() - 1) {
            _map[s[n]]->_end = true;
        } else {
            _map[s[n]]->add(s, n+1);
        }
    }
    
    bool search(string &s, int n){
        if(s.length() -1 == n) {
            if(s[n] == '.') {
                for(auto e : _map) {
                    if(e.second->_end) return true;
                }
                return false;
            }
            return _map.count(s[n]) ? _map[s[n]]->_end : false;
        }
        if(s[n] == '.') {
            for(auto e : _map) {
                if(e.second->search(s, n+1)) {
                    return true;
                }
            }
        } else {
            if(!_map.count(s[n])) return false;
            return _map[s[n]]->search(s, n+1);
        }
        return false;
    }
};

class WordDictionary {
    Trie _trie;
public:
    void addWord(string word) {
        _trie.add(word, 0);
    }
    bool search(string word) {
        return _trie.search(word, 0);
    }
};

[LintCode] Restore IP Addresses Show result

2015-12-22T03:11:00.000-08:00

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example

Given "25525511135", return

[
  "255.255.11.135",
  "255.255.111.35"
]

Order does not matter.

class Solution {
public:
    vector<string> helper(string s, int n) {
        int l = s.length();
        vector<string> res;
        
        if(3*n < l || n>l) {
            return res;
        }
        
        if(n == 1){
            if(l>1 && s[0] == '0') return res;
            if(stoi(s)<=255) {
                res.push_back(s);
            }
            return res;
        }
        
        for(int i=1;i<=3 && i<l;i++){
            string t = s.substr(0,i);
            if((i>1 && s[0] == '0') || 
                (i == 3 && stoi(t)>255)) break;
            vector<string> pp = helper(s.substr(i), n-1);
            for(auto e:pp) {
                res.push_back(t+"."+e);
            }
        }
        return res;
    }
    
    vector<string> restoreIpAddresses(string& s) {
        // Write your code here
        return helper(s, 4);
    }
};

LFU Cache

2015-10-30T00:46:00.003-07:00

Similar to LRU http://techinpad.blogspot.com/2015/06/leetcode-lru-cache.html, implement a LFU, which is the least frequently used cache.

Analysis: multimap should be the best data structure to use.

class LFUCache{
    unordered_map<int, multimap<int, pair<int,int>>::iterator> mMap;
    multimap<int, pair<int,int>> mList;
    int mCap;
public:
    LFUCache(int capacity) {
        mCap = capacity;
    }
    
    void moveToHead(int key) {
        multimap<int, pair<int,int>>::iterator it = mMap[key];
        pair<int, pair<int,int>> n(it->first+1, pair<int,int>(it->second.first, it->second.second));
        mList.erase(it);
        mMap[key] = mList.insert(n);
    }
    
    int get(int key) {
        if(!mMap.count(key)) return -1;
        moveToHead(key);
        return mMap[key]->second.second;
    }
    
    void set(int key, int value) {
        
        if(mMap.count(key)) {
            mMap[key]->second.second = value;
            moveToHead(key);
            return;
        } 
        
        if(mList.size() == mCap) {
            auto it = mList.begin();
            mMap.erase(it->second.first);
            mList.erase(it);
        }
        pair<int,pair<int,int>> n(1, pair<int,int>(key, value));
        mMap[key] = mList.insert(n);
        
    }
};

[LeetCode] Serialize and Deserialize Binary Tree

2015-10-27T16:44:00.003-07:00

Question can be found
https://leetcode.com/problems/serialize-and-deserialize-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 Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "";
        vector<string> v;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *t = q.front();
            q.pop();
            if(t == NULL) {
                v.push_back("null");
                continue;
            }
            
            v.push_back(to_string(t->val));
            
            q.push(t->left);
            q.push(t->right);
        }
        
        int l = v.size() - 1;
        while(v[l] == "null") l--;
        
        string res = v[0];
        for(int i=1;i<=l;i++){
            res += "," + v[i];
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(0 == data.length()) return NULL;
        vector<string> v;
        int start = 0;
        for(int i=1;i<data.length();i++) {
            if(data[i] != ',') continue;
            v.push_back(data.substr(start, i-start));
            start = i+1;
        }
        v.push_back(data.substr(start));
        int index = 0;
        
        TreeNode *node = new TreeNode(stoi(v[index]));
        
        queue<TreeNode*> nodesOnLevel;
        int count = v.size();
        nodesOnLevel.push(node);
        
        while(!nodesOnLevel.empty()) {
            int size = nodesOnLevel.size();
            for(int i=0;i<size;i++){
                
                int left = index + 1;
                if(left >= count) return node;
                if(v[left] != "null") {
                    TreeNode *cur = new TreeNode(stoi(v[left]));
                    nodesOnLevel.front()->left = cur;
                    nodesOnLevel.push(cur);
                }
                
                int right = index + 2;
                if(right >= count) return node;
                if(v[right] != "null") {
                    TreeNode *cur = new TreeNode(stoi(v[right]));
                    nodesOnLevel.front()->right = cur;
                    nodesOnLevel.push(cur);
                }
                nodesOnLevel.pop();
                index += 2;
            }
        }
        
        return node;
    }
};

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

[LeetCode] Find Median from Data Stream

2015-10-20T23:29:00.001-07:00

Question can be found https://leetcode.com/problems/find-median-from-data-stream/

class MedianFinder {
    priority_queue<int> up;
    priority_queue<int, vector<int>, greater<int> > down;
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        if(up.empty() || num <= up.top()) {
            up.push(num);
        }
        else if(down.empty() || num >= down.top()) {
            down.push(num);
        }
        else {
            up.push(num);
        }

        if(up.size() >= down.size() + 2) {
            int t = up.top();
            up.pop();
            down.push(t);
        }
        else if(down.size() >= up.size() + 2){
            int t = down.top();
            down.pop();
            up.push(t);
        }
    }
    // Returns the median of current data stream
    double findMedian() {
        if(up.size() > down.size()) return up.top();
        else if(down.size() > up.size()) return down.top();
        return (up.top() + down.top())/2.0;
    }
};

[LeetCode] Move Zeroes

2015-09-19T19:55:00.003-07:00

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        if(size<=1) return;
        int s = 0, e = 0;
        
        while(s<size) {
            while( s < size && nums[s] == 0) {
                s++;
            }
            if(s == size) break;
            
            swap(nums[s], nums[e]);
            e++;
            s++;
        }
        return;
    }
};

[LeetCode] Expression Add Operators

2015-09-16T20:21:00.001-07:00

Given a string that contains only digits 0-9 and a target value, return all possibilities to add operators +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

class Solution {
void helper(vector<string>& res, string &nums, 
            string expr, long prev, 
            long curVal, int target) {
                
    if (nums.length() == 0 
        && curVal == target) {
        res.push_back(expr);
        return;
    }

    for (int i = 1; i<=nums.length(); i++) {
        
        string firstNum = nums.substr(0, i);
        
        if(i > 1 && firstNum[0] == '0') {
            return;
        }
        
        long first = stol(firstNum);
        string secondNum = nums.substr(i);

        if (expr.length() == 0) {
            helper(res, secondNum, firstNum, first, first, target);
            continue;
        }
        helper(res, secondNum, expr+"+"+firstNum, 
                first, curVal + first, target);
        helper(res, secondNum, expr+"-"+firstNum,
                -first, curVal - first, target);
        helper(res, secondNum, expr+"*"+firstNum, 
                prev*first, curVal-prev+prev*first, target);
    }
}

public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        helper(res, num, "", 0, 0, target);
        return res;
    }
};

[LeetCode] Longest Common Prefix

2015-09-15T23:23:00.002-07:00

Write a function to find the longest common prefix string amongst an array of strings.

class Solution {
    static bool comp(string &s1, string &s2) {
        return s1.length() < s2.length();
    }
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0) return "";
        sort(strs.begin(), strs.end(), comp);
        string s = strs[0];
        int len = s.length();
        for(int i=1;i<strs.size();i++) {

            while(strs[i].find(s.substr(0, len)) != 0) len --;
        }
        return s.substr(0, len);
    }
};

[LeetCode] Median of Two Sorted Arrays

2015-09-15T17:15:00.002-07:00

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

class Solution {
public:
    double findK(vector<int>& nums1, int s1, 
                vector<int>& nums2, int s2, int k)
    {
        if(s1>=nums1.size()) return nums2[s2+k-1];
        if(s2>=nums2.size()) return nums1[s1+k-1];
        
        if(k == 1) return min(nums1[s1], nums2[s2]);
        
        int n1 = s1+k/2-1 < nums1.size() ? nums1[s1+k/2-1] : INT_MAX;
        int n2 = s2+k/2-1 < nums2.size() ? nums2[s2+k/2-1] : INT_MAX;
        
        if(n1 > n2)
        {
            return findK(nums1, s1, nums2, s2+k/2, k- k/2);
        }
        else
        {
            return findK(nums1, s1+k/2, nums2, s2, k- k/2);
        }
    }   
    
    double findMedianSortedArrays(vector<int>& nums1, 
                            vector<int>& nums2) {
        int l1 = nums1.size(), l2 = nums2.size();
        if((l1 + l2) % 2 == 0)
        {
            return (findK(nums1, 0, nums2, 0, (l1+l2)/2) + findK(nums1, 0, nums2, 0, (l1+l2)/2+1))/2;
        }
        
        return findK(nums1, 0, nums2, 0, (l1+l2)/2+1);
    }
};

[LeetCode] Perfect Squares

2015-09-13T22:59:00.001-07:00

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

class Solution {
public:
    int numSquares(int n) {
        vector<int> DP(n+1,INT_MAX);
        DP[0] = 0;
        for(int i =1;i<=n;i++)
        {
            for(int j=1;j*j<=i;j++)
            {
                DP[i] = min(DP[i], DP[i-j*j]+1);
            }
        }
        return DP[n];
    }
};

[LeetCode] First Bad Version

2015-09-08T11:55:00.002-07:00

The question can be found https://leetcode.com/problems/first-bad-version/

Note: if we use m = (e+s)/2, it might cause overflow.

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
    
public:
    int firstBadVersion(int n) {
        int s = 1;
        while(s < n)
        {
            int m = s + (n-s)/2;
            if(isBadVersion(m)) n = m;
            else s = m+1;
        }
        return s;
    }
};

[LeetCode] H-Index

2015-09-03T23:46:00.001-07:00

This question can be found https://leetcode.com/problems/h-index/

class Solution {
public:
    int hIndex(vector& citations) {
        sort(citations.begin(), citations.end());
        int j = 0;
        for(int i=citations.size()-1;i>=0;i--)
        {
            j++;
            if(citations[i] == j) return j;
            if(citations[i] < j) return j-1;
        }
        return j;
    }
};

[LeetCode] Course Schedule II

2015-08-27T00:17:00.002-07:00

The question can be found here: https://leetcode.com/problems/course-schedule-ii/

Analysis:
1) find the sink node which doesn't have any directed neighbors
2) put it at the head of the list and remove it
3) repeat 1) and 2)
See more at :https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html

class Solution {
    bool isSinkNode(unordered_map<int, unordered_set<int>>& map, 
                    vector<int> &visited, int cur, 
                    vector<int> & res, bool &cycle){
                        
        if(visited[cur] == 1) 
        {
            cycle = true;
            return false;
        }
        // 1 means its being visited in a path
        visited[cur] = 1;
        int nonSinkNeighbors = map[cur].size();
        for(auto e: map[cur])
        {
            if(visited[e] == 2|| 
                isSinkNode(map, visited, e,
                res, cycle)) nonSinkNeighbors--;
            else if(cycle) return false;
        }
        // if all the neighbors are sink node
        if(0 == nonSinkNeighbors) 
        {
            res.push_back(cur);
            //2 means this node is a sink node
            visited[cur] = 2;
        }
        // 3 means its visited in a path but not a sink node
        // we need to set it a value other than 1 to 
        else visited[cur] = 3; 
        return visited[cur] == 2;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res;
        unordered_map<int, unordered_set<int>> map;
        for(auto p: prerequisites) map[p.first].insert(p.second);
        bool cycle = false;
        
        vector<int> visited(numCourses, 0);
        for(int i=0;i<numCourses;i++)
        {
            //0 means its not ever visited.
            if(visited[i] == 0) isSinkNode(map, visited, i, res, cycle);
        }
        if(cycle) return vector<int>();
        return res;
    }
};

[LeetCode] Missing Number

2015-08-24T17:01:00.001-07:00

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int size = nums.size();
        int total = 0;
        for(int i=0; i<size; i++)
        {
            total += nums[i];
        }
        return size*(size+1)/2 - total;
    }
};

[LeetCode] String to Integer (atoi)

2015-08-16T19:27:00.001-07:00

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

class Solution {
public:
    int myAtoi(string str) {
        if(str.empty()) return 0;
        int i = 0;
        bool hasPlus = false;
        while(i<str.length() && str[i] == ' ') i++;
        
        if(i<str.length() && str[i] == '+') {
            i++;
            hasPlus = true;
        }
        int flag = 1;
        if(!hasPlus && i < str.length() && str[i] == '-') 
        {
            flag = -1;
            i++;
        }

        long res = 0;
        
        while(i<str.length())
        {
            if(!isdigit(str[i]) ) return res*flag;
            res = res*10 + str[i] - '0';
            if(res > INT_MAX)
            {
                if(flag == 1) return INT_MAX;
                if(res != (long)-1*INT_MIN ) return INT_MIN;
            }
            i++;
        }
        
        return res * flag;
    }
};

[LeetCode] Sum Root to Leaf Numbers

2015-08-16T13:39:00.002-07:00

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Analysis: It's the same question as get Binary Tree Paths

/**
 * 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 {
/**
 * 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 {
    vector<string> getAllPaths(TreeNode * node)
    {
        vector<string> res;
        if(!node) return res;
        string cur = to_string(node->val);
        if(!node->left && !node->right) res.push_back(cur);
        
        if(node->left)
        {
            vector<string> left = getAllPaths(node->left);
            for(auto e :left) res.push_back(cur+e);
            
        }
        if(node->right)
        {
            vector<string> right = getAllPaths(node->right);
            for(auto e :right) res.push_back(cur+e);
        }    
        return res;
    }
public:
    int sumNumbers(TreeNode* root) {
        vector<string> paths = getAllPaths(root);
        int res = 0;
        for(auto e:paths) res += stoi(e);
        return res;
    }
};

[LeetCode] Combination Sum III

2015-08-16T13:01:00.000-07:00

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

class Solution {
    void solve(vector<vector<int>> &res, vector<int> &one, int k, int s, int e)
    {
        if(e == 0 && k == 0)
        {   
            res.push_back(one);
            return;
        }

        for(int i=s;i<=e && i<=9;i++)
        {
            one.push_back(i);
            solve(res, one, k-1,i+1, e-i);
            one.pop_back();
        }
    }
public:

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> one;
        solve(res, one, k, 1, n);
        return res;
    }
};

[LeetCode] Add Digits

2015-08-16T12:41:00.002-07:00

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Please refer to this formula:

The formula is:

class Solution {
public:
    int addDigits(int num) {
        if(0 == num) return 0;
        if(num % 9 == 0) return 9;
        return num % 9;
    }
};

[LeetCode] Binary Tree Paths

2015-08-15T20:28:00.000-07:00

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

["1->2->5", "1->3"]

/**
 * 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<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if(!root) return res;
        string cur = to_string(root->val);
        if(root->left) 
        {
            vector<string> left = binaryTreePaths(root->left);
            for(auto e: left)
            {
                res.push_back(cur + "->" + e);
            }
        }
        if (root->right)
        {
            vector<string> right = binaryTreePaths(root->right);
            for(auto e: right)
            {
                res.push_back(cur + "->" + e);
            }            
        }
        
        if(!root->right && !root->left)
        {
            res.push_back(to_string(root->val));
        }
        return res;
    }
};

[LeetCode] Basic Calculator II

2015-08-15T12:10:00.001-07:00

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Note: What can be done through stl stack, can also be done through stl vector.

class Solution {

public:
    int calculate(string s) {
        vector<int> numbers;
        vector<char> operators;
        int i = 0;
        while(i<s.length())
        {
            char e = s[i++];
            if(e == ' ') continue;
            
            if(isdigit(e))
            {
                int j = i;
                while(j < s.length() && isdigit(s[j]) ) j++;
                int num = stoi(s.substr(i-1, j-i+1));
                i = j;
                if(!operators.empty() && 
                    (operators.back() == '*' 
                    || operators.back() == '/')
                  )
                {
                    char op = operators.back();
                    operators.pop_back();
                    if(op == '*') numbers.back() *= num;
                    else numbers.back() /= num;
                }
                else numbers.push_back(num);
                
            }
            else operators.push_back(e);
        }
        
        if(numbers.empty()) return 0;
        int a = numbers[0];
        int opIndex = 0;
        for(int i = 1;i<numbers.size();i++)
        {
            char op = operators[opIndex++];
            if(op == '+') a += numbers[i];
            else a -= numbers[i];
        }
        return a;
    }
};

[LeetCode] Kth Smallest Element in a BST

2015-08-13T23:56:00.003-07:00

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements

Analysis: Note, in order traverse a BST will get a sorted array from smallest to biggest.

    int visit(TreeNode* root, int k, int &i){
        if(!root)   return 0;
        int res = visit(root->left,k,i);
        if(i == k)  return res;
        if(++i == k)    return root->val;
        return visit(root->right,k,i);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int i=0;
        return visit(root,k,i);
    }

[LeetCode] Palindrome Linked List

2015-08-11T17:28:00.001-07:00

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */


class Solution {
    ListNode *reverse(ListNode *node)
    {
        ListNode *res = NULL;
        while(node)
        {
            ListNode *t = node->next;
            node->next = res;
            res = node;
            node = t;
        }
        return res;
    }
public:
    bool isPalindrome(ListNode* head) {
        if(!head) return true;
        
        ListNode *slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        if(fast) slow = slow->next;

        slow = reverse(slow);
        
        while(slow && head)
        {
            if(slow->val != head->val) return false;
            slow = slow->next;
            head = head->next;
        }
        return true;
    }
};

[LeetCode] Different Ways to Add Parentheses

2015-08-10T22:03:00.000-07:00

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Analysis:

Divide and conquer

class Solution {
    void calculate(vector<int>&res, vector<int>&l,
                   vector<int>&r, char op)
    {
        for(auto e:l)
        {
            for(auto m:r)
            {
                if(op == '+') res.push_back(e+m);
                else if(op == '-') res.push_back(e-m);
                else if(op == '*') res.push_back(e*m);
                else if(op == '/') {
                    if(m!=0)res.push_back(e/m);
                    else res.push_back(e>0?INT_MAX:INT_MIN);
                }
            }
        }
    }
    void solve(vector<int> &res,  const string & input)
    {
        bool found = false;
        for(int i=1;i<input.length();i++)
        {
            if(input[i] == '+' || input[i] == '-'  
                || input[i] == '*' || input[i] == '/')
            {
                vector<int> l, r;
                solve(l, input.substr(0,i));
                solve(r, input.substr(i+1));
                if(!found) found = true;
                calculate(res, l, r, input[i]);
            }
        }
        
        if(!found) res.push_back(stoi(input));
    }
    
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        solve(res, input);
        return res;
    }
};

[LeetCode] Summary Ranges

2015-06-25T13:21:00.002-07:00

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Note: Overflow.

class Solution {
    string getRange(int start, int end)
    {
        if(start == end) return to_string(start);
        return to_string(start) + "->" + to_string(end);
    }
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        if(nums.empty()) return res;
        
        long start = nums[0];
        long end = start;
        
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i] - end >1)
            {
                res.push_back(getRange(start, end));
                start = nums[i];
                end = start;
            }
            else
            {
                end = nums[i];
            }
        }
        res.push_back(getRange(start, end));
        return res;
    }
};

[LeetCode] LRU Cache

2015-06-07T18:09:00.001-07:00

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

NOTE:
In the list, we should be able to track the key in map, so that when it's reached the cap, we can delete the entry in map.

class LRUCache{
    struct LRUEntry
    {
        int val,key;
        LRUEntry(int k, int v) :val(v), key(k){}
    };
    //save value
    list<LRUEntry> cache;
    
    //save key
    unordered_map<int, list<LRUEntry>::iterator> map;
    int cap;
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    void moveToHead(int key)
    {
        auto it =  map[key];
        cache.push_front(LRUEntry(key, it->val));
        cache.erase(it);
        map[key] = cache.begin();
    }
    int get(int key) {
        if(map.find(key) == map.end()) return -1;
        moveToHead(key);
        return map[key]->val;
    }
    void set(int key, int value) 
    {
        if(map.find(key) != map.end())
        {
            *map[key] =  LRUEntry(key, value);
            moveToHead(key);
            return;
        }
        if(cache.size() == cap)
        {
            map.erase(cache.rbegin()->key);
            cache.pop_back();
        }
        cache.push_front(LRUEntry(key,value));
        map[key] = cache.begin();
    }
};