6. Zigzag Conversion，字符串Z型转换

Last Updated: 2023-09-29 01:26:26 Friday

-- TOC --

又一个数学游戏...

题目分析

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"

输入按ZigZag顺序排列的字符串和row numbers，按行输出。

Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:
Input: s = "A", numRows = 1
Output: "A"

Constraints:

直接计算index

应该是最快的思路了，\(O(n)\)，一次遍历，online algorithm，难道还能\(O(\log{n})\)？大家都是\(O(n)\)，考验的就是编程技巧...直接计算每个字符在按行输出时的index。预先准备好输出字符串的空间，在遍历过程中一个个填入，空间也是\(O(n)\)。

我的直接计算的方法：先计算出每一行的长度，以此为基础，直接算出每个字符新的index。（后期反思，这样硬算有点复杂了...）

Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        n = len(s)
        m = numRows - 1
        # group number
        gn = (n-1) // m
        # element numbers per row
        npr = [gn for i in range(numRows)]
        npr[0] = 1 + gn//2
        npr[-1] = (gn+1) // 2
        if (tail:=(n-1)%m) != 0:
            loop = (numRows-2,0,-1) if gn%2 else (1,m)
            for i in range(*loop):
                if tail == 0:
                    break
                npr[i] = gn + 1
                tail -= 1
        # one pass
        idx = [0 for i in range(numRows)]
        rtv = ['' for i in s]
        crow = 0  # current row
        step = 0
        for c in s:
            rtv[sum(npr[:crow])+idx[crow]] = c
            idx[crow] += 1
            if (step//m)%2 == 0:
                crow += 1
            else:
                crow -= 1
            step += 1
        return ''.join(rtv)

npr[-1]这个值其实完全用不到，sum调用的地方可以再优化一点点，提前计算出来，避免重复计算，计算目标index的加法也可以去掉。下面是优化后的版本：

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        n = len(s)
        m = numRows - 1
        # group number
        gn = (n-1) // m
        # element numbers per row
        npr = [gn for i in range(m)]
        npr[0] = 1 + gn//2
        if (tail:=(n-1)%m) != 0:
            loop = (numRows-2,0,-1) if gn%2 else (1,m)
            for i in range(*loop):
                if tail == 0:
                    break
                npr[i] = gn + 1
                tail -= 1
        # one pass
        rtv = [0 for i in s]
        idx = [sum(npr[:i]) for i in range(numRows)]
        step = crow = 0  # current row
        for c in s:
            rtv[idx[crow]] = c
            idx[crow] += 1
            crow = crow-1 if (step//m)%2 else crow+1
            step += 1
        return ''.join(rtv)

写完下面的C++版本后，我发现上面的Python版本有一行代码可能不妥：

idx = [sum(npr[:i]) for i in range(numRows)]

这行代码隐藏了一个\(O(n^2)\)级别的操作。所有我修改了一下下：

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        n = len(s)
        m = numRows - 1
        # group number
        gn = (n-1) // m
        # element numbers per row
        npr = [gn for i in range(m)]
        npr[0] = 1 + gn//2
        if (tail:=(n-1)%m) != 0:
            loop = (numRows-2,0,-1) if gn%2 else (1,m)
            for i in range(*loop):
                if tail == 0:
                    break
                npr[i] = gn + 1
                tail -= 1
        # one pass
        rtv = [0 for i in s]
        #idx = [sum(npr[:i]) for i in range(numRows)]
        idx = [0]
        for i in range(m):
            idx.append(idx[i]+npr[i])
        step = crow = 0  # current row
        for c in s:
            rtv[idx[crow]] = c
            idx[crow] += 1
            crow = crow-1 if (step//m)%2 else crow+1
            step += 1
        return ''.join(rtv)

C++

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1)
            return s;
        // allocate
        int *npr {new(nothrow) int[numRows]};
        if(npr == nullptr)
            return ""; // might be used to indicate error
        int n {(int)s.size()};
        string rtv;
        try{
            rtv.reserve(n);
            rtv.resize(n); // must set the size
        } catch(...){
            return "";
        }
        // calc npr, number of element per row
        int m {numRows-1};
        int gn {(n-1)/m};  // group number
        npr[0] = 0;  // used for idx
        npr[1] = 1 + gn/2;  // first row
        for(int i{2}; i<numRows; ++i)
            npr[i] = gn;
        if(int tail {(n-1)%m}; tail!=0){
            if(gn%2 == 0){  // even group
                for(int i{2}; (tail!=0)&&(i<numRows); ++i){
                    ++npr[i];
                    --tail;
                }
            }else{  // odd group
                for(int i{numRows-1}; (tail!=0)&&(i>1); --i){
                    ++npr[i];
                    --tail;
                }
            }
        }
        // one pass
        int *idx {npr};
        for(int i{2}; i<numRows; ++i)
            idx[i] += idx[i-1];
        int step{}, crow{};
        for(auto c: s){
            rtv[idx[crow]++] = c;
            crow = (step/m)%2 ? crow-1 : crow+1;
            ++step;
        }
        delete[] npr;
        return rtv;
    }
};

稍微修改了一下，直接使用stack上的内存，不做失败判断，去掉冗余的reserve调用，复用npr这个数组。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1)
            return s;
        int n {(int)s.size()};
        int m {numRows-1};
        int gn {(n-1)/m};  // group number
        int npr[numRows];
        npr[0] = 0;  // used for idx
        npr[1] = 1 + gn/2;  // first row
        int i{};
        for(i=2; i<numRows; ++i)
            npr[i] = gn;
        if(int tail {(n-1)%m}; tail!=0){
            if(gn%2 == 0){  // even group
                for(i=2; (tail!=0)&&(i<numRows); ++i){
                    ++npr[i];
                    --tail;
                }
            }else{  // odd group
                for(i=numRows-1; (tail!=0)&&(i>1); --i){
                    ++npr[i];
                    --tail;
                }
            }
        }
        // one pass
        for(i=2; i<numRows; ++i)
            npr[i] += npr[i-1];
        int step{}, crow{};
        string rtv;
        rtv.resize(n);
        for(auto c: s){
            rtv[npr[crow]++] = c;
            crow = (step/m)%2 ? crow-1 : crow+1;
            ++step;
        }
        return rtv;
    }
};

C

毫无惊喜的C版本。

有个坑：返回的是一个字符串指针，在申请内存的时候，要n+1，并且用0结尾！这就是C语言非常容易出错的地方！strlen得到的长度，并不包含最后的0。

char* convert(char *s, int numRows){
    if(numRows == 1)
        return s;
    int n = strlen(s);
    int m = numRows - 1;
    int gn = (n-1) / m;
    int npr[numRows];
    npr[0] = 0;
    npr[1] = 1 + gn/2;
    int i;
    for(i=2; i<numRows; ++i)
        npr[i] = gn;
    int tail = (n-1) % m;
    if(tail!=0){
        if(gn%2 == 0){
            for(i=2; (tail!=0)&&(i<numRows); ++i){
                ++npr[i];
                --tail;
            }
        }else{
            for(i=numRows-1; (tail!=0)&&(i>1); --i){
                ++npr[i];
                --tail;
            }
        }
    }
    for(i=2; i<numRows; ++i)
        npr[i] += npr[i-1];
    int step, crow;
    step = crow = 0;
    char *rtv = (char*)malloc(n+1); // n+1 
    for(i=0; i<n; ++i){
        rtv[npr[crow]++] = s[i];
        crow = (step++/m)%2 ? crow-1 : crow+1;
    }
    rtv[n] = '\x00';
    return rtv;
}

官方思路01

准备一个matrix空间，沿着zigzag的路经，将字符填入matrix，最后再按行重新读取一遍。

lc06_zigzag.jpg

我喜欢这个算法思路，因为它可以让代码简单清晰易懂，现在内存这么便宜......我开始讨厌我自己设计的第1个算法了，我都看不懂是怎么计算的了.....

Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        #gz = [[] for _ in range(numRows)]
        gz = [""] * numRows
        j, step = 0, -1
        for c in s:
            # gz[j].append(c)
            gz[j] += c
            step = -step if j%(numRows-1)==0 else step
            j += step
        #return ''.join([''.join(r) for r in gz])
        return ''.join(gz)

