一亩三分地

 找回密码 注册账号

扫描二维码登录本站


北美版丁香园
美国和加拿大
疫情地图实时动态追踪

热门职场讲座
Career in Tech
职场晋升之路

Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 318|回复: 4
收起左侧

[动态规划] 谁能讲讲651. 4 Keys Keyboard

[复制链接] |试试Instant~ |刷题, 动态规划
我的人缘0

分享帖子到朋友圈
ygmm | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (152)
 
 
3% (5)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 ygmm 于 2019-8-4 11:13 编辑


一旦全选,复制后,buffer里的可以重复 打印。
为什么解释里写“
Approach Framework

Explanation

We either press 'A', or press 'CTRL+A', 'CTRL+C', and some number of 'CTRL+V's. Thus, in the context of making N keypresses to write the letter 'A'  M times, there are only two types of moves:

Add (1 keypress): Add 1 to M.
Multiply (k+1 keypresses): Multiply M by k, where k >= 2.
In the following explanations, we will reference these as moves.


Say best[k] is the largest number of written 'A's possible after k keypresses.

If the last move in some optimal solution of k keypresses was adding, then best[k] = best[k-1] + 1.


红色地方为甚是Add1, 是不是应该是Add buffer ? best[k] = best[k-1] + buffer ?

这个题目用动态规划做,怎么理解呢?

好像也在Greedy 类别里,怎么用Greedy来做呢?

我的是这么写的,不过是错的。。。也不知道哪里错了。如果你知道哪里不对,请告诉我。

[Bash shell] 纯文本查看 复制代码
class Solution {
    public int maxA(int N) {
        if(N <= 3){
            return N;
        }
        int currentA = 0;
        int buffer = 1;
        while(N > 0){//找当前最好的情况,如果现在开始 全选copy 黏贴的结果,是不是比 直接每次加buffer,或者比 下一次全选copy 来的多? 是的话,就这一次做。
            if(N >= 3 && (currentA*(N - 2)) > (currentA + buffer) * (N - 3)
              && (currentA*(N - 2)) > (buffer * N)){
                //key2 + key3 + key4
                buffer = currentA;
                N = N - 3;
                currentA *= 2;
            }else{
                currentA += buffer;
                N--;                
            }
        }
        return currentA;
    }
}







上一篇:OS和linux怎么一起学呢?
下一篇:Data-intensive Application所有章节的summary
我的人缘0
14417335 2019-8-5 02:15:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (481)
 
 
0% (4)    👎
O(N^2)的解法应该是大多数人的解法。

https://www.1point3acres.com/bbs/thread-289736-1-1.html
还有个讨论O(1)的。

评分

参与人数 1大米 +2 收起 理由
真淘蛮 + 2 求审核下帖子

查看全部评分

回复

使用道具 举报

我的人缘0
14417335 2019-8-5 02:53:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (481)
 
 
0% (4)    👎
基本没看懂lc的那篇文章优化为O(N)的。但是从该文里面得到这个点:

虽然我下一个的copy paste比我起步晚,但是它(我下一个的)的基数比我大。我的基数:dp[ i ]。它的基数 dp[ i+1 ]。

经过多少轮我和它paste得到的值相同呢?

System.out.println(i + "=" + dp[ i+1 ]/((double)(dp[ i+1 ]-dp[ i ])));

实验得出是4-4.8次。验证了LC文章中所说最多五次的降维做法。

评分

参与人数 1大米 +2 收起 理由
真淘蛮 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| ygmm 2019-8-5 10:01:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (152)
 
 
3% (5)    👎
谢谢!  还是没看明白。
回复

使用道具 举报

我的人缘0
337845818 2019-8-7 03:38:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   81% (769)
 
 
18% (173)    👎
f[j] = max(j, 2 * f[j - 3], 3 * f[j - 4], 4 * f[j - 5], ...)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-4-11 02:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表