第一题 剪绳子 把一根绳子剪成多段，并且使得每段的长度乘积最大。
参考算法 https://blog.csdn.net/qq_25827845/article/details/73351134
解题思路：
定义函数f(n)表示为把长度为n的绳子剪成若干段后各段长度乘积的最大值，对于第一刀，我们有n-1种可能的选择，可推导出f(n)=max{f(i)*f(n-i)};
当绳子的长度为2的时候，只能剪成长度为1的两段，所以f(2) = 1，当n = 3时，容易得出f(3) = 2;
当n>=4时，其实就是计算第i刀时，f(j)与f(n-i）的最大值
因为max(f(i)*f(n-i))与max(f(n-i)*f(i)）显然会有重复运算，所以代码的j<=i/2
package com.lyc.dataautest;public class Maxcut {public static int maxcut(int n) {int result = 0;if(n<2) return 0;if(n==2) return 1;if(n==3) return 2;int[] f = new int[n+1]; for(int i=4;i<=n;i++) { int max=0;for(int j=1;jmax) {
max = res;
}
f[i] = max;
}
}
result = f[n];
return result;
}
}
第二题 二进制中 1 的个数
就是 位运算
n : 10110100
n-1 : 10110011
n&(n-1) : 10110000
public static int bit(int n) {
int count=0;
while(n!=0) {
n&=n-1;
count++;
}
return count;
}
第三题 数值的整数次方
解题思路：当指数是偶数时base^n = base^(n/2) * base^(n/2) 当指数是奇数时 base^n = base^(n/2) * base^(n/2) *base。注意n/2的值（3/2=1,4/2=2）才能了解上面的说明。判断是奇数还是偶数使用exponent%2取余。于是可递归计算。
public static double power(double base,int exponent) {
if(exponent==0) return 1;
double pow = power(base*base,exponent/2);
if(exponent%2!=0){
pow = base*pow;
}
return pow;
}
