最近的規劃

目前有一些要學習，關於CCIE，就目前來看走向不是主力，很大機會拋掉，但CCNP是已經洗下頭，所以一定會去考到手。

所以關於CCNA跟CCNP的學習是一定會完成的，弄完之後，半年維護，跟原計畫是一樣的。

看了很多文章，但心裡也沒有底到底真的會遇到怎樣程度？還是誇張了點？我看事情是很淡的，所以不一定會有那麼深的感受。如果我是客戶，一定是很要求，想著錢砸下去了，給我弄好就是了。

走SI，會不會是我一輩子的路？不好說，到三十歲以前的境遇，才會決定之後的方向，現在還沒發生，所以也不會太過擔心。

比較希望有機會能去接觸大型建置案件，我覺得這算是「成就感」。有辦法去應需求去建網路，有很多領域都要跨足，還要領導其他人跟部門，那是不簡單的事，獨當一面。

遭遇網路 Flapping

關於 Flapping ，查英文翻譯是「拍打」，一直拍打？第一時間我也沒有理解。

隨後得知 Flapping 是 up down up down 也就是斷斷續續，有時通有時不通。為什麼會發生「Flapping」至今還沒有真的理解發生的原因。

畢竟這只是一種現象，會導致這個現象的原因不只一個，可能每次發生時的問題根源都不一樣，上一次能行的辦法，下一次就不見得行的通。

最近遭遇兩次Flapping，相當棘手，還是沒有那種掌握住的感覺。

Virtual Routing and Forwarding(VRF) 學習

在 Router 設定的時候，介面的網段是不能夠重壘的，如果重壘會跳出警示。

在某些型號的 Router 如 7200 可以啟用 Virtual Routing and Forwarding (VRF)，可以當作產生一份虛擬的 routing table，跟本來的 global routing table 做出區隔。

使用 VRF ，可以在不同的介面上設定相同的IP位置，就像 VLAN 可以用邏輯上去區隔出不同LAN。於是我可以 1號介面設 10.1.1.1/24，同時用VRF在 2號介面設 10.1.1.1/24，不論接 1 或 2，都能ping通 10.1.1.1。

至於VRF的應用，就我初步來看可以做到 load sharing ，VRF也可以使用 Routing Protocol ，規劃好可以分割 routing table ，減少維護的難度吧(？)。總之先記錄一下。

之後再更多補充。 

Multiple Spanning-Tree Protocol (MSTP) 設定

對於Multiple Spanning-Tree Protocol的練習可以先看這裡。

「Jan Ho 的網絡世界 Multiple Spanning Tree Protocol (MSTP) 多重生成樹協定」

「networklessons Multiple Spanning Tree (MST)」

關於Multiple Spanning Tree Protocol的設定，有一項要注意，要設定「 truck port」，這是指南沒寫，第一項連結也沒寫到的部分。

至於更詳細的設定或實作，我想等CCNP考完再補。

先做提醒。

GNS3的分頁式終端機軟體第二選擇 -- Super-Putty

跟 GNS3 一起搭配的終端機軟體 Solar-Putty，本身是可以分頁的，也就是可以把GNS3開啟的telnet等集中在同一個視窗。

用過 Packer Tracer 的人就知道，今天如果有八個設備點開，就會有八個子視窗，這使切視窗的操作變得難一些，甚至需要去尋找目前要設定設備是哪個子視窗。

原本搭配 GNS3 的 Solar-Putty 是預期可以發揮這項功能，但是我在第二分頁時，就會跳出「Putty」的子視窗，這沒起到分頁式的效果。但經簡單測試，改GNS3的參數是宣告無效的，如果手動在cmd輸入指令就可以是分頁式，與其這樣，倒不如換一個軟體。

Super-Putty 是以 Putty為底的，免費且開源的軟體，可以用在商業與非商業用途。

[公告]Blog ---- 2020-06-22 最近暫停寫Leetcode題解

目前(2020-06-22)

感覺要有一個可以碎碎念的地方，所以就有了這一篇。最近要準備的有點多，所以決定先暫停Leetcode題解，把時間挪給更優先的事情。

現在經營有兩大主軸︰「Leetcode題解」跟「JN的CCNA」。

手一捏，可能會停二個月，不過關於「網路」的是不會停，因為那是目前最優先的部分。

