資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究C++ 中的連結串列元件
假設給我們一個頭部；這是包含唯一整數值的連結串列的頭節點。現在還給了我們列表 G，是連結串列中值的子集。我們必須找到 G 中的連通元件數，如果兩個值在連結串列中連續出現，則它們是連通的。因此，如果列表為 [0,1,2,3] 並且 G = [0,1,3]，則輸出將為 2，因為 0 和 1 是連通的，所以有兩個列表 [0,1] 和 [3]。
要解決此問題，我們將遵循以下步驟 -
- ret := 0，建立一個集合 s，並將 G 中的所有元素插入 s
- flag := false
- 當 head 不為 null 時
- x := head 值
- 如果 s 有 x，則
- 如果 flag 為 false，則 ret 增加 1
- flag := true
- 否則，將 flag 設為 false
- head := head 的下一個
- 返回 ret
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
int ret = 0;
set < int > s;
for(int i = 0; i < G.size(); i++)s.insert(G[i]);
bool flag = false;
while(head){
int x = head->val;
if(s.count(x)){
if(!flag) ret++;
flag = true;
}else flag = false;
head = head->next;
}
return ret;
}
};
main(){
vector<int> v1 = {0,1,2,3};
vector<int> v2 = {0,1,3};
ListNode *h1 = make_list(v1);
Solution ob;
cout << (ob.numComponents(h1, v2));
}輸入
[0,1,2,3] [0,1,3]
輸出
2
更新於: 04-May-2020
343 次瀏覽
廣告