嘗試幾道算法題，提升python編程思維

一、跳躍游戲

題目描述：
給定一個非負整數數組?nums，你最初位于數組的第一個下標。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最后一個下標。

示例：

輸入：nums = [2,3,1,1,4]?→ 輸出：True
輸入：nums = [3,2,1,0,4]?→ 輸出：False

---------------------------------------------------------------------------------------------------------------------------------

代碼實現：

def can_jump(nums):max_reach = 0n = len(nums)for i in range(n):if i > max_reach:  # 當前位置無法到達，直接失敗return Falsemax_reach = max(max_reach, i + nums[i])if max_reach >= n - 1:  # 已覆蓋終點，提前成功return Truereturn max_reach >= n - 1  # 遍歷結束后判斷

詳細解析：

核心變量：max_reach?記錄當前能到達的最遠索引，初始為 0（起點）。
遍歷邏輯：
- 若當前索引?i?超過?max_reach，說明該位置不可達，直接返回?False（因為無法從前面的位置跳到這里）。
- 計算從當前位置?i?能跳到的最遠距離?i + nums[i]，并更新?max_reach?為兩者中的較大值（確保始終記錄最遠可達位置）。
- 若?max_reach?已覆蓋數組最后一個索引（n-1），說明可到達終點，提前返回?True?以優化效率。
邊界處理：若遍歷完所有位置后?max_reach?仍未覆蓋終點，則返回?False（題目中大部分情況可提前判斷，此處為兜底）。
貪心思想體現：無需記錄具體路徑，只需通過局部最優（每次更新最遠可達距離）推導全局最優（是否能到終點），時間復雜度 O (n)，空間復雜度 O (1)。

二、最長遞增子序列（動態規劃解法）

題目描述：
給你一個整數數組?nums，找到其中最長嚴格遞增子序列的長度。子序列是由數組派生而來的序列，刪除（或不刪除）元素而不改變其余元素的順序，且子序列嚴格遞增。

示例：
輸入：nums = [10,9,2,5,3,7,101,18]?→ 輸出：4（最長子序列為?[2,3,7,101]?或?[2,5,7,18]）

---------------------------------------------------------------------------------------------------------------------------------

代碼實現：

def length_of_lis(nums):if not nums:return 0n = len(nums)dp = [1] * n  # 每個元素至少自身是一個子序列for i in range(1, n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

詳細解析：

動態規劃數組定義：dp[i]?表示以?nums[i]?為結尾的最長嚴格遞增子序列的長度。初始值均為 1（每個元素自身構成長度為 1 的子序列）。
狀態轉移邏輯：
- 對于每個?i（從 1 到 n-1），遍歷所有?j < i：
  - 若?nums[j] < nums[i]，說明?nums[i]?可接在?nums[j]?后面形成更長的子序列，因此?dp[i]?可更新為?dp[j] + 1（與當前?dp[i]?取最大值，確保記錄最長長度）。
結果計算：遍歷完所有?i?后，dp?數組中的最大值即為整個數組的最長遞增子序列長度。
示例驗證：以?nums = [2,5,3,7]?為例：
- i=0：dp[0] = 1（初始值）。
- i=1（nums[1]=5）：j=0?時?nums[0]=2 < 5，故?dp[1] = dp[0]+1 = 2。
- i=2（nums[2]=3）：j=0?時?nums[0]=2 < 3，故?dp[2] = dp[0]+1 = 2（j=1?時?nums[1]=5 > 3，不更新）。
- i=3（nums[3]=7）：j=0?時?dp[0]+1=2，j=1?時?dp[1]+1=3，j=2?時?dp[2]+1=3，故?dp[3] = 3。
  最終?max(dp) = 3（對應子序列?[2,5,7]?或?[2,3,7]）。
復雜度：時間復雜度 O (n2)（兩層循環），空間復雜度 O (n)（存儲?dp?數組）。

三、最長遞增子序列（貪心 + 二分查找解法）

題目描述：
同第二題（題目一致，解法不同）。

---------------------------------------------------------------------------------------------------------------------------------

代碼實現：

import bisectdef length_of_lis(nums):tails = []for num in nums:# 找到tails中第一個 >= num的位置，替換它idx = bisect.bisect_left(tails, num)if idx == len(tails):tails.append(num)else:tails[idx] = numreturn len(tails)

詳細解析：

核心思路：維護一個?tails?數組，其中?tails[i]?表示長度為?i+1?的嚴格遞增子序列的最小尾元素。例如：
- tails[0]?是長度為 1 的子序列的最小尾元素（即數組中最小的元素）。
- tails[1]?是長度為 2 的子序列的最小尾元素（即能接在?tails[0]?后面的最小元素）。
  這樣做的目的是：尾元素越小，后續越容易添加更大的元素形成更長的子序列（貪心策略）。
