Arrays

P35

对于有数数组，给定target，找出存在的index，或者插入的适合index

    public static int searchInsert(int[] nums, int target) {
        int low=0, high = nums.length-1;
        int middle= 0;
        while(low<=high){
            middle = low + (high - low) /2;
            if(nums[middle] > target){
                high = middle - 1;
            }else if (nums[middle] < target){
                low = middle + 1;
            }else if (nums[middle] == target){
                return middle;
            }
        }
        if(nums[middle] < target) return middle+1;
        return middle;
    }

P66

数组加1运算，数组元素非负，且第一位不是0.

public int[] plusOne(int[] digits) {
        int n = digits.length;
        int plus = 1;
        for (int i = n - 1; i >= 0; i--) {
            plus = (digits[i] + 1)/ 10;
            digits[i]= (digits[i]+1)%10;
            if(plus<=0) break;
        }
        if (digits[0] == 0) {
            int[] result = new int[n + 1];
            result[0] = 1;
            for(int i=0;i<n;i++) {
                result[i+1] = digits[i];
            }
            return result;
        }
        return digits;
    }

P119

关键是使用杨辉三角的性质。将性质编写为代码

public List<Integer> getRow(int rowIndex) {
        ArrayList<Integer> result = new ArrayList<>(rowIndex + 1);
        if(rowIndex<0) return result;
        for(int i=0;i<rowIndex+1;i++) {
            result.add(0,1);
            for(int j=1;j<result.size()-1;j++) {
                result.set(j, result.get(j) + result.get(j+1));
            }
        }
        return result;
    }

P167

给定数字，在有序数组中查找两个元素，其和正好为给定数字，返回对应位置

    public int[] twoSum(int[] numbers, int target) {
        int j=0,i=0;
        for(;i<numbers.length;i++) {
            if ((j = binarySearch(numbers, target - numbers[i], i+1, numbers.length - 1)) != -1) {
                return new int[]{i, j};
            }
        }
        return new int[]{0, 0};
    }

    public int binarySearch(int[] numbers, int target, int start, int end) {
        while (start <= end) {
            int middle = start + (end - start) /2;
            if (numbers[middle] > target) {
                end = middle - 1;
            } else if (numbers[middle] < target) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }