Python版Day6-Toy模板网

这篇具有很好参考价值的文章主要介绍了Python版Day6。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        nums_map = dict()
        for num1 in nums1:
            for num2 in nums2:
                nums_map[num1+num2] = nums_map.get(num1+num2,0)+1
        res = 0
        for num3 in nums3:
            for num4 in nums4:
                res += nums_map.get(-(num3+num4),0)
        return res

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ransom-note
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransomNote_letters = [0]*26
        magazine_letters = [0]*26
        for i in range(len(ransomNote)):
            ransomNote_letters[ord(ransomNote[i]) - ord('a') ]+=1
        for i in range(len(magazine)):
            magazine_letters[ord(magazine[i]) - ord('a') ]+=1
        for i in range(26):
            if ransomNote_letters[i] > magazine_letters[i]:
                return False
        return True

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                return result
            # 对第一个数字去重
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i+1
            right = len(nums)-1
            while right>left:
                sum_ = nums[i] + nums[left] + nums[right]
                if sum_ == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    # 对第二个数字去重
                    while left<right and nums[left]==nums[left+1]:
                        left+=1
                    # 对第三个数字去重
                    while left<right and nums[right]==nums[right-1]:
                        right-=1

                    right -=1
                    left +=1
                elif sum_ <0:
                    left +=1
                else:
                    right -=1
        return result

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        nums.sort()
        for i in range(len(nums)):
            a = nums[i]
            # 剪枝
            if a > target and a >0 and target>0:
                break
            # 对a去重
            if i >0 and  nums[i] ==nums[i-1]:
                continue
            for j in range(i+1,len(nums)):
                b = nums[j]
                # 剪枝
                if a+b>target and target>0:
                    break;
                # 对b去重
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                # 双指针
                left = j+1
                right = len(nums)-1
                while left<right:
                    c = nums[left]
                    d = nums[right]
                    sum_ = a + b + c + d
                    if sum_>target:
                        right-=1
                    elif sum_<target:
                        left+=1
                    else:
                        result.append([a,b,c,d])
                        # 对c去重
                        while left<right and nums[right] == nums[right-1]:
                            right-=1
                        # 对d去重
                        while left<right and nums[left] == nums[left+1]:
                            left+=1
                        right -=1
                        left +=1
            
        return result

文章来源地址https://www.toymoban.com/news/detail-472149.html

到了这里，关于Python版Day6的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！