非死不可 根本不想给过电面

我觉得po出来的思路没毛病，第一步可以算有多少个1，其实就是算累计的组合数，比如说有3个'1'的数有comb(n,3)个， 第二步利用已知有多少个0多少个1按大小排序，思路参考LC1643.

碰到二进制的题感觉心都凉半截了～一系列繁琐操作

AbelEinzbern 发表于 2021-5-18 11:57
我觉得po出来的思路没毛病，第一步可以算有多少个1，其实就是算累计的组合数，比如说有3个'1'的数有comb(n, ...

那就得dp了

wbxzhr123 发表于 2021-5-17 19:17
他的本意是要你用dp，这题我是用笔在纸上画画发现规律的。

举个例子

这个DP通式很难简单的写出来，因为101和110在下次加一的时候会变成同一结果，还要做去重。没法简单根据位置回溯。通过计算组合迅速确定k所属几个1的空间应该是最快的方法了。

终于弄明白了，一路算组合，直接能把最后能算出是靠1，2，4，8.。。。。。中的哪几个只有一个1的数字的加和。我日了这个SB题目了。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

wbxzhr123 发表于 2021-5-19 07:22
PO个代码，这应该就是3哥想要的分组
我跑了个例子，n = 100的时候含有3个1的数目是这样的
7 11 13 14 19  ...

讲真这个不如直接用组合数去算来得快。当你确定r个1之后可以直接从r+1通过算组合数直接把答案算出来。

如果这道题真的要用dp解的话（还是店面）那就真的是面试官有心挂啦。说实在话看那么多面经(包括on site)，fb出的题很多都没dp。
楼主加油，这次运气不好而已。

给你点个赞！