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

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

  • 算法1：利用构造器和静态变量 
public int sumNums(int n) {
    Temp.reset();
    for (int i = 0; i < n; i++) {
        new Temp();
    }
    // Temp[] t = new Temp[n]; // 在Java中这样不行，Temp未被初始化，数组全是null
    return Temp.sum;
}
static class Temp {
    public static int n;
    public static int sum;
    public Temp() {
        n++;
        sum += n;
    }
    public static void reset() {
        n = 0;
        sum = 0;
    }
}
  • 算法2：虚函数（Java中没有被final修饰的函数） 
A[] array = new A[2];
public int sumNums(int n) {
    array[0] = new A();
    array[1] = new B();
    return array[1].sum(n);
}
class A {
    public int sum(int n) {
        return 0;
    }
}
class B extends A {
    public int sum(int n) {
        return array[n > 0 ? 1 : 0].sum(n-1) + n;
    }
}
  • 算法3：函数指针（Java中的函数式接口） 
public int sumNums(int n) {
    IntFunction<Integer>[] intFunctions = new IntFunction[2];
    intFunctions[0] = x -> 0;
    intFunctions[1] = x -> sumNums(x);
    return n + intFunctions[n > 0 ? 1 : 0].apply(n-1);
}

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

题目：写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷四则运算符号。

  • 算法：
    • 1.各位相加但不进位，相当于亦或
    • 2.记下进位，相当于按位与再左移一位
    • 3.以上相加，重复以上步骤，直至没有进位 
public int add(int a, int b) {
    // return a + b;
    int sum = 0;
    int carry = 0;
    do {
        sum = a ^ b;
        carry = (a & b) << 1;
        a = sum;
        b = carry;
    } while (b != 0);
    return sum;
}

面试题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]。不能使用除法。

  • 算法：
    • B[i] = A[0]*A[1]*A[2]*A[3]*...A[i-1]*A[i+1]*A[i+2]*A[i+3]*...A[n-1]
    • C[i] = A[0]*A[1]*A[2]*A[3]*...A[i-1]
    • D[i] = A[i+1]*A[i+2]*A[i+3]*...A[n-1]
    • B[i] = C[i] * D[i] 
public int[] constructArr(int[] a) {
    checkArguments(a);

    int[] result = new int[a.length];
    result[0] = 1;
    for (int i = 1; i < a.length; i++) {
        result[i] = result[i-1] * a[i-1];
    }
    int temp = 1;
    for (int i = a.length - 2; i >= 0; i--) {
        temp *= a[i+1];
        result[i] *= temp;
    }
    return result;
}