LeetCode.6 Z 字形變換(zigzag-conversion)(JS)

cheukyin 發(fā)布于2019-08-23 17:51 / 1674人閱讀

摘要：看到這道題總覺得眼熟，做完之后恍然大悟，這不就是小學數(shù)學做的找規(guī)律一題目字形變換將一個給定字符串根據(jù)給定的行數(shù)，以從上往下從左到右進行字形排列。一當然是因為最近實在太忙了捂臉，幾乎周周誰遭得住。

看到這道題總覺得眼熟，做完之后恍然大悟，這不就是小學數(shù)學做的找規(guī)律

一、題目

Z 字形變換：

將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 Z 字形排列。
比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時，排列如下：
L???C???I????R
E T O E S ?I ?I ??G
E???D???H???N
(這個字符排列看不懂的話推薦去看一下原題，原題的調(diào)整示例比較清晰)
之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："LCIRETOESIIGEDHN"。
請你實現(xiàn)這個將字符串進行指定行數(shù)變換的函數(shù)：
string convert(string s, int numRows);
示例 1:
輸入: s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"
示例 2:
輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"

二、我的答案

???????首先分析一下題目，輸出內(nèi)容就是重新排列之后的各行相加，那么問題變成按照題干規(guī)律排列，序號為n的字符在第幾行。
???????在示例1中，LEETCODEISHIRING行數(shù)為3時，各個字符分別在1232-1232-1232-1232行，很明顯應該存在某種規(guī)律，可以把字符串分成幾組，然后每組按照這種規(guī)律push到不同行中，然后各行相加得出目標字符串，思路理清，代碼如下

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
  const perGroup = numRows > 1 ? (numRows - 2) * 2 + 2 : 1
  const result = []
  let i
  for(i = 0; i < numRows; i++) {
    result[i] = []
  }
  for(i = 0; i < s.length; i++) {
    result[i % perGroup < numRows ? i % perGroup : numRows - (i % perGroup - numRows + 2)].push(s[i])
  }
  let resultStr = ""
  result.forEach(item => {
    item.forEach(str => {
      resultStr += str
    })
  })
  return resultStr
};

???????最后各行的數(shù)組都算出來了，轉(zhuǎn)成字符串的操作想用的數(shù)組flat然后再join的，但是leetCode的編譯環(huán)境好像不支持flat,就只能含淚用這種循環(huán)的方法了，最后運行用時擊敗88.52%，內(nèi)存消耗擊敗33.66%，但是我不知道怎么降低內(nèi)存消耗/捂臉

三、優(yōu)秀答案

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    var map = {};
    var j = 0;
    if (numRows <= 1) {
        return s;
    }
    var boo = true;
    for (var i = 0; i < s.length; i++) {
        if (!map[j]) {
            map[j] = "";
        }
        map[j] = map[j] + s[i];
        if (boo) {
            j++;
            if (j >= numRows) {
                j = j - 2;
                boo = false;
            }
        } else {
            j--;
            if (j < 0) {
                boo = true;
                j = j + 2;
            }
        }
        
    }
    s = "";
    Object.keys(map).forEach(i => {
        s = s + map[i];
    });
    return s;
    
};

???????這段代碼我并沒有仔細看，因為看他對j＋2 - 2的這種操作還有最后相加的手段，都和我差不多，我復制下來再次提交，用時擊敗91.90%，內(nèi)存消耗擊敗49.13%。這是我和優(yōu)秀答案最近的一次/滑稽，甚至我個人感覺我的代碼的可閱讀性要比他的更好，代碼寫出來就是給別人看的嘛（開始瘋狂自我安慰）

四、路漫漫其修遠兮

???????本來說一周1-2道題的，但是這道題距離上次都快兩個月了。一當然是因為最近實在太忙了/捂臉，幾乎周周997誰遭得住。還有就是本來預計寫的第4題沒思路，隨便瀏覽的過程中感覺第42題比較有意思就去做那個，結(jié)果陷入了“這道題好難啊放一放吧去工作一會兒——工作好累啊去刷到題緩一緩——這道題好難啊放一放吧去工作一會兒”的惡性循環(huán)，現(xiàn)在這道第六題其實是我心態(tài)爆炸之后拿來找自信的，近期工作上的活也終于步入尾聲了，重整旗鼓。