数据结构
网络
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 次浏览
广告