LeetCode 75. Sort Colors [Medium] [C++] 解題筆記

這題給定一個與有 0, 1, 2 三種元素的 array nums，要求我們在 O(1) space 的限制下將其排序。

EX:

        Input: [2,0,2,1,1,0]

        Output: [0,0,1,1,2,2]

LeetCode 76. Minimum Window Substring [Hard] [C++] 解題筆記

這題給定一個字串 S 與 一個字串 T，要求在 S 中找到包含 T 中所有字元的最小子串。

EX:

    

        Input: S = "ADOBECODEBANC", T = "ABC"

        Output: "BANC"

LeetCode 80. Remove Duplicates from Sorted Array II [Medium] [C++] 解題筆記

這題給定一個排序好的array，要求每個元素最多只成重複出現 2 次，要求我們刪除多餘的元素，且必須要達到 O(1) space complexity.

EX:

    

        [1,1,1,2,2,3]

Ans: [1,1,2,2,3]

LeetCode 82. Remove Duplicates from Sorted List II [Medium] [C++] 解題筆記

這題給定一個排序好的 Linked list 要求刪除裡面有所有 val 重複的 node。

EX:

        Input: 1->2->3->3->4->4->5

        Output: 1->2->5

LeetCode 84. Largest Rectangle in Histogram [Hard] [C++] 解題筆記

這題給定一個 array，每個值表示一個寬度為1的bar的高度，要我們求這些所組成的最大矩形的面積。

EX:

LeetCode 74. Search a 2D Matrix [Medium] [C++] 解題筆記

這題給定一個 m x n 的陣列，此陣列每列皆是遞增排序好的，而且每列的最後一個數字一定小於下一列的第一個數字，題目要求在此陣列中搜尋特定數字是否存在。

EX:

    Input:

    matrix = [
      [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]
    ]
    target = 3

Ans: 3

LeetCode 73. Set Matrix Zeroes [Medium] [C++] 解題筆記

這題給定一個 m x n 大小的陣列，如果任一行或列中有一個元素為 0 則整行或整列皆需改為 0。

另外題目特別要求必須要在 O(1) 空間複雜度下完成 (in-place)。

EX:

    Input: 
    [
      [1,1,1],
      [1,0,1],
      [1,1,1]
    ]
    Output: 
    [
      [1,0,1],
      [0,0,0],
      [1,0,1]
    ]

LeetCode 72. Edit Distance [Hard] [C++] 解題筆記

這題是很經典的 DP 題目，非常值得練習。

題目給定兩個字串 word1 、 word2，並給定三種操作方式

1. Insert a character
2. Delete a character
3. Replace a character

要我們求將 word1 透過這三種操作轉變為 word2 所需要的最少操作次數。

EX:

        word1 = "horse", word2 = "ros"

Ans: 3.

step1: horse -> rorse (將 h 替換為 r )

step2: rose -> (刪除第二個 r )

step3: ros -> (刪除 e )

LeetCode 71. Simplify Path [Medium] [C++] 解題筆記

這題給定一個 Unix-style 系統上的路徑，要求我們將此路徑轉換為絕對路徑 (i.e. 最簡路徑 => 可以表達此路徑的最短 string)

EX:

        "/a/./b/../../c/"

Ans: "/c"

C++ virtual function 簡易理解 [Early/Static binding v.s. Late/Dynamic binding]

這篇主要是想紀錄一下自己對於 Virtual function 的理解。

首先要了解 virtual function 必須先了解 C++ 在編譯過程中的 early binding (又稱 static binding) 與 late binding (又稱 dynamic binding)是甚摸東西，所謂 binding  指的就是 "鏈結"， 那是要鏈結甚摸呢？ 就是 "定義"。對於每個函數呼叫(function call)編譯器必須知道這個函數是對應到哪個函數定義的，才有辦法知道具體要執行的內容是甚摸，而 binding 做的事簡單來說就是把函數呼叫跟函數定義對應起來，讓編譯器知道要執行的內容。

LeetCode 70. Climbing Stairs [Easy] [C++] 解題筆記

這題是很簡單又經典的 DP 題目，一定要會!

題目給定一正整數 n 表示有 n 級樓梯，爬樓梯時一次只能往上爬一級或二級，求爬上 n 級樓梯所有的方法數。

EX:

        Input: 2

Ans: 2,   一共兩種爬法，一次往上爬一級爬兩次( 1 steps + 1 steps)，直接往上爬兩級( 2 steps)。

LeetCode 69. Sqrt(x) [Easy] [C++] 解題筆記

這題給定一個整數 n 要我們求平方根。

EX:

       Input: 4

 

Ans: 2

LeetCode 67. Add Binary [Easy] [C++] 解題筆記

這題給定兩個 binary string(只含 '0', '1' 的 string)，要求我們相加兩個 binary string。

EX:

    a = "11", b = "1"

Ans: 100

LeetCode 66. Plus One [Easy] [C++] 解題筆記

這題給我們一個 "non-empty" array，表示一個數字，最左邊表示最高位，最右邊表示最低位，並保證最高位不會是 0，要求將這個 array 表示的數字加一後返回。

EX:

    [1,2,3] represent 123.

Ans: [1,2,4], represent 124.

LeetCode 64. Minimum Path Sum [Medium] [C++] 解題筆記

題目給定一個 m x n 的 array 裡面填滿 "非零整數" 求從左上走到右下的路徑中沿路的權重和最小值。

這題和 62. Unique Paths 與 63. Unique Paths II 非常的類似，都是用同樣的 DP 方法求解。

