亚洲一区二区制服无码中文,日韩一区三区视频,国产午夜无码视频免费网站

左神 step num

給定一個正整數(shù)，判斷它是否是某個數(shù)的step num

680的step num為680+68+6

if a<b，則 stepnum(a)<stepnum(b)

class Solution {
    boolean f(int x) {
        int l = 0, r = x;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (check(m) == x) {
                return true;
            } else if (check(m) < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return false;
    }

    private int check(int x) {
        int ans = 0;
        while (x != 0) {
            ans += x;
            x /= 10;
        }
        return ans;
    }
}

左神胡廣燕吃香蕉

有n堆香蕉

piles[i]表示第i堆香蕉的個數(shù)

警衛(wèi)將會離開h小時

胡廣燕吃香蕉的速度為k(單位：根/小時)

如果這堆香蕉少于k根，她將吃掉所有香蕉，一小時之后，才可以吃其他堆的香蕉

返回她可以在h小時內(nèi)吃掉所有香蕉的最小速度k

if a<b，則check(a)>=check(b)? ?check(a)表示胡廣燕吃香蕉的速度為a，吃完所有香蕉要幾個小時

class Solution {
    /**
     * @param arr 每堆香蕉的數(shù)量
     * @param h   警衛(wèi)離開h小時
     * @return 胡廣燕吃完所有香蕉的最小速度
     */
    int f(int[] arr, int h) {
        //1
        int l = 0, r = Integer.MIN_VALUE, ans = 0, n = arr.length;
        for (int i = 0; i < n; i++) {
            r = Math.max(r, arr[i]);
        }
        //2
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            //compare with h
            if (check(m, arr) == h) {
                ans = m;
                r = m - 1;
                //valid
            } else if (check(m, arr) < h) {
                //smaller
                r = m - 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }

    /**
     * @param m   每小時吃m個香蕉
     * @param arr 每堆香蕉的數(shù)量
     * @return
     */
    private int check(int m, int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            ans += (arr[i] + m - 1) / m;
        }
        return ans;
    }
}

左神完成所有畫作所需要的最少時間

arr[i]表示完成第i幅畫需要的時間

num表示畫匠的數(shù)量

每個畫匠只能畫連在一起的畫作

所有的畫家并行工作

返回完成所有畫作所需要的最少時間

if a<b，則check(a)>=check(b)? ?check(a)表示要在a個小時內(nèi)完成所有畫作，需要幾個畫匠

class Solution {
    /**
     * @param arr arr[i]表示完成第i幅畫需要的時間
     * @param num 畫匠的數(shù)量
     * @return 完成所有畫作的最少時間
     */
    int f(int[] arr, int num) {
        //1
        int l = Integer.MIN_VALUE, r = 0, ans = 0;
        for (int i = 0; i < arr.length; i++) {
            l = Math.max(l, arr[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            r += arr[i];
        }
        //2
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            //compare with num
            if (check(m, arr) == num) {
                ans = m;
                r = m - 1;
                //valid
            } else if (check(m, arr) < num) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }

    /**
     * @param m   要在m小時內(nèi)完成所有畫作
     * @param arr
     * @return 要在m小時內(nèi)完成所有畫作，需要的畫匠的數(shù)量
     */
    public int check(int m, int[] arr) {
        int ans = 0, sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (sum + arr[i] == m) {
                ans++;
                sum = 0;
            } else if (sum + arr[i] < m) {
                sum += arr[i];
            } else {
                ans++;
                sum = arr[i];
            }
        }
        if (sum > 0)
            ans++;
        return ans;
    }
}

本文摘自：https://www.cnblogs.com/

算法-二分2022-01-01 23:12:18

算法-二分
2022-01-01 23:12:18