注释掉的是list版本，放开的str版本。

C++

class Solution {
public:
    string convert(string s, int numRows) {
        if((numRows==1) || (numRows>=(int)s.size()))       
            return s;
        vector<string> gz(numRows);
        int j {};
        int step {-1};
        for(auto c: s){
            gz[j] += c;
            step = j%(numRows-1)==0 ? -step : step;
            j += step;
        }
        string r;
        for(j=0; j<numRows; ++j)
            r += gz[j];
        return r;
    }
};

C

char* convert(char *s, int numRows){
    char *ps = s;
    int n = strlen(s);
    if((numRows==1) || (numRows>=n))
        return s;
    char (*gz)[n+1] = (char*)calloc(numRows, n+1);
    int *idx = (int*)calloc(numRows, sizeof(int));
    int j = 0;
    int step = -1;
    while(*ps){
        gz[j][idx[j]++] = *ps++;
        step = j%(numRows-1)==0 ? -step : step;
        j += step;
    }
    *s = 0;  // no need memset
    for(j=0; j<numRows; ++j)
        strcat(s, gz[j]);
    free(gz);
    free(idx);
    return s;
}

官方思路02

当我看到上面这张官方贴出来的图片，我意识到应该还有别的直接计算新index的方法，再草稿纸上简单算算，就能找到pattern。（所以自己画图一定要清楚呀......）

Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        n = len(s)
        if numRows == 1 or numRows >= n:
            return s
        rtv = []
        m = numRows - 1
        for row in range(numRows):
            rtv.append(s[row])
            i = 2
            if row in (0,m):
                while m*i+row < n:
                    rtv.append(s[m*i+row])
                    i += 2
                continue
            while True:
                if m*i-row < n: 
                    rtv.append(s[m*i-row])
                else:
                    break
                if m*i+row < n:
                    rtv.append(s[m*i+row])
                else:
                    break
                i += 2
        return ''.join(rtv)

按这个思路解出来，的确是快了一些。

发现numRows >= n也是一个可以直接return的条件。

虽然代码是双重循环，但官方对这个逻辑的时间复杂度分析，依然是\(O(n)\)，它是这么说的：We iterate over each index of the input only once and perform constant work at each index.

C++

class Solution {
public:
    string convert(string s, int numRows) {
        int n {(int)s.size()};
        if((numRows==1) || (numRows>=n))       
            return s;
        int m {numRows-1};
        string rtv;
        rtv.reserve(n);
        int i;
        for(int row{}; row<numRows; ++row){
            rtv.append(1,s[row]);
            i = 2;
            if((row==0) || (row==m)){
                while(m*i+row < n){
                    rtv.append(1,s[m*i+row]);
                    i += 2;
                }
                continue;
            }
            while(1){
                if(m*i-row < n)
                    rtv.append(1,s[m*i-row]);
                else
                    break;
                if(m*i+row < n)
                    rtv.append(1,s[m*i+row]);
                else
                    break;
                i += 2;
            }
        }
        return rtv;
    }
};

string对象的append接口会改变size，所以前面要用reserve。

C

char* convert(char *s, int numRows){
    int n = strlen(s);
    if((numRows==1) || (numRows>=n))
        return s;
    int m = numRows - 1;
    char *rtv = (char*)malloc(n+1);
    int i;
    for(int row=0,idx=0; row<numRows; ++row){
        rtv[idx++] = s[row];
        i = 2;
        if((row==0) || (row==m)){
            while(m*i+row < n){
                rtv[idx++] = s[m*i+row];
                i += 2;
            }
            continue;
        }
        while(1){
            if(m*i-row < n)
                rtv[idx++] = s[m*i-row];
            else
                break;
            if(m*i+row < n)
                rtv[idx++] = s[m*i+row];
            else
                break;
            i += 2;
        }
    }
    rtv[n] = '\x00';
    return rtv;
}

本文链接：https://cs.pynote.net/ag/leetcode/202211291/

-- EOF --

-- MORE --

CS笔记 Since 2021.9
Powered by Python & Markdown