文章目录
道阻且长，行则将至。
1、仅仅反转字母
1.1、题目描述
给你一个字符串
s，根据下述规则反转字符串：
????所有非英文字母保留在原有位置。
????所有英文字母（小写或大写）位置反转。
返回反转后的s。
示例：
输入：s = “ab-cd”
输出：“dc-ba”
1.2、题目分析
????（1）双指针的题目，维护两个指针 l 和 r，初始化分别指向字符串首和尾；
????（2）使用 l 指针从左边开始扫描，r 指针从右边开始扫描找到 英文字母 ，也就是待反转的字符；
????（3）反转字符串之后，不要忘了左右指针也要继续扫描下去，直到扫描结束。
1.3、代码实现
class Solution {
public:
string reverseOnlyLetters(string s) {
int l = 0, r = s.size()-1;
while(true){
while(l < r && !isalpha(s[l])) ++l;
while(l < r && !isalpha(s[r])) --r;
if(l >= r){
break;
}
std::swap(s[l], s[r]);
++l;
--r;
}
return s;
}
};
2、两数之和 II - 输入有序数组
2.1、题目描述
给你一个下标从 1 开始的整数数组
numbers，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target的两个数。如果设这两个数分别是numbers[index1]和numbers[index2]，
则1 <= index1 < index2 <= numbers.length。
以长度为2的整数数组[index1, index2]的形式返回这两个整数的下标index1和index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
2.2、题目分析
????（1）双指针的经典题目了，也是比较简单的题目；
????（2）维护左右两个指针 left 和 right ，分别指向数组的首尾，思路很清晰，将当前左右指针指向的数之和与 target 比较；
????（3）大于目标值，右指针 -- ，小于目标值左指针 ++ ，否则目标值则返回。
2.3、代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int m = numbers.size();
int left = 0, right = m - 1;
while (left < right){
int sum = numbers[left] + numbers[right];
if(sum > target){
--right;
}
else if(sum < target){
++left;
}
else{
return {left+1, right+1};
}
}
return { -1, -1 };
}
};
3、区间子数组个数
3.1、题目描述
给你一个整数数组 nums 和两个整数：
left及right。找出nums中连续、非空且其中最大元素在范围[left, right]内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例：
输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]
3.2、题目分析
????（1）参考的是Leetcode中的题解，晚霞作棠；
????（2）双指针维护可行区间，遍历每一个下标，贡献为当前双指针区间 [i, j] ，j 是区间中的大于等于 L 小于等于 R 的元素下标。
3.3、代码实现
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int cnt = 0, l = 0;
int j = -1;
int i;
for(i = 0; i < nums.size(); ++i){
if(nums[i] >= left && nums[i] <= right){
j = i;
}
if(nums[i] > right){
l = i + 1;
j = -1;
}
if(j != -1){
cnt += (j - l + 1);
}
}
return cnt;
}
};
4、比较版本号
4.1、题目描述
给你两个版本号
version1和version2，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个'.'连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。例如，2.5.33和0.1都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号1和修订号001相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，版本1.0小于版本1.1，因为它们下标为0的修订号相同，而下标为1的修订号分别为0和1，0 < 1。
返回规则如下：
????如果version1 > version2返回1，
????如果version1 < version2返回-1，
????除此之外返回0。
示例：
输入：version1 = “1.01”, version2 = “1.001”
输出：0
解释：忽略前导零，“01” 和 “001” 都表示相同的整数 “1”
4.2、题目分析
????（1）比较版本号的大小，一个想法是两个版本的字符串按照 '.' 对应解析出来比较大小；
????（2）具体就是维护双指针分别指向 version1 和 version2 ，遍历它们求出对应位置的版本号数字大小进行比较；
????（3）（Ⅰ）处的初始化为 0 是为了计算当前位置版本数字大小，也是当前位置无版本号时的数字。
4.3、代码实现
class Solution {
public:
int compareVersion(string version1, string version2) {
int n = version1.size(), m = version2.size();
int i = 0, j = 0;
while(i < n || j < m){
long x = 0, y = 0; // (Ⅰ)
for(; i < n && version1[i] != '.'; ++i){
x = x * 10 + version1[i] - '0';
}
++i;
for(; j < m && version2[j] != '.'; ++j){
y = y * 10 + version2[j] - '0';
}
++j;
if(x != y){
return x > y ? 1 : -1;
}
}
return 0;
}
};
5、压缩字符串
5.1、题目描述
给你一个字符数组
chars，请使用下述算法压缩：
从一个空字符串s开始。对于chars中的每组 连续重复字符 ：
????如果这一组长度为1，则将字符追加到s中。
????否则，需要向s追加字符，后跟这一组的长度。
压缩后得到的字符串s不应该直接返回 ，需要转储到字符数组chars中。需要注意的是，如果组长度为10或10以上，则在chars数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
示例：
输入：chars = [“a”,“a”,“b”,“b”,“c”,“c”,“c”]
输出：返回 6 ，输入数组的前 6 个字符应该是：[“a”,“2”,“b”,“2”,“c”,“3”]
解释：“aa” 被 “a2” 替代。“bb” 被 “b2” 替代。“ccc” 被 “c3” 替代。
5.2、题目分析
????（1）题目中明确要求了 修改完输入数组后 再返回数组的长度，并且要求只是用常量额外空间的算法解决此问题，因此使用原地操作来实现；
????（2）维护一个读指针 read ，一个写指针 write ，分别指向 chars 中待读取的字符下标和即将写入的位置下标；
????（3）当 read 移动到了最后一个位置或者移动到了某一段连续相同字符子串的最右侧位置时，我们就写入这个字符，计算并写入字符数量；
????（4）字符数量计算并写入这一块就很妙，妙在 reverse(&chars[anchor], &chars[write]) ，头一次见到这种用法，之前都是 reverse(chars.begin(), chars.end()) 这种用法，最多也就是 reverse(chars.begin(), chars.begin() + n) 这样了。但是其实原理都是一样的，第一个位置就是 开始位置的迭代器 嘛，第二个参数就是结束的 尾后迭代器 嘛。
5.3、代码实现
class Solution {
public:
int compress(vector<char>& chars) {
int n = chars.size();
int read, write = 0, left = 0;
for(read = 0; read < n; ++read){
if(read == n-1 || chars[read] != chars[read+1]){
chars[write++] = chars[read];
int num = read - left + 1;
if(num > 1){
int anchor = write;
while(num){
chars[write++] = num % 10 + '0';
num /= 10;
}
reverse(&chars[anchor], &chars[write]);
}
left = read + 1;
}
}
return write;
}
};
6、双指针使用小结
????（1）字符串、数组 的题目，好像是废话，几乎所有的题目都是依托这两种数据结构来出题的，更进一步来讲，可以说是依托 数组 来出题的，C++ 里面称之为 容器vector。你看，链表的一些问题求解，比如反转链表、合并链表都可以先将链表元素撸到容器中，再对容器进行相应的操作，最后再撸回链表。所以说 容器 是最为常用的数据结构，以及最重要的数据结构一点都不为过；
????（2）既然 容器 很重要，那就肝它们，顺序容器：vector ，deque ，string 等；关联容器：map ，set ，以及按照关键字可重复出现的multiset ，multimap ，还有各自对应的无序集合 unordered_map 、unordered_set等等；
????（3）需要熟练各种容器的 初始化、元素的 增、删、改、查 、以及一些数据结构特有的操作。还有一些库函数的使用，比如 二分查找 ，找出大于等于 val 元素的最小元素 upper_bound(beg, end, val) 等。 当然能自己写的函数尽量自己去实现。
????（4）双指针就是定义两个指向元素的 下标 ；
????（5）双指针题目做的还不够多，暂时还没有什么特别的想法。
