- 前言
- 第一题 917. 仅仅反转字母
- 题目描述
- 解题报告
- 参考代码(C++版本)
- 第二题 167. 两数之和 II - 输入有序数组
- 题目描述
- 解题报告
- 参考代码(C++版本)
- 第三题 165. 比较版本号
- 题目描述
- 解题报告
- 参考代码(C++版本)
- 第四题 443. 压缩字符串
- 题目描述
- 解题报告
- 参考代码(C++版本)
- 总结
每日算法练习，千锤百炼，静待花开。
现在的单片机是会持续更的，因为我要靠它去捣腾暑假实习的事儿：十四天学会51单片机；
Leetcode的专栏会持续更，因为在跟着英雄哥做知识星球的事儿：在lc被欺负的这些年；
对英雄哥的知识星球有兴趣的可以看看他这篇文章喔： 英雄算法联盟 | 31天让你的算法与众不同
至于现在这专栏了，是我4月12号的想法，这个专栏只会记录全部是每日一题：知识星球每天的习题，以及在咱高校算法学习社区中，泡泡和p佬普及组和提高组的题目，一般是当天写当天更吧。我一般会先写星球上的题，因为泡泡他俩的题有点难，得晚点补上
第一题 917. 仅仅反转字母 题目描述解题报告
原题传送门双指针迭代吧，一个放在头，一个放在尾部，跟着题目的意思走，遇到不是字母的就跳过，可以通过ASCII码来实现
参考代码(C++版本)
A ~ Z 的 ASCII码是65 ~ 90
a ~ a 的 ASCII码是97 ~ 122
class Solution {
public:
string reverseOnlyLetters(string s) {
int n = s.size();
int l = 0 , r = n-1;
while(l < r)
{
//按照题意，只是交换字母，其他的就直接跳过
while(!(s[l] <= 122 && s[l] >= 97 || s[l] >= 65 && s[l] <= 90) && l < r) l++;
while(!(s[r] <= 122 && s[r] >= 97 || s[r] >= 65 && s[r] <= 90) && l < r) r--;
char tmp = s[l];
s[l] = s[r];
s[r] = tmp;
l++,r--;
}
return s;
}
};
第二题 167. 两数之和 II - 输入有序数组 题目描述解题报告
原题传送门初始时两个指针分别指向序列首和序列尾，在遍历中每次计算两个指针指向的两个元素之和，并和目标值比较。
参考代码(C++版本)
如果两个元素之和等于目标值，则发现了唯一解，统计结果，跳出循环
如果两个元素之和小于目标值，则将左侧指针右移一位，使整体的和变小
如果两个元素之和大于目标值，则将右侧指针左移一位，使整体的和变大
移动指针之后，重复上述操作，直到找到答案。
class Solution {
public:
vector twoSum(vector& numbers, int target) {
int n = numbers.size();
vector ans;
int l = 0, r = n-1;
while(l < r)
{
if(numbers[l]+ numbers[r] == target)
{
ans.push_back(l+1);
ans.push_back(r+1);
break;
}
//如果两个元素之和大于目标值，右指针减一下，从而减少整体值
if(numbers[l]+ numbers[r] > target) r--;
else l++;
}
return ans;
}
};
我电脑似乎出问题了蛮，其他网页acwing、洛谷、codeforces都能能打开，Leetcode打不开…
先浅放中午写的两个题，，待会下课回来写咱社区的题啦，后续补上这两个双指针
我的leetcode恢复啦，我回来补充啦~
第三题 165. 比较版本号两个指针扫描分别扫描两端区间+积累将一段连续的数字字符串转换成数字(同时也可以取出前导0)
题目描述解题报告
原题传送门读了题，大家都可能有思路，直接去扫描嘛，扫描小数点来进行切割，然后比较切割处理的字符串的大小。
参考代码(C++版本)
抽象一点了，确实是这么一回事，但是倘若问具体一点，
① 怎么将每个小数点前面的字符串截取出来了；
② 怎么比较这个段字符串的大小了
③ 前导0怎么处理呢
上面的这个三个提问，其实都可以通过这一段代码来解释了
想要找到小数点确实是常规的遍历，这里就通过两个指针，指针i和指针j去扫描题目提供的字符串，在扫描的途中，对扫描到的数字字符串进行数字化。
比如字符串2301，
num1 = 0 * 10 + ('2' - '0') = 2
num1 = 2 * 10 + ('3' - '0') = 23
num1 = 23 * 10 + ('0' - '0') = 230
num1 = 230 * 10 + ('1' - '0') = 2301
其实字母a - z A ~ Z的数字化也是类似的玩法。
至于剩下的按照题目要求，返回对应的数字就不用我再赘述了吧~
这个题也让我想起了把一个日期处理成回文日期
class Solution {
public:
int compareVersion(string version1, string version2) {
int i =0,j = 0;
typedef long long LL;
//这个题是两个指针在两个区间跑
int n1 = version1.size();
int n2 = version2.size();
while(i < n1 || j < n2 )
{
LL num1 = 0,num2 = 0;
//去查找小数点，然后进行分割
//这里将数字字符串转换为数字的方法可以积累一下
while(i < n1 && version1[i] != '.') num1 = num1 * 10 + (version1[i++]-'0');
while(j < n2 && version2[j] != '.') num2 = num2 * 10 + (version2[j++]-'0');
//按照题目逻辑进行比较
if(num1 > num2) return 1;
else if(num1 < num2) return -1;
i++,j++;//跳过小数点
}
//遍历完两个字符串之后都没有比较处理，就是说明相等，返回0
return 0;
}
};
第四题 443. 压缩字符串记录to_string()
题目描述解题报告
原题传送门用快慢指针常规的去遍历就好，
参考代码(C++版本)
慢的指针确定当前要扫描的连续字符的首字符
快的指针指在计数的同时，要着手指向下一个连续字符的首字符
class Solution {
public:
int compress(vector& chars) {
int n = chars.size();
//标准快慢指针
int slow = 0,quick = 0,cnt = 0;
while(quick < n)
{
//通过下述循环
//将慢指针slow指向当连续字符的首字符
//快指针quick指向下一个连续字符的首字符
while(quick < n && chars[quick] == chars[slow]) quick++;
//统计连续出现的字符的首字符
chars[cnt++] = chars[slow];
if(quick - slow > 1)
{
// char temp[100] = {0};
// // temp = to_string(quick-slow);
// sprintf(temp,"%d",quick-slow);
// for(int i = 0; i < strlen(temp);i++)
// chars[cnt++] = temp[i];
//这块有问题吧，to_string的返回值是string
//先用的auto,改string 就报错了
for(char ch : to_string(quick-slow))
chars[cnt++] = ch;
}
//移动慢的指针
slow = quick;
}
return cnt;
}
};
想记录一点字符数组和字符串的东西
关于数字转换成字符串也可以用这个
总结把双指针落实到对暴力的优化上吧，本身主要也是一个迭代的思想吧。
浅放一张y总的总结。
