真题集P93---2017年计专真题

六

思路：模拟

1、接口介绍

int turnNum(int num[], int nums)：拿来一个数组，将之表示的二进制数转化成为十进制
bool is_valid(int path[], int n, int sum, int times)：判断当前生成的路径是不是符合题意的路径
void dfs(int path[], int n, int sum, int times)：生成全排列的函数，在产生的元素个数等于2^n时候进行判断该序列合不合法，合法就输出，让所有一切别的产生序列函数停止

2、设计思路
<1>输入n,需要对2^n个位置，产生0或者1，用dfs产生全排列，当个数达到要求，判断该序列是否合法
<2>拿到序列之后，用指针i从头扫到尾，在每个i出，连续提取n个数，放入数组，转化成10进制，看出现过了吗，未出现过，计数，最后计数为2^n个，为合法序列

代码

在连续取数时候，为了防止越界，且根据题意，用循环的方式即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
bool find_ans = false;
int turnNum(int num[], int nums) {//转十进制
	int ans = 0;
	for (int i = 0; i < nums; i++) {
		ans = ans * 2 + num[i];
	}
	return ans;
}
bool is_valid(int path[], int n, int sum, int times) {
	bool visit[1000];
	int num = 0;
	for (int i = 0; i < sum; i++) {
		visit[i] = false;
	}
	for (int i = 0; i < n; i++) {
		int cur[1000] = {};
		int j = 0;//记录从path中，从i后面，抽取出的第j个数，共抽取出times个，times表示2^n中的n
		while (j < times) {
			int p = path[i % sum + j];//根据题意，如果最后越界，采用循环的方式
			cur[j++] = p;//送到cur数组准备一会转化成十进制数
		}
		int tmp = turnNum(cur, times);
		if (!visit[tmp]) {
			visit[tmp] = true;
			num++;
		}
	}
	if (num == sum) {
		return true;
	}
	return false;
}
void dfs(int path[], int n, int sum, int times) {//参数：记录排列的数组，数组中元素个数，总共应该有多少个元素，2^n中的n
	if (n == sum) {//此次排列产生完毕
		if (is_valid(path, n, sum, times)) {
			find_ans = true;//说明已经找到答案，让别的函数见到此快速退出
			for (int i = 0; i < n; i++) {
				cout << path[i] << ' ';
			}
		}
		return;
	}
	if (find_ans) {//已经找到答案，快速退出 
		return;
	}
	path[n] = 0;
	dfs(path, n + 1, sum, times);
	path[n] = 1;
	dfs(path, n + 1, sum, times);
	return;
}
void function_six() {
	int n;
	cin >> n;
	int sum = pow(2, n);
	int path[1000] = {};
	dfs(path, 0, sum, n);
	return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

七

思路

一：哈希表法

1、选一个链作为主链，先扫一遍，把元素放入对应的哈希表，注意，最后指针要停在最后一个节点上。
2、进入副链，当前元素，未在之前集合出现，连在主链末尾。
3、一定注意，数据域是整数，包括正整数，负整数，0，所以用两个数组模拟哈希。

二：排序法 (利用排序去重)

这个方法在求并集时候并不好用，作为了解，过程如下

三：拓展

一旦不求并集，而改求交集，那么排序法就很好，过程如下：

链表冒泡排序见第八章–排序

代码（仅思路一）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef struct node {
	int val;
	node* next;
};
node* function_seven(node* q, node* p) {
	bool hash[10000];//代表正数哈希
	bool hash_ano[10000];//代表负数哈希
	for (int i = 0; i < 10000; i++) {
		hash[i] = false;
		hash_ano[i] = false;
	}
	node* cur = q;//q链作为主链，之后全往q链上面挂
	while (cur->next != nullptr) {
		cur->val >= 0 ? hash[cur->val] = true : hash_ano[abs(cur->val)] = true;//根据正负放入正确的哈希表
		cur = cur->next;
	}
	node* last = p;
	while (last != nullptr) {
		if (last->val >= 0 && hash[last->val]) {//在正确的哈希表中找是否出现过
			last = last->next;
			continue;
		}
		if (last->val < 0 && hash_ano[abs(last->val)]) {//在正确的哈希表中找是否出现过
			last = last->next;
			continue;
		}
		last->val >= 0 ? hash[last->val] = true : hash_ano[abs(last->val)] = true;//根据数值存入正确的哈希表
		node* tmp = last;//连接节点，先标记这个节点
		last = last->next;
		
		cur->next = tmp;
		cur = tmp;
		cur->next = nullptr;
	}
	return q;//返回主链
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44