数据结构与算法之 Z 字形变换

原创
06/15 13:38
阅读数 20

一、说明


    将字符串 `"PAYPALISHIRING"` 以Z字形排列成给定的行数:

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

    之后从左往右,逐行读取字符: `"PAHNAPLSIIGYIR"`

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

    string convert(string s, int numRows);

    示例 1:

        输入: s = "PAYPALISHIRING", numRows = 3
        输出: "PAHNAPLSIIGYIR"

    示例 2:

        输入: s = "PAYPALISHIRING", numRows = 4
        输出: "PINALSIGYAHRPI"
    解释:

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

 

二、解决方案参考

    1. Swift 语言
class Solution {
    func convert(s: String, _ numRows: Int) -> String {
        if numRows == 1 {
            return s
        }
        
        var ret: [Character] = []
        var chars: [Character] = [Character](s.characters)
        let cnt = chars.count
        
        
        for i in 0..<numRows {
            let len = 2 * numRows - 2
            var index = i
            while index < cnt {
                ret.append(chars[index])
                
                if i != 0 && i != numRows - 1 {
                    let tmpIndex = index + 2 * (numRows - i - 1)
                    if tmpIndex < cnt {
                        ret.append(chars[tmpIndex])
                    }
                }
                
                index += len
            }
        }
        
        return String(ret)
    }
}

    2. JavaScript 语言
/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var ans, max_column;

function dfs(x, y, s, n, numRows) {
  ans[x][y] = s[n];

  if (s.length === n) {
    max_column = y;
    return;
  }

  if (y % (numRows - 1) === 0 && x !== numRows - 1) 
    dfs(x + 1, y, s, n + 1, numRows);
  else 
    dfs(x - 1, y + 1, s, n + 1, numRows);
}

var convert = function(s, numRows) {
  if (numRows === 1) 
    return s;

  ans = [];

  for (var i = 0; i < numRows; i++)
    ans[i] = [];

  dfs(0, 0, s, 0, numRows);

  var tmp = '';
  for (var i = 0; i < numRows; i++)
    for (var j = 0; j <= max_column; j++)
      if (ans[i][j] !== undefined)
        tmp += ans[i][j];

  return tmp;
};

    3. Python 语言
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows <= 1:
            return s
        n = len(s)
        ans = []
        step = 2 * numRows - 2
        for i in range(numRows):
            one = i
            two = -i
            while one < n or two < n:
                if 0 <= two < n and one != two and i != numRows - 1:
                    ans.append(s[two])
                if one < n:
                    ans.append(s[one])
                one += step
                two += step
        return "".join(ans)

    4. Java 语言
参考一:

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++)
            rows.add(new StringBuilder());

        int curRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder ret = new StringBuilder();
        for (StringBuilder row : rows) ret.append(row);
        return ret.toString();
    }
}

参考二:
class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(s.charAt(j + cycleLen - i));
            }
        }
        return ret.toString();
    }
}

    5. C++ 语言
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string convert(string s, int nRows) {
    //The cases no need to do anything
    if (nRows<=1 || nRows>=s.size()) return s;
     
    vector<string> r(nRows);
    int row = 0;
    int step = 1;
    for(int i=0; i<s.size(); i ++) {
        if (row == nRows-1) step = -1;
        if (row == 0) step = 1;
        //cout << row <<endl;
        r[row] += s[i];
        row += step;
    }
    
    string result;
    for (int i=0; i<nRows; i++){
        result += r[i];
    }
    return result;
}
int main(int argc, char**argv){
    string s;
    int r;
    s = "PAYPALISHIRING";
    r = 3;
    cout << s << " : " << convert(s, 3) << endl;
}

    6. C 语言
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char* convert(char* s, int numRows)
{
    if (numRows <= 1) return s;

    int len = strlen(s);
    char *new_str = malloc(len + 1);    
    char *p = new_str;
    int row = 0;
    for (row = 0; row < numRows; row++) {
        int interval1 = numRows + (numRows - 2) - row * 2;
        int interval2 = 2 * row;
        int flag = 0;
        int i = row;
        while (i < len) {
            *p++ = s[i];
            int delta = 0;
            do {
                delta = flag == 0 ? interval1 : interval2;
                flag = !flag;
            } while (delta == 0);
            i += delta;
        }
    }

    new_str[len] = '\0';
    return new_str;
}

int main(int argc, char **argv)
{
    if (argc < 3) {
        printlf(stderr, "./test string num");
        exit(-1);
    }

    printf("%s", convert(argv[1], atoi(argv[2])));
    return 0;
}

 

--------------------------------------

版权声明:本文为【PythonJsGo】博主的原创文章,转载请附上原文出处链接及本声明。

博主主页:https://my.oschina.net/u/3375733

本篇文章同步在个人公众号:

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部