leetcode 6. N 字形变换(medium)(优质解法)

发布时间:2023年12月25日

链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

代码:

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) {
            return s;
        }
        int length=s.length();
        StringBuilder ret=new StringBuilder();

        //获取排列后 0 行(首行)的字符
        int index=0;
        int d=2*numRows-2;
        while(index<length){
            ret.append(s.charAt(index));
            //更改下标 index
            index+=d;
        }

        //获取排列后 1 ~ numRows-2 行的字符
        for(int k=1;k<=numRows-2;k++){
            int i=k,j=d-i;
            while(i<length||j<length){
                if(i<length){
                    ret.append(s.charAt(i));
                }
                if(j<length){
                    ret.append(s.charAt(j));
                }
                i+=d;
                j+=d;
            }
        }

        //获取排列后 numRows-1(末行)的字符
        index=numRows-1;
        while(index<length){
            ret.append(s.charAt(index));
            index+=d;
        }

        return ret.toString();

    }
}

题解:

? ? ? ? 本题没有什么技巧,按照题目要求模拟题目描述的过程即可,最好通过画图找到其中的逻辑关系,以示例2为例,画出如下的图:

? ? ? ? 可以来找以下其中含有的规则,我们要获取的正确答案就是从左到右逐行读取,首先要读取的是第 0 行(首行),读取到 P?I N ,在字符串中的下标对应为 0 ,6 ,12,下标之间相差 6 ,P 到 L 有 6 个字符,所以递增的增量 d =?2*numRows - 2 ,2*4-2 = 6 ,所以要填充第一行的字符时,可以直接找到以 0 开始,增量为?d =?2*numRows - 2 的合法下标对应的字符

? ? ? ? 对于 1 ~?numRows - 2 行的字符,可以每两个字符为一组,如字符 A ,L 为一组,A 的下标为 1 (行的下标与第一个字符的下标相同),L 的下标为 5 ,可以发现 L 下标为 d - A下标,所以根据行数可以得到 A, L字符的下标,S 的下标为 7 = A 的下标 + d ,I 的下标 = L 的下标 + d ,通过<A,L> 这两个下标分别加上 d ,得到下一组字符的下标,获取所有符合条件的下标对应的字符即可

? ? ? ? 对于?numRows -1 行(尾行),第一个字符 P 的下标为 3 = 当前的行的下标,下一个字符 I 的下标为 9 ,可以看出与首行相同,字符的下标按照增量 d =?2*numRows - 2?递增,根据该规则获取符合条件的下标对应的字符即可

? ? ? ? 通过上述分析,已经知道了每一行字符下标的规则,只需要按照该规则去一行一行的获取字符拼接到字符串中即可

? ? ? ? 要注意该题有特殊情况,当 numRows = 1? 时数据要放到一行上,进行排序后和原数组相同,直接返回原数组即可

文章来源:https://blog.csdn.net/q322359/article/details/135201720
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。