點(diǎn)擊 這里 可以查看更多算法面試相關(guān)內(nèi)容~
題目描述
將一個(gè)給定字符串 s 根據(jù)給定的行數(shù) numRows 簿废，以從上往下、從左到右進(jìn)行 Z 字形排列。
比如輸入字符串為 "PAYPALISHIRING" 行數(shù)為 3 時(shí)，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的輸出需要從左往右逐行讀取层释，產(chǎn)生出一個(gè)新的字符串，比如："PAHNAPLSIIGYIR"。
請(qǐng)你實(shí)現(xiàn)這個(gè)將字符串進(jìn)行指定行數(shù)變換的函數(shù)：
string convert(string s, int numRows);
示例 1：
輸入：s = "PAYPALISHIRING", numRows = 3 輸出："PAHNAPLSIIGYIR"
示例 2：
輸入：s = "PAYPALISHIRING", numRows = 輸出："PINALSIGYAHRPI"
解釋：
P I N
A L S I G
Y A H R
P I
示例 3：
輸入：s = "A", numRows = 1 輸出："A"
提示：
1 <= s.length <= 1000-
s由英文字母（小寫(xiě)和大寫(xiě)）甩恼、','和'.'組成 1 <= numRows <= 1000
直觀規(guī)律解法
本題可以當(dāng)成模擬題來(lái)做。
對(duì)需要打印的行 i 進(jìn)行遍歷沉颂，每一行的第一個(gè)字符可以直接確定：原字符開(kāi)頭的第 i 個(gè)字符条摸。
然后計(jì)算出每行下一個(gè)字符的偏移量，這里需要分情況討論：
對(duì)于第一行和最后一行：偏移量固定铸屉，不隨著
Z的方向改變對(duì)于其他行：偏移量隨著
Z的方向發(fā)生變化
class Solution {
public String convert(String s, int r) {
int n = s.length();
if (n == 1 || r == 1) return s;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < r; i++) {
if (i == 0 || i == r - 1) {
int j = i;
int rowOffset = (r - 1) * 2 - 1;
while (j < n) {
sb.append(s.charAt(j));
j += rowOffset + 1;
}
} else {
int j = i;
int topRow = i;
int topOffset = topRow * 2 - 1;
int bottomRow = r - i - 1;
int bottomOffset = bottomRow * 2 - 1;
boolean flag = true;
while (j < n) {
sb.append(s.charAt(j));
j += flag ? bottomOffset + 1 : topOffset + 1;
flag = !flag;
}
}
}
return sb.toString();
}
}
時(shí)間復(fù)雜度：分別對(duì) s 中的每個(gè)字符進(jìn)行打印钉蒲。復(fù)雜度為
空間復(fù)雜度：
數(shù)學(xué)規(guī)律解法
在平時(shí)的練習(xí)中，對(duì)于這種找規(guī)律的題彻坛，當(dāng)我們使用直觀的思路推理出一個(gè)解法之后顷啼，可以嘗試從數(shù)學(xué)的角度上去分析。
例如本題昌屉，我們可以不失一般性的將規(guī)律推導(dǎo)為「首項(xiàng)」和「公差公式」钙蒙。
這通常能夠有效減少一些判斷。
分情況討論：
對(duì)于第一行和最后一行：公差為
2 * (n ? 1)的等差數(shù)列间驮，首項(xiàng)是i對(duì)于其他行：兩個(gè)公差為
2 * (n ? 1)的等差數(shù)列交替排列躬厌，首項(xiàng)分別是i和2 * n ? i ? 2
class Solution {
public String convert(String s, int r) {
int n = s.length();
if (n == 1 || r == 1) return s;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < r; i++) {
if (i == 0 || i == r - 1) {
int pos = i;
int offset = 2 * (r - 1);
while (pos < n) {
sb.append(s.charAt(pos));
pos += offset;
}
} else {
int pos1 = i, pos2 = 2 * r - i - 2;
int offset = 2 * (r - 1);
while (pos1 < n || pos2 < n) {
if (pos1 < n) {
sb.append(s.charAt(pos1));
pos1 += offset;
}
if (pos2 < n) {
sb.append(s.charAt(pos2));
pos2 += offset;
}
}
}
}
return sb.toString();
}
}
時(shí)間復(fù)雜度：分別對(duì) s 中的每個(gè)字符進(jìn)行打印。復(fù)雜度為
空間復(fù)雜度：
總結(jié)
這種”找規(guī)律“的模擬題竞帽，和小學(xué)奧數(shù)題十分類似烤咧。要提高自己的做題水平偏陪，需要堅(jiān)持兩個(gè)方向：
自己多在紙上畫(huà)圖找規(guī)律，這種題沒(méi)有什么通用解法
多做題煮嫌，盡量對(duì)每種”規(guī)律“都有所接觸
最后
這是我們「刷穿 LeetCode」系列文章的第 No.6 篇笛谦，系列開(kāi)始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目昌阿，部分是有鎖題饥脑，我們將先將所有不帶鎖的題目刷完。
在這個(gè)系列文章里面懦冰，除了講解解題思路以外灶轰，還會(huì)盡可能給出最為簡(jiǎn)潔的代碼。如果涉及通解還會(huì)相應(yīng)的代碼模板刷钢。
由于 LeetCode 的題目隨著周賽 & 雙周賽不斷增加笋颤，為了方便我們統(tǒng)計(jì)進(jìn)度，我們將按照系列起始時(shí)的總題數(shù)作為分母内地，完成的題目作為分子伴澄，進(jìn)行進(jìn)度計(jì)算。當(dāng)前進(jìn)度為 6/1916 阱缓。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼非凌，我建立了相關(guān)的倉(cāng)庫(kù)：Github 地址 & Gitee 地址。
在倉(cāng)庫(kù)地址里荆针，你可以看到系列文章的題解鏈接敞嗡、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和一些其他的優(yōu)選題解航背。
