データ構造:チェーン問題のまとめ

8761 ワード

［データ構造とアルゴリズム］

データ構造:チェーン問題のまとめ
いくつかのチェーンのテーマを使って、総括をします.
タイトルは
チェーンの操作自体が柔軟で、コード量が少ないです.
チェーンの基本的な操作、例えば添削して調べます.
この文章はチェーンを使っています.牛客ネットの構造です.以下の通りです.

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

チェーンのテーマで出会ったのは:

は、中間ノードなどのノードを探しています.最後からいくつかのノードです.チェーンテーブルにリングがあるかどうかを判断して、リングの入り口を探しています.

( ):チェーンを連結するときに使用できます.例えば、2つの順序付きチェーンを結合します.

は、チェーンテーブルを反転させ、nextポインタ領域を保存するように注意してください.そして、ノードの一つであるノードにしてください.

ととは、ターゲットを生成するためのチェーンテーブルであり、分割されたチェーンを連結しています.

他にもいくつかの追加があります.

テーマ:チェーン2つの共通部分を印刷します.

/*
	  :
	              .
	           
*/
vector printCommonPart(ListNode* head1, ListNode* head2) {
	vector res;
	if (head1 == NULL || head2 == NULL)
		return res;
	ListNode* p1 = head1;
	ListNode* p2 = head2;

	while (p1 != NULL&&p2 != NULL) {

		if (p1->val == p2->val) {
			res.push_back(p1->val);
			p1 = p1->next;
			p2 = p2->next;
		}
		else if (p1->val < p2->val) {
			p1 = p1->next;
		}
		else if (p1->val > p2->val) {
			p2 = p2->next;
		}
	}
	return res;
}

タイトル:シングルチェーンとダブルチェーンで最後からK番目のノードを削除します.

は、カウントによって、最後からK番目のノードの前駆

を見つける.

削除操作は、シングルチェーンとダブルチェーンの違いがあります.

//          ,      
/*
	     :     N,   K 
	1) NK,      ,1)    ,  k--
	          ,  k++,  k==0.     N-K   
*/
ListNode* RemoveLastKthNode(ListNode* &head, int lastKth) {
	if (head == NULL)
		return NULL;

	int k = lastKth;

	ListNode* cur = head;

	//      
	while (cur != NULL) {
		cur = cur->next;
		k--;
	}

	if (k == 0) {
		return head->next;
	}
	else if (k > 0) {
		return NULL;
	}
	else { // k<0
		cur = head;
		//   ++k      Kth   .
		//    k++,       Kth  
		while (++k != 0) {
			cur = cur->next;
		}
		ListNode* tobeDelete = cur->next;
		cur->next = tobeDelete->next;
		delete tobeDelete;
		tobeDelete = NULL;
		return head;
	}
}

DoubleLinkNode* RemoveLastKthNode(DoubleLinkNode* head, int lastKth) {

	if (head==NULL) {
		return NULL;
	}

	DoubleLinkNode* cur = head;
	int k = lastKth;

	while (cur != NULL) {
		cur = cur->next;
		k--;
	}

	if (k == 0) {
		return head->next;
	}
	else if (k > 0) {
		return NULL;
	}
	else {
		cur = head;
		//   ++k      Kth   .
		//    k++,       Kth  
		while (++k != 0) {
			cur = cur->next;
		}
		//      
		DoubleLinkNode* tobedeleted = cur->next;
		DoubleLinkNode* next = tobedeleted->next;
		cur->next = next;
		next->last = cur;

		delete tobedeleted;
		tobedeleted = NULL;
		return head;
	}
}

タイトル:チェーンシートの一部を反転

mの前駆者を探して、nの後継者を探します.

反転[m...n]この区間のチェーン

境界に注意する.

ListNode* reverseBetween(ListNode* head, int m, int n) {

    if (head == NULL || n <= m) {
        return head;
    }

    int len = 0;
    ListNode* cur = head;
    ListNode* beforeM = NULL;
    ListNode* M = NULL;
    ListNode* N = NULL;
    ListNode* afterN = NULL;
    while (cur != NULL) {
        len++;
        beforeM = len == m - 1 ? cur : beforeM;
        M = len == m ? cur : M;
        N = len == n ? cur : N;
        afterN = len == n + 1 ? cur : afterN;
        cur = cur->next;
    }

    ListNode* res = head; //      
    // reverse
    cur = M;
    ListNode* pre = beforeM;
    while (cur != afterN&&cur != NULL) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    M->next = afterN;

    if (beforeM == NULL) {
        res = N;
    } else {
        beforeM->next = N;
    }

    return res;
}

タイトル:チェーンシートをある値に分けて、左の小さな中間と右の大きい形にします.
方法1:単一のチェーンテーブルを配列に入れて、早い列のようなpartition動作を行い、最後に、順序付けされたノードを接続する.

/*
	   :
	1.          ,
	2.      partition
	3.          

	     O(N)
	     O(N)
	                   
*/

void ArrPartition(vector &v, int pivot) {
	int size = v.size();
	if (size == 0) {
		return;
	}

	int small = -1;
	int big = v.size();

	int index = 0;
	while (index < v.size()) {

		if (v[index]->val < pivot) {
			v[++small] = v[index++];
		}
		else if (v[index]->val > pivot) {
			swap(v[--big], v[index]);
		}
		else {
			//       pivot  
			index++;
		}
	}
}

