Posts tagged as “medium”

花花酱 LeetCode 275. H-Index II

By zxi on March 15, 2018

题目大意：给你已排序的引用次数的数组，求h-index。

Problem:

https://leetcode.com/problems/h-index-ii/description/

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Solution 1: Linear Scan

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int hIndex(vector<int>& citations) {

for (int i = 1; i <= citations.size(); ++i)

if (*(citations.rbegin() + i - 1) < i) return i - 1;

return citations.size();

}

};

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int hIndex(vector<int>& citations) {

int n = citations.size();

int l = 0;

int r = n;

while (l < r) {

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

if (citations[n - m - 1] <= m)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 799. Champagne Tower

By zxi on March 11, 2018

题目大意：往一个香槟塔（i层有i个杯子）倒入n个杯子容量的香槟之后，求指定位置杯子中酒的容量。

Problem:

https://leetcode.com/problems/champagne-tower/description/

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup (250ml) of champagne.

Then, some champagne is poured in the first glass at the top. When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has it’s excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full – there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)

Example 1:

Input: poured = 1, query_glass = 1, query_row = 1

Output: 0.0

Explanation: We poured 1 cup of champagne to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:

Input: poured = 2, query_glass = 1, query_row = 1

Output: 0.5

Explanation: We poured 2 cups of champagne to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Note:

poured will be in the range of [0, 10 ^ 9].
query_glass and query_row will be in the range of [0, 99].

Idea: DP + simulation

define dp[i][j] as the volume of champagne will be poured into the j -th glass in the i-th row, dp[i][j] can be greater than 1.

Init dp[0][0] = poured.

Transition: if dp[i][j] > 1, it will overflow, the overflow part will be evenly distributed to dp[i+1][j], dp[i+1][j+1]

if dp[i][j] > 1:
dp[i+1][j] += (dp[i][j] – 1) / 2.0
dp[i+1][j + 1] += (dp[i][j] – 1) / 2.0

Answer: min(1.0, dp[query_row][query_index])

Solution 1:

C++

Time complexity: O(100*100)

Space complexity: O(100*100)

// Author: Huahua

// Running time: 22 ms

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kRows = 100;

vector<vector<double>> dp(kRows, vector<double>(kRows));

dp[0][0] = poured;

for (int i = 0; i < kRows - 1; ++i)

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

if (dp[i][j] > 1) {

dp[i + 1][j ] += (dp[i][j] - 1) / 2.0;

dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0;

dp[i][j] = 1.0;

}

return std::min(1.0, dp[query_row][query_glass]);

}

};

Pull

// Author: Huahua

// Running time: 27 ms

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kRows = 100;

vector<vector<double>> dp(kRows, vector<double>(kRows));

dp[0][0] = poured;

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

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

if (j > 0) dp[i][j] += max(0.0, (dp[i - 1][j - 1] - 1) / 2.0);

if (j < i) dp[i][j] += max(0.0, (dp[i - 1][j ] - 1) / 2.0);

}

return std::min(1.0, dp[query_row][query_glass]);

}

};

C++

Time complexity: O(rows * 100)

Space complexity: O(100)

Push

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kCols = 100;

vector<double> dp(kCols);

dp[0] = poured;

for (int i = 0; i < query_row; ++i) {

vector<double> tmp(kCols);

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

if (dp[j] > 1) {

tmp[j ] += (dp[j] - 1) / 2.0;

tmp[j + 1] += (dp[j] - 1) / 2.0;

}

dp.swap(tmp);

}

return std::min(1.0, dp[query_glass]);

}

};

Pull

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kCols = 100;

vector<double> dp(kCols);

dp[0] = poured;

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

vector<double> tmp(kCols);

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

if (j > 0) tmp[j] += max(0.0, (dp[j - 1] - 1) / 2.0);

if (j < i) tmp[j] += max(0.0, (dp[j ] - 1) / 2.0);

}

dp.swap(tmp);

}

return std::min(1.0, dp[query_glass]);

}

};

花花酱 LeetCode 797. All Paths From Source to Target

By zxi on March 10, 2018

题目大意：给你一个无环有向图，返回所有从节点0到节点n-1的路径。

Problem:

https://leetcode.com/problems/all-paths-from-source-to-target/description

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length – 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:

Input: [[1,2], [3], [3], []]

Output: [[0,1,3],[0,2,3]]

Explanation: The graph looks like this:

0--->1

| |

v v

2--->3

There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

Solution 1: DFS

Time complexity: O(n!)

Space complexity: O(n)

// Author: Huahua

// Running time: 85 ms

