算法设计课程练习-分治_problem p01. [算法课分治] 最大二叉树

一、最大二叉树Pro01

样例输入

3 2 1 6 0 5
1

样例输出

6 3 null 2 null 1 5 0 null 
1

思路分析：
1.二叉树的构造：这里显然需要通过递归来构造最大二叉树。
①对于输入的数组，范围为first-end，找到范围数组内的最大值赋予新的节点Node，由此将数组分为了左右两部分；
②对于数组的左半部分，用于递归构造新节点的左子树，范围缩小到first-(max_index-1)，其中max_index为最大值的下标；
③同理，对于数组的右半部分，用于递归构造新节点的右子树，范围缩小到(max+1)-end；

2.特殊的前序遍历：由给出的样例可以看出，非叶子节点的左右子树都需要输出，只有叶子节点无需输出null，非叶子节点如果不存在左子树/右子树则需要输出null。

3.其他：①EOF：在输入时ctrl+z回车；②节点的结构体Node根据需要进行修改，但是基本上都含有data，*lchild，*rchild。
AC代码：

#include<bits/stdc++.h>
#define N 1000
using namespace std; 

struct Node {
      int data;
      Node *left;
      Node *right;
      Node() : data(0), left(nullptr), right(nullptr) {}
      Node(int x) : data(x), left(nullptr), right(nullptr) {}
  };
	
Node* creat(const vector<int>& nums, int left, int right) {
    if (left > right) {
        return nullptr;
    }
    //获取范围内的最大值的下标 
    int best = left;
    for (int i = left + 1; i <= right; ++i) {
        if (nums[i] > nums[best]) {
            best = i;
        }
    }
    Node* node = new Node(nums[best]);
    //递归构造左右子树 
    node->left = creat(nums, left, best - 1);
    node->right = creat(nums, best + 1, right);
    return node;
}
	
Node* Build(vector<int>& nums,int k) {//二叉树建立函数 
    return creat(nums, 0, k);
}
   
void PreOrder(Node* bt)//改造版前序遍历函数 
{
	cout<<bt->data<<" ";
	//如果是叶子节点，就无需输出null 
	if(bt->left==nullptr&&bt->right==nullptr) 
		return; 
	else{
		if(bt->left!=nullptr)
			PreOrder(bt->left);
		else
			cout<<"null ";
		if(bt->right!=nullptr)
			PreOrder(bt->right);
		else
			cout<<"null ";
		return;
	}	
} 

int main(){
	vector<int> num(N,0);
	int n;//输入的数 
	int i=0;
	while(cin>>n){
		num[i]=n;
		i++;
	}
	Node* bt = Build(num,i-1);
	PreOrder(bt);
	return 0;
}
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

二、寻找多数Pro02

样例输入

7
4 1 2 3 3 3 3
1
2

样例输出

3
1

样例输入

9
4 2 2 2 2 21 23 23 2
1
2

样例输出

2
1

思路分析：
①注意这里的条件——多数是出现的次数sum>n/2，因此首先对整个数组进行排序处理；
②排序后所有相同的数字会聚集到一起，假设数组中的a[0]为多数，出现次数初始化为sum=1，对数组进行遍历；
③下一个数和设置的多数num相同则sum++，不同则sum–，直到sum=0时，设置下标i所在的数为新的多数（比如11222，2的次数多于1，所以更新新的多数为2，之所以可以这么做是有sum>n/2这个条件）；
④此外，还需要用flag记录一下出现的次数，用于赋值新的多数出现的次数。
AC代码：

#include<bits/stdc++.h>
#define N 10000
using namespace std;

int main()
{
	int n;
	cin>>n;//数组长度
	int a[n];
	for(int i=0 ; i<n ; i++)
		cin>>a[i];
	sort(a,a+n);//排序
	int num = a[0];//设第一个数为多数
	int sum=1;//多数出现的次数 
	int flag[N]={0};//标志数组，算次数 
	flag[a[0]]=1;
	
	for(int i=1 ; i<n ; i++)
	{
		if(sum<1)
		{
			num = a[i];
			sum = flag[a[i-1]]+1;//前一个多数的出现的次数+1 
		}
		else
		{
			if(a[i]==num)
			{
				sum++;
				flag[a[i]]++; 
			}	
			else
				sum--;
		}		
	} 
	
	cout<<num;
	return 0;
 } 
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

