leetcode 11-20（2024.08.15）

立个flag，1-100题每天分配10题，不会就先空着（7）。

1. 11：盛最多水的容器

class Solution:def maxArea(self, height: List[int]) -> int:res = 0left = 0right = len(height) - 1while left < right:area = (right - left) * min(height[left], height[right])res = area if area > res else resif height[left] < height[right]:left = left + 1else:right = right - 1return res

2. 12：整数转罗马数字

class Solution:def intToRoman(self, num: int) -> str:res = ""haxi = {1000: "M", 900: "CM", 500: "D", 400: "CD", 100: "C",90: "XC", 50: "L", 40: "XL", 10: "X",9: "IX", 5: "V", 4: "IV", 1: "I"}for key in haxi:while key <= num:num = num - keyres = res + haxi[key]return res

3. 13：罗马数字转整数 

class Solution:def romanToInt(self, s: str) -> int:res = 0haxi = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}for i in range(len(s) - 1):if haxi[s[i]] >= haxi[s[i + 1]]:res = res + haxi[s[i]]else:res = res - haxi[s[i]]res = res + haxi[s[-1]]return res

4. 14：最长公共前缀

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:def get_same(str1, str2):res = ''i = 0while i < len(str1) and i < len(str2):if str1[i] == str2[i]:res = res + str1[i]i = i + 1else:breakreturn resres = strs[0]for i in range(len(strs)):res = get_same(res, strs[i])return res

 5. 15：三数之和

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res = []nums.sort()for i in range(len(nums) - 2):if i > 0 and nums[i] == nums[i - 1]:continueleft = i + 1right = len(nums) - 1while left < right:sum = nums[i] + nums[left] + nums[right]if sum > 0:right = right - 1elif sum < 0:left = left + 1elif sum == 0:res.append([nums[i], nums[left], nums[right]])left = left + 1while left < right and nums[left] == nums[left - 1]:left = left + 1right = right - 1while left < right and nums[right] == nums[right + 1]:right = right - 1return res

 6. 16：最接近的三数之和

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:minimum = float("inf")nums.sort()for i in range(len(nums) - 2):if i > 0 and nums[i] == nums[i - 1]:continueleft = i + 1right = len(nums) - 1while left < right:sum = nums[i] + nums[left] + nums[right]if sum == target:return sumelif sum < target:left = left + 1elif sum > target:right = right - 1if abs(sum - target) < minimum:res = summinimum = abs(sum - target)return res

 7. 17：电话号码的字母组合

 8. 18：四数之和

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:res = []nums.sort()for i in range(len(nums) - 3):if i > 0 and nums[i] == nums[i - 1]:continuefor j in range(i + 1, len(nums) - 2):if j > i + 1 and nums[j] == nums[j - 1]:continueleft = j + 1right = len(nums) - 1while left < right:sum = nums[i] + nums[j] + nums[left] + nums[right]if sum < target:left = left + 1elif sum > target:right = right - 1elif sum == target:res.append([nums[i], nums[j], nums[left], nums[right]])left = left + 1while left < right and nums[left] == nums[left - 1]:left = left + 1right = right - 1while left < right and nums[right] == nums[right + 1]:right = right - 1return res

 9. 19：删除链表的倒数第N个结点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy = slow = fast = ListNode()dummy.next = headwhile n:fast = fast.nextn = n - 1while fast.next:slow = slow.nextfast = fast.nextslow.next = slow.next.nextreturn dummy.next

10. 20：有效的括号 

class Solution:def isValid(self, s: str) -> bool:stack = []pair = {"(": ")", "[": "]", "{": "}"}for i in s:if i in "([{":stack.append(pair[i])else:if stack and stack[-1] == i:stack.pop()else:return Falseif stack:return Falseelse:return True