花花酱 LeetCode 942. DI String Match

By zxi on November 18, 2018

Problem

Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length.

Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

If S[i] == "I", then A[i] < A[i+1]
If S[i] == "D", then A[i] > A[i+1]

Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

Note:

1 <= S.length <= 10000
S only contains characters "I" or "D".

Solution: Greedy

“I” -> use the smallest possible number

“D” -> use the largest possible number

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> diStringMatch(string S) {

const int n = S.length();

vector<int> ans;

int lo = 0;

int hi = n;

for (char c : S) {

if (c == 'I')

ans.push_back(lo++);

else

ans.push_back(hi--);

}

ans.push_back(lo);

return ans;

}

};

花花酱 LeetCode 941. Valid Mountain Array

By zxi on November 18, 2018

Problem

Given an array A of integers, return true if and only if it is a valid mountain array.

Recall that A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

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

Note:

0 <= A.length <= 10000
0 <= A[i] <= 10000

Solution

Use has_up and has_down to track whether we have A[i] > A[i – 1] and A[i] < A[i – 1] receptively.

return false if any of the following happened:

size(A) < 3
has_down happened before has_up
not has_down or not has_up
A[i – 1] < A[i] after has_down
A[i – 1] > A[i] before has_up

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 24 ms

class Solution {

public:

bool validMountainArray(vector<int>& A) {

if (A.size() < 3) return false;

bool has_up = false;

bool has_down = false;

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

if (A[i] > A[i - 1]) {

if (has_down) return false;

has_up = true;

}

else if (A[i] < A[i - 1]){

if (!has_up) return false;

has_down = true;

} else {

return false;

}

return has_up && has_down;

}

};

花花酱 LeetCode 55. Jump Game

By zxi on November 15, 2018

Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Solution: Greedy

If you can jump to i, then you can jump to at least i + nums[i].

Always jump as far as you can.

Keep tracking the farthest index you can jump to.

Init far = nums[0].

far = max(far, i + nums[i])

check far >= n – 1

ex 1 [2,3,1,1,4]

i nums[i] i + nums[i] far

- - - 2

0 2 2 2

1 3 4 4

2 1 3 4

3 1 4 4

4 4 8 8

ex 2 [3,2,1,0,4]

i nums[i] i + nums[i] far

- - - 3

0 3 3 3

1 2 3 3

2 1 3 3

3 0 3 3 <- can not reach index 4, break

C++

// Author: Huahua, running time 16 ms

class Solution {

public:

bool canJump(vector<int>& nums) {

const int n = nums.size();

int far = nums[0];

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

if (i > far) break;

far = max(far, i + nums[i]);

}

return far >= n-1;

}

};

花花酱 LeetCode 940. Distinct Subsequences II

By zxi on November 14, 2018

Problem

Given a string S, count the number of distinct, non-empty subsequences of S .

Since the result may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".

Example 3:

Input: "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Note:

S contains only lowercase letters.
1 <= S.length <= 2000

Solution: DP

counts[i][j] := # of distinct sub sequences of s[1->i] and ends with letter j. (‘a'<= j <= ‘z’)

Initialization:

counts[*][*] = 0

Transition:

counts[i][j] = sum(counts[i-1]) + 1 if s[i] == j else counts[i-1][j]

ans = sum(counts[n])

e.g. S = “abc”

counts[1] = {‘a’ : 1}
counts[2] = {‘a’ : 1, ‘b’ : 1 + 1 = 2}
counts[3] = {‘a’ : 1, ‘b’ : 2, ‘c’: 1 + 2 + 1 = 4}
ans = sum(counts[3]) = 1 + 2 + 4 = 7

Time complexity: O(N*26)

Space complexity: O(N*26) -> O(26)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

int distinctSubseqII(string S) {

constexpr int kMod = 1e9 + 7;

std::vector<int> counts(26);

for (char c : S)

counts[c - 'a'] = accumulate(begin(counts), end(counts), 1L) % kMod;

return accumulate(begin(counts), end(counts), 0L) % kMod;

}

};

Python3

# Author: Huahua, running time: 64 ms

class Solution:

def distinctSubseqII(self, S):

kMod = 10**9 + 7

dp = {}

for c in S:

dp[c] = (sum(dp.values()) + 1) % kMod

return sum(dp.values()) % kMod

花花酱 LeetCode 939. Minimum Area Rectangle

By zxi on November 11, 2018

Problem

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

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

Example 2:

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

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Solution 1: HashTable + Brute Force

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua, running time: 96 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_map<int, unordered_set<int>> s;

for (const auto& point : points)

s[point[0]].insert(point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

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

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

if (!s[x1].count(y0) || !s[x0].count(y1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

C++ / 1D hashtable

// Author: Huahua, 68 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_set<int> s;

for (const auto& point : points)

s.insert((point[0] << 16) | point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

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

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

int p0 = (x1 << 16) | y0;

int p1 = (x0 << 16) | y1;

if (!s.count(p0) || !s.count(p1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

Huahua's Tech Road

花花酱 LeetCode 942. DI String Match

Problem

Solution: Greedy

C++

花花酱 LeetCode 941. Valid Mountain Array

Problem

Solution

C++

花花酱 LeetCode 55. Jump Game

Problem

Solution: Greedy

C++

花花酱 LeetCode 940. Distinct Subsequences II

Problem

Solution: DP

C++

Python3

花花酱 LeetCode 939. Minimum Area Rectangle

Problem

Solution 1: HashTable + Brute Force

C++

C++ / 1D hashtable