三、找到最大子序和Pro03

样例输入

9
-2 1 -3 4 -1 2 1 -5 4
1
2

样例输出

6
1

解释：第一个样例解释：连续子数组 [4,-1,2,1]的和最大，为 6。
思路分析：
①设置每个节点开始所能得到的子串的和的max为第一个节点；
②从数组的第i个数开始往后构造子串，并计算子串的和sum，如果sum大于max[i]，就对max进行更新，否则不变；
③最后对max进行sort排序，输出最大值即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	int num[n];
	int max[n];//用于记录从各个节点开始往后的最大值
	for(int i=0 ; i<n ; i++){
		cin>>num[i];
		max[i]=num[i];//设初始节点为最大值 
	}

	for(int i=0 ; i<n-1 ; i++){
		int sum=num[i];
		for(int j=i+1 ; j<n ; j++){
			sum+=num[j];
			if(sum>max[i])//和大于max就更新 
				max[i]=sum;
		}
	} 
	sort(max,max+n);
	cout<<max[n-1];
	return 0;
} 
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

四、找到 k 个最小数Pro04

样例输入

3 2
3 2 1
1
2

样例输出

1 2
1

思路分析：sort排序，输出前k个数即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0 ; i<n ; i++)
		cin>>arr[i];
	sort(arr,arr+n);
	for(int j=0 ; j<k ; j++)
		cout<<arr[j]<<" ";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

五、寻找第 k 个最大元素Pro05

样例输入

6 2
3 2 1 5 6 4
1
2

样例输出

5
1

思路分析：sort排序，输出第n-k个数即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,k;
	cin>>n>>k;
	int num[n];
	for(int i=0 ; i<n ; i++)
		cin>>num[i];
	sort(num,num+n);
	cout<<num[n-k];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

六、找到 k 个最长重复字符串Pro06

样例输入

aaabb 3
1

样例输出

3
1

样例输入

ababbc 2
1

样例输出

5
1

样例输入

abcde 2
1

样例输出

0
1

思路分析：这题是很明显的递归分治思想，分左右子串递归找到满足条件的最大子串。
①构建findMax函数，用于返回满足条件的最大子串的长度；
②首先用cnt[26]数组来统计输出的子串中各个字母出现的次数；
③设置flag来标明输入的子串是否是最大子串，flag初始化为flase，即假设输入的子串就满足子串中的字母出现次数都不小于k的条件，遍历输入的子串，如果都满足条件，最终返回输入的子串的长度len；
④遍历输入的子串，如果找到有不满足条件的字母，flag=true，从不满足的字母开始将子串分为左右两个子串，递归计算左右两个子串满足条件的最大子串的长度，并取最大值，并退出循环，返回这个最大值。
AC代码：

#include<bits/stdc++.h>
using namespace std;

int findMax(string s,int k){
	int len = s.size();
	if(len<k) return 0;
	
	int cnt[26]={0};//用于存储各个字母出现的次数
	for(int i=0 ; i<len ; i++)
		cnt[s[i]-'a']++;
		
	int flag = false;
	int m;
	for(int i=0 ; i<len ; i++){
		if(cnt[s[i]-'a']<k){
			flag = true;
			m = max(findMax(s.substr(0,i),k),findMax(s.substr(i+1,len-i-1),k));//在不满足大于k的字符出断开，递归查找两个子串中满足条件的最大子串 
			break;
		} 
	}
	if(!flag)//如果s满足条件，则最大子串的长度就是s的长度 
		return len;
	else//如果不满足条件，则最大字串长度就是左右子串中的最大字串长度的大的那一个 
		return m;
}

int main(){
	int k;//子串中各个字母出现的次数 
	string s;
	cin>>s>>k;
	int m = findMax(s,k);
	cout<<m;
	return 0; 
}
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

七、链表排序Pro07

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
1
2
3
4
5
6
7

样例输入

4 2 1 3
1

样例输出

1 2 3 4
1

样例输入

-1 5 3 4 0
1

样例输出

-1 0 3 4 5
1

