中级农民
- 积分
- 108
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2020-9-2
- 最后登录
- 1970-1-1
|
本帖最后由 ann要加油啊 于 2020-9-4 08:51 编辑
九月第三天:
42: 类似第11题最多的水,此处需要定义四个边界,最左边和左右边的边界用来双指针移动,还有两个当前容器的最高点左右边界为了得到所有的组合。var trap = function(height) {
let leftMax = -1, rightMax = -1, left = 0, right = height.length - 1, res = 0
while (left <= right) {
leftMax = height[left] > leftMax ? height[left] : leftMax
rightMax = height[right] > rightMax? height[right] : rightMax
if (leftMax > rightMax) {
res += rightMax - height[right]
right--;
}
else {
res += leftMax - height[left]
left++;
}
}
return res
};69: 平方根,可以简单的用math或者用binary-search:
var mySqrt = function(x) {
if(x == 0) {return 0;}
let start = 1; let end = Math.ceil(x/2);
while(start <= end) {
let mid = Math.floor((start + end)/2);
if(Math.floor(x/mid) == mid || Math.floor(x/(mid+1)) == mid) {
return mid;
} else if(Math.floor(x/mid) > mid) {
start = mid+1;
} else {
end = mid-1;
}
}
};
455: 先给greed和cookiesize排序,然后用贪心算法算出当前的cookiesize可以按顺序满足几个小孩。
var findContentChildren = function(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let child = 0;
for(let cookie=0;child<g.length && cookie<s.length;cookie++) {
if(g[child]<=s[cookie]) child++;
}
return child;
};
|
|