LeetCode 92. Reverse Linked List II [Medium] [C++] 解題筆記

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

EX:

        Input: 1->2->3->4->5->NULL, m = 2, n = 4

        Output: 1->4->3->2->5->NULL

LeetCode 53. Maximum Subarray [Easy] [C++] 解題筆記

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

EX:

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

        Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

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

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 the number of distinct solutions to the n-queens puzzle.

EX:

     Input: 4

    Output: 2
    Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
    [
     [".Q..",  // Solution 1
      "...Q",
      "Q...",
      "..Q."],

     ["..Q.",  // Solution 2
      "Q...",
      "...Q",
      ".Q.."]
    ]

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:

                                    

LeetCode 36. Valid Sudoku [Medium] [C++] 解題筆記

這題給我們一個玩到一半的 9 X 9 數獨，要我們判斷目前的結果是不是正確的(有沒有符合數獨的規定)。

EX:

        Input:

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
    Output: true

LeetCode 35. Search Insert Position [Easy] [C++] 解題筆記

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

EX:

        Input: [1,3,5,6], 5

        Output: 2

LeetCode 34. Find First and Last Position of Element in Sorted Array [Medium] [C++] 解題筆記

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

EX:

        Input: nums = [5,7,7,8,8,10], target = 8

        Output: [3,4]

        Input: nums = [5,7,7,8,8,10], target = 6

        Output: [-1,-1]

LeetCode 32. Longest Valid Parentheses [Hard] [C++] 解題筆記

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

EX:

        Input: "(()"

        Output: 2

        Explanation: The longest valid parentheses substring is "()"

        Input: ")()())"

        Output: 4

        Explanation: The longest valid parentheses substring is "()()"

LeetCode 31. Next Permutation [Medium] [C++] 解題筆記

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

EX:

        1,2,3 → 1,3,2

    3,2,1 → 1,2,3

    1,1,5 → 1,5,1

LeetCode 30. Substring with Concatenation of All Words [Hard] [C++] 解題筆記

這題給我們一個 string s 和一些等長 words，要我們求出 s 中所有可以由所有 words 組合形成的子串。

EX:

        Input:

        s = "barfoothefoobarman",

        words = ["foo","bar"]

        Output: [0,9]

Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

LeetCode 29. Divide Two Integers [Medium] [C++] 解題筆記

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

EX:

        Input: dividend = 7, divisor = -3

        Output: -2

        Explanation: 7/-3 = truncate(-2.33333..) = -2.

LeetCode 28. Implement strStr() [Easy] [C++] 解題筆記

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

EX:

        Input: haystack = "hello", needle = "ll"

        Output: 2

        Input: haystack = "aaaaa", needle = "bba"

        Output: -1

LeetCode 27. Remove Element [Easy] [C++] 解題筆記

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

EX:

        Given nums = [0,1,2,2,3,0,4,2], val = 2,

    Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
    Note that the order of those five elements can be arbitrary.
    It doesn't matter what values are set beyond the returned length.

LeetCode 26. Remove Duplicates from Sorted Array [Easy] [C++] 解題筆記

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

EX:

        Given nums = [0,0,1,1,1,2,2,3,3,4],

    Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
    It doesn't matter what values are set beyond the returned length.        

LeetCode 25. Reverse Nodes in k-Group [Hard] [C++] 解題筆記

這題給定我們一個 linked list，與一個值 k ，要求我們以每 k 個 node 為一組 reverse 此 list。

EX:

        Given this linked list: 1->2->3->4->5

        For k = 2, you should return: 2->1->4->3->5

        For k = 3, you should return: 3->2->1->4->5

LeetCode 24. Swap Nodes in Pairs [Medium] [C++] 解題筆記

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

EX:

        Given 1->2->3->4, you should return the list as 2->1->4->3.

LeetCode 23. Merge k Sorted Lists [Hard] [C++] 解題筆記

這題給定 k 個排序好的 linked list，要求將這 k 個 list 合併成一個排序好的 linked list。

EX:

        Input:

    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6