1.构建乘积数组

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

前缀和

位置	0	1	2	3
数组	a[0]	a[1]	a[2]	a[3]
乘积	初始化为 1	a[0]	a[1] * a[0]	a[2] * a[1] * a[0]

 public int[] constructArr(int[] a) {
        if (a == null || a.length == 0) {
            return a;
        }
        int n = a.length;
        int[] l = new int[n];
        l[0] = 1;
        // 前缀和乘积
        // l[0] = 1
        // l[1] = a[0];
        // l[2] = a[0] * a[1]
        // l[3] = a[0] * a[1] * a[2]
        for (int i = 1; i < n; i++) {
            l[i] = l[i - 1] * a[i - 1];
        }
        int t = 1;
        // 向前递乘
        for (int i = n - 2; i >= 0; i--) {
            t *= a[i + 1];
            l[i] *= t;
        }
        return l;
    }

2.二维数组中的查找

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

	public boolean findNumberIn2DArray(int[][] a, int target) {
        int i = a.length - 1;
        int j = 0;
        // 左下角开始向上方或者右边开始查找，注意合理的边界设置
        while (i >= 0 && j < a[0].length) {
            if (a[i][j] < target) j++;
            else if (a[i][j] > target) i--;
            else return true;
        }
        return false;
    }

3.旋转数组的最小数字

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

 	public int minArray(int[] a) {
        //1.找最大值
        //2.找第一个小于等于最大值的元素
	    int left = 0;
        int right = a.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 1 2 3 4 5
            if (a[mid] < a[right]) {
                right = mid;
                // 3 4 5 1 2
            } else if (a[mid] > a[right]) {
                left = mid + 1;
            } else {
                // 退出循环 和 缩短序列
                right--;
            }
        }
        return a[left];
    }

2021.12.02 09:20