每日力扣：6. Z 字形变换

我会带着你远行 2022-03-12 16:54 176阅读 0赞

package com.sample.suncht.algo;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 6. Z 字形变换
     * <p>
     * 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
     * <p>
     * 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
     * <p>
     * L   C   I   R
     * E T O E S I I G
     * E   D   H   N
     * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
     *
     * 时间复杂度：O(n), 空间复杂度：O(n)
     * @author sunchangtan
     * @date 2019/3/6 11:46
     */
    public class ZigzagConversion {
        public String convert(String s, int numRows) {
            if (s == null) {
                return "";
            }
            if (numRows <= 1) {
                return s;
            }
    
            char[] chars = s.toCharArray();
            int len = chars.length;
            if(numRows > len) {
                return s;
            }
    
            StringBuilder builder = new StringBuilder("");
    
            for (int i = 0; i < numRows; i++) {
                int span1 = 2 * (numRows - i - 1);
                int span2 = 2 * i;
                int index = i;
                int counter = 0;
                do {
                    if(counter % 2 == 0) {
                        if(span1 > 0) {
                            builder.append(chars[index]);
                            index = index + span1;
                        }
                    } else {
                        if(span2 > 0) {
                            builder.append(chars[index]);
                            index = index + span2;
                        }
                    }
                    counter++;
                } while (index < len);
            }
    
            return builder.toString();
        }
    
        public static void main(String[] args) {
            List<AlgoHelper.BiInputParams<String, Integer, String>> datas = new ArrayList<>();
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 2, "LECDIHRNETOESIIG"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 3, "LCIRETOESIIGEDHN"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 4, "LDREOEIIECIHNTSG"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 5, "LIEESGEDHNTOIICR"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 6, "LHESIEIRTEICDNOG"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", "LEETCODEISHIRING".length(), "LEETCODEISHIRING"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 1, "LEETCODEISHIRING"));
            datas.add(new AlgoHelper.BiInputParams<>("LEETCODEISHIRING", 20, "LEETCODEISHIRING"));
    
            AlgoHelper.assertResult(datas, new ZigzagConversion()::convert);
        }
    }