目錄
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]即可
提交結果:
