Posts published in January 2018

花花酱 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);

}

};

花花酱 LeetCode 322. Coin Change

By zxi on January 2, 2018

题目大意：给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个。

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

// Author: Huahua

// Running time: 189 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (auto coin : coins) {

for (int i = amount - coin; i >= 0; --i)

if (dp[i] != INT_MAX)

for (int k = 1; k * coin + i <= amount; ++k)

dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// dp[i] = min coins to make up to amount i

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (int coin : coins) {

for (int i = coin; i <= amount; ++i)

if (dp[i - coin] != INT_MAX)

dp[i] = min(dp[i], dp[i - coin] + 1);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Python3

"""

Author: Huahua

Running time: 632 ms beats 90.27%

"""

class Solution:

def coinChange(self, coins, amount):

INVALID = 2**32

dp = [INVALID] * (amount + 1)

dp[0] = 0

for coin in coins:

for i in range(coin, amount + 1):

if dp[i - coin] >= dp[i]: continue

dp[i] = dp[i - coin] + 1

return -1 if dp[amount] == INVALID else dp[amount]

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// Sort coins in desending order

std::sort(coins.rbegin(), coins.rend());

int ans = INT_MAX;

coinChange(coins, 0, amount, 0, ans);

return ans == INT_MAX ? -1 : ans;

}

private:

void coinChange(const vector<int>& coins,

int s, int amount, int count, int& ans) {

if (amount == 0) {

ans = min(ans, count);

return;

}

if (s == coins.size()) return;

const int coin = coins[s];

for (int k = amount / coin; k >= 0 && count + k < ans; k--)

coinChange(coins, s + 1, amount - k * coin, count + k, ans);

}

};

Python3

"""

Author: Huahua

Running time: 200ms

"""

class Solution:

def coinChange(self, coins, amount):

coins.sort(reverse=True)

INVALID = 10**10

self.ans = INVALID

def dfs(s, amount, count):

if amount == 0:

self.ans = count

return

if s == len(coins): return

coin = coins[s]

for k in range(amount // coin, -1, -1):

if count + k >= self.ans: break

dfs(s + 1, amount - k * coin, count + k)

dfs(0, amount, 0)

return -1 if self.ans == INVALID else self.ans

花花酱 LeetCode 754. Reach a Number

By zxi on January 1, 2018

题目大意：第i时刻可以移动+i,-i单位距离。初始在原点，问最少对少时间可以移动到target坐标。

Problem:

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3

Output: 2

Explanation:

On the first move we step from 0 to 1.

On the second step we step from 1 to 3.

Example 2:

Input: target = 2

Output: 3

Explanation:

On the first move we step from 0 to 1.

On the second move we step from 1 to -1.

On the third move we step from -1 to 2.

Note:

target will be a non-zero integer in the range [-10^9, 10^9].

Idea:

Math

Time complexity: O(sqrt(target))

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int reachNumber(int target) {

target = std::abs(target);

int k = 0;

int sum = 0;

while (sum < target) sum += (++k);

const int d = sum - target;

if (d % 2 == 0) return k;

return k + 1 + (k % 2);

}

};

O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int reachNumber(int target) {

target = std::abs(target);

int k = sqrt(target * 2);

while (sum(k) < target) ++k;

int d = sum(k) - target;

if (d % 2 == 0) return k;

return k + 1 + (k % 2);

}

private:

int sum(int k) {

return k * (k + 1) / 2;

}

};