花花酱 LeetCode 755. Pour Water

By zxi on January 7, 2018

题目大意：

给你地形的高度，有V单位的水会从K位置落下，问你稳定之后水位的高度。

Problem:

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it’s current position.

Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.

We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.

Idea:

Solution 1: Simulation

Time complexity: O(V*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<int> pourWater(vector<int>& heights, int V, int K) {

while (V--) drop(heights, K);

return heights;

}

private:

void drop(vector<int>& heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.size()

&& heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

};

Java

// Author: Huahua

// Running time: 12 ms

class Solution {

public int[] pourWater(int[] heights, int V, int K) {

while (V-- > 0) {

dropWater(heights, K);

}

return heights;

}

private void dropWater(int[] heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.length && heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

Python3

"""

Author: Huahua

Running time: 207 ms

"""

class Solution:

def pourWater(self, heights, V, K):

def drop(h, K):

best = K

for d in (-1, 1):

i = K + d

while i >= 0 and i < len(h) and h[i] <= h[i - d]:

if h[i] < h[best]:

best = i

i += d

if best != K:

break

heights[best] += 1

for _ in range(V):

drop(heights, K)

return heights

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

By zxi on January 6, 2018

题目大意：给你每天的股价，没有交易次数限制，但是卖出后要休息一天才能再买进。问你最大收益是多少？

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]

maxProfit = 3

transactions = [buy, sell, cooldown, buy, sell]

Idea:

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int sold = 0;

int rest = 0;

int hold = INT_MIN;

for (const int price : prices) {

int prev_sold = sold;

sold = hold + price;

hold = max(hold, rest - price);

rest = max(rest, prev_sold);

}

return max(rest, sold);

}

};

Related Problems:

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

花花酱 Fenwick Tree / Binary Indexed Tree / 树状数组 SP3

By zxi on January 3, 2018

本期节目中我们介绍了Fenwick Tree/Binary Indexed Tree/树状数组的原理和实现以及它在leetcode中的应用。
In this episode, we will introduce Fenwick Tree/Binary Indexed Tree, its idea and implementation and show its applications in leetcode.

Fenwick Tree is mainly designed for solving the single point update range sum problems. e.g. what’s the sum between i-th and j-th element while the values of the elements are mutable.

Init the tree (include building all prefix sums) takes O(nlogn)

Update the value of an element takes O(logn)

Query the range sum takes O(logn)

Space complexity: O(n)

Applications:

Implementation:

C++

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) {

return x & (-x);

}

vector<int> sums_;

};

Java

class FenwickTree {

int sums_[];

public FenwickTree(int n) {

sums_ = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums_.length) {

sums_[i] += delta;

i += i & -i;

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= i & -i;

}

return sum;

}

Python3

class FenwickTree:

def __init__(self, n):

self._sums = [0 for _ in range(n + 1)]

def update(self, i, delta):

while i < len(self._sums):

self._sums[i] += delta

i += i & -i

def query(self, i):

s = 0

while i > 0:

s += self._sums[i]

i -= i & -i

return s

Applications

花花酱 LeetCode 315. Count of Smaller Numbers After Self

By zxi on January 3, 2018

题目大意：给你一个数组，对于数组中的每个元素，返回一共有多少在它之后的元素比它小。

Problem:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).

To the right of 2 there is only 1 smaller element (1).

To the right of 6 there is 1 smaller element (1).

To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Idea:

Fenwick Tree / Binary Indexed Tree

BST

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

// Author: Huahua

// Runnning time: 32 ms

// Time complexity: O(nlogn)

// Space complexity: O(k), k is the number unique elements

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) { return x & (-x); }

vector<int> sums_;

};

