LeetCode 2196 - Create Binary Tree From Descriptions

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,

• If isLefti == 1, then child_i is the left child of parent_i.
• If isLefti == 0, then child_i is the right child of parent_i. Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid. example

LeetCode 814 - Binary Tree Pruning

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

example

1
2
3
4
5

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

1
2

Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

How can we solve this problem?

這題是要讓我們移除所有不包含1的sub-tree。所以，我們只要透過DFS判斷一下node的left-sub tree 以及 right-sub tree 是否都不包含1: 1. 如果左右子樹都不包含1且當前node為0, 直接返回nullptr 2. 若當前節點為1就返回自身 2. 左子樹不包含1, 當前node的左子樹設成nullptr;同理右子樹不包含1,當前node 的右子數設為nullptr

最近這2個月都沒有更新發文章，主要是因為這2個月都在專注重構畢業專題的項目，也是只OTT電影平台。
今天這篇文章主要是跟大家分享這2個月所開發的進度和目前開發到的階段，以此作為這個項目的開發日記。

LeetCode 92 - Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

example

1
2

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

1
2

Input: head = [5], left = 1, right = 1
Output: [5]

How can we solve this problem?

這一題的問題非常的簡單,就是要讓我們在給定的一個list中翻轉(Reverse)[left,right]之間的Node,並返回結果。這題跟Reverse Linked List I解法類似,不同的是多了個翻轉範圍。
首先，我們要做的是在的翻轉的開始的位置。然後再透過recursive來翻轉List,最後返回的node/head再由left位置的Node的前一個Node接起來(如有)就可以了~

這題主要是學習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 ans of length n + 1 such that for each i (0 <= i <= n), ans[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 height is greater than or equal to the next building’s height, you do not need a ladder or bricks.
• If the current building’s height is less than the next building’s height, 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中的所有的childrens都有相同的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.