C++实现LeetCode(6.字型转换字符串)

[LeetCode] 6. ZigZag Conversion 之字型转换字符串

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"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

这道题刚开始看了半天没看懂是咋样变换的，上网查了些资料，终于搞懂了，就是要把字符串摆成一个之字型的，比如有一个字符串 "0123456789ABCDEF"，转为 zigzag 如下所示：

当 n = 2 时：

0 2 4 6 8 A C E

1 3 5 7 9 B D F

当 n = 3 时：

0   4    8     C

1 3 5 7 9 B D F

2    6   A     E

当 n = 4 时：

0     6        C

1   5 7   B  D

2 4   8 A    E

3      9       F

可以发现，除了第一行和最后一行没有中间形成之字型的数字外，其他都有，而首位两行中相邻两个元素的 index 之差跟行数是相关的，为  2*nRows - 2, 根据这个特点，可以按顺序找到所有的黑色元素在元字符串的位置，将他们按顺序加到新字符串里面。对于红色元素出现的位置（Github 上可能无法正常显示颜色，请参见博客园上的帖子）也是有规律的，每个红色元素的位置为 j + 2 x numRows-2 - 2 x i, 其中，j为前一个黑色元素的 index，i为当前行数。 比如当 n = 4 中的那个红色5，它的位置为 1 + 2 x 4-2 - 2 x 1 = 5，为原字符串的正确位置。知道了所有黑色元素和红色元素位置的正确算法，就可以一次性的把它们按顺序都加到新的字符串里面。代码如下：

解法一：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) return s;
        string res;
        int size = 2 * numRows - 2, n = s.size();
        for (int i = 0; i < numRows; ++i) {
            for (int j = i; j < n; j += size) {
                res += s[j];
                int pos = j + size - 2 * i;
                if (i != 0 && i != numRows - 1 && pos < n) res += s[pos];
            }
        }
        return res;
    }
};

若上面解法中的规律不是很好想的话，我们也可以用下面这种更直接的方法来做，建立一个大小为 numRows 的字符串数组，为的就是把之字形的数组整个存进去，然后再把每一行的字符拼接起来，就是想要的结果了。顺序就是按列进行遍历，首先前 numRows 个字符就是按顺序存在每行的第一个位置，然后就是 ‘之' 字形的连接位置了，可以发现其实都是在行数区间 [1, numRows-2] 内，只要按顺序去取字符就可以了，最后把每行都拼接起来即为所求，参见代码如下：

解法二：

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) return s;
        string res;
        int i = 0, n = s.size();
        vector<string> vec(numRows);
        while (i < n) {
            for (int pos = 0; pos < numRows && i < n; ++pos) {
                vec[pos] += s[i++];
            }
            for (int pos = numRows - 2; pos >= 1 && i < n; --pos) {
                vec[pos] += s[i++];
            }
        }
        for (auto &a : vec) res += a;
        return res;
    }
};

