2020-05-23
Case 1(easy): 上山下山問題
，上山一步用U表示菇晃，下山一步用D表示完慧，起始點(diǎn)和結(jié)束點(diǎn)都是sea level屈尼。一個(gè)從sea level開始的[U,D]序列，求其中經(jīng)過了幾次valley甲捏。
思路：vallery中可能有山鞭执，但只要山的高度沒有超過vallery的深度就可以仍然算作一個(gè)vallery兄纺。也就是只要sl沒有從負(fù)值變成0，則可算作一個(gè)vallery钦奋。sl正時(shí)不考慮。設(shè)定一個(gè)sea level指標(biāo)sl朦拖，每經(jīng)過一個(gè)U則sl+1厌衔，經(jīng)過D則sl-1富寿。當(dāng)sl+1后等于0，則vallery counter+1.
def countingValleys(n, s):
if not 0 <= n <= 10**6:
return 'again'
cv = 0
sl = 0
for st in s:
if st == 'U':
sl += 1
if sl == 0:
cv +=1
elif st == 'D':
sl -= 1
return cv
Case 2 (medium): 排隊(duì)相鄰交換問題理疙，排隊(duì)的每個(gè)人有從1到n的序號(hào)泞坦，按順序發(fā)放砖顷。但是有人會(huì)bribe前面緊鄰的一個(gè)人交換位置滤蝠。每個(gè)人最多只能bribe兩次。先提供一個(gè)序列锣险，求出這個(gè)隊(duì)伍中發(fā)生了幾次bribe使得位置交換成這樣览闰。如21534压鉴，2 bribed 1(1次)，5依次bribed 3/4(2次)击蹲，累計(jì)有3次bribe婉宰。但25134這個(gè)序列則不滿足條件心包，輸出too chaotic，因?yàn)?需要bribe超過兩次才能到這個(gè)位置轮听。
思路1：復(fù)雜度為。經(jīng)過bribe調(diào)整后隊(duì)列上的元素用
表示萧锉，
是
在隊(duì)列上的索引柿隙。比較
與
的大小鲫凶，并計(jì)算比
小的元素個(gè)數(shù)
。遍歷這個(gè)隊(duì)列波附，對(duì)每個(gè)
做這樣的操作昼钻，所有
對(duì)應(yīng)的
之和
然评。得到的
就是bribe調(diào)整的次數(shù)。注意在測(cè)試中一旦
則認(rèn)為too chaotic盏求。
這個(gè)問題的假設(shè)是每個(gè)人只能bribe前面的人碎罚，不會(huì)bribe后面的人缕探，不然就not make sense了爹耗。該思路的缺點(diǎn)是復(fù)雜度高。
def minimumBribes(q):
if not 1 <= len(q) <= 10**5:
return 'again'
res = 0
for i, e in enumerate(q):
t = max(e-i-1,0)
if t > 2:
res = 'Too chaotic'
break
if i < len(q) - 1:
tl = [True for term in q[i+1:] if term-e < 0]
if sum(tl)>0:
res += sum(tl)
print(res)
思路2：一種復(fù)雜度為的算法
用到分治法倦始。
(2020.06.06 Sat)
Case 3 (medium): Power Sum問題冪之和問題。給定一個(gè)數(shù)字X山卦，和冪次數(shù)N鞋邑，找出X可以用多少種N次冪之和的表達(dá)形式。1<=X<=1000，2<=N<=10枚碗。例: X=100逾一，N=2，輸出3肮雨，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=100%3D10%5E2%3D6%5E2%2B8%5E2%3D1%5E2%2B3%5E2%2B4%5E2%2B5%5E2%2B7%5E2" alt="100=10^2=6^2+8^2=1^2+3^2+4^2+5^2+7^2" mathimg="1">共三種表達(dá)遵堵。提示用recursion。
思路：討論者給出的思路怨规，智慧得到了成長(zhǎng)。
def cal_num(X, N, num):
if pow(num, N) < X:
return cal_num(X, N, num+1) + cal_num(X-pow(num,N), N, num+1)
elif pow(num, N) == X:
return 1
else:
return 0
ans = cal_num(X, N, 1)
(2020.09.21 Mon)
Case 4 Minimal absolute difference in a list 序列中的最小絕對(duì)值
原題在這里
一個(gè)list中的元素兩兩計(jì)算差的絕對(duì)值波丰，找出其中的最小值壳坪。
如果從頭遍歷，則需要計(jì)算每個(gè)元素與其后的元素的abs diff掰烟，復(fù)雜度為爽蝴。降低復(fù)雜度，首先可以對(duì)元素排序媚赖，用復(fù)雜度為
的排序算法霜瘪，之后只需遍歷一次排序好的序列，計(jì)算相鄰元素的值惧磺，這種算法的復(fù)雜度是
即
。
def min_abs_diff(arr):
arr = sorted(arr)
ma = min(abs(x-y) for x,y in zip(arr, arr[1:]))
return ma
(2020.12.26 Sat)
尋找最大油田捻撑。有一片土地磨隘，用二維矩陣表示，如果某個(gè)地點(diǎn)有石油顾患，則相應(yīng)的位置用1表示番捂，如果沒有石油則0.有石油的土地可能相鄰(上下左右)，求一片土地上最大的連續(xù)油田江解。
分析：隨機(jī)檢測(cè)一塊土地(即矩陣中一點(diǎn))设预，該點(diǎn)有石油，則檢測(cè)其上下左右四個(gè)方向的點(diǎn)有無石油犁河，如果被檢測(cè)的點(diǎn)在之前已經(jīng)被訪問過鳖枕，則不檢測(cè)該點(diǎn)。直到遍歷整個(gè)矩陣后桨螺，找到連接面積最大的油田宾符。
在檢測(cè)過程中創(chuàng)建一個(gè)visited矩陣，記錄表示油田的矩陣中對(duì)應(yīng)的點(diǎn)是否被訪問過灭翔。
def dfs(i,j):
if i >= 0 and i < row and j >= 0 and j < col and visited[i][j] == None and oil_field[i][j] == 1:
visited[i][j] = 1
print('i: ',i,', j: ',j)
return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j+1) + dfs(i,j-1)
else:
return 0
if __name__ == '__main__':
oil_field = [ [1, 0, 0, 1, 0, 1, 0], \
[0, 1, 1, 1, 0, 1, 0], \
[1, 0, 1, 0, 1, 0, 1], \
[0, 1, 0, 0, 1, 0, 1], \
[1, 1, 1, 0, 1, 0, 1], \
[0, 0, 1, 0, 0, 1, 0], \
[0, 0, 1, 0, 0, 1, 1], \
[1, 1, 1, 1, 1, 1, 1]]
row, col = len(oil_field), len(oil_field[0])
visited = [ [None for i in range(col)] for j in range(row)]
maxof = 0
for r in range(len(oil_field)):
for c in range(len(oil_field[0])):
tmp = dfs(r, c)
if maxof > tmp:
continue
else:
maxof = tmp
print(maxof)
(2020.12.27 Sun)
艱難旅行：現(xiàn)已知一個(gè)大小為 N · M 的地圖魏烫，地圖中只有可能出現(xiàn)兩個(gè)數(shù)字：0 或 1，現(xiàn)規(guī)定如果位于數(shù)字為 0 的格子上，則下一步只能往相鄰四個(gè)格子中數(shù)字為 1 的格子走哄褒，如果位于數(shù)字為 1 的格子上稀蟋，則下一步只能往相鄰四個(gè)格子中數(shù)字為 0 的格子走。如果給定起點(diǎn)格子呐赡，則可以向上下左右四個(gè)方向移動(dòng)退客，且同一個(gè)格子不能重復(fù)走，求能在地圖中到達(dá)多少格子罚舱？
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 1 |
比如在上面的案例中以第3行第3列的0為起點(diǎn)井辜，可以到達(dá)上下左右的四個(gè)點(diǎn)，因?yàn)檫@四點(diǎn)的值都為1管闷，其中的第3行第2列的1又可以到達(dá)上下左三點(diǎn)粥脚，因?yàn)檫@三點(diǎn)的值與1不同，以此類推包个。
分析：這種類型可以通過圖的BFS來解決刷允。需要visited矩陣記錄某個(gè)點(diǎn)是否被訪問過，也需要判斷即將被訪問的點(diǎn)是否可當(dāng)前點(diǎn)的值不同碧囊。
def find_neighbours(tmp, data):
# tmp = (a,b), the index
row, col = len(data), len(data[0])
results = set()
if 0 <= tmp[0] + 1 < row:
results.add((tmp[0]+1, tmp[1]))
if row > tmp[0] - 1 >= 0:
results.add((tmp[0] - 1, tmp[1]))
if 0 <= tmp[1]+1 < col:
results.add((tmp[0], tmp[1] + 1))
if col > tmp[1]-1 >= 0:
results.add((tmp[0], tmp[1] - 1))
return results
if __name__ == '__main__':
from collections import deque
import pdb
data = [ [1, 0, 1, 1, 0],\
[1, 0, 1, 0, 1],\
[0, 1, 0, 1, 0],\
[0, 0, 1, 1, 1] ]
start_ = (2, 1)
visited = [[None for i in range(len(data[0]))] for j in range(len(data))]
q = deque()
q.append(start_)
visited[start_[0]][start_[1]] = 1 #注意visited修改的位置树灶，是append之后
cntr = 0
result = []
while q.__len__() != 0:
tmp = q.popleft()
cntr += 1
result.append(tmp)
neighbours = find_neighbours(tmp, data)
for n in neighbours:
if visited[n[0]][n[1]] == None and data[n[0]][n[1]] != data[tmp[0]][tmp[1]]:
q.append(n)
visited[n[0]][n[1]] = 1 #append之后即修改visited
print('cntr: ', cntr)
print(result)
