力扣6 N字形变换

描述

力扣6 N字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 N字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
1 <= s.length <= 1000
s 由英文字母（小写和大写）、‘,’ 和 ‘.’ 组成
1 <= numRows <= 1000

方法：模拟二维数组

思路：
模拟二维数组，重要的是要找到循环。n字形的循环从一整列开始，到下一整列起点前结束，易知一个循环的元素个数为numRows * 2 - 2。并且一个循环的列数为numRows - 1。知道了一个循环的元素个数和列数，就可以求得总列数，可以构造出二维数组。
放元素：当在整列时，下一个元素是上一个元素的行数加1，当处于斜线时，下一个元素是上一个元素的行数减1，列数加1.并且每个循环的元素是确定的，每个整列的元素也是确定的，所以巧妙利用%运算确定下一个元素坐标变化情况
具体实现及注释：

class Solution {
   public String convert(String s, int numRows) {
       char[] chars = s.toCharArray(); 
       int length = s.length();
       //当只有一行的时候，直接返回s，不然后面cycleNum计算值为0会出现除0；
       if (numRows == 1) return s;
       //一个循环所包含的元素
       int cycleNum = 2 * numRows - 2;
       //所需列数
       int colNum = (length / cycleNum + 1) * (numRows - 1);
       //模拟的二维数组
       char[][] binaryArray = new char[numRows][colNum];
       //坐标
       int x = 0;
       int y = 0;
       for (int i = 1; i <= length; i++) {
           binaryArray[x][y] = chars[i-1];
           //这里mod即为当前元素在一个循环中的位置信息。当其位置小于行数时，说明其下一个元素在整列上，反之则在斜线上。 
           int mod = i % cycleNum;
           //注意这里需要考虑mod == 0 的特殊情况，当mod == 0时，代表下一个元素是循环中的最后一个元素，他应该属于mod >= numRows的情况。
           if (mod < numRows && mod != 0) x++;
           else {
               x--;
               y++;
           }
       }
       StringBuffer sb = new StringBuffer();
       for (int i = 0; i < numRows; i++) {
           for (int j = 0; j < colNum; j++) {
               char c = binaryArray[i][j];
               if (c != 0) sb.append(c);
           }
       }
       return sb.toString();
   } 
}

原文地址：https://blog.csdn.net/dastatham/article/details/142356964

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！