2018年奇虎360春招笔试题--玫瑰花

这道题,第一感觉想用排列组合做,但是想了好久,没想到解决办法(刚刚考试的时候没有答出来)。后来想了一下应该使用动态规划来做。

我们首先分析一下情况:

1.当K>N的时候,countSum = 0;

2.当K=N的时候,countSum = N!(N的阶乘)

3.当K>N的时候,就要通过最优子结构来进行分析了。

前两点易知,下面主要分析第三点。

设F(k,n)为n个位置,k种玫瑰的结果,则 F(k,n) = k*(F(k,n-1)+F(k-1,n-1)),分析:

情况一:n-1个空缺已经放置了k种花,则新的位置放置任何一种花都可以,此时结果总数为k*F(k,n-1);

情况二:n-1个空缺已经放置了k-1种花(注意!有k种选择!),则新的位置固定需要放置剩下的那一种花,此时结果总数为k*F(k-1,n-1);

总数 = 情况一 + 情况二

代码如下:

public class Rose {
    public static void main(String[] args){
        System.out.println(roseSum(2,3));
    }
    
    public static long roseSum(int k,int n){
        if(k>n) return 0;
        if(k == n){
            int count = 1;
            for(int i = 0;i<n;i++)
                count*=i;
            return count;
        }
        long[][] DP = new long[k][n];
        for(int i = 0 ;i<n;i++)
            DP[0][i] = 1;
        for(int i = 1;i<k;i++)
            DP[i][0] = 0;
        for(int i = 1;i<k;i++)
            for(int j = 1;j<n;j++)
                DP[i][j] = (i+1)*(DP[i][j-1]+DP[i-1][j-1]);
        return DP[k-1][n-1]%772235;        
    }
}

不过此代码虽然是使用动态规划解决,但是空间复杂度为O(N*K),并不是最优,还可继续优化。

优化代码如下:

public class Rose {
    public static void main(String[] args){
        System.out.println(roseSum(2,3));
    }
    
    public static long roseSum(int k,int n){
        if(k > n) return 0;
        if(k == n){
            int count = 1;
            for(int i = 0;i<n;i++)
                count*=i;
            return count;
        }
        long[][] DP = new long[2][n];
        for(int i = 0 ;i<n;i++)
            DP[0][i] = 1;
        DP[1][0] = 0;
        for(int i = 1;i<k;i++)
            for(int j = 1;j<n;j++)
                if((i&1)==1){//此时i是奇数
                    DP[1][j] = (i+1)*(DP[1][j-1]+DP[0][j-1]);
                }else{
                    DP[0][j] = (i+1)*(DP[0][j-1]+DP[1][j-1]);
                }
        return DP[(k-1)&1][n-1]%772235;        
    }
}

这回的空间复杂度为O(N)。

自己想出来的,不一定准确,没经过大量试验,如有错误,请各位朋友指出,谢谢~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【干货】还在自己写训练过程么?你需要一个训练引擎

4143
来自专栏SeanCheney的专栏

阿姆达尔定律和古斯塔夫森定律摘要背景建议使用指南更多资源

摘要 构建软件的并行版本可使应用在更短的时间内运行指定的数据集,在固定时间内运行多个数据集,或运行非线程软件禁止运行的大型数据集。 并行化的成功通常通过测量并行...

2996
来自专栏SDNLAB

SDN应用路由算法实现工具之Networkx

SDN(Software Defined Networking)是一种新型的网络架构,通过集中式的控制平面管理数据层面的转发等操作。网络的连通性是最基础的需求,...

3289
来自专栏阿凯的Excel

巧妙设置蛋糕图(Excel绘制图表系列课程)!

一直以踏踏实实做人!安安静静分享Excel技巧为宗旨的我,今天还是标题党了! 为啥尼! 我今天想分享这个图的绘制过程! ? 我真心不知道除了面积折线组合图外还能...

3615
来自专栏腾讯开源的专栏

【开源公告】腾讯第三代高性能计算平台Angel 正式全面开源

Angel 项目简介 Angel是一个基于参数服务器(Parameter Server)理念开发的高性能分布式机器学习框架,在其之上,用户能轻松开发适用于高维度...

4197
来自专栏郭耀华‘s Blog

2018年奇虎360春招笔试题--玫瑰花

这道题,第一感觉想用排列组合做,但是想了好久,没想到解决办法(刚刚考试的时候没有答出来)。后来想了一下应该使用动态规划来做。 我们首先分析一下情况: 1.当K>...

2976
来自专栏AI研习社

让 TensorFlow 估算器的推断提速百倍,我是怎么做到的?

TensorFlow 估算器提供了一套中阶 API 用于编写、训练与使用机器学习模型,尤其是深度学习模型。在这篇博文中,我们描述了如何通过使用异步执行来避免每次...

1142
来自专栏企鹅号快讯

重合散点图绘制:neat

hello诸君,暖阳高照,午间一杯清茶,又到了爬虫俱乐部向大家种草新命令新方法的时候啦! 许多同学学到的第一个Stata绘图命令想必就是scatter命令,该命...

2569
来自专栏AI科技评论

开发 | 如何理解Nvidia英伟达的Multi-GPU多卡通信框架NCCL?

问题详情: 深度学习中常常需要多GPU并行训 练,而Nvidia的NCCL库NVIDIA/nccl(https://github.com/NVIDIA/nccl...

4068
来自专栏吉浦迅科技

为啥在Matlab上用NVIDIA Titan V训练的速度没有GTX1080快?

在Matlab官方论坛上看到这个帖子,希望给大家带来参考 有一天,有人在Matlab的论坛上发出了求救帖: ? 楼主说: 我想要加快我的神经网络训练,所以把G...

5318

扫码关注云+社区