[leetcode/lintcode 题解] 阿里面试真题:双色塔

简介: [leetcode/lintcode 题解] 阿里面试真题:双色塔

描述
现在有红,绿两种颜色的石头,现在我们需要用这两种石头搭建一个塔,塔需要满足如下三个条件:

  1. 第1层应该包含1块石头,第2层应该包含2块,第i层需要包含i块石头。
  2. 同一层的石头应该是同一个颜色(红或绿)。
  3. 塔的层数尽可能多。

在满足上面三个条件的前提下,有多少种不同的建造塔的方案?当塔中任意一个对应位置的石头颜色不同,我们就认为这两个方案不相同。石头可以不用完。
由于答案可能会很大,请对10^9+7取模。

  • red+green≥1
  • 0≤red,green≤6×104

在线评测地址:领扣题库官网

样例1
输入: 4 6
输出: 2
说明: 有两种方案:[红,绿,红,绿],[绿,绿,绿,红]

源代码

public int twoColorsTower(int red, int green) {
        if (red == 0 || green == 0) {
            return 1;
        }

        if (red > green) {
            int temp = red;
            red = green;
            green = temp;
        }
        // dp[i&1][j]表示前i层一共放j个红石头
        int[][] dp = new int[2][red + 1];
        dp[1][0] = dp[1][1] = 1;
        int level = (int) Math.sqrt(2 * (red + green));
        int sum = 1, lower = 0, upper = red;
        int curr = 1, prev;
        int MOD = (int) 1.0e9 + 7;
        
        for (int i = 2; i <= level; i++) {
            sum += i;
            int tmpUpper = Math.min(sum, red);
            int tmpLower = Math.max(sum - green, 0);
            // 红石头不够了,已经是最高层,停止更新
            if (tmpLower > tmpUpper) break;
            upper = tmpUpper;
            lower = tmpLower;
            prev = curr;
            curr = curr ^ 1;

            // j小于本层i,红石只能是之前都放完了
            for (int j = lower; j < i; j++) {
                dp[curr][j] = dp[prev][j];
            }
            // 转移方程:dp[i][j] = dp[i-1][j] + dp[i-1][j-i] (when j>=i)
            // dp[i-1][j]表示第i层放绿石 dp[i-1][j-i]表示i层放红石
            for (int j = i; j <= upper; j++) {
                dp[curr][j] = (dp[prev][j] + dp[prev][j - i]) % MOD;
            }
        }
        int ans = 0;
        for (int j = lower; j <= upper; j++) {
            ans = (ans + dp[curr][j]) % MOD;
        }
        return ans;
    }

更多题解参考:九章官网solution

相关文章
|
27天前
|
存储 SQL 算法
阿里面试:每天新增100w订单,如何的分库分表?这份答案让我当场拿了offer
例如,在一个有 10 个节点的系统中,增加一个新节点,只会影响到该新节点在哈希环上相邻的部分数据,其他大部分数据仍然可以保持在原节点,大大减少了数据迁移的工作量和对系统的影响。狠狠卷,实现 “offer自由” 很容易的, 前段时间一个武汉的跟着尼恩卷了2年的小伙伴, 在极度严寒/痛苦被裁的环境下, offer拿到手软, 实现真正的 “offer自由”。在 3 - 5 年的中期阶段,随着业务的稳定发展和市场份额的进一步扩大,订单数据的增长速度可能会有所放缓,但仍然会保持在每年 20% - 30% 的水平。
阿里面试:每天新增100w订单,如何的分库分表?这份答案让我当场拿了offer
|
2月前
|
监控 Kubernetes Java
阿里面试:5000qps访问一个500ms的接口,如何设计线程池的核心线程数、最大线程数? 需要多少台机器?
本文由40岁老架构师尼恩撰写,针对一线互联网企业的高频面试题“如何确定系统的最佳线程数”进行系统化梳理。文章详细介绍了线程池设计的三个核心步骤:理论预估、压测验证和监控调整,并结合实际案例(5000qps、500ms响应时间、4核8G机器)给出具体参数设置建议。此外,还提供了《尼恩Java面试宝典PDF》等资源,帮助读者提升技术能力,顺利通过大厂面试。关注【技术自由圈】公众号,回复“领电子书”获取更多学习资料。
|
1月前
|
缓存 NoSQL Java
阿里面试:DDD 落地,遇到哪些 “拦路虎”?如何破局?
为每个子领域定义限界上下文(bounded context),限界上下文是一个清晰定义了领域模型的边界的范围。在限界上下文内,领域模型的概念是一致的,但不同限界上下文之间可以有不同的模型和语言。界限上下文,基本可以对应到 落地层面的 微服务。这就是 DDD 建模和 微服务架构, 能够成为孪生兄弟、 天然统一的原因。具体的方法论和落地实操,请参考 《第34章视频 DDD学习圣经》DDD 战略设计的第一步就是统一语言,也叫通用语言(UBIQUITOUS LANGUAGE),用于定义上下文。
阿里面试:DDD 落地,遇到哪些 “拦路虎”?如何破局?
|
1月前
|
算法 NoSQL 应用服务中间件
阿里面试:10WQPS高并发,怎么限流?这份答案让我当场拿了offer
在 Nacos 的配置管理界面或通过 Nacos 的 API,创建一个名为(与配置文件中 dataId 一致)的配置项,用于存储 Sentinel 的流量控制规则。上述规则表示对名为的资源进行流量控制,QPS 阈值为 10。resource:要保护的资源名称。limitApp:来源应用,default表示所有应用。grade:限流阈值类型,1 表示 QPS 限流,0 表示线程数限流。count:限流阈值。strategy:流控模式,0 为直接模式,1 为关联模式,2 为链路模式。
阿里面试:10WQPS高并发,怎么限流?这份答案让我当场拿了offer
|
2月前
|
人工智能 缓存 Ubuntu
AI+树莓派=阿里P8技术专家。模拟面试、学技术真的太香了 | 手把手教学
本课程由阿里P8技术专家分享,介绍如何使用树莓派和阿里云服务构建AI面试助手。通过模拟面试场景,讲解了Java中`==`与`equals`的区别,并演示了从硬件搭建、语音识别、AI Agent配置到代码实现的完整流程。项目利用树莓派作为核心,结合阿里云的实时语音识别、AI Agent和文字转语音服务,实现了一个能够回答面试问题的智能玩偶。课程展示了AI应用的简易构建过程,适合初学者学习和实践。
135 22
|
7月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
4月前
|
存储 缓存 算法
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
|
4月前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
4月前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
123 4
|
5月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
228 2