武漢加油，中國加油，希望疫情早日結束，
由于疫情，二狗寒假在家不能到處亂逛，索性就在家里系統的刷一下演算法的內容，一段時間下來倒也有些小小的識訓，只是一來家中的小破筆記本寫起博客來實在不是很順手，二來家中吃喝玩樂的傭訓也不少了，就連著幾天沒有更新，慚愧慚愧，看來2020年還是要加強自己計劃的執行能力，
每個人都有適合自己的學習方式，雖然也挺喜歡看書，但對我來說，在學習新內容，不熟悉的內容的時候單純的啃課本還是有些事倍功半，尤其是像演算法這種這么容易看得一臉懵逼的內容，大名鼎鼎的《演算法導論》買回來了挺長時間了，只看了感興趣的幾章，并且在看得時候經常懷疑自己，我是不是腦子不行啊，要不轉行算了（苦笑），基于之前學習資料庫的經驗，趁著寒假整了個演算法的音頻課程聽了一下，感徑訓不錯，恩，看來我比較適合這種方式吧，以后再要學習什么新東西的時候記得提醒自己，先選對了學習的方式哈，
女朋友問我，演算法是什么，學這個有啥用? 其實之前我也沒有想明白，最開始從leetcode刷題目的很簡單，多長點見識，萬一面試用上了呢，所以女朋友這么問的時候我就隨口一胡扯：武功知道吧，之前的實戰經驗算是身法，這玩意兒（演算法）是心法，現在對這個抖機靈的回答還有點小驕傲，我還挺機智的呀，可不是嘛，各種常見的資料結構，常見的演算法，各大高級語言都幫我們實作好了，大家日常“CRUD”哪里用得上這些啊？但其實也不對，比如兩種資料結構都可以做的時候，哪種更合適呢？如果想效率更高呢？如果必須要在限制的空間內完成呢？或者接地氣一點：和同事關于內容battle的時候，怎么優雅地說服他呢？
來點干貨:
反正博客寫給自己看，記錄一下這兩天筆記中讓我有耳目一新的感覺的內容吧，
陣列：
- 陣列是一種線性表資料結構，它用一組連續的記憶體空間，存盤一組具有相同型別的資料，最大的特點是支持隨機訪問，
- 根據下標來隨機訪問陣列中的元素，所以陣列這種結構的”查找“其實很高效，
- 又因為它是連續存盤的，所以相對來說，”插入“和”洗掉“這兩個操作會比較低效，因為這兩個操作很有可能使得陣列內大量元素重新移動位置，
- 因為是連續的記憶體空間，所以如果記憶體中剩下一個40m的記憶體塊，一個60m的記憶體塊，其實是無法申請一個80m大小的陣列的，但是鏈表可以，
鏈表：
- 與陣列相反，鏈表不需要連續的記憶體，它通過”指標“來將一組零散的記憶體塊串起來使用，所以上面陣列中的那種情況，鏈表是可以完成的，
- 相對陣列來說，鏈表的”插入“和”洗掉“會高效很多，畢竟只要改變相關聯的指標的指向即可，
這兩種資料結構實在是太基礎了，基礎到基本不會用到，拿二狗子來說，如果有類似的東西需要實作的話我會怎么做呢，我會申請一個List出來，剩下的都交給List去做了，但看看上面兩中資料結構的比較，其實差別還是挺大的，而關于List，寫這篇博客的時候我又去微軟官方檔案瞅了一眼：
- List<T>類是 ArrayList<T>類的泛型等效項， 它通過使用大小根據需要動態增加的陣列來實作IList<T>泛型介面，
-
在決定是使用List<T> 還是 ArrayList類（兩者都具有類似的功能）時，請記住List<T> 類在大多數情況下性能更佳并且是型別安全的， 如果參考型別用于 List<T>類的型別
T，則這兩個類的行為是相同的， 但是，如果將值型別用于型別T，則需要考慮實作和裝箱問題， - 如果值型別用于型別
T，則編譯器將為該值型別專門生成 List<T>類的實作， 這意味著，在使用元素之前，不需要對 List<T>物件的 list 元素進行裝箱，在創建了大約500個串列元素后，不會對其進行裝箱的記憶體串列元素大于用于生成類實作的記憶體，
看來，List應該是用陣列來實作的，并且.net有一些特殊的處理使得這家伙既安全，又高效，至于第三條，看來如果要存盤的是值型別的資料，并且資料量較多的情況下還是使用List比較高效，另外微軟也是建議大家盡量使用List而不是自己手動實作，原因如下：
使用 List<T> 類的特定于型別的實作，而不是使用 ArrayList類或自行撰寫強型別包裝集合，這一點非常有利， 原因在于，你的實作必須執行 .NET Framework 的操作，并且公共語言運行時可以共享你的實作不能的 Microsoft 中間語言代碼和元資料，
堆疊
后進者先出，先進者后出，是一種”操作受限“的線性表，
佇列
先入佇列的先出佇列，后入的后出，同樣，佇列也是一種”操作受限“的線性表，
這兩種資料機構也很常見，新的發現是在做練習時遇到了這樣一道題，怎么用堆疊來實作一個佇列，題目不難，但是挺有趣的，貼一下題目與筆者的做法，題目來源于Leetcode，
232. 使用堆疊實作佇列的下列操作：
push(x) -- 將一個元素放入佇列的尾部，
pop() -- 從佇列首部移除元素，
peek() -- 回傳佇列首部的元素，
empty() -- 回傳佇列是否為空，
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 回傳 1
queue.pop(); // 回傳 1
queue.empty(); // 回傳 false
說明:
你只能使用標準的堆疊操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的，
你所使用的語言也許不支持堆疊，你可以使用 list 或者 deque（雙端佇列）來模擬一個堆疊，只要是標準的堆疊操作即可，
假設所有操作都是有效的 （例如，一個空的佇列不會呼叫 pop 或者 peek 操作），
1 public class MyQueue 2 { 3 private Stack<int> stack1; 4 private Stack<int> stack2; 5 6 /** Initialize your data structure here. */ 7 public MyQueue() 8 { 9 stack1 = new Stack<int>(); 10 stack2 = new Stack<int>(); 11 } 12 13 /** Push element x to the back of queue. */ 14 public void Push(int x) 15 { 16 if(stack1.Count > 0 ||(stack1.Count == 0 && stack2.Count == 0)) 17 { 18 stack1.Push(x); 19 } 20 else 21 { 22 while(stack2.Count > 0) 23 { 24 stack1.Push(stack2.Pop()); 25 } 26 27 stack1.Push(x); 28 } 29 } 30 31 /** Removes the element from in front of queue and returns that element. */ 32 public int Pop() 33 { 34 if (stack1.Count > 0) 35 { 36 while (stack1.Count > 0) 37 { 38 stack2.Push(stack1.Pop()); 39 } 40 } 41 42 return stack2.Pop(); 43 } 44 45 /** Get the front element. */ 46 public int Peek() 47 { 48 if (stack1.Count > 0) 49 { 50 while (stack1.Count > 0) 51 { 52 stack2.Push(stack1.Pop()); 53 } 54 } 55 56 return stack2.Peek(); 57 } 58 59 /** Returns whether the queue is empty. */ 60 public bool Empty() 61 { 62 return (stack1.Count == 0 && stack2.Count == 0); 63 } 64 }
上面的做法還行，思路是利用兩個堆疊來進行實作，而想到這個方法時其實是有點小開心的，有點靈機一動的快感，哈哈，佇列中的入隊操作會將一個元素添加到佇列中去，而這個佇列會在當前佇列中所有元素都出隊之后才會被訪問到，而堆疊呢，如果不向堆疊中添加新的元素，那么下一次出堆疊操作就會把這個元素給pop出來，因此很容易聯想到用兩個堆疊來實作，當需要出佇列的時候，我們就把堆疊中的元素依次pop，并push到另一個堆疊中，這樣最先進入堆疊中的元素反而就到了堆疊頂，剩下的就和佇列很類似了，
其實演算法的學習中還有很多”類似“的情況，但前提是你要了解兩種不同資料結構的特點與作用，優勢是什么，劣勢是什么，而資料結構與演算法也不是孤立的，比如大家都了解的各種排序，如插入排序，冒泡排序，快速排序等等都不是單一孤立使用的，比如各大高級語言的集合類一般都會提供排序方法，作為碼農我們直接拿來主義就可以使用了，但其實它們內部是會根據不同的資料量啊，大小等進行不同的處理，呼叫不同的演算法來進行實作的，這些其實也都挺有意思的，
附加一道題目:
這道題其實感覺有些類似與腦筋急轉彎，啟發是有時候可能是我們沒有按照計算機的方式去思考，反而復雜化了，反正筆者看這道題的解法和歡樂多的網友類似----原來我是個傻子，哈哈，Leetcode第6題：
將一個給定字串根據給定的行數，以從上往下、從左到右進行 Z 字形排列，
比如輸入字串為 "LEETCODEISHIRING" 行數為 3 時，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的輸出需要從左往右逐行讀取，產生出一個新的字串，比如："LCIRETOESIIGEDHN"，
請你實作這個將字串進行指定行數變換的函式：
string convert(string s, int numRows);
示例 1:
輸入: s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"
示例 2:
輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:
L D R
E O E I I
E C I H N
T S G
public class Solution { public string Convert(string s, int numRows) { if(numRows == 1) { return s; } var charArray = s.ToCharArray(); string[] resultList = new string[Math.Min(charArray.Length, numRows)]; int currentRow = 0; bool goDown = false; for (int i = 0; i < charArray.Length; i++) { resultList[currentRow] = resultList[currentRow] + charArray[i]; if (currentRow == 0 || currentRow == numRows - 1) { goDown = !goDown; } currentRow = goDown ? currentRow + 1 : currentRow - 1; } string result = string.Empty; for (int i = 0; i < resultList.Length; i++) { result += resultList[i]; } return result; } }
官方的解法傳送門在這里, 傳送門，
我原本的思路是如何把字串處理成想要的格式，然后再依次輸出，但是看了高手的解答真的很驚喜，何必這樣呢，其實我們更簡單一些，所見即所得的輸出不好嘛，每行看到的是什么就把什么輸出就好了，總之感覺十分奇妙，
這兩天還看了一些二分法和樹的內容，但是還沒找些題練練手，晚些再水一篇博客把，嘿嘿，
另外，希望疫情早點結束，大家的生活回到正規，感謝在一線奮戰的醫務作業者們，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93549.html
標籤：其他
下一篇：求歐拉函式（模板）