- J.H. Hsu·Last edited by J.H. Hsu on Sep 15, 2022Linked with GitHubContributed by
153. Find Minimum in Rotated Sorted Array
Difficulty: Medium
link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
1. Binary Search
題目限制
條件nums[mid] <= nums[-1]製造單調性[False, False, False, True, True]，binary search找到滿足條件最小的index。
python
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= nums[-1]:
right = mid
else:
left = mid + 1
return nums[left]
tags: leetcode
Read more
279. Perfect Squares
link: https://leetcode.com/problems/
Feb 9, 2024141. Linked List Cycle
Difficulty: Easy link: https://leetcode.com/problems/linked-list-cycle/ 1. Hash table $O(n)$ runtime, $O(n)$ space 用set紀錄看過的node，如果有重複就代表有cycle。 python # Definition for singly-linked list. # class ListNode:
Dec 28, 2022979. Distribute Coins in Binary Tree
Difficulty: Medium link: https://leetcode.com/problems/distribute-coins-in-binary-tree/ 1. DFS $O(N)$ runtime, $O(H)$ space 定義dfs函數，計算以node為root的subtree，扣掉每個child node需要的1枚硬幣後，總共會多（或少）幾枚硬幣。 如果硬幣有多，回傳值就是正的；如果硬幣有缺，回傳值就是負的；剛剛好不多不缺的情況，回傳值為0。 dfs函數顯示，node最少還需要幾枚硬幣（缺硬幣的情況），或著node至少要給出幾枚硬幣（多硬幣的情況），才能達成題目要求的硬幣分布。
Nov 26, 202246. Permutations
Difficulty: Medium link: https://leetcode.com/problems/permutations/ 1. Backtracking $O(n!)$ runtime, $O(n)$ space 需要列出所有排列數，可以用backtracking。用take紀錄有沒有拿過nums的第i個元素。 python class Solution: def permute(self, nums: List[int]) -> List[List[int]]:
Nov 26, 2022
HackMD