导读

今天进行了快手的三面，是快手客户端的负责人，人很好。主要是就我做的项目着重聊了一下，然后杭州快手各业务线的一些介绍，然后说了一下快手的技术栈及个人成长相关的事，最后手写了二分查找。这算法题我是懵的，没想到这么简单，简单到我感觉是闭着眼睛写出来的。最后了解了我的工作内容，项目经历匹配程度较高，这也可能是算法简单的原因。最后让我加他微信，有什么问题都可以找他，然后hr安排了，明天hr面试。好了下面继续今天的题目。

看题总结

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

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

Related Topics

通过对题目的阅读，我们可以得出以下几个结论

• 题目类型为字符串
• 题意为给定字符按Z字排列，然后安航输出
• 输入安全判断，空字符串

多解法及复杂度分析

解法一：按行排序

按顺序遍历字符串 s；

• list.get(i).append(c); 把每个字符 c 填入对应行 ；
• i += flag： 更新当前字符 c 对应的行索引；
• flag = - flag： 在达到 ZZ 字形转折点时，执行反向。

具体代码如下

public String convert(String s, int numRows) {
        if (s == null || s.length() == 0 || numRows < 2) { // 0行或者1行
            return s;
        }
        ArrayList<StringBuilder> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuilder());
        }

        int i = 0, flag = 1;
        for (char c : s.toCharArray()) {
            list.get(i).append(c);
            i += flag;
            if (i == 0 || i == numRows - 1) {
                flag = -flag;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < list.size(); j++) {
            sb.append(list.get(j));
        }

        return sb.toString();
    }

复杂度分析

时间复杂度：O(n)，遍历一遍字符串 s

空间复杂度：O(n)，各行字符串共占用 O(N)O(N) 额外空间

技巧与心得

1. 开一个github仓库用来记录各种题解
2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
3. 遇到不会的题不要慌，稳住心态直接看题解
4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
6. 多看几次本文跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

点击左下角了解更多，查看所有LeetCode优质题解代码