leetcode6 ZigZag Ruby解法

题目

[6] ZigZag Conversion  

https://leetcode.com/problems/zigzag-conversion/description/

* algorithms
* Medium (32.97%)
* Total Accepted:    352.2K
* Total Submissions: 1.1M
* Testcase Example:  '"PAYPALISHIRING"\n3'

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

解题思路

这道题目虽然属于中级难度，但是其实非常简单。
读清题意之后可以知道,我们可以把字符串按照长度分组。每个组内的元素的行号都可以根据这个元素在每个小组之内的位置推测出来。

以下面的例子来说

s = "PAYPALISHIRING", numRows = 3

result is
P   A   H   N
A P L S I I G
Y   I   R

首先，我们可以设定一个二维数组result来存放结果。

很显然，我们期待的结果是result = [[P,A,H,N],[A,P,L,S,I,I,G],[Y,I,R]],
这个问题就转换为获取s中的index为i的元素，我们求要把s[i]放入0到numRows的哪个子数组中。

很容易发现，每个|/可以分为一组，比如PAYP, ALIS,HIRI, NG。

这个组的长度也很好求，就是两列，第一列和row相当长度，第二列则去掉首位，所以是numRows -2

所以我们可知每个组的长度为2*numRows - 2。

假设每个组的长度为split_length, s[i]所在组内的位置position为i%split_length, 这个位置有两种情况

1. 这个元素在| 上。 这个时候， 且position < numRows, 我们把s[i] 放入 result[position]组中。

2. 这个元素在/ 上。 这个时候， 且position > numRows, 我们把s[i]放入 result[numRows- 1 - (numRows - 1 - position)] 组中。

解答

# @param {String} s
# @param {Integer} num_rows
# @return {String}
def convert(s, num_rows)
  return s if num_rows == 1 || s.length == num_rows
   split_length = 2 * num_rows - 2
   result = []
   for i in 0..s.length-1
      position = i % split_length
      if (position < num_rows)
        result[position] = result[position]  || []
        result[position]  <<  s[i]
      else
        result[2* num_rows - position - 2] = result[2* num_rows - position - 2] || []
        result[2* num_rows - position - 2] <<  s[i]
      end
   end
   return result.flatten.join
end

ok, pass

➜  java_learning leetcode submit 6.zigzag-conversion.rb
  ✔ Accepted
  ✔ 1158/1158 cases passed (68 ms)
[WARN] Failed to get submission beat ratio.