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)

 

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>