- 剑指 Offer 05. 替换空格">剑指 Offer 05. 替换空格
- 剑指 Offer 17. 打印从1到最大的n位数">剑指 Offer 17. 打印从1到最大的n位数
- 剑指 Offer 20. 表示数值的字符串">剑指 Offer 20. 表示数值的字符串
- 剑指 Offer 45. 把数组排成最小的数">剑指 Offer 45. 把数组排成最小的数
- 剑指 Offer 48. 最长不含重复字符的子字符串">(滑动窗口、双指针)剑指 Offer 48. 最长不含重复字符的子字符串
- 剑指 Offer 50. 第一个只出现一次的字符">剑指 Offer 50. 第一个只出现一次的字符
- 剑指 Offer 58 - I. 翻转单词顺序">剑指 Offer 58 - I. 翻转单词顺序
- 剑指 Offer 58 - II. 左旋转字符串">剑指 Offer 58 - II. 左旋转字符串
- 剑指 Offer 67. 把字符串转换成整数">剑指 Offer 67. 把字符串转换成整数
剑指 Offer 05. 替换空格
思路一：辅助空间
class Solution {public:string replaceSpace(string s) {string res;for(const auto& ch : s) {if (ch == ' ') {res += "%20";} else {res.push_back(ch);}}return res;}};
结果不算的话空间复杂度O(1)
时间复杂度O(N)
思路二：原地操作
class Solution {public:string replaceSpace(string s) {int cnt = 0;// 统计空格的个数int old = s.size();// 保留原字符串的长度for (auto c : s)if (c == ' ')cnt++;s.resize(s.size() + 2 * cnt);for (int i = s.size() - 1, j = old - 1; j < i; i--, j--) {if (s[j] == ' ') {s[i--] = '0';s[i--] = '2';s[i] = '%';} else {s[i] = s[j];}}return s;}};
剑指 Offer 17. 打印从1到最大的n位数
直接计算
class Solution {public:vector<int> printNumbers(int n) {vector<int> res;int i = 1;while (n--) {i *= 10;}for (int j = 1; j < i; j++) {res.push_back(j);}return res;}};
这种思路比较简单，但是如果给的n比较大会出现int溢出问题，因此可以看情况考虑下面的解法
考虑大数问题💦
- 表示大数的变量类型：
- 无论是 short / int / long … 任意变量类型，数字的取值范围都是有限的。因此，大数的表示应用字符串 String 类型。
- 生成数字的字符串集：
使用 int 类型时，每轮可通过 +1+1 生成下个数字，而此方法无法应用至 String 类型。并且， String 类型的数字的进位操作效率较低，例如 “9999” 至 “10000” 需要从个位到千位循环判断，进位 4 次。
观察可知，生成的列表实际上是 nn 位 00 - 99 的 全排列 ，因此可避开进位操作，通过递归生成数字的 String 列表。
- 递归生成全排列：
- 基于分治算法的思想，先固定高位，向低位递归，当个位已被固定时，添加数字的字符串。例如当 n = 2n=2 时（数字范围 1 - 991−99 ），固定十位为 00 - 99 ，按顺序依次开启递归，固定个位 00 - 99 ，终止递归并添加数字字符串。
剑指 Offer 20. 表示数值的字符串
模拟
class Solution {public boolean isNumber(String s) {if(s == null || s.length() == 0) return false; // s为空对象或 s长度为0(空字符串)时, 不能表示数值boolean isNum = false, isDot = false, ise_or_E = false; // 标记是否遇到数位、小数点、‘e’或'E'char[] str = s.trim().toCharArray(); // 删除字符串头尾的空格，转为字符数组，方便遍历判断每个字符for(int i=0; i<str.length; i++) {if(str[i] >= '0' && str[i] <= '9') isNum = true; // 判断当前字符是否为 0~9 的数位else if(str[i] == '.') { // 遇到小数点if(isDot || ise_or_E) return false; // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'isDot = true; // 标记已经遇到小数点}else if(str[i] == 'e' || str[i] == 'E') { // 遇到‘e’或'E'if(!isNum || ise_or_E) return false; // ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'ise_or_E = true; // 标记已经遇到‘e’或'E'isNum = false; // 重置isNum，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况}else if(str[i] == '-' ||str[i] == '+') {if(i!=0 && str[i-1] != 'e' && str[i-1] != 'E') return false; // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置}else return false; // 其它情况均为不合法字符}return isNum;}}
class Solution {public:bool isNumber(string s) {int len = s.size();if (len == 0) return false;bool isNum = false, isDot = false, isE = false;int i = 0;// 找到第一个不为空格的字符while (i < len && s[i] == ' ') i++;int first = i; // 记录第一个非空格for (; i < len; i++) {if (s[i] >= '0' && s[i] <= '9') {isNum = true; // 标记遇到数字} else if (s[i] == '.') {if (isDot || isE) return false; // 小数点不能重复，e后面不能有小数isDot = true;} else if (s[i] == 'e' || s[i] == 'E'){if (!isNum || isE ) return false; // e前面要有数字，e不能重复isE = true;isNum = false; // 重置，然后判断e后面是否有整数} else if (s[i] == '+' || s[i] == '-') {if (i != first && s[i - 1] != 'e' && s[i - 1] != 'E') return false; // + - 只能出现在第一个字符或者e的后面} else if (s[i] == ' ') {// 处理字符串尾部的空格while (i < len && s[i] == ' ') i++;// 如果尾部之前出现其他非空格，返回falseif (i == len) return isNum;else return false;} else {return false; // 其他情况都不是数字}}return isNum;}};
有限状态机💦
剑指 Offer 45. 把数组排成最小的数
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
for (auto num : nums) {
strs.push_back(to_string(num));
}
sort(strs.begin(), strs.end(), [](string &a, string &b) {
return a + b < b + a;
});
string s;
for (auto str : strs) {
s += str;
}
return s;
}
};
(滑动窗口、双指针)剑指 Offer 48. 最长不含重复字符的子字符串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() <= 1) return s.size();
unordered_map<char, int> um;
int res = 0;
int i = 0, j = 0;
int len = 0;
while (i < s.size()) {
while(um[s[i]] > 0) {
um[s[j++]]--;
}
res = max(res, i - j + 1);
um[s[i++]]++;
}
return res;
}
};
剑指 Offer 50. 第一个只出现一次的字符
用哈希表记录出现次数，然后遍历哈希表，将第一个次数为1的返回
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<int, int> frequency;
for (char ch: s) {
++frequency[ch];
}
for (int i = 0; i < s.size(); ++i) {
if (frequency[s[i]] == 1) {
return s[i];
}
}
return ' ';
}
};
剑指 Offer 58 - I. 翻转单词顺序
151题笔记
https://www.yuque.com/u22270676/qvvmek/nn95ro#WZfIE
解题思路参考151题的笔记
用栈
class Solution {
public:
string reverseWords(string s) {
stack<string> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') continue;
string temp;
while (i < s.size() && s[i] != ' ')
temp.push_back(s[i++]);
st.push(temp); // 保存单词
}
string res;
while (!st.empty()) {
res += st.top();
st.pop();
res.push_back(' ');
}
// 删除最后一个空格
res.pop_back();
return res;
}
};
- 时间复杂度O(N)
- 空间复杂度O(N)
反向遍历，直接将单词添加到要返回的字符串结尾
class Solution {
public:
string reverseWords(string s) {
string res;
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == ' ') continue;
int end = i, begin = i;//记录单词结束的位置和开始的位置
while (i >= 0 && s[i] != ' ') {
begin--;
i--;
}
i++;
for(int j = begin + 1; j <= end; j++) {
res.push_back(s[j]);
}
res += ' ';
}
res.pop_back();
return res;
}
};
原地操作
class Solution {
public:
// 移除多余的空格
void removeSpace(string &s) {
// 移除前面的空格
int slow = 0, fast = 0;
while (fast < s.size() && s[fast] == ' ') fast++;
// 移动中间的空格
while (fast < s.size()) {
if (fast - 1 > 0 && s[fast] == s[fast - 1] && s[fast] == ' ') {
fast++;
} else {
s[slow++] = s[fast++];
}
}
// 移除尾部的空格
if (slow - 1 > 0 && s[slow - 1] == ' ') {//最后一个字符为空格
s.resize(slow - 1);
} else {//最后一个字符不是空格
s.resize(slow);
}
}
//翻转字符串中的单词，左闭右闭
void reverse(string &s, int begin, int end) {
for (int i = begin, j = end; i < j; i++, j--) {
swap(s[i], s[j]);
}
}
string reverseWords(string s) {
removeSpace(s);
reverse(s, 0, s.size() - 1);
for (int i = 0; i < s.size(); i++) {
int begin = i, end = i;
while (end < s.size() && s[end] != ' ') {
end++;
i++;//for循环上i再加一，正好将空格跳过
}
reverse(s, begin, end - 1);
}
return s;
}
};
剑指 Offer 58 - II. 左旋转字符串
思路一：将字符串左移位n次
class Solution {
public:
string reverseLeftWords(string s, int n) {
for (int i = 0; i < n; i++) {
char tmp = s[0];
for (int j = 1; j < s.size(); j++) {
s[j - 1] = s[j];
}
s[s.size() - 1] = tmp;
}
return s;
}
};
复杂度分析：
- 时间复杂度为O(n^2)
-
思路二：空间换时间
class Solution { public: string reverseLeftWords(string s, int n) { string res; for (int i = n; i < s.size(); i++) res.push_back(s[i]); for (int i = 0; i < n; i++) res.push_back(s[i]); return res; } };复杂度分析：
时间复杂度为O(n)
- 空间复杂度为O(n)
思路三：全局反转+局部反转
参考反转字符串里的单词的解法，可以先将字符串整体反转，然后再将0 ~ s.size() - - 1和 s.zie() - ~ s.size() - 1分别反转就可以实现原地左旋
例如：
字符串 s = “abcdefg”, k = 2
- 全局反转后得到”gfedcba”
- 局部反转后得到”cdefgab”
```cpp
class Solution {
public:
string reverseLeftWords(string s, int n) {
} };int len = s.size(); reverse(s.begin(), s.end());//左闭右开 reverse(s.begin(), s.begin() + len - n); reverse(s.begin() + len - n, s.end()); return s;
当然，先局部反转，再全局反转，也是一样的<br />s = "abcdefg", k = 2
- 局部反转："bagfedc"
- 全局反转："cdefgab"
```cpp
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s.begin(), s.begin() + n);//左闭右开
reverse(s.begin() + n, s.end());
reverse(s.begin(), s.end());
return s;
}
};
剑指 Offer 67. 把字符串转换成整数
class Solution {
public:
int myAtoi(string s) {
if (s.size() == 0) return 0;
int i = 0, n = s.size();
while (i < n && s[i] == ' ') ++i;
int flag = 1;
long long num = 0;
if (i < n) {
if (s[i] == '+') {
++i;
} else if (s[i] == '-') {
flag = -1;
++i;
}
if (s[i] >= '0' && s[i] <= '9') {
while (i < n && s[i] >= '0' && s[i] <= '9') {
num *= 10;
num += (s[i] - '0');
if (num > INT32_MAX || num < INT32_MIN)
return flag == -1? INT32_MIN : INT32_MAX;
++i;
}
}
}
return flag * num;
}
};
若有收获，就点个赞吧
0 人点赞
