指针、简单)"/>
leetcode 58. 最后一个单词的长度(双指针、简单)
作者简介:C/C++ 、Golang 领域耕耘者,创作者
个人主页:作者主页
活动地址:CSDN21天学习挑战赛
题目来源: leetcode官网
如果感觉博主的文章还不错的话,还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~
文章目录
- 💜 题目描述
- 🧡 算法分析
- 一、直接从字符串后面开始遍历
- 二、双指针从前遍历
- 💚 代码实现
- 💙 时间复杂度分析
💜 题目描述
给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串
示例1:
输入:s = “Hello World”
输出:5
解释:最后一个单词是“World”,长度为5。
示例2:
输入:s = " fly me to the moon "
输出:4
解释:最后一个单词是“moon”,长度为4。
示例 3:
输入:s = “luffy is still joyboy”
输出:6
解释:最后一个单词是长度为6的“joyboy”。
🧡 算法分析
此题方法是用双指针
两种方法:
一、直接从字符串后面开始遍历
算法步骤:
- 一个指针从后面开始遍历,当找到第一个非空字符 记录位置;
- 第二个指针从第一次非空字符位置开始,一直找到下一次空字符;
- 返回这两个指针的距离,就是最后一个单词的长度。
二、双指针从前遍历
算法步骤:
- 定义两个变量: re, sum, 分别表示当前最后一个单词(已遍历完)的长度,以及当前单词(正在遍历,但还没遍历完)的长度;
- 然后遍历字符串
- 如果遇到非空格字符,让 sum 加1;
- 如果遇到空格,判断sum是否为0,如果大于0,说明已经遍历完一个新单词,清空sum,更新res;
💚 代码实现
class Solution {
public:int lengthOfLastWord(string s) {for(int i = s.size() - 1; i >=0; i --){if(s[i] == ' ') continue;int j = i - 1;while(j >= 0 && s[j] != ' ') j --;return i - j;}return 0;}
};
算法二
class Solution {
public:int lengthOfLastWord(string s) {int sum = 0, res = 0;for (int i = 0; i < s.size(); i ++ )if (s[i] == ' '){if (sum) res = sum;sum = 0;}elsesum ++ ;if (sum) res = sum;return res;}
};
执行结果:
💙 时间复杂度分析
其中遍历一次, 时间复杂度为O(n)
如果觉得对你有帮助的话:
👍 点赞,你的认可是我创作的动力!
🧡 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富!
更多推荐
leetcode 58. 最后一个单词的长度(双指针、简单)
发布评论