第一题 剪绳子 把一根绳子剪成多段，并且使得每段的长度乘积最大。

参考算法 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;

}