花花酱 LeetCode 102. Binary Tree Level Order Traversal

By zxi on September 4, 2017

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

/ \

9 20

/ \

15 7

return its level order traversal as:

[

[3],

[9,20],

[15,7]

]

Solution 1: BFS O(n)

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode* root) {

if(!root) return {};

vector<vector<int>> ans;

vector<TreeNode*> curr,next;

curr.push_back(root);

while(!curr.empty()) {

ans.push_back({});

for(TreeNode* node : curr) {

ans.back().push_back(node->val);

if(node->left) next.push_back(node->left);

if(node->right) next.push_back(node->right);

}

curr.swap(next);

next.clear();

}

return ans;

}

};

Solution 2: DFS O(n)

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode* root) {

vector<vector<int>> ans;

DFS(root, 0 /* depth */, ans);

return ans;

}

private:

void DFS(TreeNode* root, int depth, vector<vector<int>>& ans) {

if(!root) return;

// Works with pre/in/post order

while(ans.size()<=depth) ans.push_back({});

ans[depth].push_back(root->val); // pre-order

DFS(root->left, depth+1, ans);

DFS(root->right, depth+1, ans);

}

};

花花酱 LeetCode 241. Different Ways to Add Parentheses

By zxi on September 3, 2017

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".

1 2	((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]

Solution:

Running time: 3ms

C++

// Author: Huahua

namespace huahua {

int add(int a, int b) { return a+b; }

int minus(int a, int b) { return a-b; }

int multiply(int a, int b) { return a*b; }

} // namespace huahua

class Solution {

public:

vector<int> diffWaysToCompute(string input) {

return ways(input);

}

private:

const vector<int>& ways(const string& input) {

// Already solved, return the answer

if(m_.count(input)) return m_[input];

// Array for answer of input

vector<int> ans;

// Break the expression at every operator

for(int i=0;i<input.length();++i) {

char op = input[i];

// Split the input by an op

if(op=='+' || op=='-' || op=='*') {

const string left = input.substr(0, i);

const string right = input.substr(i+1);

// Get the solution of left/right sub-expressions

const vector<int>& l = ways(left);

const vector<int>& r = ways(right);

std::function<int(int,int)> f;

switch(op) {

case '+': f = huahua::add; break;

case '-': f = huahua::minus; break;

case '*': f = huahua::multiply; break;

}

// Combine the solution

for(int a : l)

for(int b : r)

ans.push_back(f(a,b));

}

// Single number, e.g. s = "3"

if(ans.empty())

ans.push_back(std::stoi(input));

// memorize the answer for input

m_[input].swap(ans);

return m_[input];

}

unordered_map<string, vector<int>> m_;

};

Python3

# Author: Huahua, 44 ms

class Solution:

def diffWaysToCompute(self, input):

ops = {'+': lambda x, y: x + y,

'-': lambda x, y: x - y,

'*': lambda x, y: x * y}

def ways(s):

ans = []

for i in range(len(s)):

if s[i] in "+-*":

ans += [ops[s[i]](l, r) for l, r in itertools.product(ways(s[0:i]), ways(s[i+1:]))]

if not ans: ans.append(int(s))

return ans

return ways(input)

花花酱 LeetCode 21: Merge Two Sorted Lists

By zxi on September 3, 2017

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution 1: Iterative O(n)

// Author: Huahua

class Solution {

public:

Solution 1: Iterative

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail=&dummy;

while(l1 && l2) {

if(l1->val < l2->val) {

tail->next=l1;

l1=l1->next;

}else{

tail->next=l2;

l2=l2->next;

}

tail=tail->next;

}

if(l1) tail->next = l1;

if(l2) tail->next = l2;

return dummy.next;

}

};

Solution 2: Recursive O(n)

// Author: Huahua

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

// If one of the list is emptry, return the other one.

if(!l1 || !l2) return l1 ? l1 : l2;

// The smaller one becomes the head.

if(l1->val < l2->val) {

l1->next = mergeTwoLists(l1->next, l2);

return l1;

} else {

l2->next = mergeTwoLists(l1, l2->next);

return l2;

}

};

