LeetCode 5 - Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

example

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

1
2

Input: s = "cbbd"
Output: "bb"

How can we solve this problem?

要解決這題，我們必須要先知道什麼是Palindrome。可以參考這篇文章 Palindromic string迴文 。而這題要我們找出在給定string中,找到最長的Palindrome。我們可以透過以每個單一字元(index i)以及倆個字元(index i,index i+1)為中心點，並擴展left,right找出他們的局部的最長Palindrome為多少，然後根據這個長度計算starting point i以及記錄長度len,最後以starting point和len得出字串中str[startingPoint,len]為解。

Introduction

什麼是Palindromic String 迴文字串

所謂的Palindromic String(迴文字串) 就是以一個字元為中間，而它的左邊以及右邊的組成字元相同。
例子:
abcdcba 以d為中心的左跟右的字元一樣。
cdc左跟右都為c
bcdcb 左跟右都為b
abcdcba 左跟右都為a

Introduction

什麼是最長公共子序列?

給定2個字串string A和string B,2個字串中所共同擁有的最長的子字串。
例如:

1
2
3
4
5
6
7

String A : leetcode
String B : ecbod
他們的最長公共子序列便是`ecod`

解釋:
String A 包含了 __e_cod_ => ecod
String B 包含了 ec_od => ecod

要怎麼找到最長公共子序列LCM呢?

我們需要定義一個數組用於保存當前情況下的最優解,也就是使用DP的方式。我們需要以每個字符最為考量,並一一匹配，最後得出整體最優解。

因為元宇宙(Metaverse)這個概念火熱,所有我就趁著這個機會了解一下在元宇宙領域中本人覺得比較有趣的東西。也就是這篇文章所要分享給各位的MetaHuman(虛擬數字人/虛擬數位人)

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回上一步,因為數值只會越來越大，並不是我們想要的。如果Ans我們所需的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: