当前位置:网站首页>力扣每日一题-第51天-744. 寻找比目标字母大的最小字母
力扣每日一题-第51天-744. 寻找比目标字母大的最小字母
2022-08-10 00:48:00 【重邮研究森】
2022.8.9今天你刷题了吗?
题目:
给你一个排序后的字符列表 letters ,列表中只包含小写英文字母。另给出一个目标字母 target,请你寻找在这一有序列表里比目标字母大的最小字母。
在比较时,字母是依序循环出现的。举个例子:
如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b'],则答案返回 'a'
分析:
给定一个vector,里面是char类型,以及一个target也是char类型,你需要在vector里面找到一个大于target的字母,且该字母为vector中最小字母。那么就会存在两种情况。
1.找到了存在的字母:直接返回该字母。
2.找不到该字母:直接返回vector第一个字母。
思路:遍历vector数组,每遍历一次判断一次,如果遇到满足条件直接返回,如果不满足最后返回首字母。
解析:
1.暴力法
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
sort(letters.begin(),letters.end());
for(auto &ch:letters)
{
if(ch-'a'<=target-'a')
{
}
else
{
return ch;
}
}
return letters[0];
}
};
2.二分法
延续暴力法思路,区别在于不是直接遍历vector,而是利用二分查找从中间开始找,节约时间。
class Solution {
public:
char nextGreatestLetter(vector<char>& letters, char target) {
int l=0, r=letters.size()-1;
int ret = 0;
while(l <= r){
int m = l + (r-l)/2;
if(letters[m] <= target){
l = m + 1;
}else{
ret = m;
r = m - 1;
}
}
return letters[ret];
}
};
边栏推荐
猜你喜欢
防勒索病毒现状分析
PEG derivative Biotin-PEG1-OH (cas: 95611-10-2, 2-biotinaminoethanol) advantage description
y92.第六章 微服务、服务网格及Envoy实战 -- Envoy基础(三)
Solidity最强对手:MOVE语言及新公链崛起
【kali-密码攻击】(5.1.2)密码在线破解:Medusa
Data storage - the C language
XSS高级 svg 复现一个循环问题以及两个循环问题
CVPR22 Oral|通过多尺度token聚合分流自注意力,代码已开源
Solidity最强对手:MOVE语言及新公链崛起
Shader Graph学习各种特效案例
随机推荐
使用 GoogleTest 框架对 C 代码进行单元测试
商业模式及其 SubDAO 深入研究
【软考软件评测师】软件测试基础知识
Sikuli's Automated Testing Technology Based on Pattern Recognition
[LeetCode] Find the sum of the numbers from the root node to the leaf node
【Grpc】简介
How to activate the payment function on WeChat official account?
egg.js中Class constructor BaseContextClass cannot be invoked without ‘new‘解决方法
【ROS2原理10】Interface数据的规定
Interdepartmental Communication Skills
Unity顶点动画
2022金九银十工作潮,怎么样才能成功跳槽面试拿到高薪呢?
C language pointer practice questions
小程序中计算距离信息
Mysql数据库 ALTER 基本操作
Fedora 36 dnf 安装ModSecurity和 OWASP 核心规则集
由生物素参与的D-Biotinol,CAS号:53906-36-8具体特性说明
头脑风暴:单词拆分
删除表空间数据文件
JVM :运行时数据区-虚拟机栈