這題主要是學習DP思想，做個小記錄

LeetCode 629 - K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integersn and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

LeetCode 338 - Counting Bits

Given an integer n, return an array and of length n + 1 such that for each i (0 <= i <= n), and[i] is the number of 1’s in the binary representation of i.

example:

1
2
3
4
5
6

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

1
2
3
4
5
6
7
8
9

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

How can we solve this problem?

這題要我們解決的問題是給定一個數字n,回傳0 - n中每個數字包含了多少個為1的bits。例如: n=2 => 00,01,10,回傳的結果便會是[0,1,1]。

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(虛擬數字人/虛擬數位人)