Array

724. Find Pivot Index

724. Find Pivot Index 這一題的目標是我們要找到在陣列中的一個索引,這個索引左側的所有數字的總和相等於右側的所有數字總和,索引的位置可能在這個陣列中的任何一個地方,取決於左側和右側每個數字的大小以及其分佈。 這一題比較直觀的想法是,那我先計算出這個陣列從左到右的累加總和,再計算出這個陣列從右到左的累加總和,這兩個陣列中如果有同一個位置剛好數字一樣,那就是我們要找的索引。 題目給的範例: nums = [1,7,3,6,5,6] accumulate_sum_from_left = [ 1, 8,11,17,22,28] accumulate_sum_from_right = [28,27,20,17,11, 6] 如果我們先計算出上面兩個數值,就可以很快地找到位置是在 3 。下面是程式的實作: class Solution: def pivotIndex(self,
Gary Lai

HackerRank Counting Valleys

Counting Valleys 這是 Hacker Rank 上面的題目,屬於多觀察類型的題目。 題目給出一個字串包含了「U」和「D」,兩個字元,一個是往上爬,一個是往下走,我們要去走這個步道,出發地和目的地都是在海平面,求這一路上有多少的山谷。 山谷的定義一段路都是在海平面以下,這段路如果都是起起伏伏的,但是沒有高過海平面的話,都是屬於同一個山谷,我們只能算做一次,題目也可以換另一個方式考,把山谷換成山脊。 老實說題目屬於簡單,不過我還是想了很久才想到要怎麼解,我試過從我知道的演算法,二分搜索,雙指針來做,我覺得不是做不出來,不過寫下去會發現題目給的限制鬆散(山谷的定義),遇到程式碼限制鬆散的情夼,寫起程式來一直要去判斷各種 Coner cases ,反而很容易遇到錯誤。 於是我就畫圖,如果要判斷是不是山谷,很重要的一點是要找一路上海平面轉折的地方在哪裡,因為有海平面的地方,就是山谷山脊的交界處,這時候很建議可以畫張圖看看,畫完就會觀察到,從山谷的頭尾去看,山谷從海平面開始的起始點,下一個位置一定是往下走的,山谷的終點上一個位置一定是往上走的。我們要判斷的條件就只剩下上
Gary Lai