Huahua's Tech Road

花花酱 Leetcode 153. Find Minimum in Rotated Sorted Array

By zxi on September 6, 2017

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Idea:

Divide and conquer.

Evenly Split the array into two sub-arrays, and find the minimums of them, return the smaller one.

findMin(a[0..n]) = min(findMin(a[0..n/2], a[n/2..n])

Key property:

One of the sub-array will be a sorted array, it takes O(1) to find the minimal element, just the first element.

Time complexity:

T(n) = O(1) + T(n/2) = O(logn)

Solution:

// Author: Huahua

class Solution {

public:

int findMin(vector<int> &num) {

return findMin(num, 0, num.size()-1);

}

private:

int findMin(const vector<int>& num, int l, int r)

{

// Only 1 or 2 elements

if (l+1 >= r) return min(num[l], num[r]);

// Sorted

if (num[l] < num[r]) return num[l];

int mid = l + (r-l)/2;

return min(findMin(num, l, mid-1),

findMin(num, mid, r));

}

};

花花酱 LeetCode 79. Word Search

By zxi on September 6, 2017

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea:

Search, depth first search

Solution:

C++

class Solution {

public:

bool exist(vector<vector<char>> &board, string word) {

if(board.size()==0) return false;

h = board.size();

w = board[0].size();

for(int i=0;i<w;i++)

for(int j=0;j<h;j++)

if(search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if(x<0 || x==w || y<0 || y==h || word[d] != board[y][x])

return false;

// Found the last char of the word

if(d==word.length()-1)

return true;

char cur = board[y][x];

board[y][x] = 0;

bool found = search(board, word, d+1, x+1, y)

|| search(board, word, d+1, x-1, y)

|| search(board, word, d+1, x, y+1)

|| search(board, word, d+1, x, y-1);

board[y][x] = cur;

return found;

}

private:

int w;

int h;

};

Python

# Author: Huahua, running time: 216 ms

class Solution:

def exist(self, board: List[List[str]], word: str) -> bool:

if not board: return False

h, w = len(board), len(board[0])

def search(d: int, x: int, y: int) -> bool:

if x < 0 or x == w or y < 0 or y == h or word[d] != board[y][x]:

return False

if d == len(word) - 1: return True

cur = board[y][x]

board[y][x] = ''

found = search(d + 1, x + 1, y) or search(d + 1, x - 1, y) or search(d + 1, x, y + 1) or search(d + 1, x, y - 1)

board[y][x] = cur

return found

return any(search(0, j, i) for i in range(h) for j in range(w))

花花酱 LeetCode 654. Maximum Binary Tree

By zxi on September 4, 2017

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]

Output: return the tree root node representing the following tree:

/ \

3 5

\ /

2 0

Idea:

Recursion

Solution:

With copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(nlogn) ~ O(n^2)

running time 79ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

if(nums.empty()) return nullptr;

auto it = std::max_element(nums.begin(), nums.end());

TreeNode* root=new TreeNode(*it);

vector<int> left(nums.begin(), it);

vector<int> right(it+1, nums.end());

root->left = constructMaximumBinaryTree(left);

root->right = constructMaximumBinaryTree(right);

return root;

}

Without copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(logn) ~ O(n)

running time 66ms

// Author: Huahua

class Solution {

public:

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

return makeMBT(nums, 0, nums.size());

}

private:

TreeNode* makeMBT(const vector<int>& nums, int begin, int end) {

if(begin>=end) return nullptr;

auto it = std::max_element(nums.begin() + begin, nums.begin() + end);

TreeNode* root=new TreeNode(*it);

int index = it - nums.begin();

root->left = makeMBT(nums, begin, index);

root->right = makeMBT(nums, index+1, end);

return root;

}

};

花花酱 LeetCode 669. Trim a Binary Search Tree

By zxi on September 4, 2017

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input:

/ \

0 2

L = 1

R = 2

Output:

Example 2:

Input:

/ \

0 4

L = 1

R = 3

Output:

This problem can be solved with recursion

There 3 cases in total depends on the root value and L, R

Time complexity: O(n)

Space complexity: O(1)

Solution:

// Author: Huahua

class Solution {

public:

// No cleanup -> memory leak

TreeNode* trimBST(TreeNode* root, int L, int R) {

if(!root) return nullptr;

// val not in range, return the left/right subtrees

if(root->val < L) return trimBST(root->right, L, R);

if(root->val > R) return trimBST(root->left, L, R);

// val in [L, R], recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

};

The previous solution has potential memory leak for languages without garbage collection.

Here’s the full program to delete trimmed nodes.

// Author: Huahua

#include <iostream>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

// With cleanup -> no memory leak

TreeNode*& trimBST(TreeNode*& root, int L, int R) {

if(!root) return root;

if(root->val < L) {

auto& result = trimBST(root->right, L, R);

deleteTree(root->left);

delete root;

root=nullptr;

return result;

} else if(root->val > R) {

auto& result = trimBST(root->left, L, R);

deleteTree(root->right);

delete root;

root=nullptr;

return result;

} else {

// recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

void deleteTree(TreeNode* &root) {

if(!root) return;

deleteTree(root->left);

deleteTree(root->right);

delete root;

root=nullptr;

}

};

void PrintTree(TreeNode* root) {

if(!root) {

cout<<"null ";

return;

};

if(!root->left && !root->right) {

cout<<root->val<<" ";

} else {

cout<<root->val<<" ";

PrintTree(root->left);

PrintTree(root->right);

}

int main()

{

TreeNode* root=new TreeNode(2);

root->left=new TreeNode(1);

root->right=new TreeNode(3);

PrintTree(root);

std::cout<<std::endl;

TreeNode* t = Solution().trimBST(root, 3, 4);

PrintTree(t);

std::cout<<std::endl;

// Original root was deleted

PrintTree(root);

std::cout<<std::endl;

return 0;

}

Example output

2 1 3

null

花花酱 LeetCode 671. Second Minimum Node In a Binary Tree

By zxi on September 4, 2017

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input:

/ \

2 5

/ \

5 7

Output: 5

Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input:

/ \

2 2

Output: -1

Explanation: The smallest value is 2, but there isn't any second smallest value.

Solution:

Time complexity O(n), Space complexity O(n)

/**

* 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 findSecondMinimumValue(TreeNode* root) {

if(!root) return -1;

// return BFS(root);

return DFS(root, root->val);

}

private:

// Time complexity: O(n)

// Space complexity: O(n)

int BFS(TreeNode* root) {

if(!root) return -1;

// Smallest value

int s1 = root->val;

// Sencond smallest value

int s2 = INT_MAX;

bool found = false;

deque<TreeNode*> q;

q.push_back(root);

while(!q.empty()) {

TreeNode* node = q.front();

q.pop_front();

// Keep updating second smallest value

if(node->val > s1 && node->val < s2) {

s2 = node->val;

found = true;

// No need to add it's children into queue

continue;

}

if(!node->left) continue;

q.push_back(node->left);

q.push_back(node->right);

}

return found?s2:-1;

}

// Return the second smallest number in the (sub-tree)

// s1 is the smallest value

int DFS(TreeNode* root, int s1) {

if(!root) return -1;

// If root's value is already grater than s1,

// then all its children's value should be >= s1.

// Thus root's value is the second smallest one.

// No need to visit the

if(root->val > s1) return root->val;

int sl = DFS(root->left, s1);

int sr = DFS(root->right, s1);

if(sl == -1) return sr;

if(sr == -1) return sl;

// Return the smaller one among two subtrees

return min(sl, sr);

}

};