EX:

  [1,3,1]
  [1,5,1]
  [4,2,1]

Ans: 7 ,  1->3->1->1->1

LeetCode 63. Unique Paths II [Medium] [C++] 解題筆記

這題是 62. Unique Paths 的進階題，一樣給定一個 m x n 的 grid map，要我們求從左上走到右下只能往右或往下走的話，總共有幾種走法。但是 grid map 中有些位置可能是obstacle無法通行。

EX:

  [0,0,0]
  [0,1,0]
  [0,0,0]

1 表示障礙物

Ans 2

LeetCode 62. Unique Paths [Medium] [C++] 解題筆記

這題給定一個 m x n 的 grid map，要我們求從左上走到右下只能往右或往下走的話，總共有幾種走法。

EX:

        m = 7, n = 3  

Ans: 28

LeetCode 61. Rotate List [Medium] [C++] 解題筆記

這題給定一個 Linked-list 要求從移動最尾端的 node 到最前端 一共 K 次。

EX:

       1->2->3->4->5->NULL ,  k = 2

rotate 1 steps: 5->1->2->3->4->NULL
rotate 2 steps: 4->5->1->2->3->NULL

LeetCode 60. Permutation Sequence [Medium] [C++] 解題筆記

這題要求我們求出n!全排列的第k個排列方式。

EX:

        n = 3, k = 3

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

LeetCode 42. Trapping Rain Water [Hard] [C++] 解題筆記

這題給定一個array，其中array每一個位置的值表示bar (一個width為1的長方形)，要求這些bar之間形成的空洞有多大 (可以裝水的地方)。

EX:

    [0,1,0,2,1,0,1,3,2,1,2,1]

黑色 bar 的高度對應到array個項的值，藍色的部份表示由這些bar形成的空間可以留住的水。

以這個例子來說可以留住的水就是6個單位。

LeetCode 59. Spiral Matrix II [Medium] [C++] 解題筆記

這題和 LeetCode 54. Spiral Matrix 基本上是一樣的問題，差別只在於這題沒有事先填好array的內容。詳細作法可以參考之前那篇。

LeetCode 58. Length of Last Word [Easy] [C++] 解題筆記

這題要求我們找到一個字串最後一個 word 的長度，其中 word 的定義是不包含 non-space character 的最長 substring。

EX:

"Hello World"

這裡的最後一個 word 很顯然就是就是 World 其長度為 5。

特別注意空白字元有可能在字串最後面 ex: "aa " 此時最一個word為 aa。

LeetCode 57. Insert Interval [Hard] [C++] 解題筆記

這題是 LeetCode 56. Merge Intervals 的進階題，可以先寫寫看喔。

這題給定一些"相互不重疊"(non-overlapping)的區間和一個額外的區間，要求把額外的區間插入並且與原區間集合合併(如果有重疊的話)，這裡題目保證原區間集合中的區間已經按照左端點升序排序好了。

EX:

    intervals = [[1,3],[6,9]], newInterval = [2,5]

    

    額外的區間[2,5]與原區間集合裡的[1,3]區間重疊所以需要合併。

Ans: [[1,5],[6,9]]

LeetCode 56. Merge Intervals [Medium] [C++] 解題筆記

這題給定一些區間，要求把區域相互重疊的區間合併。

EX:

[1,3],[2,6],[8,10],[15,18]

其中 [1,3],[2,6] 相互重疊，所以需要合併。(剛好 interact 也算重疊,ex: [1,4],[4,5])

Ans: [1,6],[8,10],[15,18]


想法: 

LeetCode 45. Jump Game II [Hard] [C++] 解題筆記

這題是 LeetCode 55. Jump Game 的進階題，沒做過 55. 題的朋友可以先去做做看喔。

題目給定一個array，每個位置表示在這個位置上可以走得最大範圍，需要求出最少需要多少步(Jump)才可以到達最後一個位置。

注意！這題題目保證一定可以到達最後一個位置。

LeetCode 55. Jump Game [Medium] [C++] 解題筆記

這題要求我們判斷給定一個array，每個位置表示在這個位置上可以走得最大範圍，從頭開始走是否可以走到最後一個位置。

EX:

[2,3,1,1,4]

表示在第0個位置時可以往前走最多兩步->最遠可以走到第2個位置，
以此類推可以發現在第1個位置時可以走3步到達最後一個位置(4)。

LeetCode 54. Spiral Matrix [Medium] [C++] 解題筆記

這題要求我們照著一個順時針的螺旋順序輸出陣列

EX:

 [ 1, 2, 3 ]        [ 1, 2, 3 ]
 [ 4, 5, 6 ]  ===>  [ 4, 5, 6 ]
 [ 7, 8, 9 ]        [ 7, 8, 9 ]

順序：紅->黃->綠->藍->紫
輸出：[1, 2, 3, 6, 9, 8, 7, 4, 5]

想法：
    可以把這個問題想像成一個走迷宮的問題，從座標(0,0)開始往順時針方向走，
只要撞牆(i.e.超出邊界)或是遇到已經走過的路就要換方向走。

如何在ubuntu上玩steam世紀帝國(AOE)

 

    前陣子因為windows7停止更新了，用了將近8年的windows7也早已緩慢不堪，終於下定決心在我的老夥伴上裝了ubuntu。漂亮的界面流暢的系統自帶terminal一切看似美好，但就是不能玩遊戲RRRRQQQ。嘗試了好久終於在ubuntu上裝好了steam和世紀帝國(aoe)!! 簡單紀錄一下過程

希望能幫助到同好？！