目录
1.Z 字形变换
方法1: 模拟
代码
提交结果
方法2:优化后的模拟
代码
提交结果
2.外观数列
方法1:模拟
代码
提交结果
方法2:打表
知识回顾
代码
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个外观数列并存储到文件中
知识回顾
74.【C语言】文件操作(1)
75.【C语言】文件操作(2)
77.【C语言】文件操作(3)
79.【C语言】文件操作(4)
88.【C语言】文件操作(5)
89.【C语言】文件操作(6)
代码
结果存储在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]即可
提交结果:
