力扣题库 - 简单题 - 仅记录学习
来源地址： 力扣 (LeetCode) 全球极客挚爱的技术成长平台
给定一个整数数组 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]
# 题解 2
dict_val = {}
for index,val in enumerate(nums):
if target - val in dict_val:
return [index,dict_val[target - val]]
dict_val[val]=index
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 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:
break
return 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 False
return len(elist) == 1给你一个数组 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)给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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,r=0,len(nums)-1
while l<=r:
mid = (l+r)//2
if nums[mid]<target:
l=mid+1
else:
r=mid-1
return l
return nums.index(target)
给你两个按 非递减顺序 排列的整数数组 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,p2=0,0
while p1<m or p2<n:
if p1==m:
elist.append(nums2[p2])
p2+=1
elif p2==n:
elist.append(nums1[p1])
p1+=1
elif nums1[p1]<nums2[p2]:
elist.append(nums1[p1])
p1+=1
else:
elist.append(nums2[p2])
p2+=1
nums1[:]=elist给定一个数组 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'),0
for p in prices:
cost=min(cost,p)
profit = max(profit,p-cost)
return profit给定两个字符串 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 False
return True给你一个整数数组 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 True
pos[num] = i
return False给定一个 无重复元素 的 有序 整数数组 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 i==j else f'{nums[i]}->{nums[j]}'
res = []
i=0
while i<len(nums):
f=i
while f+1<len(nums) and nums[f+1]== nums[f]+1:
f+=1
res.append(fe(i,f))
i=f+1
return res给定一个非负整数 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 = 0
while num:
sum += num % 10
num //= 10
num = sum
return num给定一种规律 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_list=s.split()
if len(word_list)!=len(pattern):
return False
mp1,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 False
mp1[a]=b
mp2[b]=a
return True给你两个字符串：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,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 True
else:
return False给定字符串 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 = 0
while i < n and j < m:
if s[i] == t[j]:
i += 1
j += 1
return i == n