花花酱 LeetCode 110. Balanced Binary Tree

By zxi on September 3, 2017

Solution 1: O(nlogn)

// Author: Huahua

// O(nlogn)

class Solution {

Solution 1: O(nlogn)

public:

bool isBalanced(TreeNode* root) {

if(!root) return true;

int left_height = height(root->left);

int right_height = height(root->right);

return (abs(left_height - right_height)<=1) && isBalanced(root->left) && isBalanced(root->right);

}

private:

int height(TreeNode* root) {

if(!root) return 0;

return max(height(root->left), height(root->right))+1;

}

};

Solution 2: O(n)

// Author: Huahua

// O(n)

class Solution {

public:

bool isBalanced(TreeNode* root) {

if(!root) return true;

bool balanced = true;

height(root, &balanced);

return balanced;

}

private:

int height(TreeNode* root, bool* balanced) {

if(!root) return 0;

int left_height = height(root->left, balanced);

if(!balanced) return -1;

int right_height = height(root->right, balanced);

if(!balanced) return -1;

if(abs(left_height-right_height)>1) {

*balanced = false;

return -1;

}

return max(left_height, right_height) + 1;

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private boolean balanced;

private int height(TreeNode root) {

if (root == null || !this.balanced) return -1;

int l = height(root.left);

int r = height(root.right);

if (Math.abs(l - r) > 1) {

this.balanced = false;

return -1;

}

return Math.max(l, r) + 1;

}

public boolean isBalanced(TreeNode root) {

this.balanced = true;

height(root);

return this.balanced;

}

Python

"""

Author: Huahua

Running time: 76 ms

"""

class Solution:

def isBalanced(self, root):

self.balanced = True

def height(root):

if not root or not self.balanced: return -1

l = height(root.left)

r = height(root.right)

if abs(l - r) > 1:

self.balanced = False

return -1

return max(l, r) + 1

height(root)

return self.balanced

花花酱 Leetcode 140. Word Break II

By zxi on September 2, 2017

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution

Time complexity: O(2^n)

Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

vector<string> wordBreak(string s, vector<string>& wordDict) {

unordered_set<string> dict(wordDict.cbegin(), wordDict.cend());

return wordBreak(s, dict);

}

private:

// >> append({"cats and", "cat sand"}, "dog");

// {"cats and dog", "cat sand dog"}

vector<string> append(const vector<string>& prefixes, const string& word) {

vector<string> results;

for(const auto& prefix : prefixes)

results.push_back(prefix + " " + word);

return results;

}

const vector<string>& wordBreak(string s, unordered_set<string>& dict) {

// Already in memory, return directly

if(mem_.count(s)) return mem_[s];

// Answer for s

vector<string> ans;

// s in dict, add it to the answer array

if(dict.count(s))

ans.push_back(s);

for(int j=1;j<s.length();++j) {

// Check whether right part is a word

const string& right = s.substr(j);

if (!dict.count(right)) continue;

// Get the ans for left part

const string& left = s.substr(0, j);

const vector<string> left_ans =

append(wordBreak(left, dict), right);

// Notice, can not use mem_ here,

// since we haven't got the ans for s yet.

ans.insert(ans.end(), left_ans.begin(), left_ans.end());

}

// memorize and return

mem_[s].swap(ans);

return mem_[s];

}

private:

unordered_map<string, vector<string>> mem_;

};

Python3

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def wordBreak(self, s, wordDict):

words = set(wordDict)

mem = {}

def wordBreak(s):

if s in mem: return mem[s]

ans = []

if s in words: ans.append(s)

for i in range(1, len(s)):

right = s[i:]

if right not in words: continue

ans += [w + " " + right for w in wordBreak(s[0:i])]

mem[s] = ans

return mem[s]

return wordBreak(s)

Huahua's Tech Road

花花酱 LeetCode 102. Binary Tree Level Order Traversal

花花酱 LeetCode 241. Different Ways to Add Parentheses

C++

Python3

花花酱 LeetCode 21: Merge Two Sorted Lists

花花酱 LeetCode 110. Balanced Binary Tree

花花酱 Leetcode 140. Word Break II

Problem

Solution

Related Problems