[leetcode]6. ZigZag Conversion字符串Z形排列
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation: P I N
A L S I G
Y A H R
P I
Solution1:
Step1: new StringBuilder[]. For each row, allocate a new StringBuilder to save characters in such row.
Pay attention! StringBuilder is treated like variable-length arrays. So StringBuilder[] is like array of array
Step2: we can observe that for 1st and last row, chars will be added into sb[0] and sb[numRows-1], seperately.
for sloping slide, chars will be added in sb[numRows -2 ] ... sb[1]
Step3: convert each row's StringBuilder into result String
code:
/*
Time Complexity: O(n)
Space Complexity: O(n)
*/ class Solution {
public String convert(String s, int numRows) {
char[] c = s.toCharArray();
int len = c.length;
StringBuilder[] sb = new StringBuilder[numRows];
// 要按row来进行遍历，每一个row先allocate一个StringBuilder
for (int i = 0; i < sb.length; i++) {
sb[i] = new StringBuilder();
}
int idx = 0; //用来扫String s
while (idx < len) {
for (int i = 0; i < numRows && idx < len; i++) {
sb[i].append(c[idx++]);
}
// sloping side
for (int i = numRows - 2; i >= 1 && idx < len; i--) {
sb[i].append(c[idx++]);
} }
//从sb[0]开始，将sb[1], sb[2], sb[3]... append到一个StringBuilder
for (int i = 1; i < sb.length; i++) {
sb[0].append(sb[i]);
}
return sb[0].toString();
}
}
最新文章
- Play Framework 完整实现一个APP（十三）
- get请求报文
- Yii2.0 GridView 新增添加按钮
- 黄聪：PHP字符串操作（string替换、删除、截取、复制、连接、比较、查找、包含、大小写转换、切割成数组等）
- C# 添加系统计划任务方案
- [itint5]直角路线遍历棋盘
- Spark快速数据处理
- WindowsService的调试方法
- jquery1.7.2的源码分析（六）基本功能
- nohup sort -k1 -n -t$'\t' ./bigfile.16 -o./test/bigfile.16.ok &
- [转]startActivityForResult的用法和demo
- NYOJ--42--dfs--一笔画问题
- Python第一天：你必须要知道的Python擅长领域以及各种重点学习框架（包含Python在世界上的应用）
- Mac OS Sierra安装源不能设置任何来源（anywhere）
- 获取本机IP地址的方法
- nginx配置文件服务器
- 修改eclipse的背景色(转载)
- Login case
- 如何在同一台服务器上部署两个tomcat
- LoadRunner性能测试入门教程