avatar
fireworks99
keep hungry keep foolish

leecode 0006.Z字型变换

题目描述

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P A H N A P L S I I G Y I R
  • 1
  • 2
  • 3

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);
  • 1

示例

输入:s = “PAYPALISHIRING”, numRows = 3
输出:”PAHNAPLSIIGYIR”

输入:s = “PAYPALISHIRING”, numRows = 4
输出:”PINALSIGYAHRPI”
解释:
P I N
A L S I G
Y A H R
P I

输入:s = “A”, numRows = 1
输出:”A”

思路

从前往后记录每个字符在第几行上,比如第 i 个字符在第 j 行上 ( rows[i] = j ),将rows数组按照从小到大的顺序进行stable_sort即可。只不过这里要携带字符,那么需要用结构体,node.c = ‘P’; node.r = ‘0’;然后进行结构体排序。

那么如何弄清每个字符在第几行上?模拟Z字型即可

Code

/** * @param {string} s * @param {number} numRows * @return {string} */ var convert = function(s, numRows) { const arr = []; let flag = true; let idx = 0; for(let i = 0; i < s.length; ++i) { if(idx === numRows) { flag = false; idx -= 2; } if(idx === -1) { flag = true; idx += 2; } arr.push({ c: s[i], r: idx }); idx += flag ? 1 : -1; } arr.sort((a, b) => a.r - b.r); let ans = ""; arr.forEach(obj => { ans += obj.c; }) return ans; }; console.log(convert("PAYPALISHIRING", 3))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy