leetcode如何解決Z字形變換問題

小編給大家分享一下leetcode如何解決Z字形變換問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

創(chuàng)新互聯(lián)公司是一家專注于成都網(wǎng)站設(shè)計、成都網(wǎng)站制作與策劃設(shè)計,豐南網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:豐南等地區(qū)。豐南做網(wǎng)站價格咨詢:13518219792

題目鏈接

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

題目描述

將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進(jìn)行 Z 字形排列。

比如輸入字符串為 "LEETCODEISHIRING" 行數(shù)為 3 時，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的輸出需要從左往右逐行讀取，產(chǎn)生出一個新的字符串，比如："LCIRETOESIIGEDHN"。

請你實現(xiàn)這個將字符串進(jìn)行指定行數(shù)變換的函數(shù)：

string convert(string s, int numRows);

示例 1:

輸入: s = "LEETCODEISHIRING", numRows = 3
輸出: "LCIRETOESIIGEDHN"

示例 2:

輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"
解釋:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解題方案

思路

標(biāo)簽：字符串
整體的思路是遍歷字符串，遍歷過程中將每行都看成新的字符串構(gòu)成字符串?dāng)?shù)組，最后再將該數(shù)組拼接起來即可
如果numRows=1則說明當(dāng)前字符串即為結(jié)果，直接返回
否則整個字符串需要經(jīng)歷，向下向右，向下向右，這樣的反復(fù)循環(huán)過程，設(shè)定down變量表示是否向下，loc變量表示當(dāng)前字符串?dāng)?shù)組的下標(biāo)
如果down為true，則loc+=1，字符串?dāng)?shù)組下標(biāo)向后移動，將當(dāng)前字符加入當(dāng)前字符串中
如果down為false，則表示向右，則loc-=1，字符串?dāng)?shù)組下標(biāo)向前移動，將當(dāng)前字符加入當(dāng)前字符串中
時間復(fù)雜度：O(n)，n為字符串s的長度

代碼

Java版本

class Solution {
   public String convert(String s, int numRows) {
       if(numRows == 1)
           return s;
       
       int len = Math.min(s.length(), numRows);
       String []rows = new String[len];
       for(int i = 0; i< len; i++) rows[i] = "";
       int loc = 0;
       boolean down = false;

       for(int i=0;i           rows[loc] += s.substring(i,i+1);
           if(loc == 0 || loc == numRows - 1)
               down = !down;
           loc += down ? 1 : -1;
       }
       
       String ans = "";
       for(String row : rows) {
           ans += row;
       }
       return ans;
   }
}

JavaScript版本

/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
   if(numRows == 1)
       return s;

   const len = Math.min(s.length, numRows);
   const rows = [];
   for(let i = 0; i< len; i++) rows[i] = "";
   let loc = 0;
   let down = false;

   for(const c of s) {
       rows[loc] += c;
       if(loc == 0 || loc == numRows - 1)
           down = !down;
       loc += down ? 1 : -1;
   }

   let ans = "";
   for(const row of rows) {
       ans += row;
   }
   return ans;
};