AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

LeetCode 6. Z 字形变换    原题链接    中等

作者: 作者的头像   zdw ,  2020-03-29 10:55:36 ,  阅读 200


0


解题思路 时间复杂度 O(n) 空间复杂度 O(n)

整体上:
找出每个字符应该在位置,找规律题型,每次间隔 d = 2 *(numRows - 1); 第一行和最后一行不同于中间的部分,分三个阶段来处理
细节上:
特判:行数为1的情况,可能会导致 d = 0, 陷入死循环

代码

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        int n = s.size(), d = 2 * (numRows - 1);
        string res;
        res.resize(n);
        int idx = 0;
        // 第一行和最后一行分开处理
        for (int i = 0; i < n; i += d) {
            res[idx++]= s[i];
        }
        for (int i = 1; i < numRows - 1; i++) {
            for (int j = i, k = d - i; j < n || k < n; j += d, k += d) {
                if (j < n) res[idx++]= s[j];
                if (k < n)  res[idx++]= s[k];
            }
        }
        for (int i = numRows - 1; i < n; i += d) {
           res[idx++]= s[i];
        }
        return res;
    }
};

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息