ListNode* LinkListPartition1(ListNode* head,int pivot) {
	if (head == NULL)
		return NULL;

	vector v;

	//        
	ListNode* cur = head;
	while (cur != NULL) {
		v.push_back(cur);
		cur = cur->next;
	}
		
	//      partition
	cur = head;
	ArrPartition(v, pivot);

	for (int i = 1; i < v.size(); i++) {
		v[i - 1]->next = v[i];
	}
	v[v.size() - 1]->next = NULL;
	return v[0];
}

方法2:3つのチェーンを作成します.それぞれ小さいです.等しいです.最後に3つのチェーンを接続するより大きいです.

/*
	  2:
	           ,
	      ,      ,  ,  
	           

	     O(N)
	     O(1)
	      
*/
ListNode* LinkListPartition2(ListNode* head, int pivot) {
	if (head == NULL)
		return NULL;

	ListNode* smallStart = NULL;
	ListNode* smallEnd = NULL;
	ListNode* equalStart = NULL;
	ListNode* equalEnd = NULL;
	ListNode* bigStart = NULL;
	ListNode* bigEnd = NULL;

	ListNode* cur = head;
	ListNode* next = NULL;
	while (cur!=NULL) {
		next = cur->next;
		cur->next = NULL; //         .                  
		//    
		if (cur->val < pivot) {
			if (smallStart == NULL) {
				smallStart = cur;
				smallEnd = cur;
			}
			else {
				smallEnd->next = cur;
				smallEnd = cur;
			}

		}
		else if (cur->val == pivot) {
			if (equalStart == NULL) {
				equalStart = cur;
				equalEnd = cur;
			}
			else {
				equalEnd->next = cur;
				equalEnd = cur;
			}
		}
		else {
			if (bigStart == NULL) {
				bigStart = cur;
				bigEnd = cur;
			} else {
				bigEnd->next = cur;
				bigEnd = cur;
			}
		}
		cur = next;
	}
	
	//         
	if (smallStart != NULL) {
		smallEnd->next = equalStart;
		//         ,       
		equalEnd = equalEnd == NULL ? smallEnd : equalEnd;
	}
	//      
	if (equalEnd != NULL) {
		equalEnd->next = bigStart;
	}

	return smallStart != NULL ? smallStart : equalStart != NULL ? equalStart : bigStart;

	
}

検索二叉樹を双方向リンクに変換します.
方法1:スタックを利用して中間順序で並べ替え、最後に結果をキューに保存し、またキューを巡回してスティッチングする.


/*
	             
*/
//          ,      ,        .              
TreeNode* convert1(TreeNode* head) {

	TreeNode* res = NULL;
	TreeNode* end = NULL;

	queue q;
	TreeNode* cur = head;

	stack s;//            

	while (!s.empty() || !cur != NULL) {
		while (cur != NULL) {
			s.push(cur);
			cur = cur->left;
		}

		if (!s.empty()) {
			cur = s.top();
			s.pop();
			q.push(cur);
			cur = cur->right;
		}
	}

	//               
	while (!q.empty()) {

		cur = q.front();
		q.pop();

		if (res == NULL) {
			res = cur;
			res->left = NULL;
			end = cur;
		}
		else {
			cur->left = end;
			end->right = cur;
			end = cur;
		}
	}
	if(end!=NULL)
		end->right = NULL;

	return res;
}

方法2:再帰関数を利用する.

/*
	      ,
	         ,
	            , ,    right     .
*/
TreeNode* convertProcess(TreeNode* head) {
	if (head == NULL) {
		return NULL;
	}

	TreeNode* leftTreeLast = convertProcess(head->left);
	TreeNode* rightTreeLast = convertProcess(head->right);

	TreeNode* leftTreeFirst = leftTreeLast != NULL ? leftTreeLast->right : NULL;
	TreeNode* rightTreeFirst = rightTreeLast != NULL ? rightTreeLast->right : NULL;
	
	if (leftTreeLast != NULL&&rightTreeLast != NULL) {
		leftTreeLast->right = head;
		head->left = leftTreeLast;
		head->right = rightTreeFirst;
		rightTreeFirst->left = head;
		rightTreeLast->right = leftTreeFirst;
		return rightTreeLast;
	}
	else if(leftTreeLast!=NULL){
		leftTreeLast->right = head;
		head->right = leftTreeFirst;
		head->left = leftTreeLast;
		return head;
	}
	else if (rightTreeLast != NULL) {
		head->right = rightTreeFirst;
		rightTreeFirst->left = head;
		rightTreeLast->right = head;
		return rightTreeLast;
	}
	else {
		head->right = head;
		return head;
	}
}

TreeNode* convert2(TreeNode* bst) {

	if (bst == NULL) {
		return NULL;
	}

	TreeNode* last = convertProcess(bst);
	//                    
	TreeNode* first = last->right;
	last->right = NULL;
	return first;
}

タイトル:O(1)時間でリンクノードを削除します.

/*
	          Node,       
*/
void DeleteNode(ListNode* node) {
	if (node == NULL) {
		return ;
	}

	ListNode* next = node->next;
	if (next == NULL) {
		throw "ERROR";
	}

	node->val = next->val;
	node->next = next->next;
	return ;
}

参考文献
チェーン問題まとめ1
チェーン問題まとめ2

Pands学習ノート1-基本操作