[算法周训 3] 字符串训练2
本周的算法周训大多属于杂项级别，但大多属于字符串系列，故依旧放在字符串中了。由于我本周事情较多，该博客也是一拖再拖，本来周末需要写的，但是拖到了现在。（写博客的时候自己重新打了一遍代码，使自己又熟悉一遍）
在此过程了，我也发现部分C++的特性没有使用到位，大多都是C with STL,说起来还是蛮惭愧的，所以我也在部分知识点回顾中写了一些我遇到的问题。接下来我也会有意识地去接触新的C++ 特性。不过倒是发现，C++特性倒是有点python的味道了。
希望对你有所帮助！
目录
- 部分知识点回顾
- 重塑矩阵
- 最长和谐子序列
- 验证回文串
- 旋转图像
- 二进制求和
- 汇总区间
部分知识点回顾
构造二维数组（vector）,规定行数r,列数为c
vector<vector<int>> ans (r,vector<int>(c));
遍历map:
我之前的做法就是使用迭代器，
map<int,int> a;
map<int,int> ::iterator it = a.begin();
for(;it!=a.end();++it){
keyname = it->first;
value = it->second;
}
这个C++特性我倒是蛮喜欢的，又方便又简洁。
map<int,int> a;
for(auto &[num,count] : a) {
a.count(key_name);
cur_key_name = a[num]
}
c++ 遍历与字符类函数：
这种遍历倒是有点Python的味道了！
for (char ch: s) {
if (isalnum(ch)) {
sgood += tolower(ch);
}
}
重塑矩阵
分析题目，比较简单，就是单纯地遍历。不过需要考虑是否能满足行列乘积为总数目的要求。
在这里我先用一个数组全部读进去，然后就是简单的遍历，总体上难度简单。
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
vector<vector<int> > a;
vector<int> tmp;
int row = mat.size();
int col = mat[0].size();
if( row * col != r*c) {
return mat;
}
vector<int> cx;
for(int i=0;i<mat.size();i++) {
for(int j=0;j<mat[0].size();j++) {
cx.push_back(mat[i][j]);
}
}
int be = 0;
for(int i=0;i<r;i++) {
tmp.clear();
for(int j=0;j<c;j++) {
tmp.push_back(cx[be]);
be ++;
}
a.push_back(tmp);
}
return a;
}
};
当然了，这个题目可以不这么做，上面的做法是偏向常规解题的。我们注意到一个行数为m，列数为n，行列下标都从0开始编号，那么（i,j）对于一维位置就是i*n + j。（类似就是把二维数组用数字把一维表达了出来）。所以我们就有了一维数组的坐标，假定是x.那么也可以根据一维数组来反求二维数组中去，其对应的（i,j）为 i = x/n ，j = x%n.
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int m = nums.size();
int n = nums[0].size();
if (m * n != r * c) {
return nums;
}
vector<vector<int>> ans (r,vector<int>(c));
for(int x = 0;x< m*n ; ++x) {
ans[x/c][x%c] = nums[x/n][x%n];
}
return ans;
}
最长和谐子序列
这个题目寻找最大值和最小值为1，这里就有多种办法（例如使用sort）注意到子序列的定义，我一开始以为是不能改变数组，这导致我就没有使用sort而陷入了僵局。因为sort将会改变数组的元素顺序。
但是我们注意到，结果只要输出数组length就可以了，这意味着我们可以不用求出元素本来的顺序，只要知道length就可以了，问题就变得很显然了。
那么我这里使用map来进行保存数组，（比较map也封装好了排序）
class Solution {
public:
int findLHS(vector<int>& nums) {
map<int,int> a;
for(auto & e : nums) {
a[e]++;
}
int res = 0;
for(auto &[num,count] : a) {
if(a.count(num+1)) {
res = max(res,a[num+1]+count);
}
}
return res;
}
};
当然了，常规方法就是sort了。不过需要使用滑动窗口来进行求解：
int findLHS(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
int ans =0,left =0,right = 0;
while(right < n ) {
while(left < right &&nums[right]-nums[left] >1){
left ++;
}
if(nums[right] - nums[left] == 1) {
ans = max(ans,right-left +1);
}
right++;
}
return ans;
}
验证回文串
题目我倒是没看清，简单来说就是字母留下数字留下，然后判断是否是回文串了。
前期工作，我的思路就是把字母改成小写，然后把数字留下，比较简单：
class Solution {
public:
bool isPalindrome(string s) {
string str = "";
int len = s.size();
string m ="";
for(int i=0;i<len;i++ ) {
if(s[i] >= 'a' && s[i] <='z' || s[i] >='0' && s[i] <='9' ) {
str += s[i];
}
if( s[i] >='A' && s[i] <= 'Z') {
str += s[i] - 'A' + 'a';
}
if(s[len-1-i] >= 'a' && s[len-1-i] <= 'z' || s[len-1-i] >= '0' && s[len-1-i] <= '9') {
m += s[len-1-i];
}
if(s[len-1-i] >='A' && s[len-1-i] <='Z') {
m += s[len-1-i] -'A' +'a';
}
}
return m == str;
}
};
方法一就是简单的思路，但同时可以使用库函数：
for (char ch: s) {
if (isalnum(ch)) {
sgood += tolower(ch);
}
}
当然了，也可以使用双指针，主要就是判断。主体思想就像折半查找
while (left < right) {
if (sgood[left] != sgood[right]) {
return false;
}
++left;
--right;
}
旋转图像
这题目我一开始比较没看出来。后来我找到了规律，规律如下：
以样例输入输出为例。查找输入最后一组数组，7,8,9对应的输出的第一列。后面倒数第二组4,5,6也是同样的，就是第二列。以此类推，发现规律这题非常简单，由于使用c++ vector较为繁琐，故这题使用Java还是比较简单的.
一开始我认为java数组和c++ vector一样，使用了matrix = tmp来进行了拷贝，发现不行，所以还是采用了for语句来进行循环遍历了。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int [][] tmp = new int[n][n];
int cnt =0;
int row = 0;
for(int i=n-1;i>=0;i--) {
row = 0;
for(int j=0;j<n;j++) {
tmp[row][cnt] = matrix[i][j];
row++;
}
cnt++;
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
matrix[i][j] = tmp[i][j];
}
}
}
}
c++ 写法，主要就是交换。主要思想和我前面找规律还是有共通之处的。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
auto a = matrix;
for(int i=0;i<matrix.size();i++) {
for(int j=0;j<matrix[0].size();j++) {
a[j][matrix.size()-i-1] = matrix[i][j];
}
}
matrix = a;
}
};
当然了，这个还有最直接的办法，就是先转置后镜像对称。
二进制求和
别的不说，大数求和模板题目，必须要背住格式！
class Solution {
public:
string addBinary(string a, string b) {
string str = "";
int cur =0,i = a.size()-1,j = b.size()-1;
while( i >= 0 || j >= 0 || cur != 0) {
if(i >= 0) cur += a[i--]-'0';
if(j >= 0) cur += b[j--] - '0';
str += to_string(cur % 2);
cur /= 2;
}
reverse(str.begin(),str.end());
return str;
}
};
汇总区间
先说一下我自己的思路，我也是一次遍历，不过看num[i]需要判断后继一个是否是相差1的数，否则就继续下去，不过代码能运行一半，后面错误有些多，故没有完成100%，这里将我的思路代码贴出来。
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<int > a;
vector<string> ve;
int flag = 0;
for(int i=0;i<nums.size()-1;i++) {
if(nums[i] == nums[i+1] - 1) {
a.push_back(nums[i]);
}else {
if( (nums[i] == nums[i-1] +1 ) && i >=1) a.push_back(nums[i]);
string str = "" ;
int be = a[0];
int end = a[a.size()-1];
if(be == end) {
str += be;
ve.push_back(str);
}else {
str += to_string(be);
str += "->";
str += to_string(end);
ve.push_back(str);
}
a.clear();
}
}
string s = ve[ve.size()-1];
int ns = int(s[s.size()-1]);
if( ns == nums[nums.size()-1] - 1) {
ve.pop_back();
s[s.size()-1] = nums[nums.size()-1] - '0';
ve.push_back(s);
}else {
string m = "";
m += to_string(nums[nums.size()-1]);
ve.push_back(m);
}
return ve;
}
};
当然了这个题本质使用双指针来进行操作。
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> ret;
int i = 0;
int n = nums.size();
while (i < n) {
int low = i;
i++;
while (i < n && nums[i] == nums[i - 1] + 1) {
i++;
}
int high = i - 1;
string temp = to_string(nums[low]);
if (low < high) {
temp.append("->");
temp.append(to_string(nums[high]));
}
ret.push_back(move(temp));
}
return ret;
}
};