花花酱 LeetCode 124. Binary Tree Maximum Path Sum

By zxi on October 17, 2017

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

/ \

2 3

Return 6.

Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

Solution: Recursion

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxPathSum(TreeNode* root) {

if (!root) return 0;

int ans = INT_MIN;

maxPathSum(root, ans);

return ans;

}

private:

int maxPathSum(TreeNode* root, int& ans) {

if (!root) return 0;

int l = max(0, maxPathSum(root->left, ans));

int r = max(0, maxPathSum(root->right, ans));

int sum = l + r + root->val;

ans = max(ans, sum);

return max(l, r) + root->val;

}

};

Python3

"""

Author: Huahua

Runtime: 138 ms (< 90.38%)

"""

class Solution(object):

def _maxPathSum(self, root):

if not root: return -sys.maxint

l = max(0, self._maxPathSum(root.left))

r = max(0, self._maxPathSum(root.right))

self.ans = max(self.ans, root.val + l + r)

return root.val + max(l, r)

def maxPathSum(self, root):

self.ans = -sys.maxint

self._maxPathSum(root)

return self.ans

Related Problems:

花花酱 LeetCode 37. Sudoku Solver

By zxi on October 16, 2017

Problem:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

Idea:

DFS + backtracking

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

void solveSudoku(vector<vector<char>>& board) {

rows_ = vector<vector<int>>(9, vector<int>(10));

cols_ = vector<vector<int>>(9, vector<int>(10));

boxes_ = vector<vector<int>>(9, vector<int>(10));

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

for(int j = 0; j < 9; j++) {

const char c = board[i][j];

if ( c != '.') {

int n = c - '0';

int bx = j / 3;

int by = i / 3;

rows_[i][n] = 1;

cols_[j][n] = 1;

boxes_[by * 3 + bx][n] = 1;

}

fill(board, 0, 0);

}

private:

vector<vector<int>> rows_, cols_, boxes_;

bool fill(vector<vector<char>>& board, int x, int y) {

if (y == 9)

return true;

int nx = (x + 1) % 9;

int ny = (nx == 0) ? y + 1 : y;

if (board[y][x] != '.') return fill(board, nx, ny);

for (int i = 1; i <= 9; i++) {

int bx = x / 3;

int by = y / 3;

int box_key = by * 3 + bx;

if (!rows_[y][i] && !cols_[x][i] && !boxes_[box_key][i]) {

rows_[y][i] = 1;

cols_[x][i] = 1;

boxes_[box_key][i] = 1;

board[y][x] = i + '0';

if (fill(board, nx, ny)) return true;

board[y][x] = '.';

boxes_[box_key][i] = 0;

cols_[x][i] = 0;

rows_[y][i] = 0;

}

return false;

}

};

Related Problems:

[解题报告] LeetCode 51. N-Queens

花花酱 LeetCode 40. Combination Sum II

By zxi on October 15, 2017

Problem:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

Idea:

DFS

Solution:

C++ / set

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

set<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return vector<vector<int>>(ans.begin(), ans.end());

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

set<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.insert(curr);

return;

}

for (int i = s; i < candidates.size(); ++i) {

int num = candidates[i];

if (num > target) return;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

C++ / vector

// Author: Huahua

// Runtime: 9ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

vector<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return ans;

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

vector<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.push_back(curr);

return;

}

for (int i = s; i < candidates.size(); ++i) {

int num = candidates[i];

if (num > target) return;

if (i > s && candidates[i] == candidates[i - 1]) continue;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

花花酱 LeetCode 72. Edit Distance

By zxi on October 15, 2017

Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Idea:

Dynamic Programming

Solution:

Recursive

// Author: Huahua

// Runtime: 13 ms

class Solution {

public:

int minDistance(string word1, string word2) {

int l1 = word1.length();

int l2 = word2.length();

d_ = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, -1));

return minDistance(word1, word2, l1, l2);

}

private:

vector<vector<int>> d_;

// minDistance from word1[0:l1-1] to word2[0:l2-1]

int minDistance(const string& word1, const string& word2, int l1, int l2) {

if (l1 == 0) return l2;

if (l2 == 0) return l1;

if (d_[l1][l2] >= 0) return d_[l1][l2];

int ans;

if (word1[l1 - 1] == word2[l2 - 1])

ans = minDistance(word1, word2, l1 - 1, l2 - 1);

else

ans = min(minDistance(word1, word2, l1 - 1, l2 - 1),

min(minDistance(word1, word2, l1 - 1, l2),

minDistance(word1, word2, l1, l2 - 1))) + 1;

return d_[l1][l2] = ans;

}

};

Iterative

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minDistance(string word1, string word2) {

int l1 = word1.length();

int l2 = word2.length();

// d[i][j] := minDistance(word1[0:i - 1], word2[0:j - 1]);

vector<vector<int>> d(l1 + 1, vector<int>(l2 + 1, 0));

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

d[i][0] = i;

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

d[0][j] = j;

for (int i = 1; i <= l1; ++i)

for (int j = 1; j <= l2; ++j) {

int c = (word1[i - 1] == word2[j - 1]) ? 0 : 1;

d[i][j] = min(d[i - 1][j - 1] + c,

min(d[i][j - 1], d[i - 1][j]) + 1);

}

return d[l1][l2];

}

};

花花酱 LeetCode 57. Insert Interval

By zxi on October 14, 2017

Problem:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Idea:

Find the position of the new interval, insert it into the list and call MergeIntervals in LeetCode 56

Solution:

C++

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {

auto it = intervals.begin();

while (it != intervals.end() && newInterval.start > it->start) ++it;

intervals.insert(it, newInterval);

// Merge intervals without sorting

vector<Interval> ans;

for (const auto& interval : intervals) {

if (ans.empty() || interval.start > ans.back().end) {

ans.push_back(interval);

} else {

ans.back().end = max(ans.back().end, interval.end);

}

return ans;

}

};

Python

"""

Author: Huahua

Runtime: 78 ms

"""

class Solution(object):

def insert(self, intervals, newInterval):

index = len(intervals)

for i in range(len(intervals)):

if newInterval.start < intervals[i].start:

index = i

break

intervals.insert(index, newInterval)

ans = []

for interval in intervals:

if not ans or interval.start > ans[-1].end:

ans.append(interval)

else:

ans[-1].end = max(ans[-1].end, interval.end)

return ans

Solution 2:

C++

// Author: Huahua

// Runtime: 13 ms

class Solution {

public:

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {

vector<Interval> l;

vector<Interval> r;

int start = newInterval.start;

int end = newInterval.end;

for (const Interval& interval : intervals) {

if (interval.end < start)

l.push_back(interval);

else if (interval.start > end)

r.push_back(interval);

else {

start = min(start, interval.start);

end = max(end, interval.end);

}

vector<Interval> ans(std::move(l));

ans.emplace_back(start, end);

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

return ans;

}

};

Python

"""

Author: Huahua

Runtime: 68 ms

"""

class Solution(object):

def insert(self, intervals, newInterval):

start, end = newInterval.start, newInterval.end

l, r = [], []

for interval in intervals:

if interval.end < start: l += interval,

elif interval.start > end: r += interval,

else:

start = min(start, interval.start)

end = max(end, interval.end)

return l + [Interval(start, end)] + r

Related problems:

Huahua's Tech Road

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Solution: Recursion

C++

Python3

花花酱 LeetCode 37. Sudoku Solver

花花酱 LeetCode 40. Combination Sum II

花花酱 LeetCode 72. Edit Distance

花花酱 LeetCode 57. Insert Interval