【剑指】6.5 发散思维能力

保持思维的灵活和变通，在解决问题时尝试通过多个角度、多种方法来完成，这样在条件受限时就不至于束手无策而是可以通过类比举一反三来寻找可能的方法。

面试题64：求1+2+...+n

题目描述

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

解题思路

这一题我在很久之前遇到过，由于不能使用循环控制符，那么可以考虑用递归；由于不能使用判断控制符，那么可以考虑用短路或者异常捕获。另外还有俄罗斯农民乘法结合短路的写法。

public int Sum_Solution(int n) {
    int result = 0;
    boolean b = ((result = n) <= 1) || (result += Sum_Solution(n - 1)) > 0;
    return result;
}

public class Solution {
    private final int[] arr = new int[]{0};
    public int Sum_Solution(int n) {
        try{
            return arr[n];
        }catch(ArrayIndexOutOfBoundsException e){
            return n + Sum_Solution(n-1);
        }
    }
}

public int Sum_Solution(int n) {
    //等差数列求和公式n(n+1)/2
    return multiply(n, n + 1) >> 1;
}

private int multiply(int n, int m){
    boolean b = (n > 1) && (((n & 1) == 1 && (m += multiply(n >> 1, m << 1)) > 0) || ((n & 1) == 0) && (m = multiply(n >> 1, m << 1)) > 0);
    return m;
}

//俄罗斯农民乘法的一般写法
private int multiply(int n, int m){
    if(n>1){
        if(n%2==1){
            m=m+multiply(n/2,m*2);
        }else{
            m=multiply(n/2,m*2);
        }
    }
    return m;
}

面试题65：不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解题思路

由于限制不能使用四则运算符，那么剩下的只有位运算了。来看两个数的二进制相加，首先不考虑进位那部分，那么0+0=0，0+1=1，1+0=1，1+1=0，这与异或性质相同；再来看进位部分，仅当1+1时会进位1，其他情况进位都是0，那么可以采用先按位与再左移1位来模拟；最后再对和部分和进位部分迭代相加，直到进位部分等于0。

public int Add(int num1,int num2) {
    int sum, carry;
    while (num2 != 0) {
        sum = num1 ^ num2;
        carry = (num1 & num2) << 1;
        num1 = sum;
        num2 = carry;
    }
    return num1;
}

面试题66：构建乘积数组

题目描述

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

解题思路

由于不能使用除法那么可以使用前缀积乘以后缀积的方法来解决，第一遍从左向右数组B[i]存储着A[i]的前缀积，第二遍从右向左使用一个变量来存储A[i]的后缀积，与已知的前缀积相乘后更新到B[i]中。

public int[] multiply(int[] A) {
    int n = A.length;
    int[] B = new int[n];
    B[0] = 1;
    for(int i = 1; i < n; i++){
        B[i] = A[i-1] * B[i-1];
    }
    int post = 1;
    for(int i = n - 1; i >= 0; i--){
        B[i] *= post;
        post *= A[i];
    }
    return B;
}