Huahua’s Tech Road

花花酱 1646. Get Maximum in Generated Array

By zxi on November 7, 2020

You are given an integer n. An array nums of length n + 1 is generated in the following way:

nums[0] = 0
nums[1] = 1
nums[2 * i] = nums[i] when 2 <= 2 * i <= n
nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Returnthe maximum integer in the array nums.

Example 1:

Input: n = 7
Output: 3
Explanation: According to the given rules:
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is 3.

Example 2:

Input: n = 2
Output: 1
Explanation: According to the given rules, the maximum between nums[0], nums[1], and nums[2] is 1.

Example 3:

Input: n = 3
Output: 2
Explanation: According to the given rules, the maximum between nums[0], nums[1], nums[2], and nums[3] is 2.

Constraints:

0 <= n <= 100

Solution: Simulation

Generate the array by the given rules.

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

C++

class Solution {

public:

int getMaximumGenerated(int n) {

vector<int> nums(n + 1);

nums[0] = 0;

if (n > 0) nums[1] = 1;

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

nums[2 * i] = nums[i];

if (i * 2 + 1 <= n) nums[2 * i + 1] = nums[i] + nums[i + 1];

}

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

}

};

花花酱 LeetCode 1206. Design Skiplist

By zxi on November 6, 2020

Design a Skiplist without using any built-in libraries.

A Skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.

For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

To be specific, your design should include these functions:

bool search(int target) : Return whether the target exists in the Skiplist or not.
void add(int num): Insert a value into the SkipList.
bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.

See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example:

Skiplist skiplist = new Skiplist();

skiplist.add(1);

skiplist.add(2);

skiplist.add(3);

skiplist.search(0); // return false.

skiplist.add(4);

skiplist.search(1); // return true.

skiplist.erase(0); // return false, 0 is not in skiplist.

skiplist.erase(1); // return true.

skiplist.search(1); // return false, 1 has already been erased.

Constraints:

0 <= num, target <= 20000
At most 50000 calls will be made to search, add, and erase.

Solution:

C++

// Author: Huahua

