C++中的Z字形變換問題
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"
思路/解法
模擬法,根據所給條件,線性處理即可(Z字形存在一定規律,每當固定的條件後前進方向進行轉變)。
class Solution { public: string convert(string s, int numRows) { int rows = numRows; int columns = ((s.length() / (2 * rows - 1)) + 1) * rows;//盡可能縮小所使用的空間,這裡columns可優化,並未精確求解 std::vector<std::vector<char>> arrs(rows, std::vector<char>(columns)); //初始化 for (int i = 0; i < rows; i++) for (int j = 0; j < columns; j++) arrs[i][j] = '0'; int x = 0, y = 0; int index = 0; while (index < s.length()) { if (index < s.length() && x < rows) arrs[x++][y] = s[index++]; if (index < s.length() && x == rows) { //更新x和y y++; x -= 2; while (index < s.length() && x > 0) arrs[x--][y++] = s[index++]; x = 0;//重置x } } std::string res; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (arrs[i][j] != '0' && arrs[i][j] != '\0') res.push_back(arrs[i][j]); } } return res; } };
到此這篇關於C++中的Z字形變換的文章就介紹到這瞭,更多相關C++ Z字形變換內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(6.字型轉換字符串)
- C++驗證LeetCode包圍區域的DFS方法
- C++實現LeetCode(49.群組錯位詞)
- C++實現LeetCode(Combinations 組合項)
- C++實現LeetCode(241.添加括號的不同方式)