LeetCode-6.Z 字形變換 - 消費補償算法

解決這題的關鍵是找到每一行的字元位置規律，根據分析可以知道：

第一行和最後一行的字元位置相差

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);
}