Python|Leetcode刷题日寄Part01

01：两数之和

题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例：
输入：nums=[2,7,11,15], target=9
输出：[0,1]
解释：因为 nums[0]+nums[1]==9，返回 [0,1]

题解：

# 哈希表
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:dic = dict()for i, num in enumerate(nums):if target - num in dic:return [dic[target - num], i]dic[nums[i]] = ireturn []

---

02：无重复字符的最长子串

题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例：
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 abc，所以其长度为 3

题解：

# 滑动窗口
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:max_len, dic = 0, {}start = 0for end in range(len(s)):dic[s[end]] = dic.get(s[end], 0) + 1if len(dic) == end - start +1:max_len = max(max_len, end - start +1)while (end - start + 1) > len(dic):head = s[start]dic[head] -= 1if dic[head] == 0:del dic[head]start += 1return max_len

03：两数相加

题目描述：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7, 0, 8]
解释：342 + 465 = 807

题解：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:if not l1:return l2if not l2:return l1l1.val += l2.valif l1.val >= 10:l1.next = self.addTwoNumbers(ListNode(l1.val // 10), l1.next)l1.val %= 10l1.next = self.addTwoNumbers(l1.next, l2.next)return l1

04：反转链表

题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：
输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]

题解：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:prev, curr = None, headwhile curr is not None:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev

05：有效的括号

题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例：
输入：s = "()"
输出：true

题解：

# 栈
class Solution:def isValid(self, s: str) -> bool:dic = {'{': '}', '[': ']', '(': ')', '?': '?'}stack = ['?']for i in s:if i in dic:stack.append(i)elif dic[stack.pop()] != i:return Falsereturn len(stack) == 1

06：回文数

题目描述：
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例：
输入：x = 121
输出：true

题解：

class Solution:def isPalindrome(self, x: int) -> bool:return str(x) == str(x)[::-1]

07：删除有序数组中的重复项

题目描述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组 nums 的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

题解：

# 双指针
class Solution:def removeDuplicates(self, nums: List[int]) -> int:if not nums:return 0n = len(nums)fast = slow = 1while fast < n:if nums[fast] != nums[fast - 1]:nums[slow] = nums[fast]slow += 1fast += 1return slow

08：删除链表的倒数第N个结点

题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

题解：

# 双指针
# 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 = ListNode(0, head)first = headsecond = dummyfor i in range(n):first = first.nextwhile first:first = first.nextsecond = second.nextsecond.next = second.next.nextreturn dummy.next

09：移除元素

题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案

题解：

# 双指针
class Solution:def removeElement(self, nums: List[int], val: int) -> int:fast = slow = 0while fast < len(nums):if nums[fast] != val:nums[slow] = nums[fast]slow += 1fast += 1return slow

10：最长回文子串

题目描述：
给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

题解：

# 动态规划
class Solution:def longestPalindrome(self, s: str) -> str:size = len(s)if size == 1:return sdp = [[False for _ in range(size)] for _ in range(size)]max_len = 1start = 0for j in range(1, size):for i in range(j):# 边界条件if j - i <= 2:if s[i] == s[j]:dp[i][j] = Truecur_len = j - i +1# 状态转移方程else:if s[i] == s[j] and dp[i+1][j-1]:dp[i][j] = Truecur_len = j - i + 1if dp[i][j]:if cur_len > max_len:max_len = cur_lenstart = ireturn s[start:start+max_len]