題目出處
難度
easy
個人範例程式碼
from typing import (
List,
)
class Solution:
"""
@param nums: An integer array sorted in ascending order
@param target: An integer
@return: An integer
"""
def last_position(self, nums: List[int], target: int) -> int:
# write your code here
if not nums:
return -1
start, end = 0, len(nums)-1
while(start + 1 < end):
mid = (start + end) // 2
if (nums[mid] == target): # find last, move start
start = mid
elif (nums[mid] < target):
start = mid
else: # (nums[mid] > target):
end = mid
else: # when quit loop
if nums[end] == target:
return end
elif nums[start] == target:
return start
else:
return -1
return -1
算法說明
基本的 binary search,採用的策略為先縮小範圍再得到答案。
也就是說 left, right 縮小至最小範圍的 left, right,再去判斷答案。
- 當然比較常見的方法是:left, right 找 mid,mid 直接找到答案會更為簡潔。
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
input handling
注意 input nums 為 [] 的時候的處理,return 個 -1 給他
Boundary conditions
start 與 end 的處理一直都是 binary search 常出錯的地方,這邊要細心一些。
我採用網路上看到的 start + 1 < end 的方式,先縮小 left, right 範圍
並且不把目標放在直接找到 mid 做為答案。
再從最小範圍 left, right 中找到最終解答。
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder | BFS (分層), DFS | Graph | Python | ||
[Lint] 127 | Topological Sorting | BFS (拓撲) | Python | 內有 indegree, outdegree 介紹 #重要題型 | ||
207 | Course Schedule | BFS (拓樸) | Graph | Python | ||
210 | Course Schedule II | BFS (拓樸) | Graph | Python | ||
[Lint] 892 | Alien Dictionary | BFS (拓樸) | Graph | Python | ||
[Lint] 431 | Connected Component in Undirected Graph | BFS (連通塊) | Graph | Python < |