Link : https://leetcode.com/problems/find-the-duplicate-number/

Problem :
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

圖來自leetcode

Thoughts :
1. 用collections.Counter來計算每個數字出現的次數。
2. 如果 count > 1,直接 return。

Solution :

class Solution:
def findDuplicate(self, nums: List[int]) -> int:
count = collections.Counter(nums)
for i,j in count.items():
if j > 1:
return i

time complexity, space complexity

Link : https://leetcode.com/problems/longest-consecutive-sequence/

Problem :
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

圖來自leetcode

Thoughts :
1. 先把 nums 放進去 set中,排除重複的數字。
2. 跑 nums迴圈,假設 nums-1 數字有在 set 中,那 nums 就不能當開頭。
3. 如果 nums-1沒有在 set 中,那就可以當開頭,計算值為1,如果 nums+1有在 set中,計算值+1,num+1。
4. 回傳最大的 curr值

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# result
res = 0
# 轉成set存,拿掉重複的數字
nums_set = set(nums)
# go over the array = nums
for num in nums:
# 如果 nums-1 存在 nums_set中,num不能作為起始點,跳過
if num-1 not in nums_set:
# 沒有在nums_set中,就可以開始計算長度
curr = 1
# 假設 nums+1有在nums_set中
while num+1 in nums_set:
# num +1,長度cur +1
num += 1
curr += 1
# 檢查有沒有比之前的result還要大
res = max(res,curr)
return res

Link : https://leetcode.com/problems/increasing-triplet-subsequence/

Problem:
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

圖來自leetcode

Thoughts:
1. 直接跑array內的值(nums[i] < nums[j] < nums[k])做比較,i<j<k這個照迴圈跑就可以達成。
2. first, second先設為 infinity,然後比較小的值取代掉 first, second
3. 假設 nums =[2,1,5,0,4,6]
num, first, second = [2, 2, inf]
num, first, second = [1, 1, inf]
num, first, second = [5, 1, 5]
num, first, second = [0, 0, 5]
num, first, second = [4, 0, 4]
num = 6, [0, 4, 6]

Solution:

class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first = float('inf')
second = float('inf')
for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
return True
return False

time complexity = O(n)

Link :https://leetcode.com/problems/container-with-most-water/

Problem :
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.
找到最大長方形面積。使用兩個pointer來實作,計算每次的長方形面積大小,將比較矮的邊長往下一個位置移動(盡量保留較大的值)。

圖來自leetcode

Thoughts:
1. 使用兩個指針(right, left)來檢查哪裡是max_area。
2. 每次都先計算出當下的area,放到max裡面進行比較。
3. 計算完後完後開始移動指針,將較小的值往中間靠近。

Solution:

class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0
left = 0
right = len(height)-1
while left<right:
tmp = min(height[left],height[right]) * (right-left)
max_area = max(max_area, tmp)
if height[left]<height[right]:
left += 1
elif height[left]>height[right]:
right-=1
else:
left+=1
right-=1
return max_area

Link : https://leetcode.com/problems/jump-game/

Problem :
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.
有一個array nums,起始位置在 first index,每一次前進的值為nums[i],試問是否在array結束前來到最後最後一個數上。

圖來自leetcode

Link : https://leetcode.com/problems/pascals-triangle-ii/

Problem :
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

圖來自leetcode

Thoughts :
1. 只 return 該行的結果。
2. 先計算該行會有幾個數字。
(Note : rowIndex從0開始)
3. 每一行的結果都是上一行的兩個數字、兩個數字加起來的。並且每一行的第一個數字都是1。
ex:
第二行為 0, 1, 1, 0
第三行為 0+1, 1+1, 0+1 = 1, 2, 1
(Note:從後面開始加,第四位跟第三位開始加,第三位跟第二位,第二位跟第一位)
如果從前面開始加會變成:
第二行為 0, 1, 1, 0
第三行為 0+1, 1+1, (1+1)+1 = 1, 2, 3 ->會出現問題,所以從後面開始加3. 4. return 結果。

Solution :

class Solution:
def getRow(self, rowIndex: int) -> List[int]:
result = [1] + [0]*rowIndex
for i in range(rowIndex):
result[0] = 1
for j in range(i+1,0,-1):
result[j] = result[j] + result[j-1]
return result

time complexity = O(n²)?, space complexity

jojo lee

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store