未分類

ZigZag Conversion

Go, LeetCode, String

ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

Exmaple:

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

1
string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

提示 解題應用
String 觀查規律

Default:

1
2
func convert(s string, numRows int) string {
}

解答思路:

numRows = 3
最初的想法是拆成三大塊分上、中、下，第一列PAHN就是利用 nRows+1(4) 為index的倍數放到array開頭，接著到第三列YIR同上 nRows-1(2) 的倍數放到array尾端，中間就只要將上述剩餘的依序放入，因為就算經過convert，如果仔細觀查橫的輸出好比YIR，這三個字元在原本的PAYPALISHIRING字串出現的順序不變，所以不用擔心，至於這三大塊該如何塞入同一array的位置，從上塊來說只要符合倍數就原本 array[index/(numRows+1)] 放入，而下塊也是符合倍數就 array[len(s)-len(s)/(numRows+1)] 中間的只要知道上塊的index到哪從後頭接著放入就對了。

顯然我完全搞錯了ZigZag的重點… 所以最初想法不看也沒差。

這裡給的範例實在太少，很可能會因為沒接觸過導致不清楚什麼是ZigZag而寫的方向錯誤，所以再附上一些結果來讓人了解。

Example:

1
2
3
4
5
numRows = 4
P       I       N
A    L  S    I  G
Y  A    H  R
P       I
1
2
3
4
5
6
numRows = 5
P         H
A      S  I
Y    I    R
P  L      I  G
A         N

花點時間應該可以看出有特殊規律，不過看討論這類的題目在面試上沒什麼太大意義，所以通常不會出現的樣子。從最初的想到的來看我也許能夠拆成上、中、下塊，只是這次的中塊大了點，不過似乎有更好的做法，拆成直線↓一組與斜線↗一組，以 numRows=4 來說，PIN ASG YH PI為直線↓，LI AR為斜線↗

(直線規律)第一排的PIN為例，P與I的indx變化(經過點)可以發現:

原點 直線↓剩餘數 斜線↗數 直線↓剩餘數
P AYP AL I
index numRows - (index + 1)%(numRows + (numRows - 2)) numRows - 2 (index + 1)%(numRows + (numRows - 2))

合併之後下一點的index

index = index + numRows - (index + 1)%(numRows + (numRows - 2)) + numRows - 2 + (index + 1)%(numRows + (numRows - 2)) = index + 2*(numRows - 1)

另外也可以發現到只有 numRows=2 時，沒有任何的斜點，因為斜線數 (numRows-2=0) 。

1
2
3
numRows = 2
P  Y  A  I  H  R  N
A  P  L  S  I  I  G

至於 numRows=1 根本跟問題給的字串一樣，所以在最一開始就要篩掉。

1
2
numRows = 1
P  A  Y  P  A  L  I  S  H  I  R  I  N  G

(斜線規律)看來沒辦法像直線一樣直接得到絕對位置簡單，只好從直線的相對位置找起(numRows=4為例):

在上一個直線規律中我們從 P→I 找關係，而這次我們則要找直線與斜線的相對關係，所以就找 A→L ，不過後來反而發現 A→S→L ，是有脈絡可尋的，而且 S→L 之間的關係與該兩點所在的行數(第幾橫排)有密切關係。

row為該兩點所在的行數

原點 中點 斜點
A S L
index 2*(numRows - 1) -2(row - 1)

其中原點到中間我們可以由先前直線規律求得，合併之後斜點的index:

index = index + 2*(numRows - 1) - 2(row - 1)

程式碼解說:

在go中，從字串提出的字元型別都是rune，你可以想成是直接轉成ascii，最大的好處在於最後將這些rune陣列轉成string回傳時，你不需要一個個去join到空字串裡頭，而是將整個rune陣列直接轉成string，非常的方便且快速。

1
result := make([]rune, slen)

這邊我用index的0~numRows來取出每一橫排的第一個值，而next就是套前述所提的直線與斜線規律所整理出的結論，因為我是從0開始算橫排，所以就不需 (row-1) ，透過觀察例子我們可以發現斜點不會與第一橫排 (index=0) 和最後一排 (index=numRows) 同一排，在找斜點的相對位置時也有可能是中點不存在而斜點存在，這些都要在最後的判斷式過慮。

1
2
3
4
5
6
7
8
9
10
11
12
for i := 0; i < numRows; i++ {
	next = i
	for next < slen {
		result[j] = rune(s[next])
		j++
		next = next + 2*(numRows-1)
		if i > 0 && i < numRows-1 && next-2*i < slen {
			result[j] = rune(s[next-2*i])
			j++
		}
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	slen := len(s)
	result := make([]rune, slen)
	next := 0
	j := 0
	for i := 0; i < numRows; i++ {
		next = i
		for next < slen {
			result[j] = rune(s[next])
			j++
			next = next + 2*(numRows-1)
			if i > 0 && i < numRows-1 && next-2*i < slen {
				result[j] = rune(s[next-2*i])
				j++
			}
		}
	}
	return string(result)
}

總結:

ZigZag就是將一字串做鋸齒狀排列來讓你找出規律。

(直線規律)絕對位置 index = index + 2(numRows - 1)

(斜線規律)相對位置 index = index + 2(numRows - 1) - 2(row - 1)

分享到