Huahua’s Tech Road

花花酱 LeetCode 1349. Maximum Students Taking Exam

By zxi on February 9, 2020

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..

Students must be placed in seats in good condition.

Example 1:

Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

seats contains only characters '.' and'#'.
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8

Solution 1: DFS (TLE)

Time complexity: O(2^(m*n)) = O(2^64)
Space complexity: O(m*n)

Solution 2: DP

Since how to fill row[i+1] only depends on row[i]’s state, we can define

dp[i][s] as the max # of students after filling i rows and s (as a binary string) is the states i-th row.

dp[i+1][t] = max{dp[i][s] + bits(t)} if row[i] = s && row[i +1] = t is a valid state.

Time complexity: O(m*2^(n+n)*n) = O(2^22)
Space complexity: O(m*2^n) = O(2^11) -> O(2^n)

C++

// Author: Huahua

class Solution {

public:

int maxStudents(vector<vector<char>>& seats) {

int m = seats.size();

int n = seats[0].size();

vector<vector<int>> dp(m + 1, vector<int>(1 << n));

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

for (int l = 0; l < (1 << n); ++l)

for (int c = 0; c < (1 << n); ++c) {

bool flag = true;

for (int j = 0; j < n && flag; ++j) {

if (!(c & (1 << j))) continue;

if (seats[i][j] == '#') flag = false;

bool l = j == 0 ? false : (c & (1 << (j - 1)));

bool r = j == n - 1 ? false : (c & (1 << (j + 1)));

bool ul = (j == 0 || i == 0) ? false : (l & (1 << (j - 1)));

bool ur = (j == n - 1 || i == 0) ? false : (l & (1 << (j + 1)));

if (l || r || ul || ur) flag = false;

}

if (flag)

dp[i + 1][c] = max(dp[i + 1][c], dp[i][l] + __builtin_popcount(c));

}

return *max_element(begin(dp[m]), end(dp[m]));

}

};

C++

// Author: Huahua

class Solution {

public:

int maxStudents(vector<vector<char>>& seats) {

const int m = seats.size();

const int n = seats[0].size();

vector<int> s(m + 1);

for (int i = 1; i <= m; ++i)

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

s[i] |= (seats[i - 1][j] == '.') << j;

vector<vector<int>> dp(m + 1, vector<int>(1 << n));

for (int i = 1; i <= m; ++i)

for (int c = s[i];;c = (c - 1) & s[i]) {

if (c & (c >> 1)) continue;

for (int l = s[i - 1];;l = (l - 1) & s[i - 1]) {

if (!(l & (c >> 1)) && !((l >> 1) & c))

dp[i][c] = max(dp[i][c], dp[i - 1][l] + __builtin_popcount(c));

if (l == 0) break;

}

if (c == 0) break;

}

return *max_element(begin(dp[m]), end(dp[m]));

}

};

花花酱 LeetCode 1345. Jump Game IV

By zxi on February 8, 2020

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

Example 2:

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You don't need to jump.

Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Example 4:

Input: arr = [6,1,9]
Output: 2

Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Solution: HashTable + BFS

Use a hashtable to store the indices of each unique number.

each index i has neighbors (i-1, i + 1, hashtable[arr[i]])

Use BFS to find the shortest path in this unweighted graph.

Key optimization, clear hashtable[arr[i]] after the first use, since all nodes are already on queue, no longer needed.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 124 ms, 30.5 MB

class Solution {

public:

int minJumps(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<int>> m;

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

m[arr[i]].push_back(i);

vector<int> seen(n);

queue<int> q({0});

seen[0] = 1;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int i = q.front(); q.pop();

if (i == n - 1) return steps;

if (i - 1 >= 0 && !seen[i - 1]++) q.push(i - 1);

if (i + 1 < n && !seen[i + 1]++) q.push(i + 1);

auto it = m.find(arr[i]);

if (it == m.end()) continue;

for (int nxt : it->second)

if (!seen[nxt]++) q.push(nxt);

m.erase(it); // no longer needed.

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1093. Statistics from a Large Sample

By zxi on February 6, 2020

We sampled integers between 0 and 255, and stored the results in an array count: count[k] is the number of integers we sampled equal to k.

Return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers. The mode is guaranteed to be unique.

(Recall that the median of a sample is:

The middle element, if the elements of the sample were sorted and the number of elements is odd;
The average of the middle two elements, if the elements of the sample were sorted and the number of elements is even.)

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

count.length == 256
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.
Answers within 10^-5 of the true value will be accepted as correct.

Solution: TreeMap

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<double> sampleStats(vector<int>& count) {

int counts = 0;

int minVal = 255;

int maxVal = 0;

int mode = -1;

int modeCount = 0;

long sum = 0;

map<int, int> m;

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

if (!count[i]) continue;

sum += static_cast<long>(i) * count[i];

minVal = min(minVal, i);

maxVal = max(maxVal, i);

if (count[i] > modeCount) {

mode = i;

modeCount = count[i];

}

m[counts += count[i]] = i;

}

auto it1 = m.lower_bound(counts / 2);

double median = it1->second;

auto it2 = next(it1);

if (counts % 2 == 0 && it2 != m.end() && it1->first == counts / 2) {

median = (median + it2->second) / 2;

}

return {minVal, maxVal, static_cast<double>(sum) / counts, median, mode};

}

};

