目录
1.Z 字形变换
https://leetcode.cn/problems/zigzag-conversion/
将一个给定字符串
s根据给定的行数numRows，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为
"PAYPALISHIRING"行数为3时，排列如下：P A H N A P L S I I G Y I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：
"PAHNAPLSIIGYIR"。请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);示例 1：
输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"示例 2：
输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释： P I N A L S I G Y A H R P I示例 3：
输入：s = "A", numRows = 1 输出："A"提示：
1 <= s.length <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
方法1: 模拟
Z 字形图示(其实看起来是N字形)
由于s.length和numRows的取值范围比较窄,因此可以创建一个1000*1000的char数组(不放心可以设大一些)
将连在一起的Z字形拆分成形状相同的部分
可以算出每一部分列数part_size_col为part_size-numRows+1,行数为numRows
可以算出每一部分字符的个数都是2 * numRows - 2个
对于每一个部分,填字符分两步:1.竖着填 2.斜着填
最后打印vector<string>时要算清右多少行
先算算有多少个完整的部分:s.size()/part_size,它们一共占(s.size()/part_size)*part_size_col行,剩下来残缺的部分不超过part_size_col行,因此可以按(s.size()/part_size)*part_size_col+part_size_col来控制行所以
代码
注:numRows == 1要特殊处理
class Solution {
public:
string convert(string s, int numRows)
{
if (numRows==1)
{
return s;
}
char arr[1010][1010];
string ret;
memset(arr, '\0', sizeof(arr));
int row = 0;
int col = 0;
int part_size = 2 * numRows - 2;
int part_size_col=part_size-numRows+1;
int total_col=(s.size()/part_size)*part_size_col+part_size_col;
for (int i = 0; i < s.size(); i++)
{
if (i % part_size >= 0 && i % part_size <= numRows - 1)
{
//竖着填
arr[row][col] = s[i];
row++;
}
else
{
//斜着填
arr[row][col] = s[i];
row--;
col++;
}
if (i % part_size == numRows - 1)
{
col++;
row = numRows - 2;
}
}
for (int i = 0; i < numRows; i++)
{
for (int j = 0; j <total_col; j++)
{
if (arr[i][j] != '\0')
ret.push_back(arr[i][j]);
}
}
return ret;
}
};提交结果
方法2:优化后的模拟
可使用模拟算法解的绝大部分题的优化方法是找规律
由特殊到一般,以s = "PAYPALISHIRING", numRows = 4为例,将字符在字符串中对应的下标填写到二维数组中
| 0 | 6 | 12 | ||||||
| 1 | 5 | 7 | 11 | 13 | ||||
| 2 | 4 | 8 | 10 | |||||
| 3 | 9 |
分行看规律:
第0行:0,6,12
第n-1行:3,9
会发现第0行和第n-1行的相邻元素都差6,而6是2 * numRows - 2的值(可自行多找一个样例验证)
第1行~第n-2行:
两两一组看:
第1行: 1,5, 7,11, 13
第2行:2,4, 8,10
可得出如下规律:第k行: k,d-k, k+d,2d-k, k+2d,3d-k,......,k+nd,(n+1)d-k,其中(n+1)d-k<s.size()
代码
注:numRows == 1要特殊处理
class Solution {
public:
string convert(string s, int numRows)
{
if (numRows == 1)
return s;
string ret;
int d = 2 * numRows - 2;
//第0行
int firstrow_i = 0;
while (firstrow_i < s.size())
{
ret.push_back(s[firstrow_i]);
firstrow_i += d;
}
//第1~(numRows-2)行
for (int row = 1; row < numRows-1; row++)
{
int i = row;
while (i < s.size())
{
ret.push_back(s[i]);
if (i + d - 2 * row < s.size())
ret.push_back(s[i + d - 2 * row]);
i += d;
}
}
//第numRows-1行
int lastrow_i = numRows - 1;
while (lastrow_i < s.size())
{
ret.push_back(s[lastrow_i]);
lastrow_i += d;
}
return ret;
}
};提交结果
2.外观数列
https://leetcode.cn/problems/count-and-say/
「外观数列」是一个数位字符串序列，由递归公式定义：
countAndSay(1) = "1"countAndSay(n)是countAndSay(n-1)的行程长度编码。
行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串
"3322251"，我们将"33"用"23"替换，将"222"用"32"替换，将"5"用"15"替换并将"1"用"11"替换。因此压缩后字符串变为"23321511"。给定一个整数
n，返回 外观数列 的第n个元素。示例 1：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"
示例 2：
输入：n = 1
输出："1"
解释：
这是基本情况。
提示：
1 <= n <= 30进阶：你能迭代解决该问题吗？
方法1:模拟
countAndSay(1) = "1",countAndSay(2)应该表示"1",即1个1,所以countAndSay(2)="11"
countAndSay(3)应该表示"11",即2个1,所以countAndSay(3)="21"
countAndSay(4)应该表示"21",即1个2,1个1,所以countAndSay(4)="1211"
countAndSay(5)应该表示"1211",即1个1,1个2,2个1,所以countAndSay(4)="111221"
循环即可,
代码
class Solution {
public:
string countAndSay(int n)//非递归,使用vector<string>存储从1~n的外观数列
{
vector<string> arr;
arr.push_back("");
arr.push_back("1");
for (int i = 2; i <= n; i++)
{
string tmp;
int num = 0;
char ch = arr[i - 1][0];
for (int j = 0; j < arr[i - 1].size(); j++)
{
if (arr[i - 1][j] == ch)
num++;
else
{
tmp = tmp + to_string(num);
tmp.push_back(ch);
ch = arr[i - 1][j];
num = 1;
}
}
if (num)
{
tmp = tmp + to_string(num);
tmp.push_back(ch);
}
arr.push_back(tmp);
}
return arr[n];
}
};提交结果
或者不使用vector<string>,只保留第n个外观数列
class Solution {
public:
string countAndSay(int n)//非递归,只保留第n个外观数列
{
string s="1";
for (int i = 2; i <= n; i++)
{
string tmp;
int num = 0;
char ch = s[0];
for (int j = 0; j < s.size(); j++)
{
if (s[j] == ch)
num++;
else
{
tmp = tmp + to_string(num);
tmp.push_back(ch);
ch = s[j];
num = 1;
}
}
if (num)
{
tmp = tmp + to_string(num);
tmp.push_back(ch);
}
s=tmp;
}
return s;
}
};
提交结果:
或者使用双指针:
以"111221"为例:
left和right之间1的个数为right-left
class Solution {
public:
string countAndSay(int n)//双指针
{
string s = "1";
for (int i = 2; i <= n; i++)
{
string tmp;
int left = 0;
int right = 0;
while (1)
{
if (s[left] == s[right])
{
right++;
if (right == s.size())
{
tmp = tmp + to_string(right - left);
tmp.push_back(s[left]);
break;
}
}
else
{
tmp = tmp + to_string(right - left);
tmp.push_back(s[left]);
left = right;
}
}
s = tmp;
}
return s;
}
};提交结果:
方法2:打表
1≤n≤30,由于n较小,因此可以批量生成前30个外观数列并存储到文件中
知识回顾
代码
结果存储在result.txt中
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()//打表
{
vector<string> arr;
arr.push_back("");//占位,可以任意写,n>0,不会访问到table[0]
arr.push_back("1");
//使用方法1的代码
for (int i = 2; i <= 30; i++)
{
string tmp;
int num = 0;
char ch = arr[i - 1][0];
for (int j = 0; j < arr[i - 1].size(); j++)
{
if (arr[i - 1][j] == ch)
num++;
else
{
tmp = tmp + to_string(num);
tmp.push_back(ch);
ch = arr[i - 1][j];
num = 1;
}
}
if (num)
{
tmp = tmp + to_string(num);
tmp.push_back(ch);
}
arr.push_back(tmp);
}
//将arr字符串写入文件中
FILE* fptr = fopen("result.txt", "w");
char str1[] = "vector<string> table={";
fprintf(fptr, "%s", str1);
for (auto s : arr)
{
fprintf(fptr, "\"%s\",\n",s.c_str());
}
fseek(fptr, -1, SEEK_CUR);//回退一个字节
fprintf(fptr, "};");//覆盖结尾的逗号
fclose(fptr);
}生成结果:
之后粘贴到leetcode上:
最后返回table[n]即可
提交结果:
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
