Gary Lai

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

207. Course Schedule

207. Course Schedule 這一個題目的設計滿巧秒的,我個人覺得這個題目綜合了樹的遍歷(遞迴)、回溯法、動態規劃以及資料與圖形轉換的設計,外加上題目可以套用在各種現實生活問題中。所以整體而言 LeetCode 給出了中等難度,但是細節很多很需要小心的想通。 先看看題目可以怎麼想,所有的課程與其先修課程基本上就是很一顆或是很多棵樹,也就是說如果一棵樹裡面沒有任何的環,我們就知道不會有一個課程他的先修課是另外一門課,而那門課的先修課又是該堂課的情況。 目標就變得很明確,我們要找出此棵樹沒有環,但是就要回到題目看看給定的課程與先修課程的關係,這是一個數列,但是並沒有特定的排列順序,所以我們需要一個可以快速查找的課程有哪些先修課的表: table = defaultdict(list) for prerequisite in prerequisites: course, prerequisiteCourse = prerequisite table[course].append(prerequisiteCourse) 這張表就是前言一開始提到的資料與圖
Gary Lai