LeetCode 87. Scramble String [Hard] [C++] 解題筆記

這題給定兩個長度相等的的字串 s1, s2，要我們判斷 s1 是不是 s2 的 scrambled string，所謂 scrambled string 是指說將 string 用 binary tree 的方式切割，若透過 swap 某些 non-leaf node 的兩個子節點的位置可以使 s1 變成 s2 的話就說 s1 is a scrambled string of s2.

EX:

     s1:                                 

    great                
   /        \
 gr       eat
 / \        /  \
g  r     e   at
          / \
        a   t

    s2:

    rgeat
   /        \
 rg       eat
 / \        /  \
r   g    e   at
          / \
        a   t

Ans: True,  可以透過交換 s1 中 gr 的兩個子節點來將 s1 轉成 s2。

LeetCode 97. Interleaving String [Hard] [C++] 解題筆記

這題給定三個字串 s1 , s2 , s3，要我們判斷 s3 是否可由 s1, s2 "交錯" 組合出來。

EX:

        s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

        Ans: True

LeetCode 3. Longest Substring Without Repeating Characters [Medium] [C++] 解題筆記

這題給定一個字串，要我們找出字元不重複的最常子串(longest substring)的長度。

EX:

        Input: "abcabcbb"

        Ans: 3 

LeetCode 2. Add Two Numbers [Medium] [C++] 解題筆記

這題給我們兩個 Linked List，並保證最後一個 node 值都不為 0，要求我們將兩個 list 的reverse order 當成兩個數字相加。

EX:

         Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

        Output: 7 -> 0 -> 8 ,  342 + 465 = 807

LeetCode 1. Two Sum [Easy] [C++] 解題筆記

LeetCode 第一題一定要寫一下拉，這題給定一個 array 與一個 target value 要求我們從 array 中找到兩個數字和為 target，並保證一定且唯一存在一個解 。

EX:

        nums = [2, 7, 11, 15], target = 9

        Ans: [0, 1] , nums[0] + nums[1] = 9

LeetCode 85. Maximal Rectangle [Hard] [C++] 解題筆記

這題給定一個 2D array ，裡面只包含 "1" 或 "0" ，要我們求由 "1" 組成的最大矩形面積。

EX:

      [

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

    Ans: 6

LeetCode 83. Remove Duplicates from Sorted List [Easy] [C++] 解題筆記

這題給定一個 Linked List ，要求我們刪除裡面重複出現的數字。

EX:

        Input: 1->1->2->3->3

        Ans: 1->2->3

想法:

    這雖然是一題 easy 的題目，但還蠻有意思的很值得練習，雖然要寫出來不難，但要寫得

簡潔也是需要一定程度的練習，尤其對指標的理解需要夠清晰。

LeetCode 79. Word Search [Medium] [C++] 解題筆記

這題定一個二維陣列，每個位置包含一個字母，並給一個 target string word，要求檢查在 array 中的字母往左右或是上下相連是否可以組成 word。

EX:

          board =

    [
      ['A','B','C','E'],
      ['S','F','C','S'],
      ['A','D','E','E']
    ]
    

    word = "ABCCED", return true.

LeetCode 86. Partition List [Medium] [C++] 解題筆記

這題給定一個 Linked List 與一個 target value x，要求我們把 list 中小於 x 的 node 都排到大於等於 x的 node 前面去，小於 x 與大於等於 x 的 node 之間的相對順序要維持原樣。

EX:

        head = 1->4->3->2->5->2, x = 3

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

LeetCode 78. Subsets [Medium] [C++] 解題筆記

這題給定一個 array，其中所有數字不重複，要我們求 array 中所有數字可以組成的不重複子集。

EX:

        nums = [1,2,3]

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

LeetCode 77. Combinations [Medium] [C++] 解題筆記

這題是基本的組合題目，一定要會！

題目很簡單就是給你兩個數 n 與 k 要你求 n 取 k 的所有組合 C(n, k) 。

EX:

        n = 5, k = 4

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

LeetCode 81. Search in Rotated Sorted Array II [Medium] [C++] 解題筆記

這題是 33. Search in Rotated Sorted Array 的 follow up，一樣給定一個 array ，這個 array 是排序好的但是不是從頭開始排序，而是從某個 index 開始排序，但 array 中的數字可能重複，要求我們在此 array 中搜索特定數字。

EX:

        nums = [1,1,3,1],  target = 3 

    

        

Ans: true

LeetCode 33. Search in Rotated Sorted Array [Medium] [C++] 解題筆記

這題給定一個 array ，這個 array 是排序好的但是不是從頭開始排序，而是從某個 index 開始排序，且 array 中的數字不重複，要求我們在此 array 中搜索特定數字。

EX:

    nums = [4,5,6,7,0,1,2], target = 0

Ans: 4