程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> ZigZag排列問題與經典筆試面試題目解析

ZigZag排列問題與經典筆試面試題目解析

編輯：關於C++

一、圖像壓縮編碼中的Z字排序

JPEG（Joint Photographic ExpertsGroup）是一種常見的圖像文件格式，也是目前靜態圖像中壓縮比最高的一種圖像文件格式，它綜合運用了多種壓縮技術而達到一種極高的壓縮比例。JPEG是作為一個國際數字圖像壓縮標准，壓縮技術十分先進，它用有損壓縮方式去除冗余的圖像和彩色數據，獲取得極高的壓縮率的同時能展現十分豐富生動的圖像。目前，它已被廣泛地應用與多媒體和網絡程序中。通常，在JEPG編碼過程中，有一個非常重要的步驟，即Z字形編排過程。Z字形編排過程大致是這樣的：經過前期處理的圖像被分為若干個的小圖像塊，此時就從小圖像塊的左上角開始沿Z字形對圖像元素進行遍歷，並將遍歷所得的結果重新寫入等大小的圖像塊中，整個過程如圖2-15所示。

要實現這樣一個Z字形排列可能讀者咋一看會感覺無從下手。但是在分析了Z字形遍歷原矩陣過程中的走向規律，其實可以設計一個非常簡單的算法來實現這種編排。對於原始矩陣matrix中的任意元素matrix[i][j]的遍歷走向規律可以分為如下三種情況
<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD7I57n7tv7OrMr91+nW0LXE1KrL2G1hdHJpeFtpXVtqXdbQ193X+LHqasrHxbzK/aOsx9JpPTC78tXfaT03o6zEx8O0senA+sK3vrbU2r7Y1fPW0LXE19/P8r7NysfLrsa9z/LT0tLGtq/Su7jxoaPI57n7tv7OrMr91+nW0LXE1KrL2G1hdHJpeFtpXVtqXdbQ193X+LHqacrHxubK/aOsx9JqPTC78tXfaj03o6yjrMTHw7Sx6cD6wre+ttTavtjV89bQtcTX38/yvs3Kx7S51rHP8s/C0sa2r9K7uPGho7P9yc/K9rnm1PLS1M3itcTH6b/2o6zI57n7tv7OrMr91+nW0LXE1KrL2G1hdHJpeFtpXVtqXbXEuuHX3df4seq6zWkrasrHxbzK/aOs1PKx6cD6wre+ttTavtjV89bQtcTX38/yvs3Kx9PSyc+9x9LGtq/Su7jxo7u38dTyo6zI9GkrasrHxubK/aOs1PKx6cD6wre+ttTavtjV89bQtcTX38/yvs3Kx9fzz8K9x9LGtq/Su7jxoaM8cD67+dPayc/K9tSt1PKjrM3qs8m+2NXzWtfW0M6x4MXFuabE3LXEtPrC68fltaXI58/CoaM8L3A+PHA+PC9wPjxwcmUgY2xhc3M9"brush:java;">#include #include using namespace std; #define SIZE 8 int main(int argc, char** argv) { int matrix[SIZE][SIZE] = {0}; int a[SIZE][SIZE] = {0}; int i, j, x, y, value = 0; int * p; p = &matrix[0][0]; //初始化矩陣 for(i = 0; i
請讀者完成編碼後編譯運行程序，並觀察輸出結果。此外，這個算法不僅對8×8的矩陣有效，對於SIZE取其他值仍然有效，讀者不妨試試看。

---------------------------------

以上內容本來收錄在我的新書《算法之美——隱匿在數據結構背後的原理（C++版）》中，該書目前仍在編輯過程中，還未上市銷售。小秀一下出版社給的封面方案先

---------------------------------

二、一道經典面試題解析

Leetcode 是一個美國的在線編程網站，上面主要收集了各大IT公司的筆試面試題，對於應屆畢業生找工作是一個不可多得的好幫手。我相信很多有求職需求的讀者都刷過Leetcode上面的題目。不過，因為我個人並沒有求職的需求，可能也離這個時期太遙遠，所以之前一直不知道這個網站的存在，實在孤陋寡聞 :（。

上面那本書還沒有上市，之所以會想到把Z字編排問題拉出來講一講，也是因為最近有朋友推薦我看下Leetcode網站。而且剛好看到和上面Z字編排問題非常類似的一道經典面試題目。當然二者也還是有區別的，可以將它們歸為同一類型的題目。類似的，其實還可以給出其他變種題型。先給出題目如下：

或者你可以訪問：https://leetcode.com/problems/zigzag-conversion/

索性我也來試做一下，還好寶刀未老，基本上Leetcode是將其分類為難度系數Easy類的題目，基本上感覺題目難度確實不大，但是還是要做到考慮全面，有一些細節上第一次做很可能考慮不到而不能通過Online 測試。現在，特與各位分享一下我的解答。代碼若有欠缺之處，還望高手賜教（C++實現）。

class Solution {
public:
    string convert(string s, int numRows) {
    	int s_c = sizeof(char);
        int length = s.length();
        int num = 1;       
        if (numRows*2-2 != 0)
        	num = 1 + (length/(numRows*2-2));
        else 
        	num = 1 + length;
        
        char * matrix = new char[numRows*s_c*num*2];
        int index = 0;
		
		//Initialize the string
       for(int j = 0; j < numRows; j++)
			for(int i = 0; i < num*2; i++)
				matrix[j*num*2*s_c + i*s_c] = ' ';
        
        for(int i = 0; i < num*2; i++){
        	if (i%2 == 0){
			    for(int j = 0; j < numRows; j++){
			    	if(s[index] != '\0'){
			    		matrix[j*num*2*s_c + i*s_c] = s[index];
						index ++;
					}
				}
			}
			else if(i%2 == 1){
				for(int j = 0; j < numRows; j++){
			    	if(s[index] != '\0' && j != 0 && j != numRows-1) {
			    		matrix[(numRows-j-1)*num*2*s_c + i*s_c] = s[index];
						index ++;
					}
				}	
			}
		}	
		
		string result = "";
		for(int j = 0; j < numRows; j++){
			for(int i = 0; i < num*2; i++){
				if(matrix[j*num*2*s_c + i*s_c] != ' ')
					result.append(1, matrix[j*num*2*s_c + i*s_c]);
			}
		}
		
		delete [] matrix;
		return result;
    }
};

這個網站的的好處在於它會告訴你測試數據以及你的輸出和正確的輸出是什麼，方便大家調試學習。目前，支持C、C++、Java、Python、Ruby等多種語言。另外它是支持在線編輯，還提供了一個在線運行環境，可以直接看到運行結果。對於有興趣刷題目或者正在求職過程中的同學，我也推薦這個資源！