首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode【279、343】

Leetcode【279、343】

作者头像
echobingo
发布2019-07-22 11:35:32
5310
发布2019-07-22 11:35:32
举报
问题描述:【BFS、Math】279. Perfect Squares
解题思路:

这道题是给一个正整数 n,将其分解为平方数加法因子,使得分解后的因子最少。

这道题实际上和 Leetcode 【DP、BFS】322. Coin Change 很相似。我们将 <= n 的平方数因子当作硬币种类数,n 当作需要换的零钱,则可以使用相同的方法,即 DP 和 BFS 来求解。

方法1(DP,时间复杂度 O(n*sqrt(n)),TLE):

类似于 Leetcode 322,使用动态规划,时间复杂度 O(n*sqrt(n)),但是 DP 方法在这道题目中超时了,参考代码如下:

Python3 实现:

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n + 1)]  # 注意dp的初始化为dp[i]=i
        for i in range(2, int(math.sqrt(n)) + 1):
            sqr = i * i  # 平方数
            for j in range(sqr, n+1):
                dp[j] = min(dp[j], dp[j-sqr] + 1)  # 更新dp[i]处的最小值
        return dp[-1]

方法2(BFS,时间复杂度 O(n*sqrt(n)),AC):

类似于 Leetcode 322,使用广度优先遍历,时间复杂度 O(n*sqrt(n)),但是可以 AC。

Python3 实现:

class Solution:
    def numSquares(self, n: int) -> int:
        sn = []  # 保存平方数
        for i in range(1, int(math.sqrt(n)) + 1):
            sn.append(i * i)
        visited = [False] * (n + 1)  # 标记某个数字是否走过
        visited[0] = True
        q = collections.deque()
        q.append((0, 0))
        step = 0
        while True:
            while len(q) > 0 and q[0][1] == step:
                x, _ = q.popleft()  # 出队列
                if x == n:  # 程序出口
                    return step
                for num in sn:  # 对于每一种平方数选择
                    if x + num <= n and visited[x+num] == False:
                        q.append((x+num, step+1))
                        visited[x+num] = True
            step += 1
        return -1  # 不可达

方法3(Math,时间复杂度 O(sqrt(n)),AC):

其实这道题的最优解法是使用一个数学公式:四平方和定理。

四平方定理: 任何一个正整数都可以表示成不超过四个整数的平方之和。

那么这个问题的解法就变得很简单了,我们的结果只有 1、2、3、4 这四种可能。

另外还有一个非常重要的推论:

满足四数平方和定理的数 n(这里要满足由四个数构成,小于四个不行),必定满足 n = (4^a) * (8b + 7)

因此,我们可以得到此题解法:

  • 先根据推论判断 n 由 4 个平方数组成的情况:如果 n 是 4 的倍数,则可以通过除以 4 将输入的 n 迅速缩小。然后判断缩小后的数除以 8 能否余 7,如果余 7,则返回 4。
  • 再判断 n 由 1 个或 2 个平方数组成的情况:对缩小后的 n 可以使用暴力破解,来判断一个数是由 1 个还是由 2 个平方数的和构成。返回 1 或者 2。
  • 那么,剩下的一种情况就是 n 由 3 个平方数组成的情况,返回 3 即可。

此题的时间复杂度主要消耗在判断 n 由 1 个或 2 个平方数组成的情况时,时间复杂度为 O(sqrt(n))。这里在编程时有一个点需要注意:比如 n = 25 这种,它应该返回 1(即 5 * 5),而不是返回 2 (即 3 * 3 + 4 * 4),因此我们的平方数要从大(int(sqrt(n)))到小(1)取,才能保证不会先出现 3 * 3 + 4 * 4 的情况

Python3 实现:

class Solution:
    def numSquares(self, n: int) -> int:
        while n % 4 == 0:  #(4^a)*(8b+7)缩减为8b+7
            n //= 4
        if n % 8 == 7:  # 如果余数为7,说明可以由4个平方数组成
            return 4
        for i in range(int(math.sqrt(n)), 0, -1): # 判断是否由1或2个平方数组成,从大的平方数取
            if i * i == n:  # 一个平方数满足
                return 1
            j = int(math.sqrt(n - i * i)) # 注意要取整
            if i * i + j * j == n:  # 两个平方数满足
                return 2
        return 3  # 剩下的就是由3个平方数组成
问题描述:【Math】343. Integer Break
解题思路:

这道题是给一个正整数 n,将其分解为若干正整数加法因子,使得分解后的因子乘积最大。

这道题看了数据范围,DFS 回溯法肯定不行,因此可以找规律。刚开始想到数字 12,发现 3 * 3 * 3 * 3 的分解结果要比 4 * 4 * 4 (或 2 * 2 * 2 * 2 * 2 * 2) 的分解结果大,因此猜想分解中的因子应该尽可能多的包含 3 而不是 4(或者 2)。

可以依次写出前面几个数字的结果:

  • dp2:1 * 1 = 1;
  • dp3:1 * 2 = 2;
  • dp4:2 * 2 = 4;
  • dp5:2 * 3 = 6;
  • dp6:3 * 3 = 9;
  • dp7:3 * dp4 = 3 * 2 * 2 = 12;
  • dp8:3 * dp5 = 3 * 2 * 3 * = 18;
  • dp9:3 * dp6 = 3 * 3 * 3 = 27;
  • dp10:3 * dp7 = 3 * 3 * 2 * 2 = 36;
  • ...

由此可以发现规律:dpn:3 * dpn-3

因此,对于 n <= 6,直接返回上述结果;对于 n > 6,每次将结果乘以 3,然后将 n 减去 3,直到 n <= 6 为止,最后将累成的结果乘以 n 就是答案。

这种做法的时间复杂度为 O(n),空间复杂度为 O(1)。

Python3 实现:
class Solution:
    def integerBreak(self, n: int) -> int:
        ansTo6 = [0, 1, 1, 2, 4, 6, 9]
        ans = 1
        while n > 6:
            ans *= 3  # 累乘结果
            n -= 3
        return ans * ansTo6[n]  # 最后将结果乘以n
改进:

其实还可以对上述程序进行改进,获得时间复杂度为 O(1) 的做法。即根据对 3 取余判断其余数,然后根据余数的不同直接计算乘积结果。代码如下:

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2: return 1
        if n == 3: return 2
        if n % 3 == 0: return 3 ** (n//3)
        if n % 3 == 1: return 3 ** (n//3-1) * 4
        if n % 3 == 2: return 3 ** (n//3) * 2
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019.07.20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述:【BFS、Math】279. Perfect Squares
  • 解题思路:
  • 问题描述:【Math】343. Integer Break
  • 解题思路:
  • Python3 实现:
  • 改进:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档