当前位置:网站首页>leetcode:881. lifeboat
leetcode:881. lifeboat
2022-07-05 14:28:00 【Oceanstar's study notes】
Title source
Title Description
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
}
};
title
greedy + Double pointer
(1) Go through the array first , If a person weighs more than limit, Then return to infinity , It means that you can't decide how many ships
(2) Then sort , Slide from the middle dividing point to the left and right
- look for <= limit/2 The rightmost position , As L The pointer
- Find the first one more than limit/2 The location of , As R The pointer
- see L Location and R Can we get a boat together , You can't , exceed
L Move to the left …L Arrived 3, Sure
Don't assign boats first ,R Slide right , Slide all the way to R If you go down one more step, you can't follow 3 Gather up a boat
- The starting point of greed : from 3 Start to the left 6 individual , Go to consume the one on the right 6 individual , It must be the most economical
(3) give an example : The right side is exhausted first
(4) give an example : The left side is exhausted first
ship Of Count The amount = × Count The amount 2 + √ Count The amount 2 + Right Side Remnant Next Of Count The amount The number of ships = \frac { × Number } {2} + \frac { √ Number } {2} + The remaining quantity on the right ship Of Count The amount =2× Count The amount +2√ Count The amount + Right Side Remnant Next Of Count The amount
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
if(people.empty()){
return 0;
}
int N = people.size();
std::sort(people.begin(), people.end());
if(people[N - 1] > limit){
return -1;
}
int lessR = -1;
for (int i = N - 1; i >= 0; --i) {
if(people[i] <= limit/2){
lessR = i;
break;
}
}
if(lessR == -1){
return N;
}
int L = lessR;
int R = lessR + 1;
int noUsed = 0;
while (L >= 0){
int solved = 0;
while (R < N && people[L] + people[R] <= limit){
solved++;
R++;
}
if(solved == 0){
noUsed++;
L--;
}else{
L = std::max(-1, L - solved);
}
}
int all = lessR + 1;
int used = all - noUsed;
int moreUnsolved = (N - all) - used;
return used + ((noUsed + 1) >> 1) + moreUnsolved;
}
};
Double pointer
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
int N = people.size();
std::sort(people.begin(), people.end());
if(people[N - 1] > limit){
return -1;
}
int ans = 0, l = 0, r = N - 1, sum = 0;
while (l <= r){
sum = l == r ? people[l] : people[l] + people[r];
if(sum > limit){
r--;
}else{
l++;
r--;
}
ans++;
}
return ans;
}
};
边栏推荐
- 用“新”字来吸引好奇的人群
- 享你所想。智创未来
- 动态规划
- 一网打尽异步神器CompletableFuture
- R language dplyr package select function, group_ By function, mutate function and cumsum function calculate the cumulative value of the specified numerical variable in the dataframe grouping data and
- Enjoy what you want. Zhichuang future
- The function of qualifier in C language
- Zhizhen new energy rushes to the scientific innovation board: the annual revenue is 220million, and SAIC venture capital is the shareholder
- 【学习笔记】阶段测试1
- Webrtc learning (II)
猜你喜欢
Tidb DM alarm DM_ sync_ process_ exists_ with_ Error troubleshooting
【学习笔记】阶段测试1
Sharing the 12 most commonly used regular expressions can solve most of your problems
循环不变式
ASP. Net large takeout ordering system source code (PC version + mobile version + merchant version)
快消品行业SaaS多租户解决方案,构建全产业链数字化营销竞争力
Intelligent supply chain collaboration system solution for daily chemical products industry: digital intelligent SCM supply chain, which is the "acceleration" of enterprise transformation
Thymeleaf th:classappend属性追加 th:styleappend样式追加 th:data-自定义属性
openGauss数据库源码解析系列文章—— 密态等值查询技术详解(下)
freesurfer运行完recon-all怎么快速查看有没有报错?——核心命令tail重定向
随机推荐
openGauss数据库源码解析系列文章—— 密态等值查询技术详解(下)
矩阵链乘 - 动态规划实例
Pointer operation - C language
PMP考试20天能通过吗?
启牛学堂班主任给的证券账户安全吗?能开户吗?
Judge whether the variable is an array
R language ggplot2 visualization: use ggplot2 to visualize the scatter diagram, and use the labs parameter to customize the X axis label text (customize X axis labels)
Share 20 strange JS expressions and see how many correct answers you can get
分享 12 个最常用的正则表达式,能解决你大部分问题
Total amount analysis accounting method and potential method - allocation analysis
无密码身份验证如何保障用户隐私安全?
[learning notes] connectivity and circuit of graph
R语言使用原生包(基础导入包、graphics)中的boxplot函数可视化箱图(box plot)
Tidb DM alarm DM_ sync_ process_ exists_ with_ Error troubleshooting
Use the word "new" to attract curious people
区间 - 左闭右开
LeetCode_ 67 (binary sum)
R language ggplot2 visualization: visual line graph, using legend in theme function The position parameter defines the position of the legend
R language ggplot2 visual density map: Visual density map by group and custom configuration geom_ The alpha parameter in the density function sets the image transparency (to prevent multiple density c
Catch all asynchronous artifact completable future