刷算法题的第2天

1、爱吃香蕉的珂珂

题目链接：

https://leetcode-cn.com/problems/koko-eating-bananas/

算法背景引入： 二分搜索算法的更深入了解

1. 我们需要确定一下几个变量，一个是x，一个是f(x)，最后一个是target，一般来说，我们定义的x都是题目需要我们求出的值，而f(x)是根据x的变化而变化的量，target是目标的值
2. 确定好函数之后，我们下一步就要确定left的值和right的值了，对于left来说，我们根据题目确定它的最小值；对于right来说，我们根据题目给的范围或者fo循环遍历，取出最大值
3. 然后根据题意进行寻找最左侧边界的二分查找 或者 寻找最右侧边界的二分查找来实现代码

// 函数 f 是关于自变量 x 的单调函数
int f(int x) {
    // ...
}

// 主函数，在 f(x) == target 的约束下求 x 的最值
int solution(int[] nums, int target) {
    if (nums.length == 0) return -1;
    // 问自己：自变量 x 的最小值是多少？
    int left = ...;
    // 问自己：自变量 x 的最大值是多少？
    int right = ... + 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (f(mid) == target) {
            // 问自己：题目是求左边界还是右边界？
            // ...
        } else if (f(mid) < target) {
            // 问自己：怎么让 f(x) 大一点？
            // ...
        } else if (f(mid) > target) {
            // 问自己：怎么让 f(x) 小一点？
            // ...
        }
    }
    return left;
}

分析题目:

1. 对于这道题目来说，我们首先需要确定的是f(x)的函数，因为题目中需要求出最少的速度是多少，那么我们设速度为x，相对应的，f(x)就是所需要的时间了，并且随着速度的越来越大，相对应的时间会越来越小，是一个单调递减的函数。（用二分搜索需要注意的是，这个f(x)一定是一个单调函数，单调递增或者单调递减都可以），
2. 第二步是确定left和right的值，left的话，是吃的速度，最小肯定是1，right的话，最大肯定是所有堆中数量最多的那一堆（这个的话就要进行for循环遍历了），那么不遍历的话，就去看一下题目给我们的范围是多少，k的取值范围是10^9，那么我们可以定义right的取值是10 ^ 9 + 1
3. 确定好了之后，我们考虑使用最左侧的二分搜索还是最右侧的二分搜索，因为题目中要求我们知道的是最小的速度是多少，那么就需要取到最左侧边界的那个值。因此我们使用寻找最左侧的二分搜索算法来实现，这里需要注意的是，我们的这个f(x)是一个单调递减的函数，在比较两个数字的时候，在mid值比target值大或者小的时候，要结合题目考虑一下（和单调递增的刚好相反），下面给出实现的代码

	int f(int[] piles, int x) {
        int hours = 0;
        for (int i = 0; i < piles.length; i++) {
            hours += piles[i] / x;
            if (piles[i] % x > 0) {
                hours++;
            }
        }
        return hours;
    }

    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1000000000 + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (f(piles, mid) > h) {
                left = mid + 1;
            } else if (f(piles, mid) <= h) {
                right = mid;
            }
        }
        return left;
    }

2、在 D 天内送达包裹的能力

题目描述： 传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。 返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

题目链接：

https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/

题目分析：

1. 首先也是确定运输的这个函数f(x),x是我们需要进行求出来的，也就是最小的货运数量，那么与最小的货运数量相对应的f(x）是运输的天数days，对于这个days，显然这个days和运货的数量之间成反比，对应的f(x)函数是一个递减函数。 【tips】：这里进行循环查找的时候，可以使用for循环和while循环结合，再搭配break方法
2. 确定左右两个边界，left的值最小的话，就是这个nums[]数组中最大的那个数字，也就是一次只能运送一个;right的值最大的话，就是那个一次性能运输完nums[]中所有的值
3. 因为是最小的运输能力，所以我们使用寻找最左侧的二分搜索算法来进行实现，代码如下所示

/**
     * 能够在几天内完成基于船的最低运载能力
     * 船的运载能力越大，时间就越小，是一个单调递减函数
     *
     * @param x 船的最低运载能力
     * @return: int 能够在几天内完成
     **/
    int f(int[] nums, int x) {
        int days = 0;
        for (int i = 0; i < nums.length; ) {
            int sum = x;
            while (i < nums.length) {
                if (nums[i] > sum) {
                    break;
                } else {
                    sum -= nums[i];
                }
                i++;
            }
            days++;
        }
        return days;
    }

    public int shipWithinDays(int[] weights, int days) {
        int left = 0;
        int right = 1;
        for (int i = 0; i < weights.length; i++) {
            left = Math.max(left, weights[i]);
            right += weights[i];
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (f(weights, mid) == days) {
                right = mid;
            } else if (f(weights, mid) > days) {
                left = mid + 1;
            } else if (f(weights, mid) < days) {
                right = mid;
            }
        }
        return left;
    }

今天完成的数量不多，哎，主要是年底了，家里在大扫除，弄卫生之类的，明天争取早点起来多做一些。