题目:

  输入一个数字n  如果n为偶数则除以2,若为奇数则加1或者减1,直到n为1,求最少次数  写出一个函数

  首先,这道题肯定可以用动态规划来解,

    n为整数时,n的解为 n/2 的解加1

    n为奇数时,n的解为 (n+1)/2 和 (n-1)/2 的解中较小的解加2

  通过这个思路,我们可以自底向上依次计算出n的解,代码如下

public static int getNum(int n) {
if(n<1) {
return 0;
}
int[] res = new int[n+1];
res[0] = 0;
res[1] = 0;
for(int i=2;i<=n;i++) {
if((i&1) == 0) {
res[i] = res[i/2] + 1;
}else {
res[i] = Math.min(res[(i+1)/2], res[(i-1)/2]) + 2;
}
}
return res[n];
}

  通过上面的思路可以得到问题的解,但是由于是自底向上依次计算n的解,所以有很多不必要的计算,时间效率和空间效率都不高。

  比如,当计算n=100时,如果已经知道n=50的解,那么就可以得出n=100的解,所以n=51到n=99都是没有必要计算的。

  如果仍然通过自底向上计算,那么想要忽略51到99这一区间的数字的计算是比较麻烦的,如果是自顶向下计算则容易做到,通过n可以确定只要计算 n/2,(n-1)/2 , (n+1)/2,这三个数就  行,利用递归来做代码如下

public static int getNum2(long n) {
if(n<=1) {
return 0;
} if((n&1) == 0) {
return getNum2(n/2) + 1;
}else {
long a = (n-1) / 2;
long b = (n+1) / 2; return Math.min(getNum2(a), getNum2(b)) + 2;
}
}

  递归来做这道题简单明了。

  递归也有递归的坏处,首先递归最可能问题就是递归深度的问题,很可能造成栈溢出。虽然对这道题来说,几乎不会出现这个问题,但是在用递归做其他问题的时候一定要考虑到这一点。

  至于为什么这道题不会造成栈溢出,自己想吧

  所有的递归算法都可以转化成非递归算法,这道题也一样,同样的,递归时还有一个小问题,就是它没有复用子问题的解,对于每个子问题,不管之前是否已经计算过解,都要再重新计算一次,转化成非递归算法时可以一并解决这个问题,代码如下

public static int getNum3(long n) {
MyTask task = new MyTask(n); ForkJoinPool pool = new ForkJoinPool();
int res = pool.invoke(task);
pool.shutdown();
return res;
} static class MyTask extends RecursiveTask<Integer> {
private long number;
private static final Map<Long,Integer> map = new ConcurrentHashMap<>(); public MyTask(long number) {
super();
this.number = number;
} private synchronized void put(Long a,Integer b) {
if(map.containsKey(a)) {
System.out.println("had existed!");
}else {
map.put(a, b);
}
} private Integer get(Long a) {
System.out.println("success");
return map.get(a);
} @Override
protected Integer compute() {
if(number<=1) {
put(number, 0);
return 0;
}else if(map.containsKey(number)) {
return get(number);
} int res = 0;
if((number&1) == 0) {
MyTask task = new MyTask(number / 2); try {
res = task.fork().get() + 1;
put(number, res);
} catch (Exception e) {
e.printStackTrace();
}
return res;
}else {
MyTask task1 = new MyTask((number-1) / 2);
MyTask task2 = new MyTask((number+1) / 2);
try {
int a = task1.fork().get() + 2;
int b = task2.fork().get() + 2; res = Math.min(a,b);
put(number, res);
} catch (Exception e) {
e.printStackTrace();
}
return res;
}
} }

  这个解法是将第二种解法的递归算法转化成了非递归算法,同时保存了之前已经计算过的子问题的解,并且用到了java中的fork/join框架,至于为什么要用这个框架,原因是,不用它我不知道怎么把这个递归算法转化成非递归算法,望各路大神指点指点

  对于这道题来说,第二种方式最快,第三种方式其次,最后是第一种方式,而且第一种方式计算的n的最大值,也远远小于后两种。

  好了,就先写到这,人生的第一篇博文就此诞生!庆祝!虽然写的我自己看了都觉得很烂,但是一步一步来嘛

  

05-04 00:49