Huahua’s Tech Road

花花酱 LeetCode 1649. Create Sorted Array through Instructions

By zxi on November 8, 2020

Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:

The number of elements currently in nums that are strictly less than instructions[i].
The number of elements currently in nums that are strictly greater than instructions[i].

For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].

Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 10⁹ + 7

Example 1:

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.

Example 2:

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3:

Input: instructions = [1,3,3,3,2,4,2,1,2]
Output: 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

Constraints:

1 <= instructions.length <= 10⁵
1 <= instructions[i] <= 10⁵

Solution: Fenwick Tree / Binary Indexed Tree

Time complexity: O(nlogm)
Space complexity: O(m + n)

m is the maximum value, n is number of values.

C++

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 Solution {

public:

int createSortedArray(vector<int>& instructions) {

const int n = instructions.size();

FenwickTree tree(1e5);

long ans = 0;

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

int lt = tree.query(instructions[i] - 1);

int gt = i - tree.query(instructions[i]);

ans += min(lt, gt);

tree.update(instructions[i], 1);

}

return ans % 1000000007;

}

};

花花酱 LeetCode 1648. Sell Diminishing-Valued Colored Balls

By zxi on November 7, 2020

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball’s value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the i^th color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

Example 2:

Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

Example 3:

Input: inventory = [2,8,4,10,6], orders = 20
Output: 110

Example 4:

Input: inventory = [1000000000], orders = 1000000000
Output: 21
Explanation: Sell the 1st color 1000000000 times for a total value of 500000000500000000. 500000000500000000 modulo 10⁹+ 7 = 21.

Constraints:

1 <= inventory.length <= 10⁵
1 <= inventory[i] <= 10⁹
1 <= orders <= min(sum(inventory[i]), 10⁹)

Solution: Greedy

Sort the colors by # of balls in descending order.
e.g. 3 7 5 1 => 7 5 3 1
Sell the color with largest number of balls until it has the same number of balls of next color
1. 7 5 3 1 => 6 5 3 1 => 5 5 3 1 # value = 7 + 6 = 13
2. 5 5 3 1 => 4 4 3 1 => 3 3 3 1 # value = 13 + (5 + 4) * 2 = 31
3. 3 3 3 1 => 2 2 2 1 => 1 1 1 1 # value = 31 + (3 + 2) * 3 = 46
4. 1 1 1 1 => 0 0 0 0 # value = 46 + 1 * 4 = 50
Need to handle the case if orders < total balls…

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

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int>& inventory, int orders) {

constexpr int kMod = 1e9 + 7;

const int n = inventory.size();

sort(rbegin(inventory), rend(inventory));

long cur = inventory[0];

long ans = 0;

int c = 0;

while (orders) {

while (c < n && inventory[c] == cur) ++c;

int nxt = c == n ? 0 : inventory[c];

int count = min(static_cast<long>(orders), c * (cur - nxt));

int t = cur - nxt;

int r = 0;

if (orders < c * (cur - nxt)) {

t = orders / c;

r = orders % c;

}

ans = (ans + (cur + cur - t + 1) * t / 2 * c + (cur - t) * r) % kMod;

orders -= count;

cur = nxt;

}

return ans;

}

};

花花酱 LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique

By zxi on November 7, 2020

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1:

Input: s = "aab"
Output: 0
Explanation: s is already good.

Example 2:

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc".
Another way it to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints:

1 <= s.length <= 10⁵
s contains only lowercase English letters.

Solution: Hashtable

The deletion order doesn’t matter, we can process from ‘a’ to ‘z’. Use a hashtable to store the “final frequency” so far, for each char, decrease its frequency until it becomes unique in the final frequency hashtable.

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

C++

class Solution {

public:

int minDeletions(string s) {

vector<int> freq(26);

for (char c : s) ++freq[c - 'a'];

unordered_set<int> seen;

int ans = 0;

for (int f : freq) {

while (f && !seen.insert(f).second) {

--f;

++ans;

}

return ans;

}

};

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

Huahua's Tech Road

花花酱 LeetCode 1649. Create Sorted Array through Instructions

Solution: Fenwick Tree / Binary Indexed Tree

C++

花花酱 LeetCode 1648. Sell Diminishing-Valued Colored Balls

Solution: Greedy

C++

花花酱 LeetCode 1647. Minimum Deletions to Make Character Frequencies Unique

Solution: Hashtable

C++

花花酱 1646. Get Maximum in Generated Array

Solution: Simulation

C++

花花酱 LeetCode 1206. Design Skiplist

Solution:

C++

Python3