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

--

--