感覺要有一個可以碎碎念的地方，所以就有了這一篇。最近要準備的有點多，所以決定先暫停Leetcode題解，把時間挪給更優先的事情。
現在經營有兩大主軸︰「Leetcode題解」跟「JN的CCNA」。
手一捏，可能會停二個月，不過關於「網路」的是不會停，因為那是目前最優先的部分。
而「JN的CCNA」在準備中，等到完成 25% 就會上線，我也不喜歡看到了一堆章節，但裡面卻沒有任何內容。QQ
總之就是這樣，如果有要回來一直寫，就會再公佈。目前只會有零星的手癢來寫題解。
JN的電腦網路日常
網路教學與日常學習
JN的電腦網路日常
網路教學與日常學習
人生第一次面試
今天是第一次面試，有人說第一次面試一定會搞糟，嗯，感覺真的搞糟，所以面試完心裡有底了。但也感謝這場面試讓我知道哪裡不足，下次可以改進。
自己在面試上還有很多可進步的地方，讓我了解自己的不足，最近接踵而來的面試邀約，也不知道有辦法可以短時間內就完成改進。還是一句「best effort」。
雖然是第一次面試，但我倒是不緊張，畢竟也不知道會問什麼。過程中令我最難應付的是：解釋「網路」，網路是個很大的領域，如果是科普的，那不是問題。但如果是要講給對網路有很好了解的人，面試官，那要講什麼才能反映當前的水準，如果講太淺，又顯得很普通。
我沒有想過要如何對於有程度或程度遠超過我之上的人要講什麼才能獲得青睞，所以就拿家用路由器最近遇到的問題來說。我覺得很糟，自認為這個題材選擇不好。面試前我預期會問一些CCNA、範圍比較明確的，我應該不會答太差。不過我也覺得要想想如何把網路講得有程度，目前想法就把一張生活圖畫出來，來把各部分簡單帶過，也許會花半小時吧，自認為可以講一小時都沒問題，講到面試官喊停為止。
回到，我這次講的家用路由器問題時，我也沒有答很明確，但其實面試官想聽的沒有我想的那麼難。
我推論是問題出在於內部，因為對外路由器能ping通外部，但電腦無法，只能通到對外路由器。我的想法是dhcp出了問題，ip 位置可能重疊到， 因為dhcp發送範圍有包含電腦自設的靜態位置。重新啟動家內的路由器跟修改Ip位置（不要在dhcp的範圍）就能解決。
當下其實我想到「arp」去查，但是不是在電腦端用「arp」，而是要在中間的路由器上，不過路由器是GUI模式，就不能直接能輸入 arp 去查，所以就沒有回答。最後也只能講用ping，結果面試官也這樣認同。不過ping能查的未必是ip重疊的情況，沒有直接影響。
面試官說IP重疊只要接一個Switch在中間就能查，這是基本，我也這麼覺得。
不過家用環境不會多一顆Switch，雖然其實大部分的家用router是多功能的，也能變成layer3 switch，但也不會有一台多的。以我的偏好來說，不改變topology 的情況下，能查出來是最好的。所以這種方法，可行，但不是最佳解。
照我的推論，應該要用「arp -a」或是「dhcp binding」查是否為這個問題。
沒提到的是，以前也常發生這樣的問題，只要電源拔插就能解決。但是沒有真的把問題找出來過，這是我的不足。
更大的敗點是我沒有補充得更多細節，也許畢竟CCNA還太菜，自從我看到NP就知道還有很多進步空間，但不代表NA不能參與網路問題的討論，如果有想法，也可以分享，不然會被覺得沒學好。如果碰到這樣的問題，就主動跟面試官分享自己的看法，同時這樣的人，也比較是公司想要的人，下次我有這樣的時我應該多說一些自己的看法。
這次面試走誠實流，誠實必然會有一些弱點，但不會心虛，這是第一次也不用太斤斤計較因為，有了第一次，才能在後面有更好的應對。面試主要是給印象，要讓人真心覺得你就是這樣人，如果有吹噓，那可能會被明眼識破。誠實流也蠻對我的味，下次面試會改進一些說法，讓一些經歷有更好的解釋。
最後，也感謝這場面試讓我知道哪裡不足，下次可以改進。
GNS3安裝與設定教學(2.2.10) ※疑難：GNS3無法順利連上VM。(VMware Player)
今天要來把GNS3的一步一步安裝完成，因為安裝設定是對於網路初學者是有一點困難，這裡以「沒有經驗」的為對象，如果有經驗了，也不一定要照做。
官方的安裝教學(Windows)，如果不排斥看英文，個人認為這裡更好。
第一步：下載 GNS3
上GNS3官網，點 Download，然後會要求要有GNS3的帳號。註冊後，就能下載。
 |
| 下載 GNS3 |
第二步：安裝 GNS3
 |