class Solution {

public:

vector<int> countSmaller(vector<int>& nums) {

// Sort the unique numbers

set<int> sorted(nums.begin(), nums.end());

// Map the number to its rank

unordered_map<int, int> ranks;

int rank = 0;

for (const int num : sorted)

ranks[num] = ++rank;

vector<int> ans;

FenwickTree tree(ranks.size());

// Scan the numbers in reversed order

for (int i = nums.size() - 1; i >= 0; --i) {

// Chechk how many numbers are smaller than the current number.

ans.push_back(tree.query(ranks[nums[i]] - 1));

// Increse the count of the rank of current number.

tree.update(ranks[nums[i]], 1);

}

std::reverse(ans.begin(), ans.end());

return ans;

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

private static int lowbit(int x) { return x & (-x); }

class FenwickTree {

private int[] sums;

public FenwickTree(int n) {

sums = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums.length) {

sums[i] += delta;

i += lowbit(i);

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums[i];

i -= lowbit(i);

}

return sum;

}

};

public List<Integer> countSmaller(int[] nums) {

int[] sorted = Arrays.copyOf(nums, nums.length);

Arrays.sort(sorted);

Map<Integer, Integer> ranks = new HashMap<>();

int rank = 0;

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

if (i == 0 || sorted[i] != sorted[i - 1])

ranks.put(sorted[i], ++rank);

FenwickTree tree = new FenwickTree(ranks.size());

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

for (int i = nums.length - 1; i >= 0; --i) {

int sum = tree.query(ranks.get(nums[i]) - 1);

ans.add(tree.query(ranks.get(nums[i]) - 1));

tree.update(ranks.get(nums[i]), 1);

}

Collections.reverse(ans);

return ans;

}

Solution 2: BST

C++

// Author: Huahua

// Running time: 26 ms

struct BSTNode {

int val;

int count;

int left_count;

BSTNode* left;

BSTNode* right;

BSTNode(int val): val(val), count(1), left_count(0), left{nullptr}, right{nullptr} {}

~BSTNode() { delete left; delete right; }

int less_or_equal() const { return count + left_count; }

};

class Solution {

public:

vector<int> countSmaller(vector<int>& nums) {

if (nums.empty()) return {};

std::reverse(nums.begin(), nums.end());

std::unique_ptr<BSTNode> root(new BSTNode(nums[0]));

vector<int> ans{0};

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

ans.push_back(insert(root.get(), nums[i]));

std::reverse(ans.begin(), ans.end());

return ans;

}

private:

// Returns the number of elements smaller than val under root.

int insert(BSTNode* root, int val) {

if (root->val == val) {

++root->count;

return root->left_count;

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

++root->left_count;

if (root->left == nullptr) {

root->left = new BSTNode(val);

return 0;

}

return insert(root->left, val);

} else {

if (root->right == nullptr) {

root->right = new BSTNode(val);

return root->less_or_equal();

}

return root->less_or_equal() + insert(root->right, val);

}

};

Java

// Author: Huahua

// Running time: 10 ms

class Solution {

class Node {

int val;

int count;

int left_count;

Node left;

Node right;

public Node(int val) { this.val = val; this.count = 1; }

public int less_or_equal() { return count + left_count; }

}

public List<Integer> countSmaller(int[] nums) {

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

if (nums.length == 0) return ans;

int n = nums.length;

Node root = new Node(nums[n - 1]);

ans.add(0);

for (int i = n - 2; i >= 0; --i)

ans.add(insert(root, nums[i]));

Collections.reverse(ans);

return ans;

}

private int insert(Node root, int val) {

if (root.val == val) {

++root.count;

return root.left_count;

} else if (val < root.val) {

++root.left_count;

if (root.left == null) {

root.left = new Node(val);

return 0;

}

return insert(root.left, val);

} else {

if (root.right == null) {

root.right = new Node(val);

return root.less_or_equal();

}

return root.less_or_equal() + insert(root.right, val);

}

花花酱 307. Range Sum Query – Mutable

By zxi on January 3, 2018

题目大意：给你一个数组，让你求一个范围之内所有元素的和，数组元素可以更改。

Problem:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9

update(1, 2)

sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Idea:

Fenwick Tree

Solution:

C++

Time complexity:

init O(nlogn)

query: O(logn)

update: O(logn)

C++

// Author: Huahua

// Running time: 83 ms

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) { return x & (-x); }

vector<int> sums_;

};

class NumArray {

public:

NumArray(vector<int> nums): nums_(std::move(nums)), tree_(nums_.size()) {

for (int i = 0; i < nums_.size(); ++i)

tree_.update(i + 1, nums_[i]);

}

void update(int i, int val) {

tree_.update(i + 1, val - nums_[i]);

nums_[i] = val;

}

int sumRange(int i, int j) {

return tree_.query(j + 1) - tree_.query(i);

}

private:

vector<int> nums_;

FenwickTree tree_;

};

Java

// Author: Huahua

// Running time: 130 ms

class NumArray {

FenwickTree tree_;

int[] nums_;

public NumArray(int[] nums) {

nums_ = nums;

tree_ = new FenwickTree(nums.length);

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

tree_.update(i + 1, nums[i]);

}

public void update(int i, int val) {

tree_.update(i + 1, val - nums_[i]);

nums_[i] = val;

}

public int sumRange(int i, int j) {

return tree_.query(j + 1) - tree_.query(i);

}

class FenwickTree {

int sums_[];

public FenwickTree(int n) {

sums_ = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums_.length) {

sums_[i] += delta;

i += i & -i;

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= i & -i;

}

return sum;

}

Python3

"""

Author: Huahua

Running time: 192 ms (< 90.00%)

"""

class FenwickTree:

def __init__(self, n):

self._sums = [0 for _ in range(n + 1)]

def update(self, i, delta):

while i < len(self._sums):

self._sums[i] += delta

i += i & -i

def query(self, i):

s = 0

while i > 0:

s += self._sums[i]

i -= i & -i

return s

class NumArray:

def __init__(self, nums):

self._nums = nums

self._tree = FenwickTree(len(nums))

for i in range(len(nums)):

self._tree.update(i + 1, nums[i])

def update(self, i, val):

self._tree.update(i + 1, val - self._nums[i])

self._nums[i] = val

def sumRange(self, i, j):

return self._tree.query(j + 1) - self._tree.query(i)

Solution 2: Segment Tree

C++

// Author: Huahua, running time: 24 ms

class SegmentTreeNode {

public:

SegmentTreeNode(int start, int end, int sum,

SegmentTreeNode* left = nullptr,

SegmentTreeNode* right = nullptr):

start(start),

end(end),

sum(sum),

left(left),

right(right){}

SegmentTreeNode(const SegmentTreeNode&) = delete;

SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;

~SegmentTreeNode() {

delete left;

delete right;

left = right = nullptr;

}

int start;

int end;

int sum;

SegmentTreeNode* left;

SegmentTreeNode* right;

};

class NumArray {

public:

NumArray(vector<int> nums) {

nums_.swap(nums);

if (!nums_.empty())

root_.reset(buildTree(0, nums_.size() - 1));

}

void update(int i, int val) {

updateTree(root_.get(), i, val);

}

int sumRange(int i, int j) {

return sumRange(root_.get(), i, j);

}

private:

vector<int> nums_;

std::unique_ptr<SegmentTreeNode> root_;

SegmentTreeNode* buildTree(int start, int end) {

if (start == end) {

return new SegmentTreeNode(start, end, nums_[start]);

}

int mid = start + (end - start) / 2;

auto left = buildTree(start, mid);

auto right = buildTree(mid + 1, end);

auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);

return node;

}

void updateTree(SegmentTreeNode* root, int i, int val) {

if (root->start == i && root->end == i) {

root->sum = val;

return;

}

int mid = root->start + (root->end - root->start) / 2;

if (i <= mid) {

updateTree(root->left, i, val);

} else {

updateTree(root->right, i, val);

}

root->sum = root->left->sum + root->right->sum;

}

int sumRange(SegmentTreeNode* root, int i, int j) {

if (i == root->start && j == root->end) {

return root->sum;

}

int mid = root->start + (root->end - root->start) / 2;

if (j <= mid) {

return sumRange(root->left, i, j);

} else if (i > mid) {

return sumRange(root->right, i, j);

} else {

return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);

}

};

Huahua's Tech Road

花花酱 LeetCode 755. Pour Water

Solution 1: Simulation

C++

Java

Python3

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

花花酱 Fenwick Tree / Binary Indexed Tree / 树状数组 SP3

C++

Java

Python3

Applications

花花酱 LeetCode 315. Count of Smaller Numbers After Self

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

Java

Solution 2: BST

C++

Java

花花酱 307. Range Sum Query – Mutable

C++

Java

Python3

Solution 2: Segment Tree

C++