class Skiplist {

public:

Skiplist() { head_ = make_shared<Node>(); }

bool search(int target) {

for (auto node = head_; node; node = node->down) {

while (node->next && node->next->val < target)

node = node->next;

if (node->next && node->next->val == target)

return true;

}

return false;

}

void add(int num) {

stack<shared_ptr<Node>> s;

shared_ptr<Node> down;

bool insert = true;

for (auto node = head_; node; node = node->down) {

while (node->next && node->next->val < num)

node = node->next;

s.push(node);

}

while (!s.empty() && insert) {

auto cur = s.top(); s.pop();

cur->next = make_shared<Node>(num, cur->next, down);

down = cur->next;

insert = rand() & 1; // 50% chance

}

if (insert) // create a new layer.

head_ = make_shared<Node>(-1, nullptr, head_);

}

bool erase(int num) {

bool found = false;

for (auto node = head_; node; node = node->down) {

while (node->next && node->next->val < num)

node = node->next;

if (node->next && node->next->val == num) {

found = true;

node->next = node->next->next;

}

return found;

}

private:

struct Node {

Node(int val = -1,

shared_ptr<Node> next = nullptr,

shared_ptr<Node> down = nullptr):

val(val), next(next), down(down) {}

int val;

shared_ptr<Node> next;

shared_ptr<Node> down;

};

shared_ptr<Node> head_;

};

/**

* Your Skiplist object will be instantiated and called as such:

* Skiplist* obj = new Skiplist();

* bool param_1 = obj->search(target);

* obj->add(num);

* bool param_3 = obj->erase(num);

Python3

import random

class Node:

def __init__(self, val=-1, right=None, down=None):

self.val = val

self.right = right

self.down = down

class Skiplist:

def __init__(self):

self.head = Node() # Dummy head

def search(self, target: int) -> bool:

node = self.head

while node:

# Move to the right in the current level

while node.right and node.right.val < target:

node = node.right

if node.right and node.right.val == target:

return True

# Move to the the next level

node = node.down

return False

def add(self, num: int) -> None:

nodes = []

node = self.head

while node:

# Move to the right in the current level

while node.right and node.right.val < num:

node = node.right

nodes.append(node)

# Move to the next level

node = node.down

insert = True

down = None

while insert and nodes:

node = nodes.pop()

node.right = Node(num, node.right, down)

down = node.right

insert = (random.getrandbits(1) == 0)

# Create a new level with a dummy head.

# right = None

# down = current head

if insert:

self.head = Node(-1, None, self.head)

def erase(self, num: int) -> bool:

node = self.head

found = False

while node:

# Move to the right in the current level

while node.right and node.right.val < num:

node = node.right

# Find the target node

if node.right and node.right.val == num:

# Delete by skipping

node.right = node.right.right

found = True

# Move to the next level

node = node.down

return found

# Your Skiplist object will be instantiated and called as such:

# obj = Skiplist()

# param_1 = obj.search(target)

# obj.add(num)

# param_3 = obj.erase(num)

花花酱 LeetCode 1642. Furthest Building You Can Reach

By zxi on November 1, 2020

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.
If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

1 <= heights.length <= 10⁵
1 <= heights[i] <= 10⁶
0 <= bricks <= 10⁹
0 <= ladders <= heights.length

Solution 0: DFS

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

AC but should be TLE

Solution 1: Binary Search + Greedy

Guess we can reach to m, sort the height differences from 0~m. Use ladders for larger values and use bricks for smallest values left.

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

C++

// Author: Huahua, 300 ms

class Solution {

public:

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

const int n = heights.size();

if (ladders >= n - 1) return n - 1;

vector<int> diffs(n);

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

diffs[i - 1] = max(0, heights[i] - heights[i - 1]);

int l = ladders;

int r = n;

while (l < r) {

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

vector<int> d(begin(diffs), begin(diffs) + m);

nth_element(begin(d), end(d) - ladders, end(d));

if (accumulate(begin(d), end(d) - ladders, 0) > bricks)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

Solution 2: Min heap

Use a min heap to store all the height differences ( > 0) so far, if heap size is greater than ladders, which means we have to use bricks, extract the smallest value and subtract the bricks.

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

C++

// Author: Huahua, 216 ms

class Solution {

public:

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

const int n = heights.size();

priority_queue<int, vector<int>, greater<int>> q;

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

const int d = heights[i] - heights[i - 1];

if (d <= 0) continue;

q.push(d);

if (q.size() <= ladders) continue;

bricks -= q.top(); q.pop();

if (bricks < 0) return i - 1;

}

return n - 1;

}

};

花花酱 LeetCode 1641. Count Sorted Vowel Strings

By zxi on November 1, 2020

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Example 1:

Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2:

Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045

Solution: DP

dp[i][j] := # of strings of length i ends with j.

dp[i][j] = sum(dp[i – 1][[k]) 0 <= k <= j

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++/O(n) Space

class Solution {

public:

int countVowelStrings(int n) {

// dp[i][j] = # of strings of length i ends with j

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

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

int s = 0;

for (int j = 0; j < 5; ++j) {

s += dp[i - 1][j];

dp[i][j] = s;

}

return accumulate(begin(dp[n]), end(dp[n]), 0);

}

};

C++/O(1) Space

class Solution {

public:

int countVowelStrings(int n) {

// dp([i])[j] = # of strings of length i ends with j

vector<int> dp(5, 1);

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

for (int j = 4; j >= 0; --j)

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

dp[j] += dp[k];

return accumulate(begin(dp), end(dp), 0);

}

};

花花酱 LeetCode 1640. Check Array Formation Through Concatenation

By zxi on October 31, 2020

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]
Output: true

Example 2:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints:

1 <= pieces.length <= arr.length <= 100
sum(pieces[i].length) == arr.length
1 <= pieces[i].length <= arr.length
1 <= arr[i], pieces[i][j] <= 100
The integers in arr are distinct.
The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

Solution: Hashtable

Store the index of the first number of each piece, for each number a in arr, concat the entire piece array whose first element equals to a.

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

C++

class Solution {

public:

bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {

unordered_map<int, int> m;

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

m[pieces[i][0]] = i;

vector<int> ans;

for (int a : arr) {

if (!m.count(a)) continue;

ans.insert(end(ans), begin(pieces[m[a]]), end(pieces[m[a]]));

}

return ans == arr;

}

};

Huahua's Tech Road

花花酱 1646. Get Maximum in Generated Array

Solution: Simulation

C++

花花酱 LeetCode 1206. Design Skiplist

Solution:

C++

Python3

花花酱 LeetCode 1642. Furthest Building You Can Reach

Solution 0: DFS

Solution 1: Binary Search + Greedy

C++

Solution 2: Min heap

C++

花花酱 LeetCode 1641. Count Sorted Vowel Strings

Solution: DP

C++/O(n) Space

C++/O(1) Space

花花酱 LeetCode 1640. Check Array Formation Through Concatenation

Solution: Hashtable

C++