网站建设考虑因素,网站架构模板,网站排名快速提升工具,做安全防护信息的网站力扣题库 - 简单题 - 仅记录学习
来源地址#xff1a; 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你…力扣题库 - 简单题 - 仅记录学习
来源地址 力扣 (LeetCode) 全球极客挚爱的技术成长平台 1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1
输入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]:# 题解 1# for num in range(len(nums)):# other target - nums[num]# if other in nums[num1:]:# return [num,nums[num1:].index(other)1num]# 题解 2dict_val {}for index,val in enumerate(nums):if target - val in dict_val:return [index,dict_val[target - val]]dict_val[val]index14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 。
示例 1
输入strs [flower,flow,flight]
输出fl
示例 2
输入strs [dog,racecar,car]
输出
解释输入不存在公共前缀。
class Solution:def longestCommonPrefix(self, strs: List[str]) - str:data for i in list(zip(*strs)):if len(set(i)) 1:data i[0]else:breakreturn data提示 zip(*strs) strs [flower,floo,wwsds] print(list(zip(*strs))) # [(f, f, w), (l, l, w), (o, o, s), (w, o, d)] 20. 有效的括号给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 示例 1
输入s ()
输出true
示例 2
输入s ()[]{}
输出true class Solution:def isValid(self, s: str) - bool:elist [?]dic {{: }, [: ], (: ), ?: ?}for val in list(s):if val in dic:elist.append(val)else:if dic[elist.pop()] !val:return Falsereturn len(elist) 1 27. 移除元素 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作 更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。 class Solution:def removeElement(self, nums: List[int], val: int) - int:for num in range(nums.count(val)):nums.remove(val)return len(nums) 35. 搜索插入位置 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5输出: 2 示例 2: 输入: nums [1,3,5,6], target 2输出: 1 class Solution:def searchInsert(self, nums: List[int], target: int) - int:# 二分查找方法if target not in nums:l,r0,len(nums)-1while lr:mid (lr)//2if nums[mid]target:lmid1else:rmid-1return lreturn nums.index(target)88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。 注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。 示例 1 输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6] 解释需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。 class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None:Do not return anything, modify nums1 in-place instead.# 方法1 直接合并后排序# nums1[m:]nums2# nums1.sort()# 方法二 我们为两个数组分别设置一个指针 p1 与 p2 来作为队列的头部指针elist[]p1,p20,0while p1m or p2n:if p1m:elist.append(nums2[p2])p21elif p2n:elist.append(nums1[p1])p11elif nums1[p1]nums2[p2]:elist.append(nums1[p1])p11else:elist.append(nums2[p2])p21nums1[:]elist
121. 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。 注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。
class Solution:def maxProfit(self, prices: List[int]) - int:cost,profit float(inf),0for p in prices:costmin(cost,p)profit max(profit,p-cost)return profit
205. 同构字符串
给定两个字符串 s 和 t 判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t 那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符同时不改变字符的顺序。不同字符不能映射到同一个字符上相同字符只能映射到同一个字符上字符可以映射到自己本身。
示例 1:
输入s egg, t add
输出true
class Solution:def isIsomorphic(self, s: str, t: str) - bool:# 方法1-索引标记for i in range(len(s)):if s.index(s[i]) ! t.index(t[i]):return Falsereturn True
219. 存在重复元素 II
给你一个整数数组 nums 和一个整数 k 判断数组中是否存在两个 不同的索引 i 和 j 满足 nums[i] nums[j] 且 abs(i - j) 。如果存在返回 true 否则返回 false 。
示例 1
输入nums [1,2,3,1], k 3 输出true
示例 2
输入nums [1,0,1,1], k 1 输出true
示例 3
输入nums [1,2,3,1,2,3], k 2 输出false
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) - bool:pos {}# 方法一哈希表for i, num in enumerate(nums):if num in pos and i - pos[num] k:return Truepos[num] ireturn False
228. 汇总区间给定一个 无重复元素 的 有序 整数数组 nums 。
区间 [a,b] 是从 a 到 b包含的所有整数的集合。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说nums 的每个元素都恰好被
某个区间范围所覆盖并且不存在属于某个区间但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出 a-b 如果 a ! b a 如果 a b 示例 1
输入nums [0,1,2,4,5,7]
输出[0-2,4-5,7]
解释区间范围是[0,2] -- 0-2[4,5] -- 4-5[7,7] -- 7 class Solution:def summaryRanges(self, nums: List[int]) - List[str]:def fe(i:int,j:int):return str(nums[i]) if ij else f{nums[i]}-{nums[j]}res []i0while ilen(nums):fiwhile f1len(nums) and nums[f1] nums[f]1:f1res.append(fe(i,f))if1return res 258. 各位相加 给定一个非负整数 num反复将各个位上的数字相加直到结果为一位数。返回这个结果。 示例 1: 输入: num 38 输出: 2 解释: 各位相加的过程为 38 -- 3 8 -- 11 11 -- 1 1 -- 2 由于 2 是一位数所以返回 2。 class Solution:def addDigits(self, num: int) - int:# 最直观的方法是模拟各位相加的过程直到剩下的数字是一位数。while num 10:sum 0while num:sum num % 10num // 10num sumreturn num 290. 单词规律 给定一种规律 pattern 和一个字符串 s 判断 s 是否遵循相同的规律。 这里的 遵循 指完全匹配例如 pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 示例1: 输入: pattern abba, s dog cat cat dog 输出: true class Solution:def wordPattern(self, pattern: str, s: str) - bool:# 判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串任意一个字符串也只被唯一的一个字符对应。在集合论中这种关系被称为「双射」。word_lists.split()if len(word_list)!len(pattern):return Falsemp1,mp2{},{}for a,b in zip(pattern,word_list):if a in mp1 and mp1[a]!b or b in mp2 and mp2[b]!a:return Falsemp1[a]bmp2[b]areturn True 383. 赎金信 给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以返回 true 否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1 输入ransomNote a, magazine b 输出false 示例 2 输入ransomNote aa, magazine ab 输出false from collections import Counter
class Solution:def canConstruct(self, ransomNote: str, magazine: str) - bool:# 方法1 Counter 用法 cnt Counter(aab) # Counter({a: 2, b: 1})# cnt Counter(magazine) # # Counter({d: 3, b: 2, c: 2, a: 1})# for c in ransomNote:# cnt[c]-1# if cnt[c]0:# return False# return True# 方法2 字符遍历m,nlist(magazine),list(ransomNote)for i in range(len(m)):if m[i] in n:n.remove(m[i])if len(n)0:return Trueelse:return False 392. 判断子序列 给定字符串 s 和 t 判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。 示例 1 输入s abc, t ahbgdc 输出true class Solution:def isSubsequence(self, s: str, t: str) - bool:# 方法一双指针n, m len(s), len(t)i j 0while i n and j m:if s[i] t[j]:i 1j 1return i n
