1

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

leetcode是一個著名的程式練習平台，

# Easy- 1848. Minimum Distance to the Target Element

``````題意:給定一個陣列nums，要搜索的數字target，索引start，

Sample Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
Output: 0

``````

``````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

Sample Input: s = "0090089"
Output: True

``````

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

``````# 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 []
``````

``````# 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

``````

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

``````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
``````

``````# 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

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.
``````

``````# 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
``````