emmmm, my procrastination is hopeless, and by the way, I got addicted to Kotlin this week. This solution, which should have been finished on Monday, has been delayed until now, = = however, this week is a biweekly contest, so I have to write two solutions again...
1351. Count Negative Numbers in a Sorted Matrix#
Problem statement:
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.
Return the number of negative numbers in grid.
Example:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
The problem is very simple. Given a matrix that is decreasing both horizontally and vertically, we need to find the count of negative numbers in this matrix. Since the data scale in both dimensions is less than 100, there’s not much to say, just brute force, traverse horizontally, and stop traversing when encountering a negative number.
from typing import List
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
if not grid:
return 0
n_length = len(grid[0])
result = 0
for item in grid:
for i in range(n_length):
if item[i] < 0:
result += n_length - i
break
return result
1352. Product of the Last K Numbers#
Problem statement:
Implement the class ProductOfNumbers that supports two methods:
1. add(int num)
Adds the number num to the back of the current list of numbers.
2. getProduct(int k)
Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.
At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
Example:
Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
Output
[null,null,null,null,null,null,20,40,0,null,32]
Explanation
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3); // [3]
productOfNumbers.add(0); // [3,0]
productOfNumbers.add(2); // [3,0,2]
productOfNumbers.add(5); // [3,0,2,5]
productOfNumbers.add(4); // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32
The problem is very simple. Design a data structure that provides an add method to allow users to add numbers and a getProduct method to allow users to calculate the product of the last K numbers. There’s not much to say about this problem, just write it out directly, adding a hashmap as a cache in between.
from typing import List, Dict
import bisect
from operator import mul
from functools import reduce
class ProductOfNumbers:
_value: List[int]
_cache_result: Dict[int, int]
_cache_index: List[int]
def __init__(self):
self._value = []
self._cache_result = {}
self._cache_index = []
def add(self, num: int) -> None:
self._value.append(num)
self._cache_index.clear()
self._cache_result.clear()
def getProduct(self, k: int) -> int:
if k in self._cache_result:
return self._cache_result[k]
cache_index = bisect.bisect(self._cache_index, k) - 1
if cache_index >= 0:
last_k = self._cache_index[cache_index]
result = self._cache_result[last_k]
for i in range(1, cache_index + 1):
temp_last_k = last_k + i
if temp_last_k >= len(self._value):
break
result *= self._value[-last_k]
else:
temp_value = (
self._value[-1 : -k - 1 : -1] if k <= len(self._value) else self._value
)
result = reduce(mul, temp_value, 1)
bisect.bisect_left(self._cache_index, k)
self._cache_result[k] = result
return result
1353. Maximum Number of Events That Can Be Attended#
Problem statement:
Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.
Return the maximum number of events you can attend.
Example:
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
Given an array where each element x represents an event, x[0], x[i] represents the start and end times of that event. A user can only attend one event per day, and we need to find out how many events the user can attend at most. This is a classic greedy problem. First, sort the event list by end time, then traverse each time to confirm which specific day can be attended. The overall time complexity is O(max(nlogn,n*m)).
from typing import List, Dict
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
if not events:
return 0
events_size = len(events)
if events_size == 1:
return 1
events = sorted(events)
_day_map: Dict[str, bool] = {}
_event_map: Dict[int, bool] = {}
count = 0
for i in range(events_size):
for j in range(events[i][0], events[i][1]+1):
temp = "{}".format(j)
if temp not in _day_map and i not in _event_map:
count += 1
_day_map[temp] = True
_event_map[i] = True
return count
1354. Construct Target Array With Multiple Sums#
Problem statement:
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:
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
This problem can be considered a mathematical problem. We first know that the sum of all elements in the array must be greater than each individual element (this is not nonsense). Then we assume there is such an array [1,1,9,17,63]. We can iterate back to the previous array structure [1,1,9,17,33], and then we can iterate forward once more [1,1,9,17,5]. At this point, the current number is no longer the largest number in the array, so we start looking for the next largest number in the array to iterate.
Here we can also find that the original value of the maximum number in the array is the current number modulo the sum of the other numbers. So we can keep iterating like this until we are done.
Alright, here’s the code:
import heapq
from typing import List
class Solution:
def isPossible(self, target: List[int]) -> bool:
if not target:
return False
total = sum(target)
target = sorted([-x for x in target])
heapq.heapify(target)
while True:
a = -heapq.heappop(target)
total -= a
if a == 1 or total == 1:
return True
if a < total or total == 0 or a % total == 0:
return False
a %= total
total += a
heapq.heappush(target, -a)
Summary#
The problems this time are still at the regular level of the weekly contest, but I really haven't practiced enough QAQ