Posts published in “Simulation”

花花酱 LeetCode 1354. Construct Target Array With Multiple Sums

By zxi on February 16, 2020

Given an array of integers target. From a starting array, A consisting of all 1’s, you may perform the following procedure :

let x be the sum of all elements currently in your array.
choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
You may repeat this procedure as many times as needed.

Return True if it is possible to construct the target array from A otherwise return False.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints:

N == target.length
1 <= target.length <= 5 * 10^4
1 <= target[i] <= 10^9

Solution: Backwards Simulation

Start with the largest number in the array, since it should be the sum of all previous numbers.

[9,3,5] => [9 – (3+5), 3, 5] => [1, 3, 5] => [1, 3, 5 – (1+3)] => [1, 3, 1] => [1, 3 – (1+1), 1] => [1,1,1] done

Time complexity: O(n + log(n*t)*logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isPossible(vector<int>& target) {

priority_queue<int> q(begin(target), end(target));

long sum = accumulate(begin(target), end(target), 0LL);

while (true) {

int t = q.top(); q.pop();

sum -= t;

if (t == 1 || sum == 1) return true;

if (t < sum || sum == 0 || t % sum == 0) return false;

t %= sum;

sum += t;

q.push(t);

}

return true;

}

};

花花酱 LeetCode 1342. Number of Steps to Reduce a Number to Zero

By zxi on February 13, 2020

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Example 2:

Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Example 3:

Input: num = 123
Output: 12

Constraints:

0 <= num <= 10^6

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int numberOfSteps (int num) {

int steps = 0;

while (num) {

if (num & 1)

--num;

else

num >>= 1;

++steps;

}

return steps;

}

};

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

By zxi on January 26, 2020

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendly_i and veganFriendly take value 1 when it is true, and 0 when it is false.

Example 1:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
Output: [3,1,5] 
Explanation: 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).

Example 2:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Example 3:

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
Output: [4,5]

Constraints:

1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Solution

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

C++

// Author: Huahua

class Solution {

public:

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {

vector<pair<int, int>> rs; // <rating, id>

for (auto& r : restaurants)

if ((!veganFriendly || veganFriendly && r[2]) && r[3] <= maxPrice && r[4] <= maxDistance)

rs.emplace_back(r[1], r[0]);

sort(rbegin(rs), rend(rs));

vector<int> ans;

for (const auto& r : rs) ans.push_back(r.second);

return ans;

}

};

花花酱 LeetCode 1313. Decompress Run-Length Encoded List

By zxi on January 11, 2020

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are a elements with value b in the decompressed list.

Return the decompressed list.

Example 1:

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

Constraints:

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

Solution: Simulation

Time complexity: O(sum(n_i))
Space complexity: O(sum(n_i)) or O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> decompressRLElist(vector<int>& nums) {

vector<int> ans;

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

for (int j = 0; j < nums[i]; ++j)

ans.push_back(nums[i + 1]);

return ans;

}

};

花花酱 LeetCode 2. Add Two Numbers

By zxi on December 30, 2019

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution: Simulation

Time complexity: O(max(n,m))
Space complexity: O(max(n,m))

C++

// Author: Huahua

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

int sum = 0;

while (l1 || l2 || sum) {

sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);

l1 = l1 ? l1->next : nullptr;

l2 = l2 ? l2->next : nullptr;

tail->next = new ListNode(sum % 10);

sum /= 10;

tail = tail->next;

}

return dummy.next;

}

};

Java

// Author: Huahua

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode tail = new ListNode(0);

ListNode dummy = tail;

int sum = 0;

while (l1 != null || l2 != null || sum > 0) {

sum += (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val);

tail.next = new ListNode(sum % 10);

tail = tail.next;

if (l1 != null) l1 = l1.next;

if (l2 != null) l2 = l2.next;

sum /= 10;

}

return dummy.next;

}

Python3

# Author: Huahua

class Solution:

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

dummy = tail = ListNode(0)

s = 0

while l1 or l2 or s:

s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

tail.next = ListNode(s % 10)

tail = tail.next

s //= 10

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

return dummy.next