Leetcode BiWeekly Contest, this week's biweekly contest, after two rounds of competition, it's a bit challenging. Let's start by writing a solution for BiWeekly 19 Contest.
1342. Number of Steps to Reduce a Number to Zero#
Problem:
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:
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.
This problem is quite simple. Given a non-negative integer, we need to divide it by 2 if it's even, and subtract 1 if it's odd, until we reach 0. Let's solve it using a brute force approach.
class Solution:
def numberOfSteps(self, num: int) -> int:
count = 0
if num == 0:
return count
result = num
while result > 1:
if result % 2 == 0:
result = int(result / 2)
else:
result -= 1
count += 1
return count + 1
Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#
Problem:
Given an array of integers arr and two integers k and threshold.
Return the number of sub-arrays of size k and average greater than or equal to threshold.
Example:
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold)
Given an array and a length k, along with a threshold value, we need to find the number of sub-arrays of size k whose average is greater than or equal to the threshold. This problem can be solved using a brute force approach by checking each sub-array. However, we can optimize it by using a sliding window technique.
from typing import List
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
if not arr:
return 0
length = len(arr)
sum_threshold = [0.0] * length
count = 0
last_index = length
for i in range(length - k, -1, -1):
if i == length - k:
total_sum = sum(arr[i:i + k])
else:
total_sum = sum_threshold[i + 1] - arr[last_index] + arr[i]
sum_threshold[i] = total_sum
if total_sum / k >= threshold:
count += 1
last_index -= 1
return count
1344. Angle Between Hands of a Clock#
Problem:
Given two numbers, hour and minutes. Return the smaller angle (in sexagesimal units) formed between the hour and the minute hand.
Example:
Input: hour = 12, minutes = 30
Output: 165
In this problem, we need to find the smaller angle formed between the hour and minute hands of a clock given the hour and minutes. We can solve this problem using some basic mathematical calculations.
class Solution:
def angleClock(self, hour: int, minutes: int) -> float:
hour %= 12
result = abs((minutes * 6) - (hour * 30 + minutes * 0.5))
return result if result < 360 else 360 - result
1345. Jump Game IV#
Problem:
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:
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.
In this problem, we need to find the minimum number of steps to reach the last index of the array. We can solve this problem using a breadth-first search (BFS) approach.
from typing import List, Set
import collections
class Solution:
def minJumps(self, arr: List[int]) -> int:
length = len(arr)
if not arr or length == 1:
return 0
value_index = collections.defaultdict(list)
for index, value in enumerate(arr):
value_index[value].append(index)
visited: Set[int] = set()
traversal_queue = collections.deque([(0, 0)])
result = 0
while traversal_queue:
next_step_queue = collections.deque()
for _ in range(len(traversal_queue)):
cur_index, cur_step = traversal_queue.popleft()
cur_value = arr[cur_index]
visited.add(cur_index)
for next_index in [cur_index + 1, cur_index - 1] + value_index[
cur_value
]:
if (length > next_index >= 0) and (next_index not in visited):
if next_index == length - 2:
return cur_step + 2
if next_index == length - 1:
return cur_step + 1
next_step_queue.append((next_index, cur_step + 1))
del value_index[cur_value]
traversal_queue = next_step_queue
return result
Summary#
The problems in this week's contest were not too difficult, but required careful attention. For example, I made a mistake in the second problem by using a brute force approach and received a Time Limit Exceeded (TLE) error. In the third problem, I didn't read the problem carefully (finding the smallest angle) and received a Wrong Answer (WA). Compared to the problems in the previous day's weekly contest, I feel fortunate. I scored 175 points in the third problem, which made me feel frustrated. I will write the solutions tomorrow.
Alright, time to go to sleep.