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

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

編輯：C++入門知識

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

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

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

要實現這樣一個Z字形排列可能讀者咋一看會感覺無從下手。但是在分析了Z字形遍歷原矩陣過程中的走向規律，其實可以設計一個非常簡單的算法來實現這種編排。對於原始矩陣matrix中的任意元素matrix[i][j]的遍歷走向規律可以分為如下三種情況

如果二維數組中的元素matrix[i][j]中縱坐標j是偶數，且i=0或者i=7，那麼遍歷路徑在矩陣中的走向就是水平向右移動一格。如果二維數組中的元素matrix[i][j]中縱坐標i是奇數，且j=0或者j=7，，那麼遍歷路徑在矩陣中的走向就是垂直向下移動一格。除上述規則以外的情況，如果二維數組中的元素matrix[i][j]的橫縱坐標和i+j是偶數，則遍歷路徑在矩陣中的走向就是右上角移動一格；否則，若i+j是奇數，則遍歷路徑在矩陣中的走向就是左下角移動一格。

基於上述原則，完成矩陣Z字形編排功能的代碼清單如下。

#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++實現）。

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD48cHJlIGNsYXNzPQ=="brush:java;">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;
    }
};