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

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

By zxi on January 17, 2018

题目大意：求给定范围内，数的二进制形式中1的个数为素数个的数字的个数。

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10

Output: 4

Explanation:

6 -> 110 (2 set bits, 2 is prime)

7 -> 111 (3 set bits, 3 is prime)

9 -> 1001 (2 set bits , 2 is prime)

10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15

Output: 5

Explanation:

10 -> 1010 (2 set bits, 2 is prime)

11 -> 1011 (3 set bits, 3 is prime)

12 -> 1100 (2 set bits, 2 is prime)

13 -> 1101 (3 set bits, 3 is prime)

14 -> 1110 (3 set bits, 3 is prime)

15 -> 1111 (4 set bits, 4 is not prime)

Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

Solution 1: Brute Force

C++

// Author: Huahua

// Running time: 22 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private:

bool isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

int bits(int n) {

int s = 0;

while (n) {

s += n & 1;

n >>= 1;

}

return s;

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 30 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

vector<int> p(20, 0);

p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = p[19] = 1;

for (int n = L; n <= R; ++n)

if (p[__builtin_popcountll(n)]) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

constexpr int magic = 665772;

int ans = 0;

for (int n = L; n <= R; ++n)

if (magic & (1 << __builtin_popcountll(n))) ++ans;

return ans;

}

};

Java

// Author: Huahua

// Running time: 39 ms

class Solution {

public int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private boolean isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= (int)Math.sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

private int bits(int n) {

int s = 0;

while (n != 0) {

s += n & 1;

n >>= 1;

}

return s;

}

Python2

"""

Author: Huahua

Running time: 1618 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def isPrime(n):

if n <= 1: return False

if n == 2: return True

for i in range(2, int(math.sqrt(n)) + 1):

if n % i == 0: return False

return True

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

ans = 0

for n in range(L, R + 1):

if isPrime(bits(n)): ans += 1

return ans

Python2

"""

Author: Huahua

Running time: 1163 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])

ans = 0

for n in range(L, R + 1):

if bits(n) in primes: ans += 1

return ans

"""

Author: Huahua

Running time: 667 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

n &= n - 1;

s += 1

return s

ans = 0

while L <= R:

if (665772 >> bits(L)) & 1 > 0: ans += 1

L += 1

return ans

花花酱 LeetCode. 69 Sqrt(x)

By zxi on January 16, 2018

题目大意：让你实现开根号函数，只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

1 2	Input: 4 Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842...

Solution 1: Brute force

Time complexity: sqrt(x)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (long long s = 1; s <= x; ++s)

if (s * s > x) return s - 1;

return -1;

}

};

C++ div

// Author: Huahua

// Running time: 162 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (int s = 1; s <= x; ++s)

if (s > x / s) return s - 1;

return -1;

}

};

Java

// Author: Huahua

// Running time: 71 ms

class Solution {

public int mySqrt(int x) {

if (x <= 1) return x;

for (long s = 1; s <= x; ++s)

if (s * s > x) return (int)s - 1;

return -1;

}

Python3 TLE

"""

Author: Huahua

TLE: 602 / 1017 test cases passed.

"""

class Solution:

def mySqrt(self, x):

if x <= 1: return x

s = 1

while True:

if s*s > x: return s - 1

s += 1

return -1

Solution 2: Binary search

Time complexity: O(logn)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int mySqrt(int x) {

long l = 1;

long r = static_cast<long>(x) + 1;

while (l < r) {

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

if (m * m > x) {

r = m;

} else {

l = m + 1;

}

// l: smallest number such that l * l > x

return l - 1;

}

};

Java

// Author: Huahua

// Running time: 47 ms

class Solution {

public int mySqrt(int x) {

int l = 1;

int r = x;

while (l <= r) {

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

if (m > x / m) {

r = m - 1;

} else {

l = m + 1;

}

return r;

}

Python3

"""

Author: Huahua

Running time: 119 ms

"""

class Solution:

def mySqrt(self, a):

l = 1

r = a

while l <= r:

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

if m * m > a:

r = m - 1

else:

l = m + 1

return r;

Solution 3: Newton’s method

C++ / float

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int mySqrt(int a) {

constexpr double epsilon = 1e-2;

double x = a;

while (x * x - a > epsilon) {

x = (x + a / x) / 2.0;

}

return x;

}

};

C++ / int

// Author: Huahua

// Running time: 27 ms

class Solution {

public:

int mySqrt(int a) {

// f(x) = x^2 - a, find root of f(x)

// Newton's method

// f'(x) = 2x

// x' = x - f(x) / f'(x) = x - (1/2*x - a/(2*x))

// = (x + a / x) / 2

int x = a;

while (x > a / x)

x = (x + a / x) / 2;

return x;

}

};

Java

// Author: Huahua

// Running time: 44 ms

class Solution {

public int mySqrt(int a) {

long x = a;

while (x * x > a)

x = (x + a / x) / 2;

return (int)x;

}

Python3

"""

Author: Huahua

Running time: 100 ms