到此这篇关于C++实现LeetCode(6.字型转换字符串)的文章就介绍到这了,更多相关C++实现字型转换字符串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(7.翻转整数)

    [LeetCode] 7. Reverse Integer 翻转整数 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment whi

  • C++实现LeetCode(131.拆分回文串)

    [LeetCode] 131.Palindrome Partitioning 拆分回文串 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"

  • C++实现LeetCode(验证回文字符串)

    [LeetCode] 125.Valid Palindrome 验证回文字符串 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a

  • C++实现LeetCode(132.拆分回文串之二)

    [LeetCode] 132.Palindrome Partitioning II 拆分回文串之二 Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example: Input: "aab" Output: 1 Explan

  • C++实现LeetCode(9.验证回文数字)

    [LeetCode] 9. Palindrome Number 验证回文数字 Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left

  • C++实现LeetCode(647.回文子字符串)

    [LeetCode] 647. Palindromic Substrings 回文子字符串 Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of sa

  • C++实现LeetCode(6.字型转换字符串)

    [LeetCode] 6. ZigZag Conversion 之字型转换字符串 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  

  • PHP中IP地址与整型数字互相转换详解

    IP转换成整型存储是数据库优化一大趋势,不少人目前存储IP时还在使用字符串类型存储,字符串索引比整型索引消耗资源很多,特别是表中数据量大的时候,以及求查询某一个ip段的数据,今天说的ip是指ip4,ip6不在本文范围内. 系统函数ip2long与long2ip PHP中有内置函数ip2long可以将ip地址转换整型. 复制代码 代码如下: $ip = '210.110.11.49'; echo ip2long($ip); 输出: 复制代码 代码如下: -764540111 输出的整型有负号是因为

  • python使用str & repr转换字符串

    可能比较 low 还是记录一下: str 和 repr的使用过程 str 是一个类型 (int, long 类似), 同样她也可以作为一个工厂方法 实例一个 string repr 是python 内置的函数, 用于保留一个 打印值在python 代码片段里的真实状态 好,以上全是废话 >>> a = 1 >>> a + "" --------------------------------------------------------------

  • python转换字符串为摩尔斯电码的方法

    本文实例讲述了python转换字符串为摩尔斯电码的方法.分享给大家供大家参考.具体实现方法如下: chars = ",.0123456789?abcdefghijklmnopqrstuvwxyz" codes = """--..-- .-.-.- ----- .---- ..--- ...-- ....- ..... -.... --... ---.. ----. ..--.. .- -... -.-. -... . ..-. --. .... .. .-

  • java转换字符串编码格式的方法

    java转换字符串编码格式的方法

    java转换字符串编码格式 (解码错误,重新解码) 字符集概念:规定了某个文字对应的二进制数字存放方式(编码)和某串二进制数值代表了哪个文字(解码)的转换关系. 我们在计算机屏幕上看到的是实体化的文字,而在计算机存储介质中存放的实际是二进制的比特流. 乱码场景(纯属瞎掰): 1) 前台输入utf-8编码的一串汉字(string1). (页面编码为utf-8, 在内存中会将这串汉字以utf-8编码为对应的二进制流存储) 2) 这串汉字(string1)的二进制流在经过http协议传输到后台时,这段

  • C++ 整型与字符串的互转方式

    flyfish 字符串转整型 C的方法 cstr是char*或者const char*类型的字符串 int num = atoi(str); int num = strtol(cstr, NULL, 10); //10 表示进制 C++11的方法 void test1() { std::string str1 = "1"; std::string str2 = "1.5"; std::string str3 = "1 with words"; i

  • Python如何转换字符串大小写

    Python中的字符串方法是从python1.6到2.0慢慢加进来的,它们也被加到了Jython中.这些方法实现了string模块的大部分方法,如下表所示列出了目前字符串内建支持的方法,所有的方法都包含了对Unicode的支持,有一些甚至是专门用于Unicode的. 例如:s 是一个字符串变量 判断字符串的方法 s.isalnum() #所有字符都是数字或者字母 s.isalpha() #所有字符都是字母 s.isdigit() #所有字符都是数字 s.islower() #所有字符都是小写 s

  • C++实现LeetCode(97.交织相错的字符串)

    [LeetCode] 97.Interleaving String 交织相错的字符串 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = &quo

  • perl简单变量 整型 浮点数 字符串

    基本上,简单变量就是一个数据单元,这个单元可以是数字或字符串.一.整型 1.整型   PERL最常用的简单变量,由于其与其它语言基本相同,不再赘述.   例:   $x = 12345;   if (1217 + 116 == 1333) {   # statement block goes here   }  整型的限制:   PERL实际上把整数存在你的计算机中的浮点寄存器中,所以实际上被当作浮点数看待.在多数计算机中,浮点寄存器可以存贮约16位数字,长于此的被丢弃.整数实为浮点数的特例.2

随机推荐