iT邦幫忙

1

打競賽學到許多coding技巧,分享個LeetCode Weekly Contest 239的詳解

leetcode是一個著名的程式練習平台,
台灣時間的每週日早上10:30~12:00可以參加線上的競賽,
共有4題,
難度依序為Easy, Medium, Medium, Hard,
通常難度為由易至難排序,按照順序寫下來即可,
一個小時半要寫完4題時間還是非常緊的,
小鹿一開始參賽往往只能解個1~2題,
後來在leetcode上練習多了,也慢慢摸熟各種程式算法思維

至leetcode競賽開辦以來,已經到「LeetCode Weekly Contest 239」了,
今天來分享自已研究的題解,
幫助想要刷leetcode練習的人吧
https://ithelp.ithome.com.tw/upload/images/20210502/20135919CgyhOSCgna.png

Easy- 1848. Minimum Distance to the Target Element

題意:給定一個陣列nums,要搜索的數字target,索引start,
找離start最接近的index,使得nums[i] == target且abs(i - start) 最小。
回傳abs(i - start)的值

Sample Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
Output: 0
說明: 每個數字都是1,選擇index=0,abs(0 - start)=0最小

這一題有刷題經驗的話應該很快就可以解的出來,
搜索陣列內的每個數字,判斷是否等於target
然後計算abs(i - start)
在python內可以漂亮的一行解掉

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        return min(abs(i - start) for i, a in enumerate(nums) if a == target)

接下來的三題小鹿覺得就非常有難度了,
可能要閱題百題以上才較有機會想出怎麼解吧

Medium- 1849. Splitting a String Into Descending Consecutive Values

題意:給定一個僅由數字組成的字串,將字串分割為兩段以上,使得字串的數值依序遞減1
回傳boolean表示是否能做到這樣的分解,允許數字的開頭是0

Sample Input: s = "0090089"
Output: True
說明: s可以分割為"0090","089"

初看應該不太知道怎麼做,
有點難,大概要有點刷題經驗
有發現這題跟leetcode以前的一道題-842. Split Array into Fibonacci Sequence很像,
那題是說能否將字串S分解為費氏數列?可能的話回傳一組解。Sample Input: "123456579", Output: [123,456,579]。

費氏數列的定義是滿足F[i] + F[i+1] = F[i+2]的數列,
由於該題的限制更多:

  • 0 <= F[i] <= 2^31 - 1
  • 數字前面不可以有額外的0(如0123禁止分解成0123)
  • 字串至少要分解成三段

因此會那題的話這題就算一個變形題而已,
小鹿用的是DFS做法,並且寫一個更general的解- 求出所有費氏數列分解。
求出所有解之後,由於題目只有返迴任意一組解,就回傳第一個

可能有人會擔心會窮舉所有解會不會超時?
實際上要滿足新切割字串n_int == c[-1] + c[-2]的字串的數量是不多的,
真正進入遞迴的數字可能就一兩組解而已

# 842. Split Array into Fibonacci Sequence題解
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        INT_MAX = 2**31-1
        
        def find(s, idx, comb):
            """
            給定s[:idx]前的所有費氏數列分解comb,
            找出所有s的費氏數列分解
            """
            if idx == len(s):
                return [c[:] for c in comb if len(c) > 2]
            res = []
            for i in range(idx, idx + 1 if s[idx] == '0' else len(s)):
                n_int = int(s[idx: i+1])
                for c in comb:
                    if n_int <= INT_MAX and (len(c) in [0,1] or n_int == c[-1] + c[-2]):
                        res += find(s, i + 1, [c + [n_int]])
            return res
        res = find(S, 0, [[]])
        return res[0] if res else []

回到本題,跑dfs的條件修改為n_int == c[-1] -1
一樣窮舉所有的解,
本題只要回傳boolean值,
就判斷陣列是否非空就好(return bool(res))

# 1849. Splitting a String Into Descending Consecutive Values 題解
class Solution:
    def splitString(self, s: str) -> bool:
        
        def find(s, idx, comb):
            if idx == len(s):
                return [c[:] for c in comb if len(c) >= 2]
            res = []
            for i in range(idx, len(s)):
                n_int = int(s[idx: i+1])
                for c in comb:
                    if len(c)==0 or n_int == c[-1] -1:
                        res += find(s, i + 1, [c + [n_int]])
            return res
        res = find(s, 0, [[]])
        return bool(res)