而「JN的CCNA」在準備中，等到完成 25% 就會上線，我也不喜歡看到了一堆章節，但裡面卻沒有任何內容。QQ

總之就是這樣，如果有要回來一直寫，就會再公佈。目前只會有零星的手癢來寫題解。

人生第一次面試

今天是第一次面試，有人說第一次面試一定會搞糟，嗯，感覺真的搞糟，所以面試完心裡有底了。但也感謝這場面試讓我知道哪裡不足，下次可以改進。

自己在面試上還有很多可進步的地方，讓我了解自己的不足，最近接踵而來的面試邀約，也不知道有辦法可以短時間內就完成改進。還是一句「best effort」。

雖然是第一次面試，但我倒是不緊張，畢竟也不知道會問什麼。過程中令我最難應付的是：解釋「網路」，網路是個很大的領域，如果是科普的，那不是問題。但如果是要講給對網路有很好了解的人，面試官，那要講什麼才能反映當前的水準，如果講太淺，又顯得很普通。

GNS3安裝與設定教學(2.2.10) ※疑難：GNS3無法順利連上VM。(VMware Player)

今天要來把GNS3的一步一步安裝完成，因為安裝設定是對於網路初學者是有一點困難，這裡以「沒有經驗」的為對象，如果有經驗了，也不一定要照做。

官方的安裝教學(Windows)，如果不排斥看英文，個人認為這裡更好。

第一步：下載 GNS3

上GNS3官網，點 Download，然後會要求要有GNS3的帳號。註冊後，就能下載。

下載 GNS3

Leetcode題解 Python & C#六月挑戰DAY20 Permutation Sequence

給一個數字 n  代表有 [1,n] 個數字要排列組合，k 代表要找第 k 小的，找出後回傳。

這題一看到時，我想起姊妹題的排列組合找下一個，使用兩兩交換，但這題不是。

這題的限制條件使n最多只有9個，也不重複，因此，使這題可以用規律性去找解法。

如：123 一共有六種組合。

123

132

213

231

312

321

Leetcode題解 Python：六月挑戰DAY19 Longest Duplicate Substring

給一字串 S，要找出最大的重複連續字串，重複字串可部分重壘。

參考︰力扣 

在這題出的這天，感覺最近要開始爆忙，也在想要不要先斷一下寫題解？但這題有難度，還是想把它做掉。

這題要用到「Rabin-Karp 's algorithm」，用來字串搜查，使用方法是把子字串做Hash轉換去對比。

但我從頭開始講，為什麼得用 Rabin-Karp 's algorithm ？

要從一字串內找的重複出現子字串時，會使用 suffix Array，中文是後綴表。

Leetcode題解 Python & C#：六月挑戰DAY18 H-Index II

給一個升序排列的非零非負的整數數列 citations ， citations[i] 代表第 i 篇論文的引文次數。

找出一個 H-Index 代表至少有 n 篇被引用 n 次，要取最大值回傳。

這是一個 Rank 的排序與篩選，可以想像從 1 開始，如果有 1 篇大於 1 次就往下進行，換成看 2 。

因為是數目也是條件，所以加上計數，如果慢慢往上加到當 citations[i] > n - i 時，那就代表不合格。

題目有提示用 O(logN) Time 解決，有個經典的方式是這樣的時間複雜度：二分搜查法。

Wildcard Mask 用Python計算去簡化輸入

Repl.it (線上執行Python) ※支援手機(Android  IOS)

OneWildcardMask: 將輸入的IP位置用一組Network和WildcardMask表示。

MultiWildcardMask: 用一或多組Network和WildcardMask去表示所有輸入的IP的。

昨天教到 wildcard mask，打開我對 wildcard 只是二進位下該位 wildcard mask 為1就任意，為零就只能是 network 對應的值，這種淺的見解。

wildcard本身有萬用字元的意思，也就是通配，這也能與 wildcard mask 二進位為1就任意(01)起到關聯。

就計算結果上來看，wildcard mask 不是 subnet mask 的相反，而是比 subnet mask 計算更複雜的值。比起翻作「反遮罩」，我認為稱之「通配遮罩」更適合。

wildcard mask 用意是為了減少路由的輸入，也就是可以 match 到多網段，如果設定的好，可以用一行就涵蓋多個網段，可以減少路由器的負荷。

「0.0.0.0 255.255.255.255」(Network, WildcardMask) 代表全部network皆匹配。在設OSPF時，也不用一個個網段輸，只用一行就能解決。

但這是有風險的，也代表該路由器是可以跟所有IP位置形成夥伴關係，一個惡意就能透過路由交換去塞滿垃圾路由或是搶走路由做 Man in Middle。

最好就只開設定內且可信的進ACL，別偷懶！但是 wildcard 計算並不是那麼直觀的，常有不同的需求，如果要手算，就怕數量一大，會很累。

如我要只要開 192.168.0.7 跟 192.168.0.15 進來，只能用一個 network 跟一個 wildcard mask 就要能表示只有該兩個位置會被挑中。

二IP位置前方三部分 192.168.0 都一樣，所以可知 wildcard mask 的前三部分是 0.0.0。

到了第四位就會有些不同，這裡得換成二進位去看其運作。

二進位      十進位

00000111 <= 7 (IP 1)

00001111 <= 15 (IP 2)

 

在左方數來的第五位，同時出現 0 和 1，那代表該位應該要通配。其餘位置上只有 0 或 1 單獨出現，所有是固定的。

0000*000 => 00001000 => 8 (wildcard)

於是得到 wildcard mask 應該是設為 「0.0.0.8」。

Leetcode題解 Python & C#：六月挑戰DAY17 Surrounded Regions

給一個二維的串列，其元素為 'X' 或 'O' 要把所有 'O' 被 'X' 包圍的換成 'X'。

這規則有點像圍棋，圍住就吃掉。

那有好幾種思路：

最直觀的，就是遇到一個 'O' 時，檢查其四周是否為 'X'，然後如果檢查時遇到 'O'，就延伸檢查。

或者變體，直接檢查 'O' 的上下左右到邊際是否有 'X' 出現，然後給標記，最後檢查標記四周只有標記與 'X'，就換成 'X'。

走到這裡，只有一種狀況會需要特別小心，就是在邊際的 'O' ，如果有碰到，就會產生要當心的狀況。

換個思考，與其費心找四周，不如把邊際或與之相連的 'O' 抓出來，其他都改成 'X' 即可。

Leetcode題解 Python & C#：六月挑戰DAY16 Validate IP Address

給一個字串 IP ，回傳其屬於 IPv4 或 IPv6 或都不是 Neighter。 

如果要找「合格」的字串，會想到用 re 去解決，這是在一般的情況下。如果是LeetCode，也許就不會用它。

不過官方的解法是有用到 re 的，直接傻眼，但那確實是最正當的解法。

通過「正則表達式(Regex)」是最嚴謹的做法，但也要有支持這項功能，在未知跟沒有的情況下，只能土炮出來。

這裡要從根本講，不論IPv6或是IPv4對電腦來說都是連續的二進位，IPv4長度為32bit，IPv6為128bit。

給人看的十進位跟十六進位是經由轉換而來的，如果換回原來的二進位形式，就只要留意是否長度是否合格就好。

所以把 string IP 轉換成連續二進位，就能輕而易舉去找出是否為合格的IP位置。(但是寫轉換的過程不容易) 

Leetcode題解 Python：Maximum Frequency Stack

實作一個 FreqStack，類似 stack，但 pop() 會先從出現次數最高的最後一個開始，也就是 出現次數 > 位置 的順序。

這題導入了 Freq 的計數，因此要有一個計數的設計，用一個 HashTable 去記錄 val 對應的出現次數。

接下來要把 stack 套上以計數為優先的方式，出現最多次的一定先被 pop() 掉，對相同次數的來說，pop() 是正常的。

但對不同次數的來說，一定要先 pop() 光更多次的，才會輪到自己這一層。

如果連 push 五次同一個 val，那麼會是第五次的 val 先被 pop() ，才會換到第四次的 val，中間會有個換層的移動，如果已經pop()光就往下一層。

fruq = {1:[val], 2:[val], 3:[val], 4:[val], 5:[val]}

在計數的時候，各 val 計數的最高值也就是最優先要被 pop() 的那一層，用一個 MaxFreq 去記錄。

