剑指offer+java

《剑指Offer》是一本非常经典的面试题集，主要涵盖了程序员面试中常见的算法和数据结构问题。以下是一些Java实现的剑指Offer题目：
1. 面试题3：数组中重复的数字

public boolean duplicate(int[] nums, int length, int[] duplication) {
    if (nums == null || length <= 0) {
        return false;
    }
    for (int i = 0; i < length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                duplication[0] = nums[i];
                return true;
            }
            swap(nums, i, nums[i]);
        }
    }
    return false;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

2. 面试题10：斐波那契数列

public int Fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int pre2 = 0, pre1 = 1;
    int fib = 0;
    for (int i = 2; i <= n; i++) {
        fib = pre2 + pre1;
        pre2 = pre1;
        pre1 = fib;
    }
    return fib;
}

3. 面试题14：剪绳子

public int maxProductAfterCutting(int length) {
    if (length < 2) {
        return 0;
    }
    if (length == 2) {
        return 1;
    }
    if (length == 3) {
        return 2;
    }
    int[] products = new int[length + 1];
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;
    int max = 0;
    for (int i = 4; i <= length; i++) {
        max = 0;
        for (int j = 1; j <= i / 2; j++) {
            int product = products[j] * products[i - j];
            if (max < product) {
                max = product;
            }
            products[i] = max;
        }
    }
    max = products[length];
    return max;
}