bfs 最簡版

 from collections import deque

g = {

    'a':['b','c'],

    'b':['d'],

    'c':['e','f'],

    'd':['g'],

    'e':[],

    'f':[],

    'g':[]    

}

def trav_bfs(g,n,v):

    q = deque([n])

    v.add(n)   

    while q:

        cnode = q.popleft()

        print(cnode,end=' ')

        for nn in g[cnode]:

            if nn not in v:

                v.add(nn)

                q.append(nn)

    

v = set()

n = 'a'

trav_bfs(g, n, v)

                

# a b c d e f g 

dfs 最簡版

 g = {

    'a':['b','c'],

    'b':['d'],

    'c':['e','f'],

    'd':['g'],

    'e':[],

    'f':[],

    'g':[]    

    }

def dfs_trav(g,n,v):

    v.add(n)

    print(n,end=' ')

    for nn in g[n]:

        if nn not in v:

            dfs_trav(g, nn, v)

v = set()

n = 'a'

dfs_trav(g, n, v)

執行結果
#a b d g c e f 

VEX VR sample

 

最大化最小距離（牛棚放牛問題）

# 例題 ： # 題目： # 有 N 個牛棚位置（已排序），要放 K 頭牛， # 希望「任意兩頭牛之間的最小距離」最大化。 # 輸入： # ``` # 位置 = [1, 2, 8, 12, 17] # K = 3 # ``` # 期望輸出： # ``` # 最大化後的最小距離 = 7 # # 放在位置 1, 8, 17 # ``` # 思路： # 設最小距離為 d， # 若能成功放完 K 頭牛，代表 d 可行； # 否則 d 太大，需縮小。 # 用二分搜尋尋找最大的可行距離。 def can_place(a, k, d): count = 1 last = a[0] for x in a[1:]: if x-last >=d: count+=1 last=x if count==k: return True return False def max_min_d(a, k): a.sort() lo,hi = 0,a[-1]-a[0] while lo<=hi: m = (lo+hi)//2 if can_place(a,k,m): ans = m lo = m+1 else: hi = m-1 return ans print(max_min_d([1, 2, 8, 12, 17], 3)) # 7 # 重點概念： # 「距離越大越難放下」具有單調性 → 二分搜尋最大可行距離。

二分搜簡例

# 題目： # 某公司每天能完成 x 單位工作量，共有 n 項工作要完成。 # 請問至少要幾天才能做完？ # 例如： # 每天完成量 = 3 # 總量 = 17 # 則答案為 6 天（因為 3×5=15 <17，3×6=18 ≥17）。 # 思路： # 天數越多 → 工作越可能完成， # 這是一個「單調可行性」問題。 def min_days(w,ws): lo,hi = 0,ws ans = hi while lo<=hi: m = (lo+hi)//2 if m * w ==ws: ans = m return ans elif m*w>ws: ans = m hi = m -1 else: lo = m +1 return ans print(min_days(3, 17)) # 6 print(min_days(5, 25)) # 5 print(min_days(15, 150)) # 10 print(min_days(105, 150000000000000000150000000000000)) # Output: # 6 # 5 # 10 # 1428571428571428572857142857143

最小可能的「最大段和」-- 二分搜應用

題目（Problem） 給定一個長度為 n 的正整數陣列 A[0..n-1]，你要把它切成 恰好 k 段連續子陣列（k ≤ n）。定義每段的「段和」為該段元素總和。目標是最小化所有段和中的最大值。 必須保持原來順序、只能切割、段與段不可交錯（連續切段）。 回傳（或輸出）。 def can_split(A, k, cap): """在每段和 ≤ cap 的限制下，最少需要幾段；是否 ≤ k。""" segments = 1 cur = 0 for x in A: if cur + x <= cap: cur += x else: segments += 1 cur = x if segments > k: # 及早停止 return False return True # 需要的段數 ≤ k def minimize_largest_sum(A, k): lo, hi = max(A), sum(A) # 下界：至少要容得下最大元素；上界：全部一段 ans = hi while lo <= hi: mid = (lo + hi) // 2 if can_split(A, k, mid): # mid 可行 → 嘗試更小 ans = mid hi = mid - 1 else: # mid 不可行 → 增大容量 lo = mid + 1 return ans A ,k = [7, 2, 5, 10, 8], 2 print(minimize_largest_sum(A, k)) A ,k = [7, 2, 5, 10, 8], 3 print(minimize_largest_sum(A, k)) # Output: # 18 # 14

最小可能的「最大段和」暴力解

題目（Problem） 給定一個長度為 n 的正整數陣列 A[0..n-1]，你要把它切成 恰好 k 段連續子陣列（k ≤ n）。定義每段的「段和」為該段元素總和。目標是最小化所有段和中的最大值。 必須保持原來順序、只能切割、段與段不可交錯（連續切段）。 回傳（或輸出）最小可能的「最大段和」。 例子 A = [7, 2, 5, 10, 8], k = 2 最佳切法是 [7, 2, 5] | [10, 8]，兩段和分別為 14 與 18，最大為 18；證明不存在更小的可能，答案是 18。 a = [7, 2, 5, 10, 8] k = 2 minmax = float('inf') for i in range(0,5-1): left = a[:i+1] right = a[i+1:] print(left,right) if max(sum(left),sum(right))