class Solution {

public:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {

vector<vector<int>> ans;

vector<int> path(1, 0);

dfs(graph, 0, graph.size() - 1, path, ans);

return ans;

}

private:

void dfs(const vector<vector<int>>& graph,

int cur, int dest, vector<int>& path, vector<vector<int>>& ans) {

if (cur == dest) {

ans.push_back(path);

return;

}

for (int next : graph[cur]) {

path.push_back(next);

dfs(graph, next, dest, path, ans);

path.pop_back();

}

};

“Cleaner” Version

class Solution {

public:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {

vector<vector<int>> ans;

vector<int> path{0};

dfs(graph, path, ans);

return ans;

}

private:

void dfs(const vector<vector<int>>& graph,

vector<int>& path, vector<vector<int>>& ans) {

if (path.back() == graph.size() - 1) {

ans.push_back(path);

return;

}

for (int next : graph[path.back()]) {

path.push_back(next);

dfs(graph, path, ans);

path.pop_back();

}

};

花花酱 LeetCode 495. Teemo Attacking

By zxi on March 8, 2018

题目大意：给你攻击的时间序列以及中毒的时长，求总共的中毒时间。

Problem:

https://leetcode.com/problems/teemo-attacking/description/

In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately. 
This poisoned status will last 2 seconds until the end of time point 2. 
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds. 
So you finally need to output 4.

Example 2:

Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned. 
This poisoned status will last 2 seconds until the end of time point 2. 
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status. 
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3. 
So you finally need to output 3.

Note:

You may assume the length of given time series array won’t exceed 10000.
You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

Idea: Running Process

Compare the current attack time with the last one, if span is more than duration, add duration to total, otherwise add (curr – last).

C++

// Author: Huahua

// Running time: 66 ms

class Solution {

public:

int findPoisonedDuration(vector<int>& t, int duration) {

if (t.empty()) return 0;

int total = 0;

for (int i = 1; i < t.size(); ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

};

Java

// Author: Huahua

// Running time: 9 ms

class Solution {

public int findPoisonedDuration(int[] t, int duration) {

if (t.length == 0) return 0;

int total = 0;

for (int i = 1; i < t.length; ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

Python3

"""

Author: Huahua

Running time: 64 ms (beats 100%)

"""

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

l = timeSeries[0]

total = 0

for t in timeSeries:

total += duration if t - l > duration else t - l

l = t

return total + duration

import numpy as np

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

d = np.diff(timeSeries)

d = np.clip(d, 0, duration)

return int(np.sum(d) + duration)

class Solution:

def findPoisonedDuration(self, t, duration):

return sum([min(c - l, duration) for l, c in zip(t, t[1:] + [1e9])])

花花酱 LeetCode 95. Unique Binary Search Trees II

By zxi on March 7, 2018

Problem

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

Idea: Recursion

for i in 1..n: pick i as root,
left subtrees can be generated in the same way for n_l = 1 … i – 1,
right subtrees can be generated in the same way for n_r = i + 1, …, n
def gen(s, e):
return [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)

# of trees:

n = 0: 1
n = 1: 1
n = 2: 2
n = 3: 5
n = 4: 14
n = 5: 42
n = 6: 132
…
Trees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)

Time complexity: O(3^n)

Space complexity: O(3^n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<TreeNode*> generateTrees(int n) {

if (n == 0) return {};

const auto& ans = generateTrees(1, n);

cout << ans.size() << endl;

return ans;

}

private:

vector<TreeNode*> generateTrees(int l, int r) {

if (l > r) return { nullptr };

vector<TreeNode*> ans;

for (int i = l; i <= r; ++i)

for (TreeNode* left : generateTrees(l, i - 1))

for (TreeNode* right : generateTrees(i + 1, r)) {

ans.push_back(new TreeNode(i));

ans.back()->left = left;

ans.back()->right = right;

}

return ans;

}

};

Java

// Author: Huahua 4 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

return generateTrees(1, n);

}

private List<TreeNode> generateTrees(int l, int r) {

List<TreeNode> ans = new ArrayList<>();

if (l > r) {

ans.add(null);

return ans;

}

for (int i = l; i <= r; ++i)

for (TreeNode left : generateTrees(l, i - 1))

for (TreeNode right: generateTrees(i + 1, r)) {

TreeNode root = new TreeNode(i);

root.left = left;

root.right = right;

ans.add(root);

}

return ans;

}

Python 3

"""

Author: Huahua

Running time: 84 ms

"""

class Solution:

def generateTrees(self, n):

def newTree(x, l, r):

t = TreeNode(x)

t.left = l

t.right = r

return t

def gen(s, e):

return [newTree(i, l, r) for i in range(s, e + 1) for l in gen(s, i - 1) for r in gen(i + 1, e)] or [None]

return gen(1, n) if n > 0 else []

Solution 2: DP

Java

// Author: Huahua, 3 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

List<TreeNode>[] dp = new List[n + 1];

dp[0] = new ArrayList<TreeNode>();

dp[0].add(null);

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

dp[i] = new ArrayList<TreeNode>();

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

for (TreeNode left : dp[j])

for (TreeNode right: dp[i - j - 1]) {

TreeNode root = new TreeNode(j + 1);

root.left = left;

root.right = clone(right, j + 1);

dp[i].add(root);

}

return dp[n];

}

private TreeNode clone(TreeNode root, int delta) {

if (root == null) return root;

TreeNode node = new TreeNode(root.val + delta);

node.left = clone(root.left, delta);

node.right = clone(root.right, delta);

return node;

}

Posts tagged as “medium”

花花酱 LeetCode 275. H-Index II

花花酱 LeetCode 799. Champagne Tower

花花酱 LeetCode 797. All Paths From Source to Target

花花酱 LeetCode 495. Teemo Attacking

花花酱 LeetCode 95. Unique Binary Search Trees II

Problem

Idea: Recursion

C++

Java

Python 3

Solution 2: DP

Java

Related Problems