fruq[MaxFreq].pop() 過後，fruq[MaxFreq] == [] 時， MaxFreq -= 1 ，同時也要把 count[val] -= 1。

雖然標 hard，但非常快就解出了，感覺要定為 medium。不過結果我寫的跟官方的只有變數命名有差。

Leetcode題解 Python & C#：Maximum Binary Tree

給一列沒有重複的整數陣列，要建立一個 maximum tree，規則如下，並回傳其 root 。

1.The root is the maximum number in the array.
2.The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.

3.The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

root一定是陣列中最大的，最大值位置左方是左子樹的所有值，右方是右子樹的。

因此把 nums[:maxVal] 傳入到 constructMaximumBinaryTree 就可以得到左方子樹，右方也同理。

如此運作下去，最後會傳入一個空陣列，這就是「中止條件」，所以一遇到就馬上回傳 None 使其停止遞迴。

Leetcode題解 Python & C#：六月挑戰DAY15 Search in a Binary Search Tree

給一個二元樹的根，要找到值為 val 的 node 並回傳，沒有則回傳 None。

這裡的二元樹是嚴格的，即 node 的左子樹皆小於自身，右子樹皆大於自身，即二元搜尋樹。

用一個標準的二元樹遞迴函數也能順利地解找到答案。

不過那樣會找到太多不必要的部分，也沒有用上二元搜尋樹的特色。

由於左邊皆比自身小，如果 val 小於 node.val，那就往左方而去，反之則右方。相等就直接回傳。

Leetcode題解 Python：Allocate Mailboxes

給一個陣列 houses ，houses[i]為第 i 個房子的位置，k 為郵筒數，要找出最佳分配下，每房子到最近郵筒的總距離。 

如果郵筒數夠，在每房子前面設一個是最好的，但如果不夠，就會折衷，在房子間找個中間點去設立。

這其實是一個分群的問題。

要設一個郵筒，如果只有二間房子，那最佳位置會在中間。如果三間，那郵筒會在中間的房子前。

換句話說，如果房子有偶數個，在中間那二間之內都可以。如果有奇數個，那只能在中間的房子前。

找到如何決定最佳設置點，接下來就要分 k 組，找到最短的距離總和。

Leetcode題解 Python：Find Two Non-overlapping Sub-arrays Each With Target Sum

給一個正整數陣列 arr ，跟一整數 target ，最找出二子陣列各自總和皆為target且二子陣列不重壘的最小長度總和。若沒有回傳 -1。

關於找子陣列(注意要為連續的或是稱序列)總和為target，通常用計算其累進值，accu[0] = arr[0], accu[1] = accu[0] + arr[0], accu[-1] = sum(arr)。

如果 accu[i] - target 在 accu 內，就代表有對應另外一個的連續子陣列存在。透過 accu[j] - accu[i] 可以找到 arr 任位置的連續子陣列總和。

在計算累進值的同時，就可以開始找目標值，也是這種算法的優勢，如果搭配 hash類 的查詢，只要累進值算完，就能找完所有可能，相當於 O(N) Time。 

Leetcode題解 Python：Kth Ancestor of a Tree Node

有 n 個 node，編號為[0, n-1]，給一個 parent ，parent[i] 代表第 i 個 node 的 parent 為第 parent[i] 節。

然後給一 node 編號與 k ，要找出其第 k 個祖先。若沒有則回傳 -1 。

難的不是在於能不能順利找到，找到是難度 easy 的問題。難在於能不能「快速」地找到。

我在過程中有試過保存 2 跳的祖先，最糟也能在 25000 跳內解決，不過會超時。

關聯是一對一的，如果為每個node做map，即root到node的每node，就可以 1 跳解決，但是記憶體會爆，O(N**2) Space，因為每node的map都是不一樣的。

這題的關鍵在於要再哪一塊做取捨，如果純照parent跳，會用 O(N) Time。而且本題「大量」執行查詢，最多50000次，那會使沒做查詢優化的超時。

雖然我做了 2 跳祖先，但不夠，仍是 O(N) Time。如果換成保存「指數」跳的祖，就能把查詢變成 O(logN) Time，才有辦法應付大量的查詢。

依 parnet 可以找到 1(2**0) 跳的祖先，那 2(2**1) 跳的是1跳的再1跳，那 4(2**2) 跳呢？是2跳的再2跳。依此類推。

