項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Lintcode】python – [458] Last Position of Target 個人解法筆記

題目出處

458 · Last Position of Target

難度

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 SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython <