Lexi's Leetcode solutions

[leetcode] ZigZag Conversion | 把zigzag的string用横着扫的方式输出

Posted on: September 30, 2013

这题正经做了一段时间;首先自己想的算法不好,不够数学;另外这个题的testcase很多情况,自己没想清楚,全是用oj来查出错误了。

数学的做法:每个zigzag(|/形状是n + n – 2的长度;除非n < 2, 则就是n本身的长度),这样可以直接在string上跳着取出应该append的index。这个有两种情况:

ABCDEFGHIJKL n = 4
-------------
A     G 
B   F H   L 
C E   I K  
D     J
  1. 第一行和最后一行每个zigzag段只要append一个就行了
  2. 中间那些行每次要append两个字母;

两个变量,想了半天。分别是“在当前段里的offset”和”在哪个zigzag段里“,但是要保证以”在那个段里“外层循环。

注意:想不明白边界条件的时候,不妨直接用if(边界在string range里),这样就能把所有出界全接住了。

public String convert(String s, int nRows) {
  if (s == null)
    return null;
  int len = nRows <= 1 ? nRows : (2 * nRows - 2);
  StringBuilder sb = new StringBuilder();
  for (int offset = 0; offset < nRows; offset++) {
    for (int zigIndex = 0; zigIndex * len < s.length(); zigIndex++) {
      int firstIndex = zigIndex * len + offset;
      if (firstIndex >= 0 && firstIndex < s.length())
        sb.append(s.charAt(firstIndex));
      if (offset > 0 && offset < nRows - 1) {
        int reverseIndex = (zigIndex + 1) * len - offset;
        if (reverseIndex >= 0 && reverseIndex < s.length())
          sb.append(s.charAt(reverseIndex));
      }
    }
  }
  return sb.toString();
}
Advertisements
Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: