CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

    • 贪心算法理论基础
    • 找零
    • 柠檬水找零
    • 分发饼干
    • K 次取反后最大化的数组和
    • 加油站
    • 分发糖果
    • 根据身高重建队列
    • 划分字母区间
    • 单调递增的数字
    • 监控二叉树
    • 使数组变成交替数组的最少操作数
    • 剑指 Offer 14- II - 剪绳子 II
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 区间调度问题

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 贪心算法
小牛肉
2022-09-28
目录

剑指 Offer 14- II - 剪绳子 II

# 📃 题目描述

题目链接:

# 🔔 解题思路

和这题 剑指 Offer 14- I. 剪绳子 (opens new window) 的唯一不同就是,这里的 n 范围变大了,如果用 dp 来做,会出现大数越界情况,对每次的dp[i] 取余确实可以避免溢出的问题,但是由于过程中修改了值,会导致最终结果和预期不同,比如 dp[i] = Math.max(dp[i] ,x * y ); x * y = 1000000005 ,若dp[i] 本该等于 1000000008 ,但是经过上次取余后变成了1,本来的结果应该是1000000008 ,现在却变成了1000000005,所以在动态规划过程中是不能取余的。可以使用 BigInter 来存储结果,把 dp 数组类型改成 BigInteger 就行,这里就不写了。

我们这里想给出的算法思想是贪心:

  • 当绳子长度大于4时,尽可能多的分成长度为3的小段,这样乘积是最大的(数学证明自行查找)

思路:

  • n 小于 4 时,返回 n-1
  • n 等于 4 时,返回 4
  • n 大于 4 时,就要切割成长度为 3 的小段,只要 n 还大于 4,每切除一段 3,就累乘起来,然后取模
class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        else if (n == 4) {
            // 2x2 > 3x1
            return 4;
        }
		
        long res = 1;
        // n > 4
        while (n > 4) {
            res = (res * 3) % 1000000007;
            n -= 3;
        }

        // n == 4, 拆成 2*2 = 4
        return (int)((res * n) % 1000000007);

    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
使数组变成交替数组的最少操作数
无重叠区间

← 使数组变成交替数组的最少操作数 无重叠区间→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式