| 一路按「Next」或「I Agree」 |
 |
| 如果沒有VM檔的可以勾選，可以先把VM檔下載回來，但一般不用勾。 至於Tools，新手全勾選，有些是必須安裝才能順利使用。 |
| 官方對於Tools的簡短敘述 |
 |
| 選一個VM Type的VM檔 (個人建議選 VMware Workstation) |
VMware跟VirtualBox蠻大型就不在這裡多介紹，Hyper-V是Windows10的才有的，而且在職缺來說，使用Hyper-V的也有不少數。
一路往下跑安裝，「Solar-PuTTY」會要填Email的，填一下，因為之後GNS3會預設使用，到時還是得填才能使用，不然就要改設定。
第三步：設定 GNS3
 |
| 首次進入GNS3，會看到這個畫面。 |
 |
| 沒有特別需求就按「Next >」 |
下一步會做一些GNS3 VM的設定，此時選 VMware。如果是純新手，這個時候需要把VM Software，給安裝完成，而且 GNS3 VM的VM檔還沒有匯入到 VM Software。最後，VM Software 裡面要有「GNS3 VM」才能順利執行。
不同的VM Software會對應不同的VM檔，如果安裝中沒有下載的，VM檔可以到官方下載。
 |
| 需要先在VM Software匯入VM檔才能下一步 ※CPU數跟記憶體預設為 1、2048MB，VM檔預設也是如此，二者建議相同。 若第一次用就不去改參數，因為用預設下，二者也會一致。 |
如果是新手，而且又用「VMware Workstation Player」的，接下來是
「十分重要」
除了「WMware Wokstation Player」還需要「VMware VIX」才能讓GNS3順利執行VMware的GNS3 VM。
安裝二者後，打開WMware，去匯入VM檔。(圖為15版，但14版也一樣。)
 |
| 先打開VM Software，這裡以「VMware」為例。 |
 |
| 然後把剛下載的VM檔ZIP解壓縮後匯入VM檔。 |
 |
| 如果第一次沒有設定好，之後可以在這裡設定。 |
 |
| 如果有順利設定好，GNS3 VM要亮綠燈。 而且，在每次開GNS3時，都會自動用VMware打開VM。 |
最後要測試VM是否能連上Internet，如果可以，後面就能專注要模擬練習的部分。先參考「GNS3模擬器」的「如何找到GNS3適合的Router與Switch」，加入一些可用的設備後，就可以開始使用GNS3做模擬設備練習。
 |
| VM進入「Test」測試，就可以知道VM是否能上網。 |
疑難雜症區
GNS3無法順利連上VM。(VMware Player)
22020-06-23，不知道是昨日Windows更新的問題，今天用GNS3無法連到VM，然後跳出一個訊息：
「Error while getting the VMs: The server vm is not a GNS3 server or it’s a 1.X server」
意思很簡單，就是目前的VM被認為不是GNS3 VM。
打開GNS3可以順利啟動VM，那最簡單的方法是重載一次VM，重設定，這樣就完成了第一步驟。
對於「VMware」來說，必須先在GNS3內去跟VMware產生的Host介面(VMnet1)連結，才能順利跟VMware產的VM做連結。
如果是用DHCP的，經過這一步驟也能讓VMware 虛擬 Host 介面跟VM做連結，然後介面會取得一個以DHCP方式得到IP位置，接下來用電腦就能ping到VM就能通。
作者用過「Vitual Box」跟「VMware」目前只在VMware發現需要有這個步驟。
 |
| 打開GNS3，GNS3也順利執行VM，但發現VM不通 |
 |
| 拖曳 Cloud 跟 VPCS (在 local server) 對 Cloud 按右鍵點 Console |
 |
| 勾選「Show special Ethernet interfaces」 然後上方切到「VMware Network Adapter WMnet1」 點「Add」 |
 |
| 按下OK後，把 PC1 跟 Cloud 的 VMnet1 接起來。 |
 |
| 啟動PC1，然後進入Console |
 |
| 這時用「CMD」打「ipconfig」去查「VMnet1」的位置 參考並選一個IP位置要做為PC1的IP位置。 (不知道的可以拿尾碼加1，此例為10.1.1.4) |
 |
| 設定IP位置，並 嘗試Ping VMnet1(位置在ipconfig可查) 嘗試Ping VM(寫在VM的資訊頁) |
 |
