大鹏外贸网站建设,wordpress包下载失败,网站架构拓扑图,三网合一网站建设计划【PythonCode】力扣Leetcode1~5题Python版
前言 力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台#xff0c;很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。 在Leetcode上刷题#xff0c;可以选择各种主流的编程语言#xff0c;如C、…【PythonCode】力扣Leetcode1~5题Python版
前言 力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。 在Leetcode上刷题可以选择各种主流的编程语言如C、JAVA、Python、Go等。还可以在线编程实时执行代码如果代码通过了平台准备的测试用例就可以通过题目。 本系列中的文章从Leetcode的第1题开始记录我用Python语言提交的代码和思路受个人能力限制只是实现功能通过用例我没有每题都研究最优的实现方法供Python学习参考。 1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出和为目标值 target 的那两个整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。 示例1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 示例 2 输入nums [3,2,4], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1] 提示 2 nums.length 104 -109 nums[i] 109 -109 target 109 只会存在一个有效答案 代码实现
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:for i in range(len(nums)):for j in range(i1, len(nums)):if nums[i] nums[j] target:return [i, j]解题思路嵌套遍历从数组中取出两个数相加用嵌套的for循环判断相加的结果是否满足要求如果满足则用列表返回两个数据的索引。因为同一个元素不能重复出现所以索引 j 从 i1 开始遍历。
2. 两数相加
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例1 输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807 示例 2 输入l1 [0], l2 [0] 输出[0] 示例 3 输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9] 输出[8,9,9,9,0,0,0,1] 提示 每个链表中的节点数在范围 [1, 100] 内 0 Node.val 9 题目数据保证列表表示的数字不含前导零 代码实现
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:l1num, l2num l1.val, l2.vali, j 0, 0cur l1while cur.next:cur cur.nexti 1l1num cur.val * 10 ** icur2 l2while cur2.next:cur2 cur2.nextj 1l2num cur2.val * 10 ** jsumnum l1num l2numresult ListNode()cur resultfor s in str(sumnum)[::-1]:cur.next ListNode(int(s))cur cur.nextreturn result.next解题思路先按照逆序的方式将 l1 和 l2 两个链表转化成对应的整数转化时依次将第 i 个节点的数字乘 10 的 i 次方并全部相加i 从 0 开始。得到两个整数计算两个整数之和。然后将整数之和倒序保存到链表中每个节点一个数字。我采用的方式是将两数之和转换成字符串倒着遍历再将每个数字转换回整数然后创建节点添加到链表中。
3. 无重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 示例1 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 提示 0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成 代码实现
class Solution:def lengthOfLongestSubstring(self, s: str) - int:length 0for i in range(len(s)):slist []for j in range(i, len(s)):if s[j] not in slist:slist.append(s[j])else:breaklength max(length, len(slist))return length解题思路遍历字符串的索引以每一个索引位为标志位从标志位往后找最长的子串。最长子串的判断方式用列表实现如果连续的字符不在列表中则添加进列表遇到重复的字符时跳出内循环。循环结束后计算列表的长度并更新当前的最长长度。每次移动标志位清空用于保存字符的列表。
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。 示例1 输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2 示例 2 输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5 提示 nums1.length m nums2.length n 0 m 1000 0 n 1000 1 m n 2000 -106 nums1[i], nums2[i] 106 代码实现
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:m len(nums1)n len(nums2)if m n:return self.findMedianSortedArrays(nums2,nums1)k (m n 1)//2left 0right mwhile left right :m1 left (right - left)//2m2 k - m1if nums1[m1] nums2[m2-1]:left m1 1else:right m1m1 leftm2 k - m1 c1 max(nums1[m1-1] if m1 0 else float(-inf), nums2[m2-1] if m2 0 else float(-inf) )if (m n) % 2 1:return c1c2 min(nums1[m1] if m1 m else float(inf), nums2[m2] if m2 n else float(inf))return (c1 c2) / 2解题思路此题在Leetcode上的难度是困难属于等级最高的难度简单、中等、困难困难的原因是要求时间复杂度为O(log (mn))。主要目的是考算法思路并且要提交者自己实现算法。如果没有时间复杂度的要求实现其实很简单如下代码就可以通过力扣的用例(甚至可以更简单导入一个求中位数的函数)
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:nums sorted(nums1 nums2)if len(nums) % 2 0:return (nums[int(len(nums) // 2) - 1] nums[int(len(nums) // 2)]) / 2else:return nums[len(nums) // 2]因为要求时间复杂度为 O(log (mn))我一开始也没有想到好的方法所以参考了力扣用户powcai的答案。两个数组都是正序排列的所以找到中位数的策略是从两个数组中找出排序在前一半的数据中间的数字就是中位数。也就是找出第 k 大的那个数字k 是两个数组长度之和的一半或中间的两个数k, k1。
假如使用遍历时间复杂度将会是 O(mn)为了将时间复杂度降到题目要求的O(log (mn))需要使用二分法的方式查找。遍历是每次排除一个数据不是第 k 大二分查找每次排除 k/2 个数据不是第 k 大。在这个思路的基础上结合上面的代码就可以分析出解题办法了。如果你需要了解更详细的解题细节可以自己再搜索更多的参考答案。
5. 最长回文子串
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。 示例 1 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。 示例 2 输入s “cbbd” 输出“bb” 提示 1 s.length 1000 s 仅由数字和英文字母组成 代码实现
class Solution:def longestPalindrome(self, s: str) - str:max_length 1start_index 0i 0while i len(s):length 1left i - 1while left 0 and s[left] s[i]:length 1left - 1right i 1while right len(s) and s[right] s[i]:length 1right 1i 1while left 0 and right len(s) and s[left] s[right]:length 2left - 1right 1if length max_length:max_length lengthstart_index left1i 1return s[start_index:start_indexmax_length]解题思路要找到字符串 s 中的最长回文子串需要找到最长回文子串的长度 max_length 和回文子串的开始索引 start_index 。因为 s 的长度最短为1所以 max_length 最小为 1start_index 初始为 0以此为初始值当找到更长的回文子串时更新两者的值。
遍历字符串的每一个字符以每一个字符为标志位判断标志位左侧的字符是否与标志位的字符相同如果相同则继续向左找每找到一个字符回文子串的长度加1右侧也同理。这样可以找到标志位两侧与标志位相同的所有连续字符包含了奇数个和偶数个两种情况。
找完与标志位相同的连续字符后再继续找左边的字符与右边的字符相同的情况此时每找到一对相同的字符回文子串的长度加2直到两边的字符不同或到达字符串 s 的边界。完成后判断此次找到的最长回文长度和前面找到的长度如果更长就更新 max_length 和 start_index 的值。
进阶本文使用 while 循环在向右找到与标志位相同的连续字符时标志位的索引 i 也加1这样可以减少 while 的遍历次数提高程序的运行效率跑Leetcode上提供的用例可以缩短5倍左右的时间。同时在这种方式的循环中不需要向左寻找与标志位相同的连续字符代码不会执行到。上面还保留着向左寻找的代码是为了与解题思路保持一致方便理解。 相关阅读
【PythonCode】这些题不会做就选A
欢迎 点赞 收藏⭐ 评论 关注❤ 如有错误敬请指正
☟ 学Python点击下方名片关注我。☟
