首页 > 代码库 > 第十六周 Leetcode 600. Non-negative Integers without Consecutive Ones(HARD) 计数dp
第十六周 Leetcode 600. Non-negative Integers without Consecutive Ones(HARD) 计数dp
Leetcode600
很简单的一道计数题 给定整数n 求不大于n的正整数中 二进制表示没有连续的1的数字个数
在dp过程中只要保证不出现连续1以及大于n的情况即可。
所以设计按位dp[i][j]表示到第i位 j=0表示第i位为0 且值等于n的情况 2为值小于n的情况
j=1表示第i位为1 且值等于n的情况 3为值小于n的情况
转移方程很简单 看代码吧 这道题应该是Mid难度吧
class Solution { public: int findIntegers(int num) { int va=num; int dp[40][4]; int f[40];memset(f,0,sizeof(f)); memset(dp,0,sizeof(dp)); int tot=31; while(va>0) { if((va%2)==1)f[tot]=1; tot--; va=(va>>1); } if(f[tot+1])dp[tot+1][1]=dp[tot+1][2]=1; else dp[tot+1][0]=1; for(int i=tot+2;i<=31;i++) { if(f[i]) { dp[i][1]+=dp[i-1][0]; dp[i][2]+=dp[i-1][0]+dp[i-1][2]+dp[i-1][1]+dp[i-1][3]; dp[i][3]+=dp[i-1][2]; }else { dp[i][3]+=dp[i-1][2]; dp[i][0]+=dp[i-1][0]+dp[i-1][1]; dp[i][2]+=dp[i-1][2]+dp[i-1][3]; } } return dp[31][0]+dp[31][1]+dp[31][2]+dp[31][3]; } };
第十六周 Leetcode 600. Non-negative Integers without Consecutive Ones(HARD) 计数dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。