脚本宝典收集整理的这篇文章主要介绍了Leetcode 刷题(持续更新),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
本文章基于Datewhale第30期组队学习
2021.11.15
# 1 两数之和 # 给定一个整数数组 nums 和一个整数目标值 target, # 请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。 # 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现
# 1.两层 for 循环 暴解 O(n^2)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
length = len(nums)
for i in range(length):
for j in range(i+1, length): # 从i+1 开始查找,因为i+1 之前的已经查找匹配过了
if nums[i] + nums[j] == target:
return [i, j]
# 时间太长了(大概2800左右) 尝试O(n)的方法
# 2. 哈希表 O(n)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
mp = {}
for i in range(len(nums)):
mp[nums[i]] = i # 因为每种输入只对应一个答案,所以只存储最后一个 值 的下标
for i in range(len(nums)):
if target - nums[i] in mp.keys() and mp[target - nums[i]] != i: # 防止返回两次自身的下标
return [i, mp[target - nums[i]]]
# 1929. 数组串联 # 给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans , # 数组下标 从 0 开始计数 ,对于所有 0 <= i < n 的 i ,满足下述所有要求: # ans[i] == nums[i] # ans[i + n] == nums[i] # 具体而言,ans 由两个 nums 数组 串联 形成。
"""
例:输入:nums = [1,2,1]
输出:[1,2,1,1,2,1]
解释:数组 ans 按下述方式形成:
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]
"""
# 如题所述
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
length = len(nums)
ans = [0] * 2 * length
length = len(nums)
for i in range(length):
ans[i] = nums[i]
ans[i + length ] = nums[i]
return ans
# 但实际上只需要将 nums * 2 或者 用 extend 即可
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
# return nums * 2
# return nums + nums
nums.extend(nums)
return nums
# 771. 宝石与石头 # 给你一个字符串 jewels 代表石头中宝石的类型,另有一个字符串 stones 代表你拥有的石头。 # stones 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。 # 字母区分大小写,因此 "a" 和 "A" 是不同类型的石头。
""""
输入:jewels = "aA", stones = "aAAbbbb"
输出:3
"""
# 暴力解法 O(mn)
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
# return sum(stones.count(i) for i in jewels) # 将 宝石中 的每个元素在 石头中的数量相加
num = 0 # string.count的时间复杂度为 O(n)
for i in stones: # 石头中的每个元素
if i in jewels: # 此元素在 宝石 中 则 num++
num += 1
return num
# O(m+n) 官方解法
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
jewelsSet = set(jewels) # 哈希表 将搜索的时间复杂度变为O(1)
return sum(s in jewelsSet for s in stones)
以上是脚本宝典为你收集整理的Leetcode 刷题(持续更新)全部内容,希望文章能够帮你解决Leetcode 刷题(持续更新)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。