枚举算法:解决问题的穷举之道(二)

2023-12-27 18:01:02

💗💗💗欢迎来到我的博客,你将找到有关如何使用技术解决问题的文章,也会找到某个技术的学习路线。无论你是何种职业,我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章,也欢迎在文章下方留下你的评论和反馈。我期待着与你分享知识、互相学习和建立一个积极的社区。谢谢你的光临,让我们一起踏上这个知识之旅!
请添加图片描述

🍋1925. 统计平方和三元组的数目

一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 a,b 和 c 。

给你一个整数 n ,请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。
在这里插入图片描述

class Solution(object):
    def countTriples(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        for i in range(2,n+1):
            for j in range(i+1,n+1):
                for k in range(j+1,n+1):
                    if i**2 + j**2 == k**2:
                        count+=1
        return count*2

🍋2605. 从两个数字数组里生成最小数字

给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ,每个数组中的元素 互不相同 ,请你返回 最小 的数字,两个数组都 至少 包含这个数字的某个数位。

在这里插入图片描述

class Solution(object):
    def minNumber(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        min_ = 0
        l_ = []
        for i in nums1:
            if i in nums2:
                l_.append(i)
        if len(l_)!=0:
            min_ = sorted(l_)[0]
            return min_
        else:
            if min_ == 0:
                s1 = sorted(nums1)
                s2 = sorted(nums2)
                s3 = s1[0]
                s4 = s2[0]
                return int(str(min(s3,s4)) + str(max(s3,s4)))

🍋1995. 统计特殊四元组

给你一个 下标从 0 开始 的整数数组 nums ,返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 :

nums[a] + nums[b] + nums[c] == nums[d] ,且
a < b < c < d

在这里插入图片描述

class Solution(object):
    def countQuadruplets(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        count = 0
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                for k in range(j+1,len(nums)):
                    for z in range(k+1,len(nums)):
                        if nums[i] + nums[j] + nums[k] == nums[z]:
                            count+=1
        return count

🍋869. 重新排序得到 2 的幂

给定正整数 n ,我们按任何顺序(包括原始顺序)将数字重新排序,注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂,返回 true;否则,返回 false。

在这里插入图片描述

import math
class Solution(object):
    def reorderedPowerOf2(self, n):
        """
        :type n: int
        :rtype: bool
        """
        l_ = []
        for i in range(30):
           l_.append(Counter(str(1<<i)))
        return any(Counter(str(n)) == s for s in l_)

🍋816. 模糊坐标

我们有一些二维坐标,如 “(1, 3)” 或 “(2, 0.5)”,然后我们移除所有逗号,小数点和空格,得到一个字符串S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零,所以不会出现类似于"00", “0.0”, “0.00”, “1.0”, “001”, "00.01"或一些其他更小的数来表示坐标。此外,一个小数点前至少存在一个数,所以也不会出现“.1”形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间(逗号之后)都有一个空格。
在这里插入图片描述

class Solution:
    def ambiguousCoordinates(self, s) :
        def get_pos(s):
            pos = []
            if s[0] != '0' or s == '0':
                pos.append(s)
            for p in range(1, len(s)):
                if p != 1 and s[0] == '0' or s[-1] == '0':
                    continue
                pos.append(s[:p] + '.' + s[p:])
            return pos

        n = len(s) - 2
        res = []
        s = s[1: len(s) - 1]
        for l in range(1, n):
            lt = get_pos(s[:l])
            if len(lt) == 0:
                continue
            rt = get_pos(s[l:])
            if len(rt) == 0:
                continue
            for i, j in product(lt, rt):
                res.append('(' + i + ', ' + j + ')')
        return res

🍋2240. 买钢笔和铅笔的方案数

给你一个整数 total ,表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 ,分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱,去买任意数目的两种笔。

请你返回购买钢笔和铅笔的 不同方案数目 。
在这里插入图片描述

class Solution(object):
    def waysToBuyPensPencils(self, total, cost1, cost2):
        """
        :type total: int
        :type cost1: int
        :type cost2: int
        :rtype: int
        """
        # count = 0
        # sum3 = 0
        # for i in range(total//cost1+1): # 2
        #     for j in range(total//cost2+1): # 4
        #         sum3 = i*cost1+j*cost2
        #         if sum3<=total:
        #             count+=1
        # return count  # 超时了
        n = 1 + total // cost1
        return n + sum((total - cost1 * i) // cost2 for i in range(n))

大佬的思路很好https://leetcode.cn/problems/number-of-ways-to-buy-pens-and-pencils/solutions/1426720/mei-ju-mai-liao-duo-shao-zhi-gang-bi-by-r97vg/

请添加图片描述

挑战与创造都是很痛苦的,但是很充实。

文章来源:https://blog.csdn.net/null18/article/details/135246881
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。