文章目錄
- 一、題目
- 二、解題思路
- 1、特殊情況
- 2.進行周期分析:
- 3、同行相鄰點的位置分析
- 4、注意事項
- 5、代碼實作
- 6、模擬法代碼
一、題目
將一個給定字串 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 <= 1000
s 由英文字母（小寫和大寫）、’,’ 和 ‘.’ 組成
1 <= numRows <= 1000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zigzag-conversion
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
1、特殊情況
當一行時目標字串即為其本身，所以我們著重討論2行及以上的情況
2.進行周期分析:
1)兩行時:周期為2，
注:下圖藍色圈中的部分即為一個周期，
2）三行時:周期為4，
注:下圖藍色圈中的部分為一個周期，
3)四行時:周期為6，
注:下圖藍色圈中的部分為一個周期，
4）以此類推，我們發現n行時周期T=2(n-1)(n≠1)
3、同行相鄰點的位置分析
1）兩行時,我們發現點1間距下一個點1的距離是2，點2亦是，
我們發現，點1和下一個點1，點2和下一個點2的距離就是T，
2)三行時,我們發現點1距離下一個點的距離是4，點3亦然，
然而點2的距離是2.
我們發現:點1與最近的點1之間的間距是T，點3與最近的點3之間的間距也是T，點2與最近的點2之間的間距是2、2、2、2、2、2、2-------我們把連續的三個點二看成一個整體，用ABC表示，我們發現AC之間的距離始終為4，即為一個周期T
3)4行時，T=(4-1)*2=6，由圖我們發現點1與最近的點1之間的間距始終為6；點4與相鄰的點4之間的間距也為6；兩個相鄰2之間的間距是4、2、4、2、4、2·····；兩個相鄰3之間的間距是2、4、2、4、2、4···
由此可知:相鄰點1之間的間距和相鄰點4之間的間距都為T，我們可以把連續的3個點2或者點4看成一個整體ABC，AC之間的距離總為T
4）n行時(n≠1)
我們可以總結出以下規律:
一列中最邊緣的兩個點，相鄰兩同行點的間距總為T，然而對于m(m≠1&&m≠n)行，其從第一個m點開始，設d=T-(m-1)*2,d1=(m-1)*2-它們與相鄰點的距離應該是d、d1、d、d1、d、d1······
4、注意事項
1.在使用一個變數前一定要先把該變數進行相應的更新
2.String類每次賦值都會開辟一個新的空間，不僅浪費
空間還會浪費時間，所以對于需要多次修改字串，用
StringBuilder會更好 (StringBuffer為執行緒安全的，在多
執行緒的情況下使用，效率比String高，比StringBuilder低)
3、做演算法題時往往并不需要找到嚴格的數學證明，可以
通過找規律的方法去找到相應的數學運算式，但是這時需
要進行數量足夠多的測驗來證明自己的邏輯正確性，
5、代碼實作
class Solution {
public String convert(String s, int numRows) {
StringBuilder s1=new StringBuilder();
if(numRows==1)return s;//特殊情況的處理
int m=(numRows-1)*2;//每個周期的數
int n=m;//同行相鄰兩點的間隔距離
int i=0;//用來尋找每個周期第一個數
int mark=0;//用來判斷是否是每個周期的第一個數
int location=0;//每次回圈的位置
while(s1.length()<s.length()) {
location+=n*mark;//每次都要進行位置的更新
mark=1;//用來判斷是否為周期的第一個數
if(location>=s.length()) {
i++;//周期第一個數的改變
n=m-i*2>0?i*2:m;
location=i;mark=0;continue;
}
s1.append(s.charAt(location));
n=m-n>0?m-n:n;
}
return s1.toString();
}
}
上述代碼的時間復雜度和空間復雜度都是O(n);
執行結果:
6、模擬法代碼
class Solution {
public String convert(String s, int numRows) {
if(numRows==1)return s;
int n=Math.min(numRows, s.length());//避免造成空間資源的浪費
StringBuilder s1=new StringBuilder();
List<StringBuilder> list=new ArrayList<StringBuilder>();
boolean godown=true;
for(int i=0;i<n;i++) {
list.add(new StringBuilder());
}
int k=0;
for (char c:s.toCharArray()) {
list.get(k).append(c);
if(k==0||k==numRows-1)godown=!godown;
k=godown?--k:++k;
}
for(StringBuilder s2:list) {
s1.append(s2);
}
return s1.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263407.html
標籤：其他
上一篇：無法提交？FormData()未定義？原因在這里！！
下一篇：Redis 組態檔重要屬性介紹