思路分析：本题采用自顶向下的归并排序方法。
①利用快慢指针找到输入的链表的中点，然后将输入的链表断开成左右链表，然后递归使用sortList对左右链表进行排序，当只有一个节点的时候结束递归；
②然后对排序后的左右链表进行合并排序操作mergeList，返回完整的一个有序列表。
AC代码：

#include<bits/stdc++.h>
using namespace std;

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

//合并函数，将两个链表合并为一个链表 
ListNode *mergeList(ListNode *list1, ListNode *list2)
{
    ListNode *dummyHead = new ListNode(0);
    ListNode *merge_temp = dummyHead;
    ListNode *list1_temp = list1;
    ListNode *list2_temp = list2;
    while (list1_temp && list2_temp)
    {
        if (list1_temp->val <= list2_temp->val)
        {
            merge_temp->next = list1_temp;
            list1_temp = list1_temp->next;
        }
        else
        {
            merge_temp->next = list2_temp;
            list2_temp = list2_temp->next;
        }
        merge_temp = merge_temp->next;
    }
	//可能存在其中一个链表提前融合完的情况，因此要进行扫尾  
    if (list1_temp)
        merge_temp->next = list1_temp;

    if (list2_temp)
        merge_temp->next = list2_temp;

    return dummyHead->next;
}

ListNode *sortList(ListNode *head, ListNode *tail)
{
    // 递归退出条件，即划分至只有一个结点
    if (head->next == tail)
    {
        head->next = nullptr; // 断链
        return head;
    }
	//利用快慢指针找到中间节点（快指针的步数是慢指针的两倍，因此快指针到结尾的时候，慢指针刚好到中间）
    // 使用快慢指针找出链表的 mid 结点
    // slow 最终得到的是真实 mid 的后一个结点
    // fast 最终得到的是最后一个结点的后一个结点
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast != tail)
    {
        fast = fast->next;
        slow = slow->next;
        if (fast != tail)
            fast = fast->next;
    }

    ListNode *mid = slow;    // mid 是第二个链表的头结点
    return mergeList(sortList(head, mid), sortList(mid, tail));
}

int main(){
	int k;
	ListNode *head = new ListNode(0,nullptr);
	ListNode *p = head;
	while(cin>>k) {//构造链表 
		ListNode *bt = new ListNode(k);
		p->next = bt;
		p = bt;
	}
	p->next = nullptr;//最后维护尾节点 
	ListNode *n = sortList(head->next,p->next);
	while(n!=nullptr){
		cout<<n->val<<" ";
		n=n->next;
	}
	return 0;
}
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

六、找到 k 个最长重复字符串Pro06

样例输入

3
2 2 1
1
2

样例输出

3
1

样例输入

5
10 2 10 10 10
1
2

样例输出

2
1

样例输入

7
150 150 150 10 150 150 150
1
2

样例输出

4
1

思路分析：这题是很明显的递归分治思想，分左右子串递归找到假币。
①首先得到正常的硬币的重量，因为假币的重量小于正常的硬币所以直接对硬币数组a取max得到正常的重量；
②分左右子序列找到假币，如果mid对应的硬币小于正常的重量，则该币就是假币；
③对左右子序列中总重量小于正常的总重量的子序列进行递归查找。
AC代码：

#include<bits/stdc++.h>
using namespace std;
int weight;//存储正常的重量
int n;//存储硬币的数量
 
int sum(vector<int> a,int first,int end){
	int s=0;
	for(int i=first ; i<=end ; i++)
		s += a[i];
	return s;
}

void find(vector<int> a,int first,int end){
	int mid = (first+end)/2;
	if(a[mid]<weight)//mid下表对应的币值不对直接打印 
		cout<<mid;
	else{//否则继续检查左右两个子序列 
		if(sum(a,first,mid-1)<weight*(mid-first))
			find(a,first,mid-1);
		else if(sum(a,mid+1,end)<weight*(end-mid))
			find(a,mid+1,end);
	}
}

int main(){
	cin>>n;
	vector<int> a(n+1,0);
	int i=1;
	int tmp;
	while(scanf("%d",&tmp)!=EOF)
		a[i++] = tmp;
	weight = *max_element(a.begin(),a.end());//数组中的最大值就是正常的重量 
	find(a,1,n);
	return 0;
}
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