尝试解决算法问题的曲折模式

Question

问题如下：字符串“PAYPALISHIRING”在给定数量的行上以锯齿形图案写入，如下所示：（您可能希望以固定字体显示此图案以提高可读性）P   A   H   NA P L S I I GY   I   R然后逐行阅读：“PAHNAPLSIIGYIR”编写将采用字符串并在给定行数的情况下进行此转换的代码：字符串转换（字符串 s，int numRows）；示例 1：输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR" 示例 2：输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释：P     I    NA   L S  I GY A   H RP     I我已经编写了以下代码，但是在如何将行标记为一次向下移动方面我陷入了困境，我增加了起始行，但是当它曲折回到顶部时，它应该减少。我无法弄清楚在不影响向下运动的情况下进行这项工作的逻辑。任何帮助，将不胜感激。const convert = (s, numRows) => {    let startRow = 0    let endRow = numRows - 1    let startColumn = 0    let endColumn = Math.floor((s.length / 2) - 1)    s = s.split('')    let results = []    // to setup the columns    for (let i = 0; i < numRows; i++) {        results.push([])    }    while (startRow <= endRow && startColumn <= endColumn && s.length) {        for (let i = startRow; i <= endRow; i++) {            results[i][startColumn] = s.shift()        }        for (let i = endRow - 1; i >= startRow; i--) {            results[i][startColumn + 1] = s.shift()            startColumn++        }        //this line seems to be the issue        startRow++    }    return results}console.log(convert('PAYPALISHIRING', 4))

Answer 1

我重写了您的 while 循环，如下所示，我只是走“之字形”模式！希望它足够简单易懂。

let c=0, row=0,col=0, down=0;

while(c<s.length) {

    results[row][col]=s[c];

    if(down==0) { // moving down 

        row++;

        if(row==numRows) {

            down = 1;

            col++;

            row-=2;

        }

    } else { // moving up

        row--;

        col++;

        if(row==0) {

            down=0;

        }

    }

    c++;

}

附言。上面的代码无法处理numRows < 3，因此您必须在此循环之前管理它们。

Answer 2

我的微积分有点生疏，但这个问题背后的逻辑似乎是一个正弦波。我在创建阻止它工作的 sin 方程的某个地方出现了数学错误（r 从不等于 c 与当前参数），但如果这是您选择的方向，希望这会有所帮助。

/*If x-axis is position in string, and y-axis is row number...

n=number of rows

Equation for a sin curve: y = A sin(B(x + C)) + D

D=vertical shift (y value of mid point)

D=median of 1 and n

n:  median:

1   1

2   1.5

3   2

4   2.5

5   3

6   3.5

7   4

median=(n+1)/2

D=(n+1)/2

A=amplitude (from the mid-point, how high does the curve go)

median + amplitude = number of rows

amplitude = number of rows - median

A=n-D

C=phase shift

Phase shift for a sin curve starting at its lowest point: 3π/2

(so at time 1, row number is 1, and curve goes up from there)

C=3π/2

Period is 2π/B

n   p

3   4

4   6

5   8

6   10

period=2(n-1)

2(n-1)=2π/B

B(2(n-1)=2π

B=2π/2(n-1)

B=π/(n-1)

Variables:

s = string

n = number of rows

c = current row number being evaluated

p = position in string

r = row number

*/

var output='';

function convert(s,n) {

    D=(n+1)/2

    A=n-D

    C=(3*Math.PI)/2

    B=Math.PI/(n-1)

  for (c=1;c<=n;c++) { //loop from 1st row to number of rows

    for (p=1;p<=s.length;p++) { //loop from 1st to last character in string

    r=A*Math.sin(B*(p+C))+D //calculate the row this character belongs in

        if (r==c) { output+= s.charAt(r) } //if the character belongs in this row, add it to the output variable. (minus one because character number 1 is at position 0)

}}

//do something with output here

}