摘要：字母区分大小写，因此和是不同类型的石头。输入输出暴力解法将宝石中的每个元素在石头中的数量相加的时间复杂度为石头中的每个元素此元素在宝石中则官方解法哈希表将搜索的时间复杂度变为
本文章基于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)
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/123495.html
摘要：正式地讲，提莫在发起发起攻击意味着艾希在时间区间含和处于中毒状态。示例输入输出解释提莫攻击对艾希的影响如下第秒，提莫攻击艾希并使其立即中毒。第秒，提莫再次攻击艾希，艾希中毒状态又持续秒，即第秒和第秒。 ...
摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
前端LeetCode刷题 下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。 数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...
⭐️前面的话⭐️ 大家好！这是Java基础知识与数据结构博文的导航帖，收藏我！学习Java不迷路！ ?博客主页：未见花闻的博客主页 ?欢迎关注?点赞?收藏⭐️留言? ?本文由未见花闻原创，CSDN首发！ ?首发时间：?2021年11月11日? ✉️坚持和努力一定能换来诗与远方！ ?参考书籍：?《Java核心技术卷1》，?《Java核心技术卷2》，?《Java编程思想》 ?参考在线编程网站：?牛...
阅读 1521·2021-11-18 10:02
阅读 3345·2021-11-16 11:45
阅读 1619·2021-09-10 10:51
阅读 1943·2019-08-30 15:43
阅读 1265·2019-08-30 11:23
阅读 1376·2019-08-29 11:07
阅读 1781·2019-08-23 17:05
阅读 1226·2019-08-23 16:14
