電腦裡的魔法世界-希聲的部落格

2020年5月31日星期日

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"

2020年5月30日星期六

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:

2020年5月29日星期五

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，並給定三種操作方式

Insert a character
Delete a character
Replace a character

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

EX:

word1 = "horse", word2 = "ros"

Ans: 3.

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

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

step3: ros -> (刪除 e )

2020年5月26日星期二

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

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

EX:

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

Ans: "/c"

2020年5月25日星期一

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 做的事簡單來說就是把函數呼叫跟函數定義對應起來，讓編譯器知道要執行的內容。