LeetCode 1268 - Search Suggestions System

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

example:

1
2

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

1
2

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

How can we solve this problem?

這題要我們解決的問題是回傳在sorted array(Input Array沒有排序)中第kth大的元素。最簡單的解法是直接排序,然後回傳kth元素即可。但是, 這裡我們也可以使用Priority Queue(Heap)來幫我們解決這個問題。因為Priority Queue的特性,越大的值(MaxHeap)/越小的值(MinHeap)會越接近root,也就是說最大值(MaxHeap)/最小值(MinHeap)會在root。所以我們可以運用MinHeap來幫助的我們解決這個問題,只要Priority Queue裡面的元素多於K個我們就會把top的值移除，因更小的值會在前面,每次pop的值都會是當前最小的值,直到最後，省下來的值的root/top就會是我們的第K個最大的值，而priority queue中最後一個值便會是Input中最大的值。

LeetCode 1642 - Furthest Building You Can Reach

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

• If the current building’s high is greater than or equal to the next building’s high, you do not need a ladder or bricks.
• If the current building’s high is less than the next building’s high, you can either use one ladder or (h[i+1] - h[i]) bricks. Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

example:

Introduction

什麼是TrieTree?

Trie稱為前綴樹或字典樹,是有序樹的一種,Node的key通常為String類型。Trie Tree與Binary-Searching Tree不同的點是,Trie Tree的Key並不會直接保存在Node中,而是它在Tree中的位置所決定的。一個Node中的所有的children都有相同的Prefix(前綴)。假設有個Node的key 為T,它的children將會是Time, Tim, Test等,因為他們都會相同的Prefix(前綴)T。

820 - Short Encoding of Words

A valid encoding of an array of words is any reference string s and array of indices indices such that:

• words.length == indices.length
• The reference string s ends with the '#' character.
• For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

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回上一步,因為數值只會越來越大，並不是我們想要的。如果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",並嘗試其他數值/結果。