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/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

--

--