"""

class Solution:

def mySqrt(self, a):

x = a

while x * x > a:

x = (x + a // x) // 2

return x

花花酱 LeetCode 494. Target Sum

By zxi on January 9, 2018

题目大意：给你一串数字，你可以在每个数字前放置+或-，问有多少种方法可以使得表达式的值等于target。You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.

Output: 5

Explanation:

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

Idea: DP

Solution 1: DP

Time complexity: O(n*sum)

Space complexity: O(n*sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S) return 0;

const int offset = sum;

// ways[i][j] means total ways to sum up to (j - offset) using nums[0] ~ nums[i - 1].

vector<vector<int>> ways(n + 1, vector<int>(sum + offset + 1, 0));

ways[0][offset] = 1;

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

for (int j = nums[i]; j < 2 * sum + 1 - nums[i]; ++j)

if (ways[i][j]) {

ways[i + 1][j + nums[i]] += ways[i][j];

ways[i + 1][j - nums[i]] += ways[i][j];

}

return ways.back()[S + offset];

}

};

C++ SC O(n)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

for (int i = num; i < kMaxN - num; ++i)

if (ways[i]) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < S) return 0;

final int kOffset = sum;

final int kMaxN = sum * 2 + 1;

int[] ways = new int[kMaxN];

ways[kOffset] = 1;

for (final int num : nums) {

int[] tmp = new int[kMaxN];

for (int i = num; i < kMaxN - num; ++i) {

tmp[i + num] += ways[i];

tmp[i - num] += ways[i];

}

ways = tmp;

}

return ways[S + kOffset];

}

C++ / V2

// Author: Huahua

// Running time: 17 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

const int kOffset = sum;

const int kMaxN = sum * 2 + 1;

vector<int> ways(kMaxN, 0);

ways[kOffset] = 1;

for (int num : nums) {

vector<int> tmp(kMaxN, 0);

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

if (i + num < kMaxN) tmp[i] += ways[i + num];

if (i - num >= 0) tmp[i] += ways[i - num];

}

std::swap(ways, tmp);

}

return ways[S + kOffset];

}

};

Solution 2: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 422 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < std::abs(S)) return 0;

int ans = 0;

dfs(nums, 0, S, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int d, int S, int& ans) {

if (d == nums.size()) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d], ans);

dfs(nums, d + 1, S + nums[d], ans);

}

};

Java

// Author: Huahua

// Running time: 615 ms

class Solution {

private int ans;

public int findTargetSumWays(int[] nums, int S) {

int sum = 0;

for (final int num : nums)

sum += num;

if (sum < Math.abs(S)) return 0;

ans = 0;

dfs(nums, 0, S);

return ans;

}

private void dfs(int[] nums, int d, int S) {

if (d == nums.length) {

if (S == 0) ++ans;

return;

}

dfs(nums, d + 1, S - nums[d]);

dfs(nums, d + 1, S + nums[d]);

}

Solution 3: Subset sum

Time complexity: O(n*sum)

Space complexity: O(sum)

C++ w/ copy

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

vector<int> dp(target + 1, 0);

dp[0] = 1;

for (int num : nums) {

vector<int> tmp(dp);

for (int j = 0; j <= target - num; ++j)

tmp[j + num] += dp[j];

std::swap(dp, tmp);

}

return dp[target];

}

};

C++ w/o copy

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int findTargetSumWays(vector<int>& nums, int S) {

S = std::abs(S);

const int n = nums.size();

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum < S || (S + sum) % 2 != 0) return 0;

const int target = (S + sum) / 2;

vector<int> dp(target + 1, 0);

dp[0] = 1;

for (int num : nums)

for (int j = target; j >= num; --j)

dp[j] += dp[j - num];

return dp[target];

}

};

花花酱 LeetCode 759. Employee Free Time

By zxi on January 8, 2018

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Output: [[3,4]]

Explanation:

There are a total of three employees, and all common

free time intervals would be [-inf, 1], [3, 4], [10, inf].

We discard any intervals that contain inf as they aren't finite.

Example 2:

1 2	Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

schedule and schedule[i] are lists with lengths in range [1, 50].
0 <= schedule[i].start < schedule[i].end <= 10^8.

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

// Author: Huahua

// Running time: 81 ms

class Solution {

public:

vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

vector<Interval> all;

for (const auto intervals : schedule)

all.insert(all.end(), intervals.begin(), intervals.end());

std::sort(all.begin(), all.end(),

[](const Interval& a, const Interval& b){

return a.start < b.start;

});

vector<Interval> ans;

int end = all.front().end;

for (const Interval& busy : all) {

if (busy.start > end)

ans.emplace_back(end, busy.start);

end = max(end, busy.end);

}

return ans;

}

};

Related Problems:

Huahua's Tech Road

花花酱 LeetCode 239. Sliding Window Maximum

Solution 1: Brute Force

C++

Java

Python

Solution 2: BST

C++

Solution 3: Monotonic Queue

C++

C++ V2

C++ V3

Java

Python3

Python3 V2

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

花花酱 LeetCode. 69 Sqrt(x)

Solution 1: Brute force

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 494. Target Sum

Idea: DP

Solution 1: DP

C++

C++ SC O(n)

Java

C++ / V2

Solution 2: DFS

C++

Java

Solution 3: Subset sum

C++ w/ copy

C++ w/o copy

花花酱 LeetCode 759. Employee Free Time