Google+ Followers

Thursday, July 20, 2017

[Leetcode] Expression Add Operators, Solution


Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +-, 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"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

[Thoughts]

这道题除了DFS,我还没想出更好的办法。需要注意的是如何处理*号。每当尝试用*号的时候,要注意处理上一次计算。比如第二个例子 “232”,当处理到2+3的时候,值是5,这时候对于下一个数字2,如果用*号,就得把上一次计算回滚,(5 - 3) + 3*2。

除此之外,没有难点。


[Code]

1:    vector<string> addOperators(string num, int target) {  
2:      vector<string> result;  
3:      if(num.size() == 0) return result;  
4:        
5:      nextStep(num, 0, target, 0, "", 0, result);  
6:      return result;  
7:    }  
8:      
9:    void nextStep(string& numStr, int cur_index, int& target, long value, string equation, long pre_num, vector<string>& result) {  
10:      if(value == target && cur_index == numStr.size()) {  
11:        result.push_back(equation);  
12:        return;  
13:      }  
14:        
15:      for(int i = 1; i< numStr.size() - cur_index +1; i++) {  
16:        if(i >1 && numStr[cur_index] == '0') break;  
17:        string temp = numStr.substr(cur_index, i);  
18:        long num = stol(temp);  
19:          
20:        if(cur_index == 0){  
21:          nextStep(numStr, cur_index +i, target, num, temp, num, result);  
22:          continue;  
23:        }  
24:          
25:        nextStep(numStr, cur_index +i, target, value + num, equation + '+' + temp, num, result);  
26:        nextStep(numStr, cur_index +i, target, value - num, equation + '-' + temp, -num, result);  
27:        nextStep(numStr, cur_index +i, target, value - pre_num + pre_num * num, equation + '*' + temp, pre_num * num, result);  
28:      }  
29:    }  




[Leetcode] Serialize and Deserialize Binary Tree, Solution

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.
For example, you may serialize the following tree
    1
   / \
  2   3
     / \
    4   5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.


[Thoughts]

这题纯粹是一道实现题,没有难点。看Code。



[Code]

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Codec {  
11:  public:  
12:    
13:    // Encodes a tree to a single string.  
14:    string serialize(TreeNode* root) {  
15:      stringstream ss;  
16:      serializeImpl(root, ss);  
17:      return ss.str();  
18:    }  
19:    
20:    // Decodes your encoded data to tree.  
21:    TreeNode* deserialize(string data) {  
22:      std::istringstream ss(data);  
23:      return deserializeImpl(ss);  
24:    }  
25:      
26:    void serializeImpl(TreeNode* root, stringstream& ss) {  
27:      if(root == NULL) {  
28:        ss<<"#,";  
29:        return;  
30:      }  
31:        
32:      ss << root->val << ",";  
33:      serializeImpl(root->left, ss);  
34:      serializeImpl(root->right, ss);  
35:    }  
36:      
37:    TreeNode* deserializeImpl(istringstream & ss) {  
38:      std::string token;  
39:    
40:      std::getline(ss, token, ',');  
41:        
42:      if(token == "#") {  
43:        return NULL;  
44:      }  
45:        
46:      TreeNode* root = new TreeNode(stoi(token));  
47:        
48:      root->left = deserializeImpl(ss);  
49:      root->right = deserializeImpl(ss);  
50:      return root;  
51:    }  
52:      
53:      
54:  };  
55:    
56:  // Your Codec object will be instantiated and called as such:  
57:  // Codec codec;  
58:  // codec.deserialize(codec.serialize(root));  


[Leetcode] Palindrome Pairs, Solution

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]


[Thoughts]

这题不难,找的是words[i] + words[j]是个palindrome。找两个例子就可以清晰的分析出规律来。

比如 “sssll”这个词,如果把这个词从中间切成两块, 就是 “ss” + “sll”。 ss本身就是palindrome,而“sll”的翻转就是字典里的“lls”

所以对于任意一个词,我们总是可以在其中任意一个位置K把它一切为二:



那么对于可能的candidate只有情况:

  1. left 是 palindrome,那么可能的组合是 candidate | left | right,candidate就是right的翻转
  2. right 是palindrome, 那么可能的组合是 left | right | candidate, 而这里candidate是left的翻转

所以,一开始有个hashmap,把翻转的字符串保存下来,这样在后面切字符串的时候,方便查询即可。

[Code]


1:    vector<vector<int>> palindromePairs(vector<string>& words) {  
2:      unordered_map<string, int> dict;  
3:      set<vector<int>> result;  
4:      for(int i =0; i< words.size(); i++) {  
5:        string word = words[i];  
6:        reverse(word.begin(), word.end());  
7:        dict[word] = i;  
8:      }  
9:      for(int i =0; i< words.size(); i++) {  
10:        string word = words[i];  
11:        // 切字符串三种情况,最左边切,中间切,和最右边切。   
12:        //注意,这里j<= word.size()为了cover最右边切这种情况  
13:        for(int j = 0; j<=word.size(); j++) {  
14:          string left = word.substr(0, j);  
15:          string right = word.substr(j, word.size() - j);  
16:          // candi | left | right  
17:          if(isPalindro(left) && dict.find(right) != dict.end() && dict[right] != i) {  
18:            result.insert({dict[right], i});  
19:          }  
20:          // left | right | candi  
21:          if(isPalindro(right) && dict.find(left) != dict.end() && dict[left] != i) {  
22:            result.insert({i, dict[left]});  
23:          }  
24:        }   
25:      }  
26:      std::vector<vector<int>> output(result.begin(), result.end());   
27:      return output;  
28:    }  
29:    bool isPalindro(string& str) {  
30:      int left = 0, right = str.size() -1;  
31:      while(left < right) {  
32:        if(str[left++] != str[right--]) return false;  
33:      }  
34:      return true;  
35:    }  



Sunday, October 25, 2015

[Leetcode] Product of Array Except Self, Solution

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
[Thoughts]
一般这种题都可以分解成若干子问题来解决。As defined, 
output[i] is equal to the product of all the elements of nums except nums[i].
简单的说
    output[i] =  { i 前面的数的乘积}  X  { i 后面的数的乘积}
问题就解决了,首先从前往后扫描数组一遍,对每一个i,得到{i 前面的数的乘积}(可以称做output_before),然后在从后往前扫描数组一遍,获得 { i 后面的数的乘积}(可以称做output_after)。 将两数相乘即为所求。
举个例子(如下图),nums = {1,2,3,4}, 第一遍,从前往后扫描一遍,得到的output_before = {1, 1, 2, 6}. 从后往前扫描一遍,得到的output_after = {24, 12, 4, 1}.
那么  output [i] = output_before[i] * output_after[i],   output = {24, 12, 8, 6}

[Code]
1:  class Solution {  
2:  public:  
3:    vector<int> productExceptSelf(vector<int>& nums) {  
4:      vector<int> products;  
5:      if(nums.size() == 0) return products;  
6:      int product = 1;  
7:      products.push_back(1);  
8:      for(int i =1; i< nums.size(); i++) {  
9:        product *= nums[i-1];  
10:        products.push_back(product);  
11:      }  
12:      product = 1;  
13:      for(int i =nums.size()-2; i>=0; i--) {  
14:        product = product * nums[i+1];  
15:        products[i] = products[i] * product;   
16:      }  
17:      return products;  
18:    }  
19:  };  

github: https://github.com/codingtmd/leetcode/blob/master/src/Product%20of%20Array%20Except%20Self.cpp








Saturday, October 17, 2015

[Leetcode] Different Ways to Add Parentheses, Solution

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]

[Thoughts]
这题就是分治法- Divide and Conquer的一个例子。在递归的过程中,根据符号位,不断将一个字符串分成两个子串,然后将两个子串的结果merge起来。


[Code]

1:  class Solution {  
2:  public:  
3:    int compute(int a, int b, char op) {  
4:      switch(op) {  
5:        case '+': return a + b;  
6:        case '-': return a - b;  
7:        case '*': return a * b;  
8:      }  
9:    }  
10:    vector<int> diffWaysToCompute(string input) {  
11:      int number = 0, i=0;  
12:      for(; i< input.length() && isdigit(input[i]); ++i) {  
13:        number = number * 10 + input[i]-'0';  
14:      }  
15:      // if pure number, just return  
16:      if(i == input.length()) return {number};  
17:      vector<int> diffWays, lefts, rights;  
18:      for(int i =0; i< input.length(); i++) {  
19:        if(isdigit(input[i])) continue;  
20:        lefts =   
21:          diffWaysToCompute(input.substr(0, i));  
22:        rights =   
23:          diffWaysToCompute(input.substr(i + 1, input.length() - i - 1));  
24:        for(int j = 0; j < lefts.size(); ++j)   
25:          for( int k =0; k < rights.size(); ++k)   
26:            diffWays.push_back(compute(lefts[j], rights[k], input[i]));  
27:      }  
28:      return diffWays;  
29:    }  
30:  };  



Note: 已有的实现有大量的重复计算,如果想进一步优化时间的话,可以考虑用memoization来避免冗余计算。比如,用个hash map 来保存中间计算的结果,如下:

1:  class Solution {  
2:  public:  
3:    unordered_map<string, vector<int>> memo;  
4:    int compute(int a, int b, char op) {  
5:      switch(op) {  
6:        case '+': return a + b;  
7:        case '-': return a - b;  
8:        case '*': return a * b;  
9:      }  
10:    }  
11:    string generateKey(int startIndex, int endIndex) {  
12:      return to_string(startIndex) + "-" + to_string(endIndex);  
13:    }  
14:    vector<int> diffWaysToCompute(string input) {  
15:      return diffWaysToComputeWithMemo(input, 0, input.size()-1);  
16:    }  
17:    vector<int> diffWaysToComputeWithMemo(string& input, int startIndex, int endIndex) {    
18:      string cache_key = generateKey(startIndex, endIndex);  
19:      if(memo.find(cache_key) != memo.end()) return memo[cache_key];  
20:      int number = 0, i=startIndex;  
21:      for(; i<= endIndex && isdigit(input[i]); ++i) {  
22:        number = number * 10 + input[i]-'0';  
23:      }  
24:      // if pure number, just return  
25:      if(i > endIndex) return {number};  
26:      vector<int> diffWays, lefts, rights;  
27:      for(int i =startIndex; i< endIndex; i++) {  
28:        if(isdigit(input[i])) continue;  
29:        lefts =   
30:          diffWaysToComputeWithMemo(input, startIndex, i-1);  
31:        rights =   
32:          diffWaysToComputeWithMemo(input, i+1, endIndex );  
33:        for(int j = 0; j < lefts.size(); ++j)   
34:          for( int k =0; k < rights.size(); ++k)   
35:            diffWays.push_back(compute(lefts[j], rights[k], input[i]));  
36:      }  
37:      memo[cache_key] = diffWays;  
38:      return diffWays;  
39:    }  
40:  };  


github: https://github.com/codingtmd/leetcode/blob/master/src/Different%20Ways%20to%20Add%20Parentheses(Memoization).cpp










[Leetcode] Valid Anagram, Solution

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.
[Thoughts]
对于字符出现次数做个统计就好了。因为只有26个小写字母,所以可以建立一个大小为26的索引数组charcount,用来统计每个字符的出现次数。
对于s, 将其作为字符数组进行遍历,在遍历的过程中,对每个出现的字符计数加一。
对于t, 同样将其遍历,对每个出现的字符计数减一。
如果s和t是anagram , 那么最后的charcount数组中所有字符的计数都应该是0, 否则就不是anagram。

[Code]
1:  class Solution {  
2:  public:  
3:    bool isAnagram(string s, string t) {  
4:      vector<int> charcount(26, 0);  
5:      for(int i =0; i< s.length(); i++) {  
6:        charcount[s[i] - 'a'] ++;  
7:      }  
8:      for(int i =0; i< t.length(); i++) {  
9:        charcount[t[i] - 'a'] --;  
10:      }  
11:      for(int i =0; i<charcount.size(); i++) {  
12:        if(charcount[i] != 0) {  
13:          return false;  
14:        }  
15:      }  
16:      return true;  
17:    }  
18:  };  

Friday, October 16, 2015

[Leetcode] Binary Tree Paths, Solution

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:
["1->2->5", "1->3"]

[Thought]
这个主要就是实现题。对树进行深度遍历,在遍历的过程中保存访问节点,当遍历到叶节点的时候,打印出来路径即可。

[Code]
1:  class Solution {  
2:  public:  
3:    vector<string> binaryTreePaths(TreeNode* root) {  
4:      vector<string> paths;  
5:      vector<int> nodes;  
6:      getAllPaths(root, nodes, paths);       
7:      return paths;  
8:    }  
9:    void getAllPaths(TreeNode* node, vector<int>& nodes,vector<string>& paths) {  
10:      if(node == NULL) {  
11:        return;  
12:      }  
13:      if(node->left== NULL && node->right == NULL) {  
14:        stringstream ss;  
15:        for(int i =0; i< nodes.size(); i++) {  
16:          ss << nodes[i] << "->";  
17:        }  
18:        ss << node->val;  
19:        paths.push_back(ss.str());  
20:        return;  
21:      }  
22:      nodes.push_back(node->val);  
23:      getAllPaths(node->left, nodes, paths);  
24:      getAllPaths(node->right, nodes, paths);  
25:      nodes.pop_back();  
26:    }  
27:  };  

Github: https://github.com/codingtmd/leetcode/blob/master/src/Binary%20Tree%20Paths.cpp