Skip to content

Latest commit

 

History

History
517 lines (370 loc) · 15.2 KB

基础-数学.md

File metadata and controls

517 lines (370 loc) · 15.2 KB
Raw

数学

Problems

LeetCode 0343 整数拆分 (中等, 2021-12)

数学 动态规划 LeetCode

问题简述 
给定一个正整数 n，将其拆分为至少两个正整数的和，使这些整数的乘积最大化。返回最大乘积。
详细描述 
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：动态规划
  • 在不使用任何数学结论的前提下，可以把本题当做纯 DP 来做：
Python（写法1）

LeetCode 官方题解中的写法：整数拆分

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n + 1)

        for i in range(2, n + 1):
            for j in range(1, i):
                # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>=1）
                #   j * (i - j)   表示将 i 拆分成 j 和 i-j，且 i-j 不再拆分
                #   j * dp[i - j] 表示将 i 拆分成 j 和 i-j，且 i-j 会继续拆分，dp[i-j] 即为继续拆分的最优结果（最优子结构）
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

        return dp[n]
Python（写法2）

《剑指Offer》中的写法

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 对于 n = 2、3 的情况，直接硬编码
        if n == 2:
            return 1
        if n == 3:
            return 2

        # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>3）
        #   当 i <= 3 时，不满足该定义，此时不拆效率最高
        #   初始状态（dp[0] 仅用于占位）
        dp = [0,1,2,3] + [0] * (n - 3) 

        for i in range(4, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], dp[i-j] * dp[j])

        return dp[n]
思路2：数学/贪心

  • 数学上可证：尽可能按长度为 3 切，如果剩余 4，则按 2、2 切；

    证明见：剪绳子1（数学推导 / 贪心思想，清晰图解）

  • 简述：当 x >= 4 时，有 2(x-2) = 2x - 4 >= x；简言之，对任意大于等于 4 的因子，都可以拆成 2 和 x-2 而不损失性能；因此只需考虑拆成 2 或 3 两种情况（1除外）；而由于 2*2 > 3*1 和 3*3 > 2*2*2，可知最多使用两个 2；

Python 
class Solution:
    def cuttingRope(self, n: int) -> int:
        import math
        if n <= 3:
            return n - 1
        
        a, b = n // 3, n % 3
        if b == 1:
            return int(math.pow(3, a - 1) * 4)
        elif b == 2:
            return int(math.pow(3, a) * 2)
        else:
            return int(math.pow(3, a))

LeetCode 0441 排列硬币 (简单, 2021-10)

二分查找 数学 LeetCode

问题简述 
你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例 1：
    输入：n = 5
    输出：2
    解释：因为第三行不完整，所以返回 2 。

提示：
    1 <= n <= 2^31 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arranging-coins
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
法1）Python：二分查找
  • 因为时间复杂度为 O(logN)，所以直接在 [1, n] 的范围里找即可
class Solution:
    def arrangeCoins(self, n: int) -> int:
        left, right = 1, n
        while left < right:
            mid = (left + right + 1) // 2
            if mid * (mid + 1) <= 2 * n:
                left = mid
            else:
                right = mid - 1
        return left
法2）Python：数学公式
  • 解方程 $(1+x)*x/2 = n$；
  • 去掉小于 0 的解，保留：$x=(-1+\sqrt{8n+1})/2$
class Solution:
    def arrangeCoins(self, n: int) -> int:
        return int((-1 + (8 * n + 1) ** 0.5) / 2)

剑指Offer 1401 剪绳子（整数拆分） (中等, 2021-11)

动态规划 贪心 数学 剑指Offer

问题简述 
给定一个正整数 n，将其拆分为至少两个正整数的和，使这些整数的乘积最大化。返回最大乘积。
详细描述 
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
    2 <= n <= 58

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：动态规划
  • 在不使用任何数学结论的前提下，可以把本题当做纯 DP 来做：
Python（写法1）

LeetCode 官方题解中的写法：整数拆分

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n + 1)

        for i in range(2, n + 1):
            for j in range(1, i):
                # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>=1）
                #   j * (i - j)   表示将 i 拆分成 j 和 i-j，且 i-j 不再拆分
                #   j * dp[i - j] 表示将 i 拆分成 j 和 i-j，且 i-j 会继续拆分，dp[i-j] 即为继续拆分的最优结果（最优子结构）
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

        return dp[n]
Python（写法2，推荐）

《剑指Offer》中的写法

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 对于 n = 2、3 的情况，直接硬编码
        if n == 2:
            return 1
        if n == 3:
            return 2

        # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>3）
        #   当 i <= 3 时，不满足该定义，此时不拆效率最高
        #   初始状态（dp[0] 仅用于占位）
        dp = [0,1,2,3] + [0] * (n - 3) 

        for i in range(4, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], dp[i-j] * dp[j])

        return dp[n]
思路2：数学/贪心

  • 数学上可证：尽可能按长度为 3 切，如果剩余 4，则按 2、2 切；

    证明见：剪绳子1（数学推导 / 贪心思想，清晰图解）

  • 简述：当 x >= 4 时，有 2(x-2) = 2x - 4 >= x；简言之，对任意大于等于 4 的因子，都可以拆成 2 和 x-2 而不损失性能；因此只需考虑拆成 2 或 3 两种情况（1除外）；而由于 2*2 > 3*1 和 3*3 > 2*2*2，可知最多使用两个 2；

Python 
class Solution:
    def cuttingRope(self, n: int) -> int:
        import math
        if n <= 3:
            return n - 1
        
        a, b = n // 3, n % 3
        if b == 1:
            return int(math.pow(3, a - 1) * 4)
        elif b == 2:
            return int(math.pow(3, a) * 2)
        else:
            return int(math.pow(3, a))

剑指Offer 1402 剪绳子 (中等, 2021-11)

数学 剑指Offer

问题简述 
将 n 拆分为 m 段（m、n 都是整数，且 n>1 and m>1），求可能的最大乘积；

答案需取模 1e9+7（1000000007）
详细描述 
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：
    2 <= n <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 本题与“剪绳子1”的区别仅在于 n 的范围；
  • 对于较大的 n，使用动态规划可能会超时；
Python 
class Solution:
    def cuttingRope(self, n: int) -> int:

        if n == 2:
            return 1
        if n == 3:
            return 2

        y = n % 3  # 余数

        if y == 2:
            ret = 3 ** (n // 3) * 2
        elif y == 1:
            ret = 3 ** (n // 3 - 1) * 4
        else:
            ret = 3 ** (n // 3)
        
        return ret % 1000000007

牛客 0056 回文数字 (简单, 2022-03)

数学 牛客

问题简述 
在不使用额外的内存空间的条件下判断一个整数是否是回文。
回文指逆序和正序完全相同。

回文数字_牛客题霸_牛客网

思路1：模拟
  • 通过数学计算，不断获取首位和末位，比较；
  • 注意使用 log10 计算数字的位数时，x 不能为 0；
Python 
class Solution:
    def isPalindrome(self , x: int) -> bool:
        # write code here
        import math
        
        # 负数不符合
        if x < 0: return False
        
        # 获取 x 的位数
        #     +0.1 防止 x 为 0，因为 x 为整数，所以不会影响结果
        n = math.ceil(math.log10(x + 0.1))
        
        # n > 0 也可以，大于 1 更好，如果最后只剩一个数字，必然符合
        while n > 1:  
            l = x // (10 ** (n - 1))
            r = x % 10
            if l != r:
                return False
            x -= l * 10 ** (n - 1)  # 移去首位
            x //= 10  # 移去末位
            n -= 2  # 位数减 2
        
        return True
思路2：反转数字
Python 
class Solution:
    def isPalindrome(self , x: int) -> bool:
        if x < 0: return False
        
        ret = 0
        tmp = x
        while tmp:
            c = tmp % 10
            ret = ret * 10 + c
            tmp //= 10
        
        return ret == x