Python | LeetCode

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0]. Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i. Другими словами, если вы находитесь в nums[i], вы можете перейти к любому nums[i + j], где: 0 <= j <= nums[i] иi + j < n Возвращает минимальное количество переходов для достижения nums[n - 1]. Тестовые примеры генерируются таким образом, чтобы вы могли достичь nums[n - 1].

class Solution: 
  def jump(self, nums: List[int]) -> int: 
    ans = 0 
    end = 0 
    farthest = 0 
 
    # Implicit BFS 
    for i in range(len(nums) - 1): 
      farthest = max(farthest, i + nums[i]) 
      if farthest >= len(nums) - 1: 
        ans += 1 
        break 
      if i == end:      # Visited all the items on the current level 
        ans += 1        # Increment the level 
        end = farthest  # Make the queue size for the next level 
 
    return ans

Учитывая массив nums, состоящий из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.

class Solution: 
    def permute(self, nums: List[int]) -> List[List[int]]: 
        result = [] 
 
        def permute_rec(nums, current_index, result): 
            if current_index == len(nums) - 1: 
                result.append(nums.copy()) 
                return 
 
            for index in range(current_index, len(nums)): 
                nums[current_index], nums[index] = nums[index], nums[current_index] 
                permute_rec(nums, current_index + 1, result) 
                nums[current_index], nums[index] = nums[index], nums[current_index] 
 
        permute_rec(nums, 0, result) 
        return result

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа. Открытые скобки должны закрываться в правильном порядке. Каждой закрывающей скобке соответствует открытая скобка того же типа.

  def isValid(self, s: str) -> bool:
        dic = {'(':1 , ')':2 , '[':3 , ']':6 , '{':5 , '}':10}
        res = []
        for one in s:
            temp = dic[one]
            if(temp %2 ):
                res.append(temp)
            else:
                if(len(res) and res[-1]==temp//2):
                    del res[-1]
                else:
                    return False
        return res==[]

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

# class ListNode:
#     def init(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head.next == None:
            return None
        tmp = head
        size = 0
        
        # find the size of the linked list
        while tmp:
            size += 1
            tmp = tmp.next
        tmp = head
        
        #if we have to remove the first node:
        if n == size: 
            return head.next
        
        for i in range(size-n-1):
            tmp = tmp.next
        tmp.next = tmp.next.next
        return head

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что: 0 <= a, b, c, d < n a, b, c и d различны. nums[a] + nums[b] + nums[c] + nums[d] == цель Вы можете вернуть ответ в любом порядке.

```def fourSum(self, nums, target):
    nums.sort()
    results = []
    self.findNsum(nums, target, 4, [], results)
    return results

def findNsum(self, nums, target, N, result, results):
    if len(nums) < N or N < 2: return

    # solve 2-sum
    if N == 2:
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                results.append(result + [nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while r > l and nums[r] == nums[r + 1]:
                    r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
    else:
        for i in range(0, len(nums)-N+1):   # careful about range
            if target < nums[i]*N or target > nums[-1]*N:  # take advantages of sorted list
                break
            if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N
                self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
    return
```

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        self.dfs(nums, [], res)
        return res
    
    def dfs(self, nums, path, res):
        res.append(path)
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[i+1:], path + [nums[i]], res)

Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.

```class Solution:
    def threeSumClosest(self, num, target):
        num.sort()
        result = num[0] + num[1] + num[2]
        for i in range(len(num) - 2):
            j, k = i+1, len(num) - 1
            while j < k:
                sum = num[i] + num[j] + num[k]
                if sum == target:
                    return sum
                
                if abs(sum - target) < abs(result - target):
                    result = sum
                
                if sum < target:
                    j += 1
                elif sum > target:
                    k -= 1
                else:
                    return result
            
        return result
```