花花酱 LeetCode 108. Convert Sorted Array to Binary Search Tree

By zxi on February 2, 2020

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution: Recursion

Recursively build a BST for a given range.

def build(nums, l, r):
if l > r: return None
m = l + (r – l) / 2
root = TreeNode(nums[m])
root.left = build(nums, l, m – 1)
root.right = build(nums, m + 1, r)
return root

return build(nums, 0, len(nums) – 1)

Time complexity: O(n)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

TreeNode* sortedArrayToBST(vector<int>& nums) {

function<TreeNode*(int l, int r)> build = [&](int l, int r) {

if (l > r) return static_cast<TreeNode*>(nullptr);

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

TreeNode* root = new TreeNode(nums[m]);

root->left = build(l, m - 1);

root->right = build(m + 1, r);

return root;

};

return build(0, nums.size() - 1);

}

};

Java

// Author: Huahua

class Solution {

public TreeNode sortedArrayToBST(int[] nums) {

return buildBST(nums, 0, nums.length - 1);

}

private TreeNode buildBST(int[] nums, int l, int r) {

if (l > r) return null;

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

TreeNode root = new TreeNode(nums[m]);

root.left = buildBST(nums, l, m - 1);

root.right = buildBST(nums, m + 1, r);

return root;

}

Python3

# Author: Huahua

class Solution:

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

def buildBST(l: int, r: int) -> TreeNode:

if l > r: return None

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

root = TreeNode(nums[m])

root.left = buildBST(l, m - 1)

root.right = buildBST(m + 1, r)

return root

return buildBST(0, len(nums) - 1)

JavaScript

// Author: Huahua

var sortedArrayToBST = function(nums) {

var buildBST = function(l, r) {

if (l > r) return null;

let m = l + Math.floor((r - l) / 2);

let root = new TreeNode(nums[m]);

root.left = buildBST(l, m - 1);

root.right = buildBST(m + 1, r);

return root;

}

return buildBST(0, nums.length - 1);

};

花花酱 LeetCode 1344. Jump Game V

By zxi on February 1, 2020

Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).

You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:

Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Example 4:

Input: arr = [7,1,7,1,7,1], d = 2
Output: 2

Example 5:

Input: arr = [66], d = 1
Output: 1

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

Solution: Recursion w/ Memoization

dp(i) = max{1, max{dp(j) + 1}}, if i can jump to j.
ans = max(dp(i))

Time complexity: O(n*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

int n = a.size();

vector<int> m(n);

function<int(int)> dp = [&](int i) {

if (m[i]) return m[i];

int ans = 1;

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

ans = max(ans, dp(j) + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

ans = max(ans, dp(j) + 1);

return m[i] = ans;

};

int ans = 0;

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

ans = max(ans, dp(i));

return ans;

}

};

Solution 2: DP

Time complexity: O(nlogn + n*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxJumps(vector<int>& a, int d) {

const int n = a.size();

vector<pair<int, int>> m(n); // <height, index>

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

m[i] = {a[i], i};

// Solve from the lowest bar.

sort(begin(m), end(m));

vector<int> dp(n, 1);

for (auto [v, i] : m) {

for (int j = i + 1; j <= min(n - 1, i + d) && a[i] > a[j]; ++j)

dp[i] = max(dp[i], dp[j] + 1);

for (int j = i - 1; j >= max(0, i - d) && a[i] > a[j]; --j)

dp[i] = max(dp[i], dp[j] + 1);

}

return *max_element(begin(dp), end(dp));

}

};

Huahua's Tech Road

花花酱 LeetCode 1349. Maximum Students Taking Exam

Solution 1: DFS (TLE)

Solution 2: DP

C++

C++

花花酱 LeetCode 1345. Jump Game IV

Solution: HashTable + BFS

C++

Related Problems

花花酱 LeetCode 1093. Statistics from a Large Sample

Solution: TreeMap

C++

花花酱 LeetCode 108. Convert Sorted Array to Binary Search Tree

Solution: Recursion

C++

Java

Python3

JavaScript

花花酱 LeetCode 1344. Jump Game V

Solution: Recursion w/ Memoization

C++

Solution 2: DP

C++