查詢網(wǎng)格圖中每一列的寬度

【模擬】python可以轉(zhuǎn)置完直接遍歷列（其他語言遍歷下標），然后求數(shù)字字符串形式的長度。

一個數(shù)組所有前綴的分數(shù)

【前綴和】一邊遍歷一邊計算前綴最大值 mx，以及前綴的得分之和 sm。

二叉樹的堂兄弟節(jié)點 II

【BFS】對于每個節(jié)點node來說，它所有堂兄弟節(jié)點的和，等價于node這一層所有節(jié)點值之和減去node及其兄弟節(jié)點值之和。BFS遍歷二叉樹，對于每一層，首先遍歷當前層的每個節(jié)點，通過節(jié)點的左右兒子計算下一層的節(jié)點值之和，然后再次BFS遍歷當前層的每個節(jié)點node，計算node的左右兒子的節(jié)點值之和，更新node 的左右兒子節(jié)點的節(jié)點值。

設計可以求最短路徑的圖類

【Dijkstra】輸入的圖最壞是稠密圖，用鄰接矩陣建圖。定義start為起點，dis[i]為start到i的最短路的長度，初始化dis[start] = 0，其余dis[i] = inf。首先從start出發(fā)，更新鄰居的最短路，下一步尋找除去start的dis的最小值，設這個點為x，那么dis[x]就已經(jīng)是從start到x的最短路的長度了。再尋找dis最小值時，用vis數(shù)組排除在前面循環(huán)中找到的x。

【Floyd】定義d[k][i][j]為i到j的最短路長度，并且從i到j的路徑上的中間節(jié)點(不含i和j)的編號至多為k，分類討論：如果i到j的路徑上的節(jié)點編號沒有k，那么d[k][i][j] = d[k - 1][i][j]；如果i到j的路徑上的節(jié)點編號有k，可以是做先從i到k，再從k到j，那么d[k][i][j] = d[k - 1][i][k] + d[k - 1] [k][j]。取最小值，d[k][i][j] = min(d[k - 1][i][j], d[k - 1][i][k] + d[k - 1][k][j])。初始值d[0][i][j] 為原圖中i到j的邊長，如果不存在則為inf。最終i到j的最短路長度為d[k - 1][i][j]。代碼實現(xiàn)時第一個維度可以優(yōu)化掉，即d[i][j] = min(d[i][j], d[i][k] + d[k][j])。