| 檢查GNS3 VM是不有亮綠燈 沒有則重啟GNS3，再看是否有沒有亮綠燈 |
Leetcode題解 Python & C#六月挑戰DAY20 Permutation Sequence
給一個數字 n 代表有 [1,n] 個數字要排列組合，k 代表要找第 k 小的，找出後回傳。
這題一看到時，我想起姊妹題的排列組合找下一個，使用兩兩交換，但這題不是。
這題的限制條件使n最多只有9個，也不重複，因此，使這題可以用規律性去找解法。
如：123 一共有六種組合。
123
132
213
231
312
321
當 k == 3 的時候，第一個數字為2，因為每一個首位數的後面只有2種組合，因些每個首位數字只佔2個，
所以透過除以區間數，就能以商去判斷當前是哪一個數字。
完成了第一步，後面下一個數字能用同樣的模式接上就能解出來了。
如果 k == 3 ，也取了第一個數字 2，剩下的 [1,3] ，可以用分治法的想法去看成子問題︰[1,3] 和 k2 的要找當前數字是什麼。
k2 是多少？因為是 k = 3 所以我們可以預期第二個數字是 1，拿 k2 去除區間大小(1)，得到的商應該是 0 才對，代表從[1,3]取位置[0]出來。
這時有一個問題，是商去決定當前是哪個數，那 k2 應該要是 0 ， 因為 0 除以 1 才會為 0，但 k / 2 = 1…1 ，餘數 1 並沒有對上 k2 去。
為什麼？因為位置系統是以 0 為首，但第 k 小是以 1 為首，所以對不上，因此只要把 k – 1 就能使位置對齊。
最後，只剩一個要取的數時，後面也沒有組合數了，不能再跑下一個迴圈，就直接把最後一個未取的數補到最後方即可。
Python
class Solution:
def getPermutation(self, n: int, k: int) -> str:
result = ""
nums = [str(i) for i in range(1, n+1)]
method = [1]
for i in range(1, n):
method.append(method[i-1]*i)
k -= 1
for i in range(n-1, 0, -1):
result += nums.pop(k // method[i])
k = k % method[i]
result += nums.pop()
return result
C#
public class Solution {
public string GetPermutation(int n, int k) {
var result = new List();
var number = new List();
var factorial = new int[9];
factorial[0] = 1;
for(int i = 1; i < n; i ++)
{
factorial[i] = factorial[i-1]*i;
number.Add(i);
}
number.Add(n);
k -= 1;
for(int i = n-1; i > 0; i--)
{
result.Add(number[k / factorial[i]]);
number.RemoveAt(k / factorial[i]);
k = k % factorial[i];
}
result.Add(number[0]);
return string.Join("", result);
}
}
Leetcode題解 Python：六月挑戰DAY19 Longest Duplicate Substring
給一字串 S，要找出最大的重複連續字串，重複字串可部分重壘。
參考︰力扣
在這題出的這天，感覺最近要開始爆忙，也在想要不要先斷一下寫題解？但這題有難度，還是想把它做掉。
這題要用到「Rabin-Karp ‘s algorithm」，用來字串搜查，使用方法是把子字串做Hash轉換去對比。
但我從頭開始講，為什麼得用 Rabin-Karp ‘s algorithm ？
要從一字串內找的重複出現子字串時，會使用 suffix Array，中文是後綴表。
suffix Array
例一：
banana，生成後綴表 => [banana, anana, nana, ana, na, a]
然後依字母大小跟長度排序 => [a, ana, anana, na, nana, banana]
拿 [i] [i+1] 去找前綴最長共同長度 => a,ana: 1, ana,anana:3 ,…
共同前綴最長部分就是題目所求，也就是取最大值。
為什麼可行？在排序的時候，就已經把性質相近，組成相似的排在一起，因此只會跟最有可能有最長共同前綴的相比。
這方法的時間複雜度很大，因此需要改良。
提示一：Binary Search。
例二：
banana 的長度為 6，因此最大重複字串的長度不會超過五，會落在[0,5]間，從中間先找長度 3 有沒有出現重複子字串，
這會比起例一每次都從長度 1 開始，還快上不少。
比較的參照是用 HashSet，取二分法的長度 m，從頭把長度 m 的子字串輪一遍，先檢查是否在 HashSet，若有就是有重複出現，沒有就把放入HashSet。
因此 banana 會從長度 3 開始，有，l = 4。接著 m = (6-4)//2+4 = 5，拿長度 5 找，沒有，r = 5。
最後 m = 4，沒有，r = 4，此時 l 3。
找到重複時，就可以回傳其對應到的位置，也不用繼續找 下去。
但是，數量一大，子字串是 string，長度相對也會爆炸式增長，這使得記憶體會巨大消耗，會超使用限制。
提示二：Rabin-Karp ‘s algorithm。
用簡單來講，就是把字串的位置跟值做 hash，然後得到一個能表示字串組合的hash值，該值若有在HashSet，就代表有重複。
把可能出現的值給一個對應值，這題只有英文小寫字母，故會有26個值，從 0 到 25 。
如果長度為2為下，hash值為0，那可對應 aa。hash值26，為ba。
例二的最大問題是「記憶體使用太多」，如果把子字串資訊轉換成hash值，hash值不超過 log2(26*26)，
也就是佔用不超過10bit，但長度為2的string，至少也16bit。因此可以有效解決記憶體使用太多的問題。
雖然目前的hash值保證為1對1，但如果這樣算，一旦長度為32以上，hash值可能有超過26**32，這值太大會在某些語言造成溢位出現。
把值對一個大數取餘，就能限制hash值的長度，也會有開始有多值對一個hash的可能，但大數夠大，發生的機率是相當的低。(大部分的hash都會去限制長度，如：MD5、SHA256)
我不是很喜歡這題，因為正確的寫法可能會過不了。
Python
class Solution:
def longestDupSubstring(self, S: str) -> str:
hashMap = dict()
count = 0
nums = []
for c in S:
if c not in hashMap:
hashMap[c] = count
count += 1
nums.append(hashMap[c])
mod = 2**64
def search(length):
SubStrHash = 0
for i in range(length):
SubStrHash = (SubStrHash*count + nums[i])%mod
hashset = {SubStrHash}
al = (count**length)%mod
for i in range(length, n):
SubStrHash = (SubStrHash*count - nums[i-length]*al + nums[i])%mod
if SubStrHash in hashset:
return i
hashset.add(SubStrHash)
return -1
n = len(S)
l, r = 0, n
end = -1
while r > l:
m = (r - l)//2 + l
res = search(m+1)
if res == -1:
r = m
else:
l = m + 1
end = res
return "" if end == -1 else S[end - r + 1: end+1]
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 解決，有個經典的方式是這樣的時間複雜度：二分搜查法。
二分搜查法要切在左方合格，右方不合格的位置，最後選擇右界。
那 H-Index 是 citations[r] 嗎？不是。
在右界與之後都是 >= citations[r] 的，也就是有 n – r 篇，H-Index 的 n 篇 n 次，若有不同，也只能取 n – r 和 citations[r] 小的為主，這樣子的 H-Index 才能合要求。
不過二者的大小關係是 citations[r] >= n – r ，然後要取小為主所以 H-Index 為 n – r。
Python
class Solution:
def hIndex(self, citations: List[int]) -> int:
if not citations: return 0
n = len(citations)
l, r = 0, n
while l < r:
m = (r-l)//2 + l
if citations[m] >= n-m:
r = m
else:
l = m + 1
return n-r
C#
public class Solution {
public int HIndex(int[] citations) {
int l = 0;
int r = citations.Length;
while(l < r)
{
int m = (r-l)/2 + l;
if(citations[m] >= citations.Length - m)
r = m;
else
l = m + 1;
}
return citations.Length - r;
}
}
testcase
[100]
[]
[1]
[0,1,3,5,6]
[0,1,2,5,6]
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」。
這套算法是最基礎的，照這套路能很輕易就手算出各種要求。
那今天有10個VLAN，也就是10個不同網段，甚至是20個以上呢？手算光寫出二進位就很花時間了，更別說可能會看錯。
那交給電腦算吧。
在 wildcard 這種通配規則在該位同時有 01 的情況下要為 1，所以拿兩兩相比來看，運行的是 XOR 計算。
也就是說如果計算結果二進位下的某位為 1，那代表該位需要通配。
因此再把兩兩XOR的結果做一次總體的OR運算，就能算出只用一行指令的限制，最小限度的wildcard mask。但這不能保證只有目標只被挑出，可能會摻一些不在設定內的。
先只考慮濃縮成一個wildcard mask 去包含所有想要在內的IP位置，寫成Python來看
"""
ips間互相做XOR得到結果一
再把結果一做OR，得到單一最低限度的wildcard mask
"""
ips = [[192,168,0,7], [192,168,0,15]]
result = [set(), set(), set(), set()]
wc = []
# 兩兩 XOR => 計算結果1
for i1 in range(len(ips)-1):
for i2 in range(i1+1, len(ips)):
for i3 in range(4):
result[i3].add(ips[i1][i3] ^ ips[i2][i3])
# 計算結果1 做 OR 總計算
for i in range(4):
num = 0
for res in result[i]:
num |= res
wc.append(num)
print(wc)
"""
再次簡化
"""
ips = [[192,168,0,7], [192,168,0,15]]
wc = [0, 0, 0, 0]
for i1 in range(len(ips)-1):
for i2 in range(i1+1, len(ips)):
for i3 in range(4):
wc[i3] |= (ips[i1][i3] ^ ips[i2][i3])
print(wc)雖然算得出來，但是因為一開始要算兩兩成對XOR，所以會至少要算 n(n-1)/2 次，如果要把一個範圍納入，如最後二位可[0, 255]間，會計算(255*255)*((255*255)-1)/1次。那會運算相當久，但對人來說，那可能是一秒就能算完的。換個想法，既然在IP位置清單內的都要能符合，不如從一個 (Network, Wildcard) 的組合，對應每一個IP位置去做一些修改，讓每一個都能符合條件。
ips = []
for l1 in range(256):
for l2 in range(256):
ips.append([192, 168, l1, l2])
wc = [[[0,0,0,0], [255,255,255,255]]]
if ips:
wc = [[ips.pop(0), [0,0,0,0]]]
for ip in ips:
for i in range(4):
wc[0][1][i] |= wc[0][0][i] ^ ip[i]
print(wc)
=> [[[192, 168, 0, 0], [0, 0, 255, 255]]]
這只要計算 (255*255) 次，明顯快很多，原來兩兩成對的XOR是可以拔除的，同時最後的輸出也已經是指令要打的格式了。
這十分接近理想，但不夠，目前仍未解決沒輸入的IP位置也可能被選中的情況。
要解決這個情況，就可能會用上多個 (Network, Wildcard) 的組合，即使用多個，也要是輸入最少次數就能處理掉。
所幸這是可以被計算出來的，最近看到 Software-Defined(SD)，如果自動用上這樣的算法，人就只要去挑出範圍或對應的處理，剩下的計算或輸入指令，就可以交給程式碼代勞。
"""
給一串可以預期整理成下方結果的IP
Network: 192.168.0.0, Wildcard Mask: 0.0.0.3
Network: 192.168.0.4, Wildcard Mask: 0.0.0.8
"""
ips = [[192,168,0,0],[192,168,0,1],[192,168,0,2],[192,168,0,3],[192,168,0,4],[192,168,0,12]]
from collections import defaultdict
wc = defaultdict(list)
"""
將 IP位置 做 summary
"""
def check(strIP, strIP2):
"""
只能有一個位置01同時出現
但如果是 * 符，二者沒有對上，就表示無法整合。
"""
dismatch = 0
pos = -1
for i in range(32):
if strIP[i] != strIP2[i]:
if strIP[i] == "*" or strIP2[i] == "*": return -1
dismatch += 1
pos = i
if dismatch == 2: return -1
return pos
for ip in ips:
strIP = "{:0>8}{:0>8}{:0>8}{:0>8}".format(*[bin(num)[2:] for num in ip]) # 換成 連續二進位 string
level = 0
pos = 0
while pos != -1 and wc[level]:
for j in range(len(wc[level])):
pos = check(strIP, wc[level][j][1])
if not pos == -1:
ip = wc[level].pop(j)[0]
strIP = strIP[:pos] + "*" + strIP[pos+1:]
level += 1
break
wc[level].append([ip, strIP])
"""
將 Summary 後的結果轉換回十進位格式
"""
result = []
for key in wc:
for NW in wc[key]:
NW[1] = NW[1].replace("1", "0").replace("*", "1")
result.append([NW[0], [int(NW[1][0:8],2), int(NW[1][8:16],2),int(NW[1][16:24],2),int(NW[1][24:32],2)]])
"""
將十進位的資料型態換成字串
"""
for each in sorted(result):
Network = ".".join([str(num) for num in each[0]])
WildcardMask = ".".join([str(num) for num in each[1]])
print("Network: {:}, Wildcard Mask: {:}".format(Network, WildcardMask))
現在人只要決定哪些IP位置在要裡面，也能確保不會有預期之外的IP會被選中。
不過這對於 Range 沒有很好的支持，如果要 0 到 255 就得一一個打。但這是前處理的範疇，本篇就不做深做探討。
Leetcode題解 Python & C#：六月挑戰DAY17 Surrounded Regions
給一個二維的串列，其元素為 ‘X’ 或 ‘O’ 要把所有 ‘O’ 被 ‘X’ 包圍的換成 ‘X’。
這規則有點像圍棋，圍住就吃掉。
那有好幾種思路：
最直觀的，就是遇到一個 ‘O’ 時，檢查其四周是否為 ‘X’，然後如果檢查時遇到 ‘O’，就延伸檢查。
或者變體，直接檢查 ‘O’ 的上下左右到邊際是否有 ‘X’ 出現，然後給標記，最後檢查標記四周只有標記與 ‘X’，就換成 ‘X’。
走到這裡，只有一種狀況會需要特別小心，就是在邊際的 ‘O’ ，如果有碰到，就會產生要當心的狀況。
換個思考，與其費心找四周，不如把邊際或與之相連的 ‘O’ 抓出來，其他都改成 ‘X’ 即可。
Python
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board or not board[0]: return
excludePos = set()
rows = len(board)
cols = len(board[0])
def searchExclude(y, x):
if y = rows: return
if x = cols: return
if board[y][x] == "O" and (y,x) not in excludePos:
excludePos.add((y,x))
searchExclude(y-1, x)
searchExclude(y+1, x)
searchExclude(y, x-1)
searchExclude(y, x+1)
for y in range(rows):
searchExclude(y, 0)
searchExclude(y, cols-1)
for x in range(cols):
searchExclude(0, x)
searchExclude(rows-1, x)
for x in range(1, cols-1):
for y in range(1, rows-1):
if board[y][x] == "O" and (y,x) not in excludePos:
board[y][x] = "X"
C#
public class Solution {
public int rows;
public int cols;
public HashSet excludePos;
public void Solve(char[][] board) {
rows = board.Length;
if(rows == 0){return;}
cols = board[0].Length;
if(cols == 0){return;}
excludePos = new HashSet();
for(int y = 0; y < rows; y++)
{
SearchExcluded(board, y, 0);
SearchExcluded(board, y, cols-1);
}
for(int x = 0; x < cols; x++)
{
SearchExcluded(board, 0, x);
SearchExcluded(board, rows-1, x);
}
for(int y = 0; y < rows; y++)
{
for(int x = 0; x < cols; x++)
{
if(board[y][x] == 'O' && !excludePos.Contains((y, x)))
{
board[y][x] = 'X';
}
}
}
}
public void SearchExcluded(char[][] board, int y, int x) {
if(y = rows){return;}
if(x = cols){return;}
if(board[y][x] == 'O' && !excludePos.Contains((y, x)))
{
excludePos.Add((y, x));
SearchExcluded(board, y-1, x);
SearchExcluded(board, y+1, x);
SearchExcluded(board, y, x-1);
SearchExcluded(board, y, x+1);
}
}
}
JN的CCNA: 如何使用
這裡依照 《CCCNA 200-301 Official Cert Guide》 這本書的目錄做章節的分類，這使得照這裡的步驟去學習是與官方指南是一致的。所以只要一回回都確實完成，就能含蓋所有範圍。
每個章節(Charpter)可以分成三個部分︰
「學習內容」：
如果有書籍或其他來源沒有寫仔細的部分，我就會補充，否則只會放上出處。這裡會按照推薦順序排列，越好的會排在前面，多寡不一定，但最少一定會有書籍。
「實作練習」：
搭配《Cisco Packet Tracer》作練習，使用的版本為「7.3」。實作可分為二種：解說型、演練型。解說型主要目的為配合當節內容作「觀察」，注重各時刻的狀況變化；演練型的會有幾種：單項設定、除錯、多項設定、設計。每個演練型的最後都要完成一些要求，如：ping通，或是切斷部分仍能正常運作。
「相關題目」：
會把題庫中相關的題目放到這裡， 針對考題內容作實作(如果有辦法的話)。
我建議每個章節分三個狀態，然後自己紀錄下來進度，確保每個部分都有完成。
1. 「 」：尚未開始
2. 「X」：已經開始但尚未結束
3. 「O」：完成
JN的CCNA: 對學習CCNA的看法
前言 – – 對學習CCNA的看法 2020.06.13
我在 2020-06-12 考到了 CCNA 的證照。
有人覺得 CCNA 的證照很好考，也許是，因為只要把「題庫」背熟，背多分，就能考過。但能考過是一回事，要考滿分又是另外一回事。2020年改版的CCNA題庫，因為還不成熟，各家答案並不一致，所以要是沒有強大的「實作」能力，只背是不可能明暸前因後果，找到一個能信服自己的答案(但不一定是正確的)。
總之，如果在台灣考，選用某中文論壇(hh)的題庫，正確率高，範圍精準，品質也好。但是我覺得還是有美中不足的地方，就是有一些關鍵敘述是漏掉的，那會「嚴重」影響解題。這現象在各版現有我看過的題庫，都有出現。
我認為不必花錢買題庫，因為不能保障買到的品質，更不能買到自己到題目會有深刻的理解。只有腳踏實地，一個個篇章逐一擊破，拿到證書才能稱上實質合格的CCNA。
CCNA的考試範圍是很大的，官方書籍(ccna certification study guide)的頁數總和就有千頁以上！新版合併各範圍成一個 200-301，因此也把各範圍拉一些到書的後面章節，分數也佔了不少。那些篇章不是 router & switch ，就好像從頭從零開始，然後多半又屬於記憶性的。先不說能看完就算厲害的，但看完只是入門，不夠，需要實作，
講這麼多，我認為CCNA是需要很多時間去精熟的，培訓課程開66小時，但那只夠把要上的都粗略講一遍，除非夠聰明，不然很難一次就照單全收，且能夠互相搭配運用。除了上課之外，練習也是很重要的，大概也要再花66小時去練實作，實作會學到的跟用到的可能是CCNP或是CCIE級別的深度。這裡的實作不只是單一項目的設定，也可能包含一些情境式的設計，或是效率優化的配置，那會用到許多CCNA會講到的協定，使根基更穩固。
我也是有上班級的，課餘花了很多時間去探索那些CCNA範圍內的知識與其運作。有CCNA證照不代表那些該會的能做得出來，懂不懂，那一眼就看得出來。CCNA並不限制一定要上他們合作機構的課程才能考試，所以課程沒上完就能考證照，沒上課也可以考試。
有證照一定是加分，會做是門檻，「會不會做才是關鍵」。
真實的工作情況大部分都是TroubleShooting，而也只有多練，過程自己一定會有不小心(遺漏或打錯)，思考可能是哪裡出了錯，去找出那些問題，並且解決掉，才有辦法去往高階去創建或維護大型且複雜的網路。
看到一些同學在練習時，一臉盲然，努力回想上次老師講了什麼指令，然後重頭輸入。他們學習充滿了挫折感，因為不知為何。一個「不小心」，就連TroubleShooting的能力都沒有，呆坐電腦前，因為他們的腦內世界沒有TroubleShooting指令，只有上課講到的指令。
這樣的學習方式是大錯特錯，我並不是嘲諷那些人或教學方式的死板，而且老師教得不錯。
「輸入指令絕對不是第一步！」
要先有一個期望或設計(目的地)，然後再想說要輸什麼指令(決定交通方式)，再輸入指令(前往目的地)，檢查(有沒有到達正確的地方)。這也是寫程式語言的標準流程。
那些學得挫折的同學，大多都沒有第一步的概念，也沒有第二步的思考與選擇，所以連去哪都不清楚，自己在搭乘什麼也不清楚，當然，所以自己此時此刻身處何方是沒有概念的，內心可能有這種感受「我是誰？我在哪？我在幹嘛？」
又或者沒有能區分「設計」與「設定」的對錯。
「設計」沒有對錯，除非是不合規則的(如router二介面設計在同一網段)。
而「設定」是跟隨設計，設定才會有明顯的對錯分別，沒照設計或是不合規則就是錯的。
能夠按設計圖施工，設定完成一個結構的人，才是「工程師」。如果每一步都要等人發號施令，那只是「工人」。這也使我在教同學時，到底要把所有指令全講，或是提示部分讓他思考，最終培育出不同程度的能力。
總之，要培養一個明確的思維思路，我都稱之「程式邏輯」。難的不是指令背不起來，而是沒辦法想到與制定一個如SOP一步一步的概念，要是能想到，指令再補上，就套方法可以用到許多領域。
最後，我的目標是「CCIE」，而且還想要有二張，因此，
關於CCNA或CCNP的學習頁面會一直作整理(更新)直到我考完CCIE第二張的半年。
這是我的規劃，在這期間內，如果有任何問題或更新，我會「Best Effort」去做，要是有幫上忙，就給個支持或留個言。
Leetcode題解 Python & C#：六月挑戰DAY16 Validate IP Address
給一個字串 IP ，回傳其屬於 IPv4 或 IPv6 或都不是 Neighter。
如果要找「合格」的字串，會想到用 re 去解決，這是在一般的情況下。如果是LeetCode，也許就不會用它。
不過官方的解法是有用到 re 的，直接傻眼，但那確實是最正當的解法。
通過「正則表達式(Regex)」是最嚴謹的做法，但也要有支持這項功能，在未知跟沒有的情況下，只能土炮出來。
這裡要從根本講，不論IPv6或是IPv4對電腦來說都是連續的二進位，IPv4長度為32bit，IPv6為128bit。
給人看的十進位跟十六進位是經由轉換而來的，如果換回原來的二進位形式，就只要留意是否長度是否合格就好。
所以把 string IP 轉換成連續二進位，就能輕而易舉去找出是否為合格的IP位置。(但是寫轉換的過程不容易)
在 IPv4 中用「.」做分隔，是用十進位的數字，分四段，每一段要有8bit。
在 IPv6 中用「:」做分隔，是用十六進位的數字，分八段，每一段要有32bit。
寫成IP轉換版，轉 IPv6 或 IPv4 的流程是大同小異的，甚至可以只用一個函數修改一些傳入參數就能變成IPv4或IPv6皆可的式子。
Python
class Solution:
def validIPAddress(self, IP: str) -> str:
deci = {*"0123456789"}
hexdeci = {*"0123456789abcdef"}
def checkIPv4(IP):
group = IP.split(".")
if len(group) != 4: return False
for seg in group:
if not(3 >= len(seg) >= 1): return False
if any([c not in deci for c in seg]): return False
if not(255 >= int(seg) >= 0): return False
if str(int(seg)) != seg: return False
return True
def checkIPv6(IP):
group = IP.lower().split(":")
if len(group) != 8: return False
for seg in group:
if not(4 >= len(seg) >= 1): return False
if any([c not in hexdeci for c in seg]): return False
return True
if checkIPv4(IP): return "IPv4"
if checkIPv6(IP): return "IPv6"
return "Neither"
Python(IP轉換版)
class Solution:
def validIPAddress(self, IP: str) -> str:
decimal = {*"0123456789"}
def covertIPv4(IP):
IPv4 = ""
seg = ""
segCount = 0
for c in IP:
if c == ".":
segCount += 1
if segCount >= 4 or not seg: return False
if len(seg) > 1 and seg[0] == '0': return False
seg = "{:0>8}".format(bin(int(seg))[2:])
if len(seg) > 8: return False
IPv4 += seg
seg = ""
elif c in decimal:
seg += c
else:
return False
if seg:
if len(seg) > 1 and seg[0] == '0': return False
seg = "{:0>8}".format(bin(int(seg))[2:])
if len(seg) > 8: return False
IPv4 += seg
return len(IPv4) == 32
hexadecimal = {*"0123456789abcdefABCDEF"}
def covertIPv6(IP):
IPv6 = ""
seg = ""
segCount = 0
for c in IP:
if c == ":":
segCount += 1
if segCount >= 8 or not seg: return False
seg = "{:0>16}".format(seg)
if len(seg) > 16: return False
IPv6 += seg
seg = ""
elif c in hexadecimal:
seg += "{:0>4}".format(bin(int(c, 16))[2:])
else:
return False
if seg:
seg = "{:0>16}".format(seg)
if len(seg) > 16: return False
IPv6 += seg
return len(IPv6) == 128
if covertIPv4(IP): return "IPv4"
if covertIPv6(IP): return "IPv6"
return "Neither"
Python(IP轉換合一版)
class Solution:
def validIPAddress(self, IP: str) -> str:
decimal = {*"0123456789"}
hexadecimal = {*"0123456789abcdef"}
def covertIP(strIP, Segs, PerSegBit, Carry, Delimiter):
def addSeg(IP, seg):
if segCount >= Segs or not seg: return False
if Delimiter == "." and len(seg) > 1 and seg[0] == '0': return False
if Delimiter == ":" and len(seg) > 4: return False
try:
seg = ("{:0>"+str(PerSegBit)+"}").format(bin(int(seg, len(Carry)))[2:])
except:
return False
if len(seg) > PerSegBit: return False
return IP + seg
IP = seg = ""
segCount = 0
for c in strIP.lower():
if c == Delimiter:
segCount += 1
IP = addSeg(IP, seg)
if not IP: return False
seg = ""
elif c in Carry:
seg += c
else:
return False
if not seg: return False
IP = addSeg(IP, seg)
if not IP: return False
return len(IP) == Segs * PerSegBit
if covertIP(IP, 4, 8, decimal, "."): return "IPv4"
if covertIP(IP, 8, 16, hexadecimal, ":"): return "IPv6"
return "Neither"
C#
public class Solution {
public string ValidIPAddress(string IP) {
if(IsIPv4(IP)){return "IPv4";}
if(IsIPv6(IP)){return "IPv6";}
return "Neither";
}
private bool IsIPv4(string IP) {
var parts = IP.Split('.');
if(parts.Length != 4){return false;}
int dec = 0;
foreach(var part in parts)
{
if(!(Int32.TryParse(part, out dec))){return false;}
if(dec 255 || (dec.ToString().Length != part.Length)){return false;}
}
return true;
}
private bool IsIPv6(string IP) {
var parts = IP.Split(':');
if(parts.Length != 8){return false;}
int hex;
foreach(var part in parts)
{
if(part.Length > 4){return false;}
if(!Int32.TryParse(part,
System.Globalization.NumberStyles.HexNumber,
null,
out hex)){return false;}
if(hex < 0){return false;}
}
return true;
}
}
TestCase
"1.1.1.01"
"01.01.01.01"
"001.001.001.001"
"301.301.301.301"
"12..33.4"
"1.0.1."
"1.-1.1.1"
"0.0.0.0"
"172.16.254.1"
"256.256.256.256"
"2001:0db8:85a3:0:0:8A2E:0370:7334"
"2001:0db8:85a3::8A2E:0370:7334"
"2001:db8:85a3:0:0:8A2E:0370:7334"
"20EE:FGb8:85a3:0:0:8A2E:0370:7334"
"2001:0db8:85a3:00000:0:8A2E:0370:7334"
"1081:db8:85a3:01:-0:8A2E:0370:7334"
"2001:0db8:85a3:0:0:8A2E:0370:7334:"
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。不過結果我寫的跟官方的只有變數命名有差。
Python
class FreqStack:
def __init__(self):
self.count = defaultdict(int)
self.freq = defaultdict(list)
self.MaxFreq = 0
def push(self, x: int) -> None:
self.count[x] += 1
self.freq[self.count[x]].append(x)
self.MaxFreq = max(self.MaxFreq, self.count[x])
def pop(self) -> int:
num = self.freq[self.MaxFreq].pop()
self.count[num] -= 1
if not self.freq[self.MaxFreq]: self.MaxFreq -= 1
return num