APP
左神 step num
給定一個正整數，判斷它是否是某個數的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堆香蕉的個數
警衛將會離開h小時
胡廣燕吃香蕉的速度為k(單位：根/小時)
如果這堆香蕉少于k根，她將吃掉所有香蕉，一小時之后，才可以吃其他堆的香蕉
返回她可以在h小時內吃掉所有香蕉的最小速度k
if a<b，則check(a)>=check(b)? ?check(a)表示胡廣燕吃香蕉的速度為a，吃完所有香蕉要幾個小時
?
class Solution { /** * @param arr 每堆香蕉的數量 * @param h 警衛離開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 每堆香蕉的數量 * @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表示畫匠的數量
每個畫匠只能畫連在一起的畫作
所有的畫家并行工作
返回完成所有畫作所需要的最少時間
if a<b，則check(a)>=check(b)? ?check(a)表示要在a個小時內完成所有畫作，需要幾個畫匠
class Solution { /** * @param arr arr[i]表示完成第i幅畫需要的時間 * @param num 畫匠的數量 * @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小時內完成所有畫作 * @param arr * @return 要在m小時內完成所有畫作，需要的畫匠的數量 */ 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/
