LeetCode-6.Z 字形变换 - 消费补偿算法
原创LeetCode-6.Z 字形变换 - 消费补偿算法
原创
题目
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例：
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
解决这题的关键是找到每一行的字符位置规律，根据分析可以知道：
第一行和最后一行的字符位置相差 2*numRows-2，如下图所示：
而对于其他行来说，字符位置加4会略过当前行的一个字符。如下图所示：
先定义一个money作为这个跨度，即int money = 2*numRows-2，定义 j 为要访问的s字符串的字符下标。
然后，我打算对当前行做一个"补偿"，即让他倒退2个位置。即j = j + money - (2*i - 2)，这样一来，T的位置就可以在E的基础上算出来（j=1, money=4）： 1+4-(2*2-2)=3。
你可以理解为原来我要消费money块钱，现在我补偿回一些钱给你。那么在下次消费时，就要恰好把money消费完。即：money -= money - (2*i - 2)，即money=4-(2*2-2)=2，这样就可以访问到O字符了。
这个算法，我称之为消费补偿算法，还没有看题解，不知道其他大佬的思想是不是类似。下面贴我的代码：
#include <iostream>
#include <string>
using namespace std;
/**
* LeetCode
* 6. Z 字形变换
* https://space.bilibili.com/54183978
*/
class Solution {
public:
string convert(string s, int numRows) {
int size = s.size();
string ans = "";
if(numRows == 1){
return s;
}
for(int i = 1; i <= numRows; i++){
// 加第i行字符
int j = i - 1;
// 每行第一个字符
ans += s[j];
int money = 2*numRows-2;
while(j < size){
if(money == 2*numRows-2 && i!=numRows){
// 消费补偿
j = j + money - (2*i - 2);
if(j >= size){
break;
}
ans += s[j];
money -= money - (2*i - 2);
} else{
// 消费剩余
j = j + money;
if(j >= size){
break;
}
ans += s[j];
money = 0;
}
if(money == 0){
money = 2*numRows-2;
}
}
}
return ans;
}
};
int main(){
Solution solution;
cout << solution.convert("LEETCODEISHIRING", 3);
}下面是代码评测结果：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。