LeetCode 刷题之 Z 字形变换

LeetCode 刷题之 Z 字形变换

Chris Yue No Comment
Posts

题目:

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);

这个题我感觉还是很好解答的,虽然难度为『中』但我咋觉得比简单难度还简单。解题思路简单说一下:先设置一个 numRows 长度的字符串一维数组,字符串第一个字母肯定是放在数组第 1 个元素里,第 n 个字符放在数组第 n 个元素里……第 numRows 个字符放在数组第 numRows 个元素里,但这个时候,下一个字符,就得调个头放在 numRows – 1 个元素里;再下 n 个字符放在 numRows – n 个元素里,直到 numRows – n 为 0,再调头……最后把一维数组 join 起来就完事儿了。

写出来的代码也很简单,就几行:

class Solution {

    /**
     * @param String $s
     * @param Integer $numRows
     * @return String
     */
    function convert($s, $numRows) {
        if (2 > $numRows) return $s;

        $len = strlen($s);
        if ($len <= $numRows) return $s;

        $rows = [];
        $i = 0;
        $alpha = -1;
        for ($j = 0; $j < $len; ++$j) {
            $rows[$i] .= $s[$j];
            if (0 === $i || $numRows - 1 === $i) $alpha = -$alpha;
            $i += $flag;
        }

        return implode('', $rows);
    }
}

不过这么写呢,执行效率不是很高,就打败了 20% 多的其他用户。如果是为了追求快,最好的方式还是找规律,去算新字符串每个字符在原字符串里的位置是什么,毕竟计算是计算机的绝对优势,比如新字符串第二个字符,应该在原字符 1 + (numRows – 1) * 2 的位置上,第三个字符应该在原字符 1 + (numRows – 1) * 2 * 2 的位置上……如果新字符串不在第一排或者是最后一排,那么我们还可以一次性算出两个字符的位置来……可惜我数学没学好,只能硬找规律,感觉这个过程挺无聊的,就直接贴代码吧:

class Solution {

    /**
     * @param String $s
     * @param Integer $numRows
     * @return String
     */
    function convert($s, $numRows) {
        if (2 > $numRows) return $s;

        $len = strlen($s);
        if ($len <= $numRows) return $s;

        $ret = '';
        for ($i = 0; $i < $numRows; ++$i) {
            for ($j = $i; $j < $len; $j += ($numRows - 1) * 2) {
                $ret .= $s[$j];
                if ($i > 0 && $i < $numRows - 1) {
                    $sec = $j + 2 * ($numRows - $i - 1);
                    if ($sec < $len) {
                        $ret .= $s[$sec];
                    }
                }
            }
        }

        return $ret;
    }
}

这种做法比上面的做法快了很多,一下打败了 99%+ 的用户。

LeetCode 刷题之 Z 字形变换 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

微信赞赏码

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人

发表评论

51 − 44 =