Jackson.tmm

Loving life and dreams.

0%

發表於： 分類於：

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:

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

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:

發表於：

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 1268 - Search Suggestions System

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed. example:

發表於： 分類於：

LeetCode 5 - Longest Palindromic Substring

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

example

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

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]為解。

發表於： 分類於：

LeetCode 583 - Delete Operation for Two Strings

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string example

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Input: word1 = "leetcode", word2 = "etco"
Output: 4

How can we solve this problem?

這題要我們解決的問題是給定2個字串Word1和Word2,每次從Word1或者Word2中移除1個Character，問我們最少需要多少步使得2個string一樣。
首先,我們需要先知道這2個Word有哪些Character的是一致的。為了能獲得他們之間的最長共同子字串，我們可以透過Longest Commond Substring來得到他們之間共同子字串的長度，只要每個字串的長度減去LCM的長度，就可以知道各自需要多少步。最後相加起來即可。
Longest Commond Substring Template

發表於： 分類於：

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

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

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.

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

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

Input: digits = ""
Output: []

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

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

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

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]`為第三大。