一、最后一个单词的长度
思路1：从后往前遍历
- 从后往前遍历，先找到最后一个字母，然后继续往前遍历，直到遇到空格，返回长度即可。
- 具体情况如下：
- 如果从后往前开始遍历到的是空格，跳过即可。
- 如果不是，那就直接开始计数，从最后一个字母开始，计算完一定会遇到空格或者字符串的开始位置，即下标0位置处，返回长度即可。
具体代码如下：
class Solution { public: //思路：从后往前遍历，先找到最后一个字母，然后继续往前遍历，直到遇到空格，返回长度即可。 int lengthOfLastWord(string s) { //情况1： //如果从后开始是空格，那就跳过 int end = s.size() -1; while(s[end]==' ') --end; //此时遇到了最后一个单词的最后一个字母 int len = 0; while(end>=0 && s[end]!=' ') { ++len; --end; } return len; } };
时间复杂度O(n)，空间复杂度O(1)
思路2：
这个思路看看就行，不太推荐。
- 大致情况是一样的，但有一点不同。
- 我们知道，每两个单词之间必有空格，所以我们可以这样操作：
- 从后往前遍历，如果第
i个位置是字符，并且第i-1个位置是空格，则说明i位置是最后一个单词的最开始的字母，到此刻就停下来即可。 - 然而面对下面的情况就有心无力了：
- 只有一个单词，没有任何其他的空格怎么办呢，我们就主动在该字符串的最开始位置加一个空格。
- 添加空格之前需要整体将字符串往后挪一位。
- 比如
Hello,变成了Hello
这样就可以了。
具体代码如下：
class Solution { public: int lengthOfLastWord(string s) { int len = 0; int flag = 0; //手动在后面开一个空间，再向后挪动数据。 //然后在0位置处加一个'\0' s.push_back(' '); for(int i = s.size()-1;i>0;--i) { s[i] = s[i-1]; } s[0] = ' '; for(int i = s.size()-1;i>=0;--i) { //如果一开始就是空格，跳过即可，直到遇到字母。 //计算完最后一个单词的长度后，后面肯定是空格 if(isalpha(s[i])) { ++len; if(s[i-1] == ' ') break; } } return len; } };
时间复杂度O(n),空间复杂度O(1)
二、重新排列字符串
思路
- 对于任意一组数据，比如
45670213
codeleet
- 我们需要做的是：
- 把下标4对应的字符c放到一个新的string的下标4位置处。
就完成了。
过程如下：
具体代码如下：
//思路，顺序表（indices）中的第i个元素是多少，就放到对应的ret的ret[indices[i]]的位置上，这个位置就放s[i] //比如s[0]的字符c，对应的indices[0] = 4，那就将字符'c'放入到ret的第4个下标位置。 //时间复杂度O(N),空间复杂度O(N) string restoreString(string s, vector<int>& indices) { //首次开辟s.size()大小的空间,初始化成任何字符均可。 string ret(s.size(),'a'); for(int j =0; j < s.size(); ++j) { ret[indices[j]] = s[j]; } return ret; } };
注意：
这里的string ret(s.size(),‘a’);
是初始化一个string类ret，给定s.size()大小的空间
具体的重载如上，其中后面的字符不管初始化成什么均可。
时间复杂度:O(n)，遍历字符串的长度个字符，空间复杂度O(n)，需要新开辟n大小的空间。
