珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢逐步吃，但仍旧想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
提示： 吃每一堆分别要几小时;寻找左侧界限
class Solution {
public int minEatingSpeed(int[] piles, int H) {
Arrays.sort(piles);
int left = 1, right = piles[piles.length - 1] + 1;
while(left < right){
int mid = left + (right - left)/2;
if(canFinish(mid, piles, H)){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
public boolean canFinish(int k, int[] piles, int H){
long tmpHour = 0;
for(int i = 0; i< piles.length;i++){
tmpHour += (long)(piles[i] / k);
if(piles[i] % k > 0){
tmpHour ++;
}
}
if(tmpHour <= H){
return true;
}else{
return false;
}
}
}
复制代码
1011. 在 D 天内送达包裹的本领
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会凌驾船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载本领。
示例：
int left = weights[0], right = (weights[0] + weights[len -1]) * len / 2 + 1;
while(left < right){
int mid = left + (right - left)/2;
if(canFinish(weights, D, mid)){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
public boolean canFinish(int[] w, int D, int cap){
int i = 0;
for (int day = 0; day < D; day++) {
int maxCap = cap;
while ((maxCap -= w[i]) >= 0) {
i++;
if (i == w.length)
return true;
}
}
return false;
}
}
复制代码
392. 判定子序列
给定字符串 s 和 t ，判定 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
class Solution {
public boolean isSubsequence(String s, String t) {
int fromIndex = 0;
for(int i = 0; i < s.length(); i++){
char tmp = s.charAt(i);
int j = fromIndex;
for(; j < t.length(); j++){
if(t.charAt(j) == tmp){
fromIndex = j + 1;
break;
}
}
if(j == t.length()){
return false;
}
}
return true;
}
}
复制代码
后续挑衅 :
如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
class Solution {
public boolean isSubsequence(String s, String t) {
int m = s.length(), n = t.length();
ArrayList<Integer>[] index = new ArrayList[256];
// 先记下 t 中每个字符出现的位置
for (int i = 0; i < n; i++) {
char c = t.charAt(i);
if (index[c] == null)
index[c] = new ArrayList<>();
index[c].add(i);
}
int j = 0; // t 上的指针
// 借助 index 查找 s[i]
for (int i = 0; i < m; i++) {
char c = s.charAt(i);
// 整个 t 压根儿没有字符 c
if (index[c] == null) return false;
int pos = find(index[c], j);
// 二分搜索区间中没有找到字符 c
if (pos == index[c].size()) return false;
// 向前移动指针 j
j = index[c].get(pos) + 1;
}
return true;
}
public int find(ArrayList<Integer> arr, int target){