アルゴリズム問題C+(二)

このブログの目次

回転印字マトリクス

回転正方形行列

「之」字形印刷マトリクス

反転一方向チェーンテーブル

秩序チェーンテーブルの共通部分

を印刷する.

チェーンテーブルが返信構造であるか否かを判断する

.
ロータリプリントマトリクス
整列マトリクスを指定し、時計回りに回転してマトリクスを印刷します.

class printCircleMatrix
{
public:
	printCircleMatrix();
	~printCircleMatrix();
	/*
	     
	        ，     +1，   -1
	    ，                
	*/

	void print(int matrix[3][4], int row, int column) {
		int tR = 0;
		int tC = 0;
		int dR = row - 1;
		int dC = column - 1;
		while (tR <= dR && tC <= dC) {
			printEdage(matrix, tR++, tC++, dR--, dC--);
		}
	}

	/*
	      
	      
	1.        
	2.        
	3.         
	          ，                  
	         （0，0）
	*/
	void printEdage(int matrix[3][4], int tR, int tC, int dR, int dC) {
		if (tR == dR) {
			for (int i = tC; i <= dC; i++) {
				cout << matrix[tR][i] << " ";
			}
		}
		else if (tC == dC) {
			for (int i = tR; i <= dR; i++) {
				cout << matrix[i][tC];
			}
		}
		else {
			int curC = tC;  //      
			int curR = tR;  //      
			while (curC != dC) {
				cout << matrix[tR][curC++] << " ";
			}
			while (curR != dR) {
				cout << matrix[curR++][dC] << " ";
			}
			while (curC != tC) {
				cout << matrix[dR][curC--] << " ";
			}
			while (curR != tR) {
				cout << matrix[curR--][tC] << " ";
			}
		}
	}
};

かいてんせいほうけいマトリクス
正方形マトリクスが与えられ、時計回りに90度回転します.

class rotateMatrix
{
public:
	rotateMatrix();
	~rotateMatrix();
	
	void rotate(int** arr, int size) {
		int tR = 0;
		int tC = 0;
		int dR = size - 1;
		int dC = size - 1;
		while (tR <= dR) {
			rotateEdge(arr, tR++, tC++, dR--, dC--);
		}
	}

	void rotateEdge(int** arr, int tR, int tC, int dR, int dC) {
		int times = dR - tR;
		int tmp = 0;
		for (int i = 0; i != times; i++) {
			tmp = arr[tR][tC + i];
			arr[tR][tC + i] = arr[dR - i][tC];
			arr[dR - i][tC] = arr[dR][tC - i];
			arr[dR][tC - i] = arr[tR + i][dC];
			arr[tR + i][dC] = tmp;
		}
	}
};

フォント印刷マトリックス
マトリクスを指定し、その文字に従ってマトリクスを印刷します.

class zigZagPrint
{
public:
	zigZagPrint();
	~zigZagPrint();

	void print(int **arr, int row, int column) {
		int tR = 0;
		int tC = 0;
		int dR = 0;
		int dC = 0;
		int endR = row - 1;
		int endC = column - 1;
		bool fromUp = false;
		while (tR != endR + 1) {
			printLevel(arr, tR, tC, dR, dC, fromUp);
			tR = tC == endC ? tR + 1 : tR;
			tC = tC == endC ? tC : tC + 1;
			dC = dR == endR ? dC + 1 : dC;
			dR = dR == endR ? dR : dR + 1;
			fromUp = !fromUp;
		}
	}

	void printLevel(int **arr, int tR, int tC, int dR, int dC, bool fromUp) {
		if (fromUp) {
			while (tR != dR + 1) {
				cout << arr[tR++][tC--] << " ";
			}
		}
		else {
			while (dR != tR - 1) {
				cout << arr[dR--][dC++] << " ";
			}
		}
	}
};

逆一方向チェーンテーブル
チェーンテーブルを反転させる関数

class reverseList
{
public:
	reverseList();
	~reverseList();
	
	/*
	     
	*/
	ListNode* reverse(ListNode* head) {
		if (head == NULL || head->next == NULL) {
			return head;
		}
		ListNode* pre = NULL;
		ListNode* next = NULL;
		while (head != NULL) {
			next = head->next;
			head->next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}

	/*
	    
	*/
	ListNode* recuision(ListNode* head) {
		if (head == NULL || head->next == NULL) {
			return head;
		}
		ListNode* reverseHead = recuision(head);
		head->next->next = head;
		head->next = NULL;
		return reverseHead;
	}
};

2つの順序付きチェーンテーブルの共通部分を印刷

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
		val(x), next(NULL) {
	}
};

class printCommonPart
{
public:
	printCommonPart();
	~printCommonPart();
	
	void print(ListNode* head1, ListNode* head2) {
		vector tmp;
		ListNode* node1 = head1;
		ListNode* node2 = head2;
		while (node1 != NULL && node2 != NULL) {
			if (node1->val < node2->val) {
				node1 = node1->next;
			}
			else if (node1->val > node2->val) {
				node2 = node2->next;
			}
			else {
				tmp.push_back(node1->val);
				node1 = node1->next;
				node2 = node2->next;
			}
		}
		for (int i = 0; i < tmp.size(); i++) {
			cout << tmp[i] << " ";
		}
	}
};

チェーンテーブルが返信構造であるかどうかを判断する

struct ListNode
{
	int val;
	struct ListNode* next;
};

class isPalindromeList
{
public:
	isPalindromeList();
	~isPalindromeList();
	
	//  O(N)
	bool isPalindrome1(ListNode* head) {
		stack tmp;
		ListNode* cur = head;
		while (cur != NULL) {
			tmp.push(cur->val);
			cur = cur->next;
		}
		cur = head;
		while (cur != NULL) {
			if (cur->val != tmp.top()) {
				return false;
			}
			else {
				tmp.pop();
				cur = cur->next;
			}
		}
		return true;
	}

	//  O(N/2)
	/*
	      ，     ，     
	        ，        
	        ，       ，   node         ，        ，         
	       ，    
	*/
	bool isPalindrome2(ListNode* head) {
		if (head == NULL || head->next == NULL) {
			return true;
		}
		ListNode* slow = head;
		ListNode* fast = head;
		while (slow != NULL && fast != NULL) {
			slow = slow->next;
			fast = fast->next->next;
		}
		stack tmp;
		while (slow != NULL) {
			tmp.push(slow->val);
			slow = slow->next;
		}
		slow = head;
		while (!tmp.empty()) {
			if (slow->val != tmp.top()) {
				return false;
			}
			else {
				tmp.pop();
				slow = slow->next;
			}
		}
		return true;
	}

	//  O(1)
	/*
	      ，     ，     
	        ，        
	        ，       ，   node         ，        ，         
	        
	      
	  ，             
	*/
	bool isPalindrome3(ListNode* head) {
		if (head == NULL || head->next == NULL) {
			return true;
		}
		ListNode* cur = head;
		ListNode* fast = head;
		while (fast != NULL) {
			cur = cur->next;
			fast = fast->next->next;
		}
		ListNode* pre = NULL;
		while (cur != NULL) {
			ListNode* next = cur->next;
			cur->next = pre;
			pre = cur;
			cur = next;
		}
		ListNode* last = pre;
		cur = head;
		bool isP = true;
		while (last != NULL) {
			if (cur->val != last->val) {
				isP = false;
				break;
			}
			cur = cur->next;
			last = last->next;
		}
		cur = pre;
		pre = NULL;
		while (cur != NULL) {
			ListNode* next = cur->next;
			cur->next = pre;
			pre = cur;
			cur = next;
		}
		return isP;
	}
};

リファレンス
牛客網左程雲アルゴリズム授業