做宠物网站导航应该写什么字,百度抓取不到网站,wordpress 主题 love,wordpress 会员注册插件文章目录题目描述思路 代码无注释二刷题目描述
难点在于 O(n)
思路 代码
理解题意#xff0c;分析出 O(n) 复杂度应该是要用到之前的值来得到当前值——动态规划核心结论#xff1a;奇数比前一个数多一个1#xff0c;偶数和偶数除二后的数的1数量一样边界 代码无注释二刷题目描述
难点在于 O(n)
思路 代码
理解题意分析出 O(n) 复杂度应该是要用到之前的值来得到当前值——动态规划核心结论奇数比前一个数多一个1偶数和偶数除二后的数的1数量一样边界 状态转移方程 最优子结构 见代码注释时间复杂度 O(n)
class Solution {public int[] countBits(int num) {int[] ans new int[num 1];// 边界ans[0]已经初始化为0了for(int i 1; i num; i){// 两个状态转移方程// 奇数情况比前一个偶数多1if((i 1) 1){ans[i] ans[i - 1] 1; }// 偶数情况和当前数除2后的数一样else{ans[i] ans[i 1];}// 最优子结构ans[i - 1] or ans[i 1]}return ans;}
}无注释二刷
当然之前的位运算写法确实更有逼格啦。。
class Solution {public int[] countBits(int n) {int[] ans new int[n 1];for(int i 0; i n; i) {if(i % 2 1) {ans[i] ans[i - 1] 1;}else {ans[i] ans[i / 2];}}return ans;}
}
