LeetCode 51. N-Queens [Hard] [C++] 解題筆記

這題是經典的 n 皇后問題。

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

EX:

        Input: 4

        Output: [
         [".Q..",  // Solution 1
          "...Q",
          "Q...",
          "..Q."],

         ["..Q.",  // Solution 2
          "Q...",
          "...Q",
          ".Q.."]
        ]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

LeetCode 50. Pow(x, n) [Medium] [C++] 解題筆記

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

EX:

        Input: 2.00000, 10

        Output: 1024.00000

        Input: 2.00000, -2

        Output: 0.25000
        Explanation: 2-2 = 1/22 = 1/4 = 0.25

LeetCode 49. Group Anagrams [Medium] [C++] 解題筆記

這題給定一個 array 包含一些 string，要求我們將由同樣字元組成的 string 歸到同一個 array。

EX:

        Input: ["eat", "tea", "tan", "ate", "nat", "bat"],

        Output:
        [
          ["ate","eat","tea"],
          ["nat","tan"],
          ["bat"]
        ]

LeetCode 48. Rotate Image [Medium] [C++] 解題筆記

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

EX:

        Given input matrix = 

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

    rotate the input matrix in-place such that it becomes:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]

LeetCode 47. Permutations II [Medium] [C++] 解題筆記

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

EX:

        Input: [1,1,2]

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

LeetCode 46. Permutations [Medium] [C++] 解題筆記

Given a collection of distinct integers, return all possible permutations.

EX:

        Input: [1,2,3]

    Output:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

LeetCode 44. Wildcard Matching [Hard] [C++] 解題筆記

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

注意這裡的 '*' 是匹配任意字串!

EX:

    Input:

    s = "adceb"
    p = "*a*b"
    Output: true
    Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

LeetCode 43. Multiply Strings [Medium] [C++] 解題筆記

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

EX:

        Input: num1 = "123", num2 = "456"

        Output: "56088"

LeetCode 41. First Missing Positive [Hard] [C++] 解題筆記

Given an unsorted integer array, find the smallest missing positive integer.

EX:

        Input: [1,2,0]

        Output: 3

        Input: [3,4,-1,1]

        Output: 2

        Input: [7,8,9,11,12]

        Output: 1

LeetCode 40. Combination Sum II [Medium] [C++] 解題筆記

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

EX:

        Input: candidates = [10,1,2,7,6,1,5], target = 8,

    A solution set is:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

LeetCode 39. Combination Sum [Medium] [C++] 解題筆記

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

EX:

        Input: candidates = [2,3,5], target = 8,

    A solution set is:
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

LeetCode 38. Count and Say [Easy] [C++] 解題筆記

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the n^th term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note: Each term of the sequence of integers will be represented as a string.

EX:

        Input: 4

        Output: "1211"

Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" 

which means frequency = 1 and value = 2, 

the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

LeetCode 37. Sudoku Solver [Hard] [C++] 解題筆記

這題是 36. Valid Sudoku 的進階題，要我們實作一個 9 X 9 數獨的 Solver。

EX: