Jackson.tmm

LeetCode 216 - Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

example

1
2
3
4
5

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

1
2
3
4
5
6
7

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

1
2
3
4

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

How can we solve this problem?

這題主要關注的點是數字範圍為[1,9]，每個結果中，數字只能使用一次，而且數字必須是順序排列。例如:2,3,4,1,2,5。解決這題我們可以用back-traking大法。只要我們當前的Sum大於n我們就直接退回back track回上一步,因為數值只會越來越大，並不是我們想要的。如果And我們所需的k個就直接判斷是否等於n，如果是就直接加入到我們的result即可。

LeetCode 17 - Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

example

1
2

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

1
2

Input: digits = ""
Output: []

1
2

Input: digits = "2"
Output: ["a","b","c"]

How can we solve this problem?

這題是要我們拿到Input的數字所能組合出所有字串。解法也很簡單，我們可以透過Map記錄每個數字代表來那些字符，然後再透過Back-tracking技巧來幫助我們組合字串。你有可能會問什麼是Back-tracking。簡單來說就是一個Recursive Function,但他會迴避一些不正常的數值。比如:“abc”,而"abc"可能不是我們要的。因此退回上一步的"ab",並嘗試其他數值/結果。

LeetCode 341 - Flatten Nested List Iterator

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

LeetCode 456 - 132 Pattern

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false. example

1
2
3

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

1
2
3

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

1
2
3

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

How can we solve this problem?

這題就是要我們找出List有沒有符合132 Pattern。那怎麼才算是132 Pattern呢。從題目定義可以看出在List中任意的nums[i] < nums[k] < nums[j]，也就是說nums[k]為最大,nums[j]為第二大,nums[i]`為第三大。

LeetCode 1209 - Remove All Adjacent Duplicates in String II

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

LeetCode 225 - Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

LeetCode 1679 - Max Number of K-Sum Pairs

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

example

1
2
3
4
5
6

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

1
2
3
4
5

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

How can we solve this problem?

這題就是要移除Array中2個elements加起來等於k的操作有幾次。 第一個解法，我們可以使用sorting以及two-pointer approach來解決。先將array排序，然後設置i為0,j為n-1,直接使用iteration找出nums[i]+nums[j] = k的數，然後answer+1即可。

LeetCode 581 - Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

example:

1
2
3

Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

1
2

Input: nums = [1,2,3,4]
Output: 0

1
2

Input: nums = [1]
Output: 0

How can we solve this problem?

這題比較難懂一點點，這裡先做一下題目的解釋。這題主要先問的是在輸入的Array裡面找到一個最小需要排序的Sub-array。 從例子[2,6,4,8,10,9,15]中，我們可以很明顯的看到[6,4,8,10,9]並不是ascending order(順序),而這個sub-array要進行排序的話，所有elements都需要進行排序，所以，他的length是5。 再舉另外一個例子[1,3,2,3,3]，這個Array我們可以看到[3,2,3,3]並不是順序的，但是在這個sub-array裡面,只有[3,2]需要排序,所以，他的結果會是2。

LeetCode 905 - Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

example:

1
2
3

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

1
2

Input: nums = [0]
Output: [0]

How can we solve this problem?

這個問題很簡單，就是把偶數移動到Array的前面，基數移動到後面。我們這裡可以使用Two-pointer approach, i為尋找前面的基數，而j 為尋找後面的偶數，只要nums[i]為基數,nums[j]為偶數就進行交換。

LeetCode 844 - Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

example:

1
2
3

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

1
2
3

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

1
2
3

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

How can we solve this problem?

這題主要要什麼比較2個String移除於#前的字符後是否為相同的String，就相當於Backspace(#) 字符。 這題有2種解法: