LeetCode 刷题笔记——day 5
LeetCode 刷题笔记——day 5
6. Z 字形变换
难度:中等
将一个给定字符串 s
根据给定的行数 numRows
,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING"
行数为 3
时,排列如下:
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
示例 3:
输入:s = "A", numRows = 1
输出:"A"
提示:
1 <= s.length <= 1000
s
由英文字母(小写和大写)、','
和'.'
组成1 <= numRows <= 1000
我的答案
思路: 首先,因为在行数大于等于字符串长度或者行数为 1 的时候,输出字符串本身即可,所以在第一步就直接判断两种情况并返回,节省程序运行时间,然后把 Z 字形字符串以第一行为界分为几个小区间,在每个小区间内遍历字符并分配到所在行数,最终把所有行字符串相加即可。
class Solution {
public:
string convert(string s, int numRows) {
if(s.size() <= numRows || numRows == 1) {
return s;
}
vector<string> str(numRows);
int n = (numRows - 1) * 2;
for(int i = 0; i < s.size(); i += n) {
int m = 0;
for(int j = 0; i + j < s.size() && j < n; j++) {
if(j <= n / 2) {
m = j;
} else {
m--;
if(m == 0) {
break;
}
}
str[m] += s[i + j];
}
}
string s0 = "";
for(int i = 0; i < numRows; i++) {
s0 += str[i];
}
return s0;
}
};
- 执行用时: 8 ms
- 内存消耗: 10.5 MB
官方答案
老实说,我觉得我的解法还行,不过还是看看官方题解。官方题解里依然给出了两种方法:
按行排序
思路 通过从左向右迭代字符串,我们可以轻松地确定字符位于 Z 字形图案中的哪一行。 算法 我们可以使用min(numRows,len(s) 个列表来表示 Z 字形图案中的非空行。 从左到右迭代sss,将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。 只有当我们向上移动到最上面的行或向下移动到最下面的行时,当前方向才会发生改变。 作者:LeetCode
这里用 C++ 复现了一遍官方解法:
class Solution {
public:
string convert(string s, int numRows) {
if(numRows >= s.size() || numRows == 1) {
return s;
}
vector<string> str(numRows);
int i = 0;
bool m = false;
for(char c : s) {
str[i] += c;
if(i == 0 || i == numRows - 1) m = !m;
i += m ? 1 : -1;
}
string s0;
for(string st : str) s0 += st;
return s0;
}
};
- 执行用时: 12 ms
- 内存消耗: 10.4 MB
官方题解中第一步只判断输出了行数为 1 的情况,增加
numRows >= s.size()
判断,也算是难得给官方升级一下。
同样练习练习用 Java 来实现一遍:
class Solution {
public String convert(String s, int numRows) {
if (numRows >= s.length() || numRows == 1) return s;
List<StringBuilder> strs = new ArrayList<>();
for(int i = 0; i < numRows; i++) strs.add(new StringBuilder());
int n = 0;
boolean m = false;
for(char c : s.toCharArray()) {
strs.get(n).append(c);
if(n == 0 || n == numRows - 1) m = !m;
n += m ? 1 : -1;
}
StringBuilder str = new StringBuilder();
for(StringBuilder sb : strs) str.append(sb);
return str.toString();
}
}
- 执行用时: 5 ms
- 内存消耗: 39 MB
官方给出的第二种解法是:
按行访问
思路 按照与逐行读取 Z 字形图案相同的顺序访问字符串。 算法 首先访问
行 0
中的所有字符,接着访问行 1
,然后行 2
,依此类推… 对于所有整数k,
作者:LeetCode
这里用 C++ 复现了一遍官方代码:
class Solution {
public:
string convert(string s, int numRows) {
if(numRows >= s.size() || numRows == 1) {
return s;
}
string str;
int n = s.size();
int m = 2 * numRows - 2;
for(int i = 0; i < numRows; i++) {
for(int j = 0; j + i < n; j += m) {
str += s[j + i];
if(i != 0 && i != numRows -1 && j + m - i < n) str += s[j + m - i];
}
}
return str;
}
};
- 执行用时: 4 ms
- 内存消耗: 8 MB
不得不说,效率提升很多啊。
继续练习一遍 Java 实现:
class Solution {
public String convert(String s, int numRows) {
if (numRows >= s.length() || numRows == 1) return s;
StringBuilder sb = new StringBuilder();
int n = s.length();
int m = 2 * numRows - 2;
for(int i = 0; i < numRows; i++) {
for(int j = 0; j + i < n; j += m) {
sb.append(s.charAt(j + i));
if(i != 0 && i != numRows - 1 && j + m - i < n) sb.append(s.charAt(j + m - i));
}
}
return sb.toString();
}
}
- 执行用时: 2 ms
- 内存消耗: 38.8 MB
总结 虽然说,我觉得我的代码还是挺不错的,但是学习完两种方法之后,貌似,我只是将两种方法的缺点组合在了一起。思路还好,但是实现过程实在算不上是丝滑。
相关文章
- LeetCode每日一题-9:替换后的最长重复字符串
- LeetCode笔记:Weekly Contest 308
- ☆打卡算法☆LeetCode 211. 添加与搜索单词 - 数据结构设计 算法解析
- LeetCode笔记:Biweekly Contest 86
- LeetCode笔记:Weekly Contest 310
- LeetCode笔记:Weekly Contest 312
- LeetCode笔记:Weekly Contest 304
- Leetcode 5:最长回文子串(最详细的解法!!!)[通俗易懂]
- LeetCode周赛295,赛后看了大佬的代码,受益良多……
- ☆打卡算法☆LeetCode 198. 打家劫舍 算法解析
- leetcode-2两数相加[通俗易懂]
- LeetCode 刷题笔记——并查集
- LeetCode 7. 整数反转
- leetcode-142. 环形链表 II
- 太全了!字节总监总结240道算法LeetCode刷题笔记
- 【day08】LeetCode(力扣)每日一刷[409. 最长回文串 ][144. 二叉树的前序遍历][589. N 叉树的前序遍历 ]
- LeetCode周赛331,思维题训练场
- LeetCode-分治
- JavaScript刷LeetCode-字符串类解题技巧4
- LeetCode | 搜索插入位置
- JavaScript刷LeetCode拿offer-双指针技巧(上)_2023-03-15