机关网站建设征求意见,谷歌搜索引擎免费入口2022,佛山哪家网站建设比较好,ip动态地址做网站一、比特位计数
给你一个整数 n #xff0c;对于 0 i n 中的每个 i #xff0c;计算其二进制表示中 1 的个数 #xff0c;返回一个长度为 n 1 的数组 ans 作为答案。
输入#xff1a;n 2
输出#xff1a;[0,1,1]
解释#xff1a;0 -- 0 1 -- 1 2 -…一、比特位计数
给你一个整数 n 对于 0 i n 中的每个 i 计算其二进制表示中 1 的个数 返回一个长度为 n 1 的数组 ans 作为答案。
输入n 2
输出[0,1,1]
解释0 -- 0 1 -- 1 2 -- 10
思路一 如果是偶数的话1的个数和它的一半是相同的如果是奇数的话1的个数等于它前面那个偶数的个数1
代码:
int countBits(int num) {int[] resnew int[num1]result[0] 0;for(int i 1; i num; i){if(i%20)res[i]res[i/2];else res[i]res[i-1]1;}return result;}思路二遇到一个数想办法把它拆成 最靠近它的2的幂 和另一个数
eg:7拆成4和3 4中1的个数有1个3中1的个数有2个 所以res[7]res[4]res[3]
如果遇到2的幂次dp[i]1;
代码 public int[] countBits(int n) {int[] dp new int[n 1];dp[0] 0;int x 1;for (int i 1; i n; i) {// 如果是2的幂只有最高位为1if (i x) {dp[i] 1;x * 2;} else {// 如果不是2的幂则为取模最高位后的值1// 例如 5 % 4 1 那么就是41也就是 101也就是1dp[1]; int mod i % (x / 2);dp[i] 1 dp[mod];//1代表的是2的幂dp[mod]代表的是剩下的那个数的1的值}}return dp;}
二、打家劫舍/打家劫舍II二刷 dp
题意小偷要偷窃相邻房屋是不能偷窃的否则就会发出报警信号。给定一个数组nums表示每个房间的价值第一个房屋和最后一个房屋是相邻的给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
思路
因为房屋是相邻的所以要破除这个环那么应该如何破除因为首尾是相连的所以我们只需要考虑两种情况偷首就不能偷尾偷尾就不能偷首
那我们就把两种情况分别可以偷窃到的最高金额计算出来比较之后返回。
那么如何计算偷窃道德最高金额动态规划。
一间屋子可以偷也可以不偷偷的话dp[i]dp[i-2]nums[i];不偷的话:dp[i]dp[i-1]
dp[i]:偷窃到第i间房子所偷窃的最大价值
递推公式dp[i]Math.max(dp[i-2]nums[i],dp[i-1]);
初始化dp[0]nums[0],dp[1]Math.max(nums[0],nums[1]);
遍历顺序从i2开始
代码:
class Solution {public int rob(int[] nums) {if(nums.length1)return nums[0];//如何破环int part1getMax(nums,0,nums.length-2);int part2getMax(nums,1,nums.length-1);return Math.max(part1,part2);}public int getMax(int[] nums,int left,int right){if(rightleft)return nums[left];int[] dpnew int[right-left1];dp[0]nums[left];dp[1]Math.max(nums[left],nums[left1]);for(int ileft2;iright;i){dp[i-left]Math.max(dp[i-2-left]nums[i],dp[i-1-left]);}return Math.max(dp[dp.length-1],dp[dp.length-2]);}
}
三、两个键的键盘(dp)
最初记事本上只有一个字符 A 。你每次可以对这个记事本进行两种操作
Copy All复制全部复制这个记事本中的所有字符不允许仅复制部分字符。Paste粘贴粘贴 上一次 复制的字符。
给你一个数字 n 你需要使用最少的操作次数在记事本上输出 恰好 n 个 A 。返回能够打印出 n 个 A 的最少操作次数。
思路
如何才可以得到n个‘A’可以根据因数来做。
eg:n12; 可以是6个A CopyAll-Paste之后得到12个A
也可以是3个A CopyAll-Paste3次后得到12个A
还可以是2个A CopyAll-Paste5次后得到12个A
如果是质数的话那么操作的次数就是它本身需要CopyAllPaste(n-1)次
所以就是在它的因数里面找最小操作次数。双循环
代码
class Solution {public int minSteps(int n) {//dp[i]的定义打印出i个A字符需要的操作次数int[] dpnew int[n1];//dp初始化dp[1]0;//遍历数组for(int i2;in;i){dp[i]i;for(int j2;jMath.sqrt(i);j){if(i%j0){dp[i]Math.min(dp[i],dp[j]i/j);dp[i]Math.min(dp[i],dp[i/j]j);}}}return dp[n];}
}
四、解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码
1 - A 2 - B 25 - Y 26 - Z
然而在 解码 已编码的消息时你意识到有许多不同的方式来解码因为有些编码被包含在其它编码当中2 和 5 与 25。
给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串返回 0。
输入s 226
输出3
解释它可以解码为 BZ (2 26), VF (22 6), 或者 BBF (2 2 6) 。
思路这道题是爬楼梯类似。但是比爬楼梯要多个决定条件。
给定一串字符串。
如果该数字不等于0那么就可以只切割该字符此时dp[i1]dp[i]; 和爬楼梯从下一层爬到该层一样;
在上一个条件的基础上如果该数字可以和前一个数字组成一个合法的字符1026那么就可以从下两层爬到该层(一次爬两个)。此时dp[i1]dp[i-1];
动态规划五部曲
1.dp[i]:代表的含义是字符串中以i-1为结尾的字串的切割方法有多少种。dp.lengths.length()1
2.递推公式 2.1如果和上一个数字无法组成合法的大写字母:dp[i1]dp[i]; 2.2 如果和上一个数字可以组成合法的大写字母:dp[i1]dp[i]dp[i-1]
3.初始化:dp[0]dp[1]1; 默认空串也有一种切割方式。
eg:226。遍历到index1的时候可以组成一个合法的大写字母。dp[i1]dp[i]dp[i-1]。这里的dp[i-1]就代表着22
代码
class Solution {public int numDecodings(String s) {int sizes.length();int[] dpnew int[size1];dp[0]1;//初始化 dp[1]1;//dp[i]表示的是字符串中以(i-1)为结尾的字串 有多少种切割方式if(s.charAt(0)0)return 0;for(int i1;isize;i){char ch1s.charAt(i);if(ch1-0!0){dp[i1]dp[i];}char ch2s.charAt(i-1);//如果这两个数字可以组成一个有效的大写字母if((ch2-0)*10(ch1-0)10(ch2-0)*10(ch1-0)26){dp[i1]dp[i-1];}}return dp[size];}
}
