Posts published in “Data Structure”

花花酱 LeetCode 225. Implement Stack using Queues

By zxi on March 13, 2018

题目大意：用队列来实现栈。

Problem:

https://leetcode.com/problems/implement-stack-using-queues/description/

Implement the following operations of a stack using queues.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
empty() — Return whether the stack is empty.

Notes:

You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Idea:

Using a single queue, for every push, shift the queue (n – 1) times such that the last element becomes the first element in the queue.

e.g.

push(1): q: [1]

push(2): q: [1, 2] -> [2, 1]

push(3): q: [2, 1, 3] -> [1, 3, 2] -> [3, 2, 1]

push(4): q: [3, 2, 1, 4] -> [2, 1, 4, 3] -> [1, 4, 3, 2] -> [4, 3, 2, 1]

Solution:

Time complexity:

Push: O(n)

Pop/top/empty: O(1)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class MyStack {

public:

/** Initialize your data structure here. */

MyStack() {}

/** Push element x onto stack. */

void push(int x) {

q_.push(x);

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

q_.push(q_.front());

q_.pop();

}

/** Removes the element on top of the stack and returns that element. */

int pop() {

int top = q_.front();

q_.pop();

return top;

}

/** Get the top element. */

int top() {

return q_.front();

}

/** Returns whether the stack is empty. */

bool empty() {

return q_.empty();

}

private:

queue<int> q_;

};

花花酱 LeetCode 239. Sliding Window Maximum

By zxi on January 24, 2018

题目大意：给你一个数组，让你输出移动窗口的最大值。

Problem:

https://leetcode.com/problems/sliding-window-maximum/

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Idea:

Solution 1: Brute Force

Time complexity: O((n – k + 1) * k)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 180 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

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

ans.push_back(*max_element(nums.begin() + i - k + 1, nums.begin() + i + 1));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 80 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return new int[0];

int[] ans = new int[nums.length - k + 1];

for (int i = k - 1; i < nums.length; ++i) {

int maxNum = nums[i];

for (int j = 1; j < k; ++j)

if (nums[i - j] > maxNum) maxNum = nums[i - j];

ans[i - k + 1] = maxNum;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 1044 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

if not nums: return []

return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Solution 2: BST

Time complexity: O((n – k + 1) * logk)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

if (nums.empty()) return ans;

multiset<int> window(nums.begin(), nums.begin() + k - 1);

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

window.insert(nums[i]);

ans.push_back(*window.rbegin());

if (i - k + 1 >= 0)

window.erase(window.equal_range(nums[i - k + 1]).first);

}

return ans;

}

};

Solution 3: Monotonic Queue

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 70 ms

class MonotonicQueue {

public:

void push(int e) {

while(!data_.empty() && e > data_.back()) data_.pop_back();

data_.push_back(e);

}

void pop() {

data_.pop_front();

}

int max() const { return data_.front(); }

private:

deque<int> data_;

};

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

MonotonicQueue q;

vector<int> ans;

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

q.push(nums[i]);

if (i - k + 1 >= 0) {

ans.push_back(q.max());

if (nums[i - k + 1] == q.max()) q.pop();

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> index;

vector<int> ans;

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

while (!index.empty() && nums[i] >= nums[index.back()]) index.pop_back();

index.push_back(i);

if (i - k + 1 >= 0) ans.push_back(nums[index.front()]);

if (i - k + 1 >= index.front()) index.pop_front();

}

return ans;

}

};

C++ V3

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> q;

vector<int> ans;

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

while (!q.empty() && nums[i] > q.back()) q.pop_back();

q.push_back(nums[i]);

const int s = i - k + 1;

if (s < 0) continue;

ans.push_back(q.front());

if (nums[s] == q.front()) q.pop_front();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 19 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return nums;

int[] ans = new int[nums.length - k + 1];

Deque<Integer> indices = new LinkedList<>();

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

while (indices.size() > 0 && nums[i] >= nums[indices.getLast()])

indices.removeLast();

indices.addLast(i);

if (i - k + 1 >= 0) ans[i - k + 1] = nums[indices.getFirst()];

if (i - k + 1 >= indices.getFirst()) indices.removeFirst();

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 238 ms

"""

class MaxQueue:

def __init__(self):

self.q_ = collections.deque()

def push(self, e):

while self.q_ and e > self.q_[-1]: self.q_.pop()

self.q_.append(e)

def pop(self):

self.q_.popleft()

def max(self):

return self.q_[0]

class Solution:

def maxSlidingWindow(self, nums, k):

q = MaxQueue()

ans = []

for i in range(len(nums)):

q.push(nums[i])

if i >= k - 1:

ans.append(q.max())

if nums[i - k + 1] == q.max(): q.pop()

return ans

Python3 V2

"""

Author: Huahua

Running time: 193 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

indices = collections.deque()

ans = []

for i in range(len(nums)):

while indices and nums[i] >= nums[indices[-1]]: indices.pop()

indices.append(i)

if i >= k - 1: ans.append(nums[indices[0]])

if i - k + 1 == indices[0]: indices.popleft()

return ans

花花酱 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 Disjoint set / Union Find Forest SP1

By zxi on November 29, 2017

Disjoint-set/Union-find Forest

Find(x): find the root/cluster-id of x

Union(x, y): merge two clusters

Check whether two elements are in the same set or not in O(1)*.

Find: O(ɑ(n))* ≈ O(1)

Union: O(ɑ(n))* ≈ O(1)

Space: O(n)

Without optimization: Find: O(n)

Two key optimizations:

Path compression: make tree flat
Union by rank: merge low rank tree to high rank one

*: amortized

ɑ(.): inverse Ackermann function

Implementations:

C++

// Author: Huahua

class UnionFindSet {

public:

UnionFindSet(int n) {

ranks_ = vector<int>(n + 1, 0);

parents_ = vector<int>(n + 1, 0);

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

parents_[i] = i;

}

// Merge sets that contains u and v.

// Return true if merged, false if u and v are already in one set.

bool Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

// Meger low rank tree into high rank tree

if (ranks_[pv] < ranks_[pu])

parents_[pv] = pu;

else if (ranks_[pu] < ranks_[pv])

parents_[pu] = pv;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

// Get the root of u.

int Find(int u) {

// Compress the path during traversal

if (u != parents_[u])

parents_[u] = Find(parents_[u]);

return parents_[u];

}

private:

vector<int> parents_;

vector<int> ranks_;

};

Java

// Author: Huahua

class UnionFindSet {

private int[] parents_;

private int[] ranks_;

public UnionFindSet(int n) {

parents_ = new int[n + 1];

ranks_ = new int[n + 1];

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

parents_[i] = i;

ranks_[i] = 1;

}

public boolean Union(int u, int v) {

int pu = Find(u);

int pv = Find(v);

if (pu == pv) return false;

if (ranks_[pv] > ranks_[pu])

parents_[pu] = pv;

else if (ranks_[pu] > ranks_[pv])

parents_[pv] = pu;

else {

parents_[pv] = pu;

ranks_[pu] += 1;

}

return true;

}

public int Find(int u) {

while (parents_[u] != u) {

parents_[u] = parents_[parents_[u]];

u = parents_[u];

}

return u;

}

Python

"""

Author: Huahua

"""

class UnionFindSet:

def __init__(self, n):

self._parents = [i for i in range(n + 1)]

self._ranks = [1 for i in range(n + 1)]

def find(self, u):

while u != self._parents[u]:

self._parents[u] = self._parents[self._parents[u]]

u = self._parents[u]

return u

def union(self, u, v):

pu, pv = self.find(u), self.find(v)

if pu == pv: return False

if self._ranks[pu] < self._ranks[pv]:

self._parents[pu] = pv

elif self._ranks[pu] > self._ranks[pv]:

self._parents[pv] = pu

else:

self._parents[pv] = pu

self._ranks[pu] += 1

return True

Union-Find Problems

References

花花酱 LeetCode 715. Range Module

By zxi on October 22, 2017

Problem:

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example 1:

addRange(10, 20): null

removeRange(14, 16): null

queryRange(10, 14): true (Every number in [10, 14) is being tracked)

queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)

queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Note:

A half open interval [left, right) denotes all real numbers left <= x < right.
0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
The total number of calls to addRange in a single test case is at most 1000.
The total number of calls to queryRange in a single test case is at most 5000.
The total number of calls to removeRange in a single test case is at most 1000.

Idea:

map / ordered ranges

Solution:

C++ / vector

// Author: Huahua

// Runtime: 276 ms

class RangeModule {

public:

RangeModule() {}

void addRange(int left, int right) {

vector<pair<int, int>> new_ranges;

bool inserted = false;

for (const auto& kv : ranges_) {

if (kv.first > right && !inserted) {

new_ranges.emplace_back(left, right);

inserted = true;

}

if (kv.second < left || kv.first > right) {

new_ranges.push_back(kv);

} else {

left = min(left, kv.first);

right = max(right, kv.second);

}

if (!inserted) new_ranges.emplace_back(left, right);

ranges_.swap(new_ranges);

}

bool queryRange(int left, int right) {

const int n = ranges_.size();

int l = 0;

int r = n - 1;

// Binary search

while (l <= r) {

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

if (ranges_[m].second < left)

l = m + 1;

else if (ranges_[m].first > right)

r = m - 1;

else

return ranges_[m].first <= left && ranges_[m].second >= right;

}

return false;

}

void removeRange(int left, int right) {

vector<pair<int, int>> new_ranges;

for (const auto& kv : ranges_) {

if (kv.second <= left || kv.first >= right) {

new_ranges.push_back(kv);

} else {

if (kv.first < left)

new_ranges.emplace_back(kv.first, left);

if (kv.second > right)

new_ranges.emplace_back(right, kv.second);

}

ranges_.swap(new_ranges);

}

vector<pair<int, int>> ranges_;

};

C++ / map

// Author: Huahua

// Runtime: 199 ms

class RangeModule {

public:

RangeModule() {}

void addRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// At least one range overlapping with [left, right)

if (l != r) {

// Merge intervals into [left, right)

auto last = r; --last;

left = min(left, l->first);

right = max(right, last->second);

// Remove all overlapped ranges

ranges_.erase(l, r);

}

// Add a new/merged range

ranges_[left] = right;

}

bool queryRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// No overlapping range

if (l == r) return false;

return l->first <= left && l->second >= right;

}

void removeRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// No overlapping range

if (l == r) return;

auto last = r; --last;

int start = min(left, l->first);

int end = max(right, last->second);

// Delete overlapping ranges

ranges_.erase(l, r);

if (start < left) ranges_[start] = left;

if (end > right) ranges_[right] = end;

}

private:

typedef map<int, int>::iterator IT;

map<int, int> ranges_;

void getOverlapRanges(int left, int right, IT& l, IT& r) {

l = ranges_.upper_bound(left);

r = ranges_.upper_bound(right);

if (l != ranges_.begin())

if ((--l)->second < left) l++;

}

};

Related Problems: