剑指 Offer 58 - I. 翻转单词顺序
剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode）
题目大意
输入: "the sky is blue"
输出: "blue is sky the"
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
C++
双指针,一个指针从字符串的末尾开始往前找,找到第一个空格,且空格后面不是空格,说明空格的后面就是一个单词,然后把这个单词放到提前开好的string里面.
如"the sky is blue",从后往前找,先找到blue前面的那个空格,然后从’b’开始往后拷贝,把"blue"拷贝到一个新的字符串ans中,再往前找找到"is",把"is"再拷贝到字符串ans中,重复上面的步骤,最后返回ans.
代码实现上有不少细节要注意,比如从后往前走的最后一个单词拷贝完不能加空格,比如从后往前走的最后一个单词前面没有空格无法进入if的条件里面,这些实现细节因人而异.
class Solution {
public:
string reverseWords(string s) {
if (s=="")
{
return s;
}
int len = s.size();
string res;
int cnt = 0;
res.resize(len);
for (int i = len - 1; i >= 0; i--)
{
if (i+1<len&&s[i] == ' '&&s[i+1]!=' ')
{
int j = i + 1;
while (j >= 0 && j < len && s[j] != ' ')
{
res[cnt] = s[j];
cnt++;
j++;
}
res[cnt] = ' ';
cnt++;
}
}
if (s[0]!=' ')
{
int j = 0;
while (j >= 0 && j < len && s[j] != ' ')
{
res[cnt] = s[j];
cnt++;
j++;
}
}
if (cnt-1>=0&&cnt-1<len&&res[cnt-1]==' ')
{
res[cnt - 1] = '\0';
}
return res;
}
};
Python
额,python新手,利用接口即可.split里面不加参数就把字符串里的所有空格字符作为分割字符,分割出来的单词放入一个列表内返回,reverse方法反转列表,然后再用join方法把每个单词直接加上一个空格连接起来.
具体接口直接查文档即可:内置类型 — Python 3.10.7 文档
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
tokens = s.split()
tokens.reverse()
return ' '.join(tokens)
796. 旋转字符串 - 力扣
796. 旋转字符串 - 力扣（LeetCode）
题目大意
看字符串s能不能旋转成goal
输入: s = "abcde", goal = "cdeab"
输出: true
输入: s = "abcde", goal = "abced"
输出: false
C++
方法一
在goal字符串里面建立s首字母的索引加快比对速度,建立好之后开始比对即可.
class Solution {
public:
bool rotateString(string s, string goal) {
if (s=="")
{
return goal == "";
}
int len_s = s.size();
int len_g = goal.size();
if (len_s ==len_g)
{
char ch = s[0];
vector<int>v;
for (int i = 0; i <len_g;i++ )
{
if (goal[i]==ch)
{
v.push_back(i);
}
}
bool f = 0;
for (int i=0;i<v.size();i++)
{
int beg_g = v[i];
int beg_s = 0;
while (s[beg_s]==goal[beg_g])
{
beg_s++;
beg_g++;
beg_g %= len_g;
if (beg_s==len_s)
{
return true;
}
}
}
return false;
}
else
{
return false;
}
}
};
方法二
确保字符串长度相等,再利用search方法查找子串.search的实现效率很高,比kmp还高,底层实现是BM算法,具体实现没了解过
class Solution {
public:
bool rotateString(string s, string goal) {
string s1 = s + s;
return s.size() == goal.size()
&& search(s1.begin(), s1.end(), goal.begin(), goal.end())!=s1.end();
}
};
Python
检查长度相等,然后直接在s+s里面找子串看能不能找到goal
class Solution(object):
def rotateString(self, s, goal):
"""
:type s: str
:type goal: str
:rtype: bool
"""
if(len(s)!=len(goal)):
return False
return goal in (s+s)
Python3
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
return len(s)==len(goal) and goal in (s+s)
2255. 统计是给定字符串前缀的字符串数目
2255. 统计是给定字符串前缀的字符串数目 - 力扣（LeetCode）
题目大意
判断words数组里的字符串是否是s字符串的前缀,返回words是字符串前缀的字符串的数目.
输入：words = ["a","b","c","ab","bc","abc"], s = "abc"
输出：3
解释：
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。
输入：words = ["a","a"], s = "aa"
输出：2
解释：
两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。
C++
遍历每一个单词,让每个单词的字符和s的每个字符从前往后比对来判断单词是否是s的前缀.
class Solution {
public:
int countPrefixes(vector<string>& words, string s) {
int sz = s.size();
int cnt = 0;
for (auto& e:words)
{
string& tmp = e;
int len = tmp.size();
if (len>sz)
{
continue;
}
else
{
bool f = 0;
for (int i=0;i<len;i++)//挨个比对
{
if (tmp[i]!=s[i])
{
f = 1;
break;
}
}
if (f==0)
{
cnt++;
}
}
}
return cnt;
}
};
Python
和c++一样的思路,暴力遍历然后比对
class Solution(object):
def countPrefixes(self, words, s):
"""
:type words: List[str]
:type s: str
:rtype: int
"""
cnt=0;
for word in words:
if s.startswith(word):
cnt+=1;
return cnt;
|