二分查找的作用：
- 對于每個新元素?num，用?bisect_left?在?tails?中查找第一個大于等于?num?的位置?idx（tails?始終是嚴格遞增的，因此可二分）。
- 若?idx?等于?tails?的長度，說明?num?比所有現有尾元素都大，可直接追加到?tails?末尾（此時子序列長度 + 1）。
- 否則，將?tails[idx]?替換為?num（目的是用更小的尾元素更新該長度的子序列，為后續元素留更多可能）。
示例驗證：
輸入?nums = [10,9,2,5,3,7,101,18]：
- num=10?→?tails?為空，idx=0?等于長度 0，追加 →?tails = [10]。
- num=9?→ 二分找到?tails?中第一個 ≥9 的位置是 0（tails[0]=10），替換 →?tails = [9]。
- num=2?→ 二分找到位置 0，替換 →?tails = [2]。
- num=5?→ 二分找到位置 1（超過?tails?長度 1），追加 →?tails = [2,5]。
- num=3?→ 二分找到?tails?中第一個 ≥3 的位置是 1（tails[1]=5），替換 →?tails = [2,3]。
- num=7?→ 二分找到位置 2（超過長度 2），追加 →?tails = [2,3,7]。
- num=101?→ 二分找到位置 3（超過長度 3），追加 →?tails = [2,3,7,101]。
- num=18?→ 二分找到位置 3（tails[3]=101 ≥18），替換 →?tails = [2,3,7,18]。
  最終?tails?長度為 4，即最長子序列長度為 4（與題目示例一致）。
關鍵說明：tails?數組本身不是最長子序列，但其長度等于最長子序列的長度（因為每次更新都對應子序列長度的潛在增長）。
復雜度：時間復雜度 O (n log n)（每個元素二分查找 O (log k)，k 是當前?tails?長度，總復雜度 O (n log n)），空間復雜度 O (n)（tails?最長為 n）。

四、島嶼數量（DFS 解法）

題目描述：
給你一個由?'1'（陸地）和?'0'（水）組成的二維網格，請你計算網格中島嶼的數量。島嶼由相鄰的陸地連接形成，相鄰指水平或垂直方向（斜向不算）

示例：
輸入：

grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]

輸出：3

-------------------------------------------------------------------------------------

答案：

def num_islands(grid):if not grid:return 0rows, cols = len(grid), len(grid[0])count = 0def dfs(i, j):# 越界或不是陸地，直接返回if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':returngrid[i][j] = '0'  # 標記為已訪問（淹沒）# 遞歸遍歷四個方向（上下左右）dfs(i+1, j)  # 下dfs(i-1, j)  # 上dfs(i, j+1)  # 右dfs(i, j-1)  # 左for i in range(rows):for j in range(cols):if grid[i][j] == '1':count += 1  # 發現新島嶼dfs(i, j)  # 淹沒整個島嶼，避免重復計數return count

詳細解析：

核心問題：統計 “連通分量” 的數量（相鄰陸地構成的獨立區域）。
DFS 函數作用：從坐標?(i,j)?出發，遞歸 “淹沒” 所有相連的陸地（將?'1'?改為?'0'），確保每個島嶼只被計數一次。
DFS 終止條件：
- 坐標越界（i?或?j?超出網格范圍）。
- 當前位置不是陸地（grid[i][j] != '1'，可能是水或已被淹沒的陸地）。
主循環邏輯：
- 遍歷網格中的每個單元格?(i,j)。
- 若遇到?grid[i][j] == '1'，說明發現一個新島嶼，計數器?count?加 1。
- 立即調用?dfs(i,j)?淹沒該島嶼（將所有相連的?'1'?改為?'0'），防止后續遍歷再次計數。
示例驗證：
以上述示例為例：
- 首次遇到?(0,0)?為?'1'，count=1，啟動 DFS 淹沒左上角所有相連的?'1'（第一、二行前兩列變為?'0'）。
- 繼續遍歷，遇到?(2,2)?為?'1'，count=2，啟動 DFS 淹沒中間島嶼。
- 最后遇到?(3,3)?為?'1'，count=3，啟動 DFS 淹沒右下角島嶼（(3,3)?和?(3,4)?相連）。
  最終?count=3，與示例一致。
復雜度：時間復雜度 O (rows×cols)（每個單元格最多被訪問一次），空間復雜度 O (rows×cols)（最壞情況全是陸地，遞歸棧深度為網格大小）。