Medium- 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

題意:給定一個字串,找到它的下k個排列,問說要幾次相鄰字元交換,可以將原字串變成下k個排列
Sample Input: num = "5489355142"
Output: 2
說明: 原字串的下面四個排列為"5489355214","5489355241","5489355412","5489355421",
欲把"5489355142"變為"5489355421",需要將最右邊的4、1交換一次,
再將最右邊的1、2交換一次

小鹿覺得這是一道經驗題,可以拆解成兩個部分:

  • 求下一個排列
  • A,B互為重新排列,求陣列B要經過幾次相鄰元素交換可以變成A

可以各包裝為一個函數,讓解題思路清晰,
其中「求下一個排列」為leetcode的31. Next Permutation,做法有點tricky,
不看詳解有點難想到

另外就是「求陣列B要經過幾次相鄰元素交換可以變成A」,
這個很像bubble sort(見wiki-泡沫排序),
利用兩兩交換元素做排序的感覺,
實作函數如下:

def countswap(A,B):
    """
    計算陣列B要經過幾次相鄰元素交換可以變成A,
    很像bubble sort的感覺
    """
    cnt = 0
    while A:
        b_idx = B.index(A.pop(0))
        cnt += b_idx
        B.pop(b_idx)
    return cnt

完整code:

# 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number題解
def nextPermutation(nums):
    """
    (in-place)
    找全排列的下一個排列。
    思路(這是看出的規律,若不知道的話很難):
    1.從右往左找到第一個降序的數字,記作A[X]
    2.從右往左找到第一個大於A[X]的數,記作A[Y]
    3. Swap(A[X],A[Y])
    4. 將A[X]後的陣列反轉(成為sorted)
    >>> nextPermutation([1,2,3])
    [1, 3, 2]
    >>> nextPermutation([1,3,2])
    [2, 1, 3]
    >>> nextPermutation([3,2,1])
    [1, 2, 3]
    """
    i = len(nums)-2
    while i > -1:
        if nums[i] < nums[i+1]:
            j = i+1
            while j<len(nums) and nums[i] < nums[j]:
                j += 1
            nums[i], nums[j-1] = nums[j-1], nums[i]
            break
        i -= 1
    nums[i+1:] = nums[i+1:][::-1]

def countswap(A,B):
    """
    計算陣列B要經過幾次相鄰元素交換可以變成A,
    很像bubble sort的感覺
    """
    cnt = 0
    while A:
        b_idx = B.index(A.pop(0))
        cnt += b_idx
        B.pop(b_idx)
    return cnt
            
class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        origin = list(num)
        num = list(num)
        for _ in range(k):
            nextPermutation(num)
        return countswap(origin, num)

Hard- 1851. Minimum Interval to Include Each Query

題意:給定一個二維陣列表示區間[left, right]\(表示left, right兩個數字),區間的長度定義為right - left + 1
另給定一個陣列表示query,要回答每個query包含該數字的最小長度為何?
Sample Input:intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
說明: 
- Query = 2: [2,4] 是最小的區間包含 2,故答案為 4 - 2 + 1 = 3
- Query = 3: [2,4] 是最小的區間包含 3,故答案為 4 - 2 + 1 = 3
- Query = 4: [4,4] 是最小的區間包含 4,故答案為 4 - 4 + 1 = 1
- Query = 5: [3,6] 是最小的區間包含 5,故答案為 6 - 3 + 1 = 4.

本題需要事先將queries和intervals排序,
每次進來一個新的query時,將舊的元素踢除(區間右界小於現在的query),
嘗試加入新的可能元素(區間左界小於現在的query),
由於需要一直新增、移除元素,
還要查詢最小值,故想到用「heap」結構

# 1851. Minimum Interval to Include Each Query 題解
from heapq import heappop, heappush
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        A = sorted(intervals)
        Q = sorted((q, i) for i, q in enumerate(queries))
        heap = []
        res = [-1] * len(Q)
        j = 0
        
        for query, idx in Q:
            while heap and heap[0][1] < query:
                heappop(heap)
            while j < len(A) :
                left, right = A[j]
                if left>query:
                    break
                if right>=query:
                    heappush(heap, (right - left + 1, right))
                j+=1
            if heap:
                res[idx] = heap[0][0]
        return res

尚未有邦友留言

立即登入留言