Hi this is Di again. I realize it's too clumsy to post for every leetcode problem I solved. Therefore I decided to accumalate one weeks' reflection together and post them once.
202. Happy Number
If we add on all the square of a number's every digit, it end up with result 1, we call this number is a happy number.
It's easy to end the loop by detecting the emerge of 1. But how can we know when to end the endless loop without knowing whether 1 will appear?
Here is the maths prove behind it:
- For one digit numbers, the max is 9, its square sum is 81, far bigger than 9.
- For two digit numbers, the max is 99, its square sum is 81+81=162, slightly bigger than 99.
- For three digit numbers, the max is 999, its square sum is 81x3=243, far less than 999
- For four digit numbers, the max is 9999, its square sum is 81x4=324, far less than 9999
No matter how large the number is, after first calculation, it will collapse into range 1-999. Then turn into 1-243 in next iteration, then converged into this range forever. In endless loop, the 243 numbers will eventually appeared once. If a number come up twice, the number is sure to be "unhappy".
According to this convincing theory, our strategy is to loop until we find 1 or some number appears twice. Within the loop, we use a loop to calculate the square sum.
def isHappy(self, n: int) -> bool:
myset = set()
while n != 1 and n not in myset:
myset.add(n)
res = 0
while n != 0:
thedigit = n % 10
res += pow(thedigit, 2)
n = n // 10
n = res
return n == 1
It's not that easy to come up with the idea of set() to document duplicate without knowing the convergence theory behind. Harder than Easy tier.
128.Longest consecutive sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
To find it in O(n) time, we are going to examine whether each element is the starter number in sequence. For number n, if n-1 is in the nums, skip it, because it's not the beginner. Else, find the following elements until not satisfied.
def longestConsecutive(self, nums: List[int]) -> int:
# Convert list to set to satisfy the Container interface with O(1) lookups
num_set = set(nums)
longest_streak = 0
for num in num_set:
# Check if 'num' is the start of a sequence
# If (num - 1) exists, 'num' is NOT a start, so we skip it
if (num - 1) not in num_set:
current_num = num
current_streak = 1
# Keep counting the length of this consecutive sequence
while (current_num + 1) in num_set:
current_num += 1
current_streak += 1
# Update the maximum streak found so far
longest_streak = max(longest_streak, current_streak)
return longest_streak
The main idea is to find the beginning element and calculate the length of the sequence.
But why set instead of list?
The underlying implementation of set() is hashmap, allowing O(1) time search.
56.Merge intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
It's not hard to think of greedy method. But a segent of simple and elegant code snippet is precious.
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
# 2. Sort intervals by start time (O(n log n))
# Note: list.sort() is in-place and efficient in Python
intervals.sort(key=lambda x: x[0])
merged = []
for curr_start, curr_end in intervals:
# DRY: If merged is empty or no overlap, append the interval
# The 'if not merged' handles the initialization of the result list
if not merged or merged[-1][1] < curr_start:
merged.append([curr_start, curr_end])
else:
# Overlap: Update the end time of the last merged interval
# Use max() to ensure we cover the largest possible range
merged[-1][1] = max(merged[-1][1], curr_end)
return merged
Lamda expression
Noticeintervals.sort(key=lambda x: x[0]).
this lamda expression allows you to sort the array by any key.xhere is the every element in the list. If we want to have priority, use tuple to assign.Sequence Unpacking
"We can unpack the intervals directly in the for-loop header to improve readability."
for curr_start, curr_end in intervals:The members in the list are lists with 2 elements in it. So this unpacking is quite smart and time-saving, and readability-strengthening.Interval situations.
When two intervals are overlapped.
The first former one completely includes the latter one.
Two intervals have partial intersection.
These can be all tackled bymerged[-1][1] = max(merged[-1][1], curr_end)
Cuz we just want the farthest end of the interval.
57.Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
It's quite similar to leetcode 56 except we have to insert the new interval into the intervals and do the algorithms in 56 again.
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals:
intervals.append(newInterval)
return intervals
if not newInterval:
return intervals
res = []
inserted = False
for i in range(len(intervals)):
start,end = intervals[i]
if start >= newInterval[0]:
intervals.insert(i,newInterval)
inserted = True
break
if inserted == False:
intervals.append(newInterval)
for start,end in intervals:
if not res or res[-1][1] < start:
res.append([start,end])
else:
res[-1][1] = max(res[-1][1], end)
return res
Use a flag inserted to trace the new interval. If it's gonna be the last one in intervals, the flag would still be False, then deal with it at last.
Top comments (0)