最近，「在華為，請假一天的代價是3700」的貼文在網路上引發了熱烈討論。

一位華為員工的分享，透露在華為，因為請假會影響到每月的獎金和年終獎，許多員工寧願選擇利用周末加班來「調休」，以避免請假對收入的影響。在華為，周末加班的報酬是雙倍薪資。

換句話說，一天的請假，相當於放棄了兩天的雙倍日薪資。根據這位員工的描述，我們可以粗略估計，華為員工的月基礎薪資約為37000元。

這一訊息一經釋出，立即在網上引起了廣泛的討論。有人感嘆華為員工的高收入，有人則對比自己公司的請假政策，感慨萬千。

尤其是那句「這麽高的base，不是月薪3k的我應該討論的事情」，更是引發了不少網友的共鳴，笑談中透露出對高收入群體生活的遙遠想象。

但不可否認，這樣的請假代價確實很高，足以讓人感到「請假很心痛」。

下面是今日演算法題

今日演算法題，來自LeetCode的第6題：Z 字形變換，下面是我的演算法思路及實作，讓我們來看看吧。

# 演算法題目

將一個給定字串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。

比如輸入字串為 "PAYPALISHIRING"，行數為 3 時，排列如下：

PA H NAP L S I I GYI R

之後，你的輸出需要從左往右逐行讀取，產生出一個新的字串，如上例則為 "PAHNAPLSIIGYIR"。

# 演算法思路

實作Z字形變換的關鍵是找到字元在Z字形排列中的規律，然後根據這個規律來重構字串。以下是解決這個問題的步驟：

1. 建立行字串：根據給定的行數，建立相同數量的字串，用於存放每一行的字元。

2. 定位行索引：初始化當前行的索引為0，並設定一個標誌位用於指示索引移動的方向（向下或向上）。

3. 遍歷字元：遍歷輸入字串中的每一個字元，並將它添加到對應行的字串上。

# 程式碼實作

C語言實作

#include<string.h>#include<stdlib.h>char* convert(char* s, int numRows){if (numRows == 1 || numRows >= strlen(s)) return s;char **rows = malloc(numRows * sizeof(char*));for (int i = 0; i < numRows; i++) { rows[i] = malloc((strlen(s) + 1) * sizeof(char)); rows[i][0] = '\0'; }int curRow = 0;int step = -1;for (int i = 0; s[i] != '\0'; i++) {strcat(rows[curRow], (char[]){s[i], '\0'});if (curRow == 0 || curRow == numRows - 1) step = -step; curRow += step; }char *ret = malloc((strlen(s) + 1) * sizeof(char)); ret[0] = '\0';for (int i = 0; i < numRows; i++) {strcat(ret, rows[i]);free(rows[i]); }free(rows);return ret;}

Java實作

public String convert(String s, int numRows){if (numRows == 1 || numRows >= s.length()) {return s; } StringBuilder[] rows = new StringBuilder[numRows];for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();int curRow = 0;boolean goingDown = false;for (char c : s.toCharArray()) { rows[curRow].append(c);if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; curRow += goingDown ? 1 : -1; } StringBuilder ret = new StringBuilder();for (StringBuilder row : rows) ret.append(row);return ret.toString();}

‍

Python實作

defconvert(s: str, numRows: int) -> str:if numRows == 1or numRows >= len(s):return s rows = [''] * numRows curRow, step = 0, -1for c in s: rows[curRow] += cif curRow == 0or curRow == numRows - 1: step = -step curRow += stepreturn''.join(rows)

# 演算法解析

Z字形變換演算法的時間復雜度為O(n)，其中n是輸入字串的長度，因為每個字元只被處理一次。空間復雜度也為O(n)，用於儲存重構後的字串。

# 範例和測試

輸入：s = "PAYPALISHIRING", numRows = 3輸出："PAHNAPLSIIGYIR"

# 總結

Z字形變換問題展示了如何透過找到字元間的規律來解決問題，它不僅鍛煉了我們對字串的處理能力，還教會我們如何將看似復雜的問題簡化。掌握這種方法，可以幫助我們更好地解決其他字串處理問題。

熱門推薦