try-leetcode/algorithms/golang/6.zig-zag-conversion.go at master · devfan2021/try-leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import (
	"strings"
)

/*
 * @lc app=leetcode id=6 lang=golang
 *
 * [6] ZigZag Conversion
 *
 * https://leetcode.com/problems/zigzag-conversion/description/
 *
 * algorithms
 * Medium (35.79%)
 * Likes:    1749
 * Dislikes: 4733
 * Total Accepted:    472.7K
 * Total Submissions: 1.3M
 * Testcase Example:  '"PAYPALISHIRING"\n3'
 *
 * 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)
 *
 *
 * 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:
 *
 *
 * string convert(string s, int numRows);
 *
 * Example 1:
 *
 *
 * Input: s = "PAYPALISHIRING", numRows = 3
 * Output: "PAHNAPLSIIGYIR"
 *
 *
 * Example 2:
 *
 *
 * Input: s = "PAYPALISHIRING", numRows = 4
 * Output: "PINALSIGYAHRPI"
 * Explanation:
 *
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 *
 */

// @lc code=start
func convert(s string, numRows int) string {
	return convert1(s, numRows)
}

// line 0: indexK = 2 * numRows -2
// numRows -1, indexK = k(2*numRows-2) + numRows -1
// line i: k, 2 * numRows -2 + i  or  (k+1)(2*numRows-2)
/*n=numRows
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4
*/
func convert2(s string, numRows int) string {
	if len(s) <= numRows || numRows == 1 {
		return s
	}
	period := 2*numRows - 2
	res := make([]string, numRows)

	for i, v := range s {
		mod := i % period
		// fmt.Printf("i: %d, mod: %d, period: %d\n",i, mod, period)
		if mod < numRows {
			res[mod] += string(v)
		} else {
			res[period-mod] += string(v)
		}
	}
	return strings.Join(res, "")
}

func convert1(s string, numRows int) string {
	if len(s) == 0 || numRows == 0 || numRows == 1 {
		return s
	}

	rows := min(len(s), numRows)
	retVals := make([]string, rows)

	curRow, goingDown := 0, false
	for i := range s {
		retVals[curRow] += string(s[i : i+1])
		if curRow == 0 || curRow == rows-1 {
			goingDown = !goingDown
		}

		if goingDown {
			curRow++
		} else {
			curRow--
		}
	}

	vals := ""
	for _, val := range retVals {
		vals += val
	}
	return vals

	// return strings.Join(retVals, "")
}

func min(val1, val2 int) int {
	if val1 < val2 {
		return val1
	}
	return val2
}

// @lc code=end