包子小道消息-2020刚到就很挺闹心呀-Leetcode 6: Zig Zag Conversion

包子面试培训

发布于 2020-01-15 11:27:19

4140

发布于 2020-01-15 11:27:19

文章被收录于专栏：包子铺里聊IT

包子小道消息@01/04/2020

2020这才刚来没几天，挺闹心呀

国际大事儿，Trump直接轰伊拉克巴格达机场炸死伊朗军队重要将领，你就是为了2020大选制造紧张氛围和恐惧，和我们伟大祖国打打贸易战打打嘴炮就好，你去惹什么伊朗呀？他们好惹吗？反正包子君周围的伊朗哥们都挺猛的。。。World Peace, Amen!
局部地区，中国台湾马上一周就要大选，老韩和老蔡吵得火热，每一届都是重要的一届，这一届对于两岸关系尤为重要，因为包子君马上要去中国台湾旅游了，呵呵。BTW，老韩的口才真是好，特别能喷
就在湾区，一个中国工程师/数据科学家在奥克兰星巴克被老黑抢了电脑，追的途中争执不幸身亡。湾区，尤其是旧金山奥克兰hunters point，真的非常乱，湾区的小伙伴一定要小心！砸车抢电脑都已经是家常便饭了，人没事儿就好，不知道LA92 那一幕什么时候会重演，男丁们，去靶场多练练枪法吧
说点实在的，要不感觉都不是小道消息了。。去买特斯拉股票吧，上海工厂works very well, period.
最后，包子的这道题目在4年前录过了?‍♂️，结果被热心粉丝发现留言了，谢谢这位仁兄的同时，闹心呀。。。

Leetcode solution 6: Zig Zag Conversion

Blogger:https://blog.baozitraining.org/2020/01/leetcode-solution-6-zigzag-conversion.html

Youtube: https://youtu.be/62LdZVhwcMg

博客园: https://www.cnblogs.com/baozitraining/p/12052398.html

B站: https://www.bilibili.com/video/av79569155/

Problem Statement

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

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
B站

Thought Process

It's a very good implementation problem, by simply simulating each character in the string to each row, it would take extra O(N) space to hold up the array where N is the string size. However, there is definitely a difference between a good and poor implementation.

There is also a math formula we can use, please see attached pdf for solutions.

Solutions

Simulation poor implementation

 1 public String convertSimulation(String s, int nRows) {
 2     if (s == null || s.length() == 0 || nRows <= 0) {
 3         return "";
 4     }
 5 
 6     if (nRows == 1) {
 7         return s;
 8     }
 9 
10     int size = s.length();
11     List<StringBuilder> buckets = new ArrayList();
12 
13     for (int i = 0; i < nRows; i++) {
14         buckets.add(new StringBuilder());
15     }
16 
17     int i = 0;
18     int index = 0;
19     boolean fromTopToBottom = true;
20     while (i < size) {
21         char c = s.charAt(i);
22 
23         if (fromTopToBottom) {
24             if (index == nRows - 1) {
25                 fromTopToBottom = false;
26                 buckets.get(index).append(c);
27                 index--;
28             } else {
29                 buckets.get(index).append(c);
30                 index++;
31             }
32         } else {
33             if (index == 0) {
34                 fromTopToBottom = true;
35                 buckets.get(index).append(c);
36                 index++;
37             } else {
38                 buckets.get(index).append(c);
39                 index--;
40             }
41         }
42         i++;
43     }
44 
45     String res = "";
46     for (StringBuilder sb : buckets) {
47         res += sb.toString();
48     }
49 
50     return res;
51 }

Time Complexity: O(N) where N is the string size

Space Complexity: O(N) since we used an extra array to store each character in the string

Simulation good implementation

 1 public String convertSimulationOptimizedImplementation(String s, int nRows) {
 2     if (s == null || s.length() == 0 || nRows <= 0) {
 3         return "";
 4     }
 5 
 6     if (nRows == 1) {
 7         return s;
 8     }
 9 
10     int size = s.length();
11     // directly allocate a string builder array
12     StringBuilder[] buckets = new StringBuilder[nRows];
13     for (int i = 0; i < nRows; i++) {
14         buckets[i] = new StringBuilder();
15     }
16 
17 
18     int i = 0;
19     int index = 0;
20     boolean fromTopToBottom = true;
21     while (i < size) {
22         char c = s.charAt(i);
23         buckets[index].append(c);
24         index += fromTopToBottom ? 1 : -1;
25 
26         if (index == nRows - 1 || index == 0) {
27             fromTopToBottom = !fromTopToBottom;
28         }
29 
30         i++;
31     }
32 
33     String res = "";
34     for (StringBuilder sb : buckets) {
35         res += sb.toString();
36     }
37 
38     return res;
39 }