建设快卡额度查询网站,php完整电商网站开发源码,网站开发招标技术规范书,网站建设一对一培训班Python|Leetcode刷题日寄Part0101#xff1a;两数之和02#xff1a;无重复字符的最长子串03#xff1a;两数相加04#xff1a;反转链表05#xff1a;有效的括号06#xff1a;回文数07#xff1a;删除有序数组中的重复项08#xff1a;删除链表的倒数第N个结点09#xf…
Python|Leetcode刷题日寄Part0101两数之和02无重复字符的最长子串03两数相加04反转链表05有效的括号06回文数07删除有序数组中的重复项08删除链表的倒数第N个结点09移除元素10最长回文子串01两数之和
题目描述 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 输入nums[2,7,11,15], target9 输出[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_len03两数相加
题目描述 给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 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, val0, nextNone):
# 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 l104反转链表
题目描述 给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 输入head [1, 2, 3, 4, 5] 输出[5, 4, 3, 2, 1]
题解
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# 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 prev05有效的括号
题目描述 给定一个只包括 (){}[] 的字符串 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) 106回文数
题目描述 给你一个整数 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 slow08删除链表的倒数第N个结点
题目描述 给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
示例 输入head [1,2,3,4,5], n 2 输出[1,2,3,5]
题解
# 双指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# 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.next09移除元素
题目描述 给你一个数组 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 slow10最长回文子串
题目描述 给你一个字符串 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[i1][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:startmax_len]
