力扣题库 - 简单题 - 仅记录学习

来源地址： 力扣 (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[num+1:]:#         return [num,nums[num+1:].index(other)+1+num]# 题解 2dict_val = {}for index,val in enumerate(nums):if target - val in dict_val:return [index,dict_val[target - val]]dict_val[val]=index

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 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')]

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 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

class Solution:def removeElement(self, nums: List[int], val: int) -> int:for num in range(nums.count(val)):nums.remove(val)return len(nums)

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 二分查找方法if target not in nums:l,r=0,len(nums)-1while l<=r:mid = (l+r)//2if nums[mid]<target:l=mid+1else:r=mid-1return lreturn nums.index(target)

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,p2=0,0while p1<m or p2<n:if p1==m:elist.append(nums2[p2])p2+=1elif p2==n:elist.append(nums1[p1])p1+=1elif nums1[p1]<nums2[p2]:elist.append(nums1[p1])p1+=1else:elist.append(nums2[p2])p2+=1nums1[:]=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:cost=min(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

给定一个  无重复元素 的 有序 整数数组 nums 。

区间 [a,b] 是从 a 到 b（包含）的所有整数的集合。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被

某个区间范围所覆盖，并且不存在属于某个区间但不属于 nums 的数字 x 。

列表中的每个区间范围 [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 i==j else f'{nums[i]}->{nums[j]}'res = []i=0while i<len(nums):f=iwhile f+1<len(nums) and nums[f+1]== nums[f]+1:f+=1res.append(fe(i,f))i=f+1return res

class Solution:def addDigits(self, num: int) -> int:# 最直观的方法是模拟各位相加的过程，直到剩下的数字是一位数。while num >= 10:sum = 0while num:sum += num % 10num //= 10num = sumreturn num

class Solution:def wordPattern(self, pattern: str, s: str) -> bool:# 判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。word_list=s.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

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,n=list(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

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