# wangyi > 記錄一次某大廠筆試的AC過程  ``給定一個二維 ...
wangyi
記錄一次某大廠筆試的AC過程
給定一個二維矩陣，代表一片海域，海域由土地(0)和水域(1)組成，島嶼是由最大(上下左右)4個方向的聯通的土地(0)組成的土地群，封閉島嶼則是指完全由1包圍的島嶼，請找出封閉島嶼的數量。
題中給的圖可以看到外圍的1已經用藍色標出來的了，但是真正是封閉島嶼的只有這一塊，
class Solution:
def closedIsland(self , grid: List[List[int]]) -> int:
# write code here
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
dir = [(0,1),(0,-1),(1,0),(-1,0)]
def dfs(i,j):
if i<0 or j<0 or i>=m or j >=n:
return False
if grid[i][j] == 1:
return True
grid[i][j] = 1
res = [dfs(i+dx,j+dy) for dx, dy in dir]
return all(res)
return sum(dfs(i,j) for i in range(m) for j in range(n) if grid[i][j] == 0)
這是一個比較經典的深度搜索問題，我們可以通過遍歷每個格子，當遇到土地0時進行四個方向的搜索，同時標記已經遍歷過的格子，最直接的辦法就是把他變成水域。使用all函數如果iterable的所有元素不為0、''、False或者iterable為空，all(iterable)返回True，否則返回False；
為了慶祝某游戲周年慶，策劃組正在為該游戲設計一次福利活動，他們希望推出一個迷宮尋寶小游戲，讓玩家探索迷宮中的寶箱，玩家可以在不同的寶箱中獲取不同數量的金幣，並最終通過金幣兌換游戲中的限定道具。
為了增加玩法的多樣性，策劃同學希望能夠提供2種尋寶地圖，但是每個玩家一天只能選擇一張尋寶地圖進行探索。同時策劃同學提供了寶箱價值的列表，但是這個寶箱價值能不能被合理投放在兩個地圖中尚未驗證，因此希望能藉助程式的手段來驗證寶箱價值的設計是否合理，具體要求如下:
1.每個寶箱必須目只能被放置在一個地圖中，不能重覆利用。
2.為了確保玩家獲得的獎勵數量，策劃同學提供了一個“保底值”，兩張地圖的寶箱獎勵總和必須都大於等於這個保 底值。
現在需要請你來設計投放程式，假設保底值為k，每個寶箱的價值都是正整數，並被存放乾數組nums中，需要通過返回值告訴策劃，這樣的寶箱價值能夠有幾種合理的投放方式.
由於每個寶箱只能被選擇一次，並且需要計算所有可能的寶箱組合，對於每一個寶箱，只存在兩種情況，選入當前地圖或者不選入當前地圖。同時在計算某個價值是否能通過前i個寶箱價值的組合獲取時，可能會出現重覆計算，使用動態規劃存儲子問題的結果來提高運行效率。
動態規划過程：
- 定義一個
dp[i]存儲一個地圖的寶箱總價值恰好為i的分配的方案數- 狀態轉移：對於每一個價值為v的寶箱，我們可以選擇選入或者不選入當前地圖。如果選入，則有
dp[i-v]種方案；如果不選入，則有dp[i]種方法，所以dp[i] = dp[i] + dp[i-v]- 初始化狀態：沒有任何元素時，和為0的方案數為1，所以
dp[0] = 1- 遍歷整個數組，將i>=k並且i<=total_value-k的方法進行求和
class Solution:
def countPartitions(self, nums: List[int], k: int) -> int:
n = len(nums)
total_value = sum(nums)
if total_value < 2 * k:
return 0
dp = [0] * (total_value + 1)
dp[0] = 1
for i in nums:
for j in range(total_value, i - 1, -1):
dp[j] += dp[j - i]
count = sum(dp[i] for i in range(k, total_value - k + 1))
return count
第三個設計題設計一個LRU緩存類
本文來自博客園，作者：ivanlee717，轉載請註明原文鏈接：https://www.cnblogs.com/ivanlee717/p/17644128.html
