文章目录
JZ14 剪绳子
题目描述
思路详解
本题使用动态规划来解题，注意找规律哦
首先我们考虑一段绳子，如果一旦分出一段长度为1的小段，只会减少总长度，还不能增加乘积，因此长度为2的绳子不分比分开的乘积大，长度为3的绳子不分比分开的乘积大，长度为4的绳子分成2*2比较大。前面的我们都可以通过这样递推得到，后面的呢？
同样递推！如果我有一个长度为n的绳子，我们要怎么确定其分出最大的乘积，我们可以尝试其中一段不可分的为j，那么如果另一段n−j最大乘积已知，我们可以遍历所有j找到这个最大乘积。因此用dp[i]表示长度为i的绳子可以被剪出来的最大乘积，那么后续遍历每个j的时候，我们取最大dp[i]=max(dp[i],j∗dp[i−j])就好。
代码与结果
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ public int cutRope(int target) { //不超过3直接计算 if(target <= 3) return target- 1; //dp[i]表示长度为i的绳子可以被剪出来的最大乘积 int[] dp = new int[target + 1]; dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; //遍历后续每一个长度 for(int i = 5; i <= target; i++) //可以被分成两份 for(int j = 1; j < i; j++) //取最大值 dp[i] = Math.max(dp[i], j * dp[i - j]); return dp[target]; } }
JZ15 二进制中1的个数
题目描述
思路详解
本题我们采用按位比较，使用移位的方法不仅可以达到效果而且运行速度也会更快哦
代码与结果
import java.util.*; public class Solution { public int NumberOf1(int n) { int res = 0; //遍历32位 for(int i = 0; i < 32; i++){ //按位比较 if((n & (1 << i)) != 0) res++; } return res; } }
JZ16 数值的整数次方
题目描述
思路详解
既然是求次方，那我们做不断累乘就可以了，重点是处理负的次方数，我们只需底数转换为相应分数，乘方次数变成正数就可以了。
代码与结果
import java.util.*; public class Solution { public double Power(double base, int exponent) { //处理负数次方 if(exponent < 0){ base = 1 / base; exponent = -exponent; } double res = 1.0; //累乘 for(int i = 0; i < exponent; i++) res *= base; return res; } }
✨总结
今日的题还是比较简单的，相对而言第一题的动态规划需要更多的思考，加油！！！
