侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【模拟】解码斜向换位密码

GabrielxD
2022-06-16 / 0 评论 / 0 点赞 / 36 阅读 / 922 字 / 正在检测是否收录...

题目

2075. 解码斜向换位密码


字符串 originalText 使用 斜向换位密码 ,经由 行数固定 为 rows 的矩阵辅助,加密得到一个字符串 encodedText

originalText 先按从左上到右下的方式放置到矩阵中。

image-20220616223708925

先填充蓝色单元格,接着是红色单元格,然后是黄色单元格,以此类推,直到到达 originalText 末尾。箭头指示顺序即为单元格填充顺序。所有空单元格用 ' ' 进行填充。矩阵的列数需满足:用 originalText 填充之后,最右侧列 不为空 。

接着按行将字符附加到矩阵中,构造 encodedText

image-20220616223723812

先把蓝色单元格中的字符附加到 encodedText 中,接着是红色单元格,最后是黄色单元格。箭头指示单元格访问顺序。

例如,如果 originalText = "cipher"rows = 3 ,那么我们可以按下述方法将其编码:

image-20220616223733692

蓝色箭头标识 originalText 是如何放入矩阵中的,红色箭头标识形成 encodedText 的顺序。在上述例子中,encodedText = "ch ie pr"

给你编码后的字符串 encodedText 和矩阵的行数 rows ,返回源字符串 originalText

注意:originalText 不 含任何尾随空格 ' ' 。生成的测试用例满足 仅存在一个 可能的 originalText

示例 1:

输入:encodedText = "ch   ie   pr", rows = 3
输出:"cipher"
解释:此示例与问题描述中的例子相同。

示例 2:

image-20220616223740178

输入:encodedText = "iveo    eed   l te   olc", rows = 4
输出:"i love leetcode"
解释:上图标识用于编码 originalText 的矩阵。 
蓝色箭头展示如何从 encodedText 找到 originalText 。

示例 3:

image-20220616223744748

输入:encodedText = "coding", rows = 1
输出:"coding"
解释:由于只有 1 行,所以 originalText 和 encodedText 是相同的。

示例 4:

image-20220616223754043

输入:encodedText = " b  ac", rows = 2
输出:" abc"
解释:originalText 不能含尾随空格,但它可能会有一个或者多个前置空格。

提示:

  • 0 <= encodedText.length <= 10^6
  • encodedText 仅由小写英文字母和 ' ' 组成
  • encodedText 是对某个 不含 尾随空格的 originalText 的一个有效编码
  • 1 <= rows <= 1000
  • 生成的测试用例满足 仅存在一个 可能的 originalText

解题

方法一:模拟

思路

算出矩阵的列数然后从左至右枚举每一条左上到右下的路径,并按顺序记录所有经过的字符,对于某个坐标 (r,c)(r, c) 在字符串中的索引就是 r * cols + c

由于原码中不存在后缀 ' ' 字符,所以要把解码出来的字符串的 ' ' 全部删去然后返回。

注意:由于原码中可能存在前导 ' ' ,所以不能直接使用 trim() 方法删除空格。

代码

class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        int n = encodedText.length();
        int cols = n / rows;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < cols; i++) {
            int r = 0, c = i;
            while (r < rows && c < cols) {
                ans.append(encodedText.charAt(r++ * cols + c++));
            }
        }
        int idx = ans.length() - 1;
        while (idx >= 0 && ans.charAt(idx) == ' ') ans.deleteCharAt(idx--);
        return ans.toString();
    }
}

优化

不能直接用 trim() 但可以现在字符串前面随便加个字符然后 trim() 然后把那个字符删去。

class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        int n = encodedText.length();
        int cols = n / rows;
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < cols; i++) {
            int r = 0, c = i;
            while (r < rows && c < cols) {
                ans.append(encodedText.charAt(r++ * cols + c++));
            }
        }
        ans.insert(0, 'A');
        String ansStr = ans.toString().trim();
        return ansStr.substring(1);
    }
}
0

评论区