Solving the 'Zigzag Conversion' on LeetCode with C++

問題

https://leetcode.com/problems/zigzag-conversion/

答え

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};

この問題の解決策を考えてみよう。

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PAHNAPLSIIGYIR"

P   A   H   N
A P L S I I G
Y   I   R

最初の行から最後の行まで、それぞれの行の文字列を組み合わせた答えを求めます。

最初の行は "PAHN "である。 2行目は「APLSIIG」。 3行目は「YIR」。

"PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR" となる。

上記のアルゴリズムをコードとして書いてみよう。 答えのコードを再掲する。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};

上のコードを分解してみよう。

    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

numRowsが1の場合は1行なので、s`を返すべきである。

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

numRowsまたは入力sのサイズの最小値を取る必要がある。なぜなら、numRowsが 4 でs` のサイズが 3 の場合、すべての行が使用されるわけではないからである。

goingDown は移動方向を表し、行の上下を表す。

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }
        }

rows[currentRow] += c;` は各行に文字列を作成します。

if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;

currentRowが最初の行、またはcurrentRowが最後の行の場合、goingDownを反転する。 goingDown が true の場合、currentRow を次の行に移動する。 goingDownがfalseの場合、currentRow` を前の行に移動する。

例えば 行数は 3 です。

行は上から下に移動するので、 goingDown は true です。 次の currentRow は 1 である。goingDown は true であり、currentRow はまだ最後の行ではないので、行はまだ上から下に移動する。 次の currentRow は 2 で、currentRow が最後の行であるため、goingDown は true から false に変わる。次の currentRow は 1 である必要があります。

        string result；
        for(string row : rows) { 
            result += row；
        }

各行の文字列を結合する。

www.DeepL.com/Translator（無料版）で翻訳しました。

dev.to