Leetcode題解 Python & C#：六月挑戰DAY13 Largest Divisible Subset

給一組不同的正整數 nums，要找出滿足條件 s[i]%s[j]==0 or s[j]%s[i]==0 之最大的集合

這題要回傳的是「最大的集合」，所以需要先知道最大的，然後再回頭生成。

要滿足條件，大的一定要是次大的乘以某整數，這樣才能歸納於同一組，同時也符合餘數的條件。

我卡了很久，因為我一直想突破 O(N^2) 的障礙，要是想到 O(N^2) 的方法就不會去嘗試，而且對於這樣的題目被太多種DP衍生的可能給卡住。

大概花了二天，才完成我的理想型，也是最初設想的數學理論版。要把想法變成方法就是難度所在，也是樂趣所在。

一個排列過的最大集合，最大的一定是其左一個乘上某數，即「因數」。而一個數的左方會接子集合有最大數目的因數。

Leetcode題解 Python & C#：六月挑戰DAY14 Cheapest Flights Within K Stops

有 n 個城市，出發地 src 目的地 dst ，以及航次表 edges : [[cityA(src), cityB(dis), price]...]，最多可轉 K 站到 dis。

要在轉K站之內，找出從 src 到 dst 的最少的總花費，如果沒有則 -1 ，有則回傳花費。

QQ，最近兩天不順，沒有順利解Leetcode，昨日的挑戰也不小心中斷了。

這是一題「Path」題，找路線不外乎就是先把 edge 串連起來，然後再開始找。

 

最常用的是 Dictionary 做映照，如 DP[0] 要映出從 city0 可到的目的地，然後看題目決定要不要雙向，這題是不用雙向。

除了位置的連結，這題還要把花費累積，因此需要不斷從各可能花費取最小的保留。

Leetcode題解 Python & C#：Insert Delete GetRandom O(1) - Duplicates allowed

這題是「Insert Delete GetRandom O(1)」的進階，連運作原理都相同。

這次允許了重複出現，也就是說，一個數值的位置保存是要能容納多個的。

這時會有 list() 或是 set() 的取捨，但是由於要在 O(1) Time 的限制，就選擇 set() 來存放同val的多個位置。

其它都跟前一題差不多，前一題能解，這題就不是大問題。

Leetcode題解 Python & C#：六月挑戰DAY12 Insert Delete GetRandom O(1)

設計一個資料結構，要在 O(1) Time 內完成 insert() remove() getRandom() 三個功能。

如果只有 insert 與 remove 那麼用 hash 系列是比較快的，不過多了 getRandom()，這使 hash 類的不能單獨使用，因為hash類的沒有 sequence 之分。
沒有序列之分，又要隨機，那就得把 hash 轉換成有 squence 的，用隨機抽一個位置。

但與其每次這樣轉換，倒不如多用一個有 squence 的做 val 的存放。更別提轉換會用到 O(N) Time。

要查 val 是否存在？去查 hash 系列的最快。要回隨機值？用有 squence 的再隨機回一個位置最快。

整合起來，val 不僅在有squence的資料類型存在，也要同時存在於hash系列。

Leetcode題解 Python：Minimum Moves to Reach Target with Rotations

有一個 n * n 大小的網格，有一條蛇佔據二格，要從 (0,0) 和 (0,1) 移動到 (n-1,n-2) 和 (n-1, n-1)。

網格上的點為 0 代表是空的， 1 代表障礙。

蛇可以往右移或往下移，或是旋轉，旋轉以左上方的那格為基準，轉朝下或右。旋轉時鄰近右下那一格必需是 0 。

這題光寫基本流程就蠻花時間的，其實並不難。

首先如果有二個點且中間有障礙，要找最短路徑。可以想像用一個越來越大的圓，圓心是出發點，最後圓納入終點的時候，其半徑即為最短路徑。

向外擴張的時候，可以把每輪向外的一步都當成新的圓半徑。為了要實現這樣的方式，不能使用 DFS ，要用像是二元樹的階層式往深探索。

起點(0,0) steps: 0，下一輪往四周 (-1,0), (0,1), (0,-1), (1,0) steps: 1，為了避免重複尋找，要把找過的位置加入 memo ，

若從 memo 找到要找的位置，就直接換下一個找。

這題蛇加入了「旋轉」，朝右或朝下會影響下一步能怎麼走，所以除了位置之外，保存狀態也是必要的。

每一步以 (row, col, state) 保存，並且在每次尋找最前方做判斷，為中止條件。

如果以一個起點出發，要是可以通，在找到路徑之前，就會先探索許多背離終點的路徑。更好的作法是再加上從終點尋找，只要二者路徑重疊到，就代表找到最短路徑。

Leetcode題解 Python & C#：六月挑戰DAY11 Sort Colors

有三種顏色，編號為 0, 1, 2。給一個陣列包含三種顏色，要在 in-place 去由小至大排序過。

Note：不要使用內建的 sort() function。

題目給了兩種方向，先 Count 後排序，二是跑一遍就完成。方向一太簡單，數完各顏色再從頭依種類、數量做替換。

二被限制只能用常數空間，換句話說，只能記沒有長度的數值。

答案一定是 0 都在陣列的最左方， 2 都在陣列的最右方。如果 pass 一遍，遇 0 往左擺，遇 2 往右擺，這樣就能快速分類。

左方擺過 0 的位置就不再使用，同理右方擺過 2 的，如果重複用到，就會破壞已經排好的序列。

因此採用 「Two Pointer」 ，而 Two Pointer 也是一個 O(1) Space 的方法。

pass 過程遇到 0 或 2 都會使左界或右界縮窄，可以想成把答案夾出來。

Leetcode題解 Python & C#：六月挑戰DAY10 Search Insert Position

給一個排序過的數列 nums 和目標值 target，要找出 目標值 insert() 到 nums 後的不影響排序的位置。 

nums是遞增(升序)排列，因此要找到一個位置 index ，該位置使 nums[index - 1] < target 且 nums[index] >= target。

可以從最前方開始找，快一點的做法是使用二分搜尋。

Leetcode題解 Python & C#：六月挑戰DAY9 Is Subsequence

給字串 s 和字串 t，找出 s 是否為 t 的子順序。子順序是相對位置不變，但中間可以刪減部分字元。

 這類的題目在LeetCode有不少，但變化性少，只會這個學會了，就能解部分類似的。

依 Follow up 的方式，我猜，要從 s 的組成字元逐一找該字元是否在 t 裡面，但我不是很懂它想表達的意思。

但沒關係，我的解法也是逐一去找的運作模式。

既然子順序的中間可以塞入非配對的字元，那可想成把那些字元拿掉後，剩下的字串跟 s 能全配對那就是 True。

從 t  的左至右搜查，如果匹對到 s[0] ，那就只能目前從 t 剩下的去匹配 s[1] ，中間沒匹配的都是可以拿掉的字元。

當 len(s) == 0 的時候，即為全匹配。如果還有 s 的字元但 t 已經到最後，那就沒有成功匹配。

Leetcode題解 Python & C#：六月挑戰DAY8 Power of Two

給一個整數，回傳該數是否為 2 的次方。

除了要注意整數 0 與負整數，其他整數都比較沒有問題。

2 的零次方是 1 ，而負次方都位於[0, 1]之間，也不是整數。所以只需要考量零以上次方要怎麼找。

如果是二的次方，除以二的餘數皆為 0，用此條件，只要餘數為 1 就不是 2 的次方。一直除到變成 1 (2**0)時，確定輸入是 2 的次方。

換一種進位，以「二進位」來看，二的次方，只會有一個bit為 1，最高位的bit為1，其餘為 0 ，所以只要判斷是否bit只存在一個1。

Leetcode題解 Python & C#：六月挑戰DAY7 Coin Change 2

給各硬幣的幣值 coins，與目標金額 amount ，要找出有幾種硬幣組合的總金額會等於 amount。

在這題琢磨了好幾小時，因為對於 DP 速度感到好奇，這題用 DFS 就是慢。

對於這種求特定組合數的題目，最重要的就是去看限制條件，再決定 DP 要取什麼要比較快。

「0 <= amount <= 5000」這意味著每道題目的答案並不是大數目，從「the answer is guaranteed to fit into signed 32-bit integer」也可得知。

如果是天文數字，就會有 % (10**9+7) ，這樣的題型不可能遍歷所有位置去解。但這題最快的方法是去跑遍所有位置。

Leetcode題解 Python：Next Greater Element I & II & III

在 contest 前，來抽一題暖手感，剛好就中這一題，有系列就依序解完吧。

(這次的contest有解完)

【Next Greater Element I】

給二個陣列 nums1 和 nums2，nums1 是 nums2 的子集合。

依 nums1 的元素找出(對應nums2位置)下一個比自身大的值。如果沒有則 -1 ，回傳所有的結果 List<int>。

由於 nums1 並非照著原來在 nums2 的相對關係排序，最快的方法是依照 nums1 的元素，在 O(N) Time 解決。

但如果從 nums2 對應的位置開始照規則找，最糟會到 O(N^2) Time。

先找出所有的答案再依 nums1 重組，時間複雜度恰好 O(MN) ，也不用在找答案過程做是否在 nums1 的判斷。

Leetcode題解 Python & C#：六月挑戰DAY6 Queue Reconstruction by Height

給一個串列 people ， 其中每一個元素為 (h, k)，h 代表自身的高度， k 代表自身前方有 k 個人的 h >= 自身。

people目前是亂的，要回傳照規則(即每個位置與其 h, k 值皆是對的)排列的串列。 

我沒有第一時想通，看了一下別人的題解。

卡在我只有想到 brute force，但沒有想到要如何簡化。

按照逆向的想法，預想本來會有一個原形只有身高的排列，然後從身高小到大從後方取出，並標上其位置(前方有位置號個比自己 h >=)

所以逆向回去，即身高由高到矮，從前方排，依序一個個放入。

由於是按身高高到矮放入，因此直接把整理好的 people 按其 people[i][1] 去 insert(people[i][1], people[i]) ，即可確保前方有 people[i][1] 比自身高或同。

而輪到較矮的 insert() 也不會影響其排列的正確性，就能順利逆向回所求。

Leetcode題解 Python & C#：六月挑戰DAY5 Random Pick with Weight

給一串正整數權重 w ，w[i] 代表 i 的權重。然後要寫一個 pickIndex 方法，以加權的機率抽出一個 i 。

雖然說 Python 的 random 模組有方法可以模擬做加權抽樣，但是速度不夠快，以致於超時，所以要減少 random 的使用，靠自己寫更有效率的代碼。

(這也是很少見的專門模組效率會遜於自撰的)

加權抽樣若以 1 為單位，把所有 index 放入一個假想的箱子，權重為 1 放1個，權重為 3 放3個，最後從中隨機抽取一個出來。

抽中 i 的機率為 w[i] / total(總權重) ，所有的機率加起來會等於 1 。若把機率從頭逐一累加，保存累進序列，這序列以權重把[0,1]之間切割區間。

用 random.random() ，可以得到一個 [0, 1] 之間的 float ，然後我們要用這個 [0, 1]之間的 random數 去對應出一個 i。

以輸入[1,4]為例，對照累進機率，若 random數 位於 [0, 0.2]，那代表抽到 0 。若 random數 位於 [0.2, 1]，那代表抽到 1。

要找出 random數 落於哪個區間，可以用二分法去搜尋，預期 O(logN) Time 。(不知道random的方法是用到 O(N) Time嗎？至少二分法比O(N)快)

如果剛好落在區間界線(如 == 0.2)要算前面的 i 還是後面的 i ？其實都沒差，根據「積分」，剛好落在 0.2 的機率為 0 ，所以不會影響到權重。

Leetcode題解 Python & C#：六月挑戰DAY4 Reverse String

寫一個功能反轉 char 陣列，在內部修改，不用回傳值。

對於初學物件導向的人，很容易用新的實例來取代原本的，不過如果是 C# 等，就得宣告才會產生新的，自然不會有混淆的問題。(比較少)

反轉字串的方式，就是最前與最後開始兩兩交換，換到 len()//2 之前停止。

Leetcode題解 Python & C#：六月挑戰DAY3 Two City Scheduling

要把 2n 個人，平分給 cityA 和 cityB，costs[i] 代表第 i 個人，costs[i][0] 代表第 i 個人到 cityA 的花費，而 costs[i][1] 則是到 cittyB。要回傳最小總花費。※去 cityA 和 去 cityB 都應該有 n 個人。

一看到題目，馬上用DP解，因為我解的上一題是也是分配的問題。不過一看到用時，就知道這不是好的寫法。

對總體來說，如果每個人都以「相對代價」較低的為目的地，就可以找到最佳分配的情形。

相對代價 costs[i][0] - costs[i][1]，我們讓前 n 個相對代價較小的到 cityA ，後面的到 cityB，就是最佳方案。  

(若有 3 個以上的選擇，就不能用這算法。)

Leetcode題解 Python：Probability of a Two Boxes Having The Same Number of Distinct Balls

有 2n 個球，球有 k 個顏色，寫成一串 k 長度 balls 陣列，balls[i] 代表第 i 顏色有多少顆球。

今天要隨機分到兩箱子，分完打開看，回傳最後兩箱子球的顏色數目相同的機率。

因為是隨機，所以拿到顏色順序不會按照顏色種類排列，例：[1,3] [3,1] ，而二者都是合規則的可能情形。 

按照真實隨機分配的方式，即一顆顆隨機抽出，運算次數會隨 k 與 sum(balls) 呈指數爆炸性成長。

如：[6,6,6,6,6,6]，會作 36! 次探討，自然會超時，要想辦法改進。

對於隨機排列組合，像是抽籤等情況，要掌握到這是「邊抽邊開」還是「抽完再開」？二者在計算上是不同的。

「抽完再開」的如此題，同顏色的順序就不重要，如：白1白3、白3白1，都視作 白白，視為同一種。

Leetcode題解 Python & C#：六月挑戰DAY2 Delete Node in a Linked List

寫一個功能去從一 linked list 中刪除一個 node，會給那個要被刪除的 node。

這題真的難到我了，在第一眼看到的時候。明明有兩個input，怎麼只傳入一個node？一旦看懂之後就很簡單了。

如果要刪除一個node，那最簡單的方式就是把它上一個跟它下一個接起來，但是這裡沒有上一個，而是直接給要刪除的node。

沒辦法修改實例位置完成，那就修改屬性。

Leetcode題解 Python & C#：六月挑戰DAY1 Invert Binary Tree

反轉二元樹。

這題被啟發的述說蠻好笑的，會寫軟體，但不會在白板寫出反轉二元樹。
有時候會被簡單卡關是難免的。

要反轉二元樹，也就是左右對調，node.left, node.right = node.right, node.left，如此運作下去到底。

我也沒有一次到位，不過很快就察覺到該怎麼寫。

Leetcode題解 Python & C#：五月挑戰DAY31 Edit Distance

給兩個字串，要找最小的編輯次數讓 word1 變成 word2。編輯只有三種操作：insert、delete、replace。

這是hard題，蠻有意思的，可以找出像是基因序列相似的程度，或是字典中找相似的詞。

如果用人的概念去想，要怎麼選，要用哪種換法，基準點在哪裡，似乎不是那麼好想像的。

但是能確定朝著每個操作，是 word1 和 word2 之間的交換。

舉例：word1 = ABC, word2 = BABC。

可以想到把 word2[0]做delete，或 word1 insert(0,"B")，就可以得到 word1 == word2。

為了好講，這裡不探討 word2 上做操作，統一以 word1 當基準，也就是只看 word1 -> word2。

像是 word1[0] == word2[1] == "A"，在這位置上不用操作，因為二者相等。說到「位置」這裡換個思考 DP[p1][p2] ，

二者的方向關係是一個表格DP，若 word1[p1] == word2[p2] ， 則 dp[p1][2] 的基本值等於0，即不需要任何操作，反之則 1。

  

題目要找出最小操作次數，也可以想像把操作數往右下角，一路取最小壘加，最後的結果就是最小操作次數。

如果 word1[p1] != word2[p2]，代表要進行操作，在 DP[p1][p2] 取 {DP[p1-1][p2-1], DP[p1-1][p2], DP[p1][p2-1]}三者最小值加 1 (基本值)。

分別對應{replace, delete, insert}三種操作中取最佳方案到DP[p1][p2] ，看 DP[p1][p2] 的「相對位置」來決定是哪種操作，本身基本值 1 有三種操作的可能，至少一定是其中一個。