4.6 two pointers

程序员文章站 2024-02-29 09:46:22

...

2019年9月PAT - 练习笔记——4.6

以下页码标注的是阅读器中实际页码，而不是书本身自印的页码。

第4章入门篇（2）——算法初步

4.6 two pointers

注意

要熟练掌握几种基本排序算法：插入、归并、冒泡、选择、快速、堆
two pointers扫描中可以在两个序列最后都添加一个最大（小）数INF，见A1029

B1030 / A1085 完美数列
B1035 / A1089 Insert or Merge
A1029 Median
A1048 Find Coins

B1030 / A1085 完美数列

见4.5节
1. 《算法笔记》P183
  
  这里给出two pointers的解决方案

B1035 / A1089 Insert or Merge

根据*的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

我的

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n = 0;

bool InsertionSort(vector<int> origin, const vector<int>&mid)
{
	bool flag = false;
	for (int i = 1;i < n;++i) {
		int j = 0;
		for (;j < i && origin[j] < origin[i];++j);
		int num = origin[i];
		for (int k = i;k > j;--k) origin[k] = origin[k - 1];
		origin[j] = num;
		
		if (flag) {
			cout << "Insertion Sort" << endl;
			for (int i = 0;i < n;++i) {
				if (i) cout << " ";
				cout << origin[i];
			}
			return true;
		}
		if (origin == mid) flag = true;
	}
	
	return false;
}

void Merge(vector<int>&origin, const int left, const int right)
{
	sort(origin.data() + left, origin.data() + right);
}

void MergeSort(vector<int>&origin, const vector<int>&mid)
{
	cout << "Merge Sort" << endl; 
	
	bool flag = false;
	for (int s = 1;s < n;s *= 2) {
		int i = 0;
		for (;i + 2 * s < n;i += 2 * s) Merge(origin, i, i + 2 * s);
		if (i + s < n) Merge(origin, i, n);
		
		if (flag) {
			for (int i = 0;i < n;++i) {
				if (i) cout << " ";
				cout << origin[i];
			}
			return;
		}
		if (origin == mid) flag = true;
	}
} 

int main(void)
{
	cin >> n;
	vector<int> origin(n), mid(n);
	for (int i = 0;i < n;++i) cin >> origin[i];
	for (int i = 0;i < n;++i) cin >> mid[i];

	if (!InsertionSort(origin, mid)) MergeSort(origin, mid);

	return 0;
}

《算法笔记》P185

A1029 Median

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×105) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output Specification:

For each test case you should output the median of the two given sequences in a line.

Sample Input:
```
4 11 12 13 14
5 9 10 15 16 17
```
Sample Output:
```
13
```
1. 我的
```
#include <iostream>

using namespace std;

const int n = 2 * 1e5 + 1;
int nums1[n], nums2[n];

int main(void)
{
	int n1 = 0;
	scanf("%d", &n1);
	for (int i = 0;i < n1;++i) scanf("%d", &nums1[i]);
	int n2 = 0;
	scanf("%d", &n2);
	for (int i = 0;i < n2;++i) scanf("%d", &nums2[i]);
	
	int k = 0, i = 0, j = 0, mid = (n1 + n2 - 1) / 2;
	for (;i < n1 && j < n2 && k < mid;++k) {
		if (nums1[i] < nums2[j]) ++i;
		else ++j;
	}
	if (k == mid) {
		if (i >= n1) printf("%d", nums2[j]);
		else if (j >= n2) printf("%d", nums1[i]);
		else printf("%d", (nums1[i] < nums2[j] ? nums1[i] : nums2[j]));
	}
	else if (i < n1) {
		for (;i < n1 && k < mid;++k) ++i;
		printf("%d", nums1[i]);
	}
	else {
		for (;j < n2 && k < mid;++k) ++j;
		printf("%d", nums2[j]);
	}

	return 0;
}
```
  测试点8内存超限
2. 《算法笔记》P188
  1. “步骤1：类似于配套用书4.6.1节所讲的“序列合并问题”，只不过本题不要求把整个合并后的序列输出，而是只需要输出中位数。由于在给定两个子序列的长度N和M后，新序列的长度N+M就是已知的，因此中位数的位置为（N + M - 1）/ 2（此处为向下取整），其中对 N + M - 1 的原因是序列下标从0开始，例如长度为8时应为3，长度为9应为4”
  2. 注意点
    1. “int类型的最大值为2³¹-1，也即0x7fffffff”
    2. “为了使代码更加简练，不妨令两个序列的最后都添加一个很大的数INF（本题为int类型的最大值），这样在two pointers的扫描过程中，就可以在其中一个序列已经扫描完但count还没有到中位数的情况下解决访问越界的问题”
    3. “使用cin、cout会超时，请使用scanf与printf”
  亲测：参考代码无法通过测试点8，内存超限
3. 柳神：https://www.liuchuo.net/archives/2248 .
  1. 我参照原代码改成了自己更能接受的形式
```
#include <iostream>

using namespace std;

const int INF = 0x7fffffff;
int nums[200005];

int main(void)
{
    int n1 = 0;
    scanf("%d", &n1);
    for (int i = 0;i < n1;++i) scanf("%d", &nums[i]);
    nums[n1] = INF;
    int n2 = 0;
    scanf("%d", &n2);
    
    int i = 0, count = 0, mid = (n1 + n2 - 1) / 2;
    for (int j = 0;j < n2 && count <= mid;++j) {
        int num = 0;
        scanf("%d", &num);
        for (;nums[i] < num && count <= mid;++i) {
            if (count == mid) cout << nums[i];
            ++count;
        }
        if (count == mid) cout << num;
        ++count;
    }
    if (count < mid) {
        for (;count < mid;++count, ++i);
        cout << nums[i];
    }

	return 0;
}
```
A1048 Find Coins

见4.2节
1. 《算法笔记》P190
  
  这里给出two pointers的做法。

4.6 two pointers

第4章入门篇（2）——算法初步

4.6 two pointers

B1030 / A1085 完美数列

B1035 / A1089 Insert or Merge

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

A1029 Median

Input Specification:

Output Specification:

Sample Input:

Sample Output:

A1048 Find Coins

two pointers 双针法

4.6 two pointers

Move Zeroes——Two Pointers

two pointers

51nod 1495 中国好区间【2-pointers】

leetcode: 2 pointers

2021暑假Leetcode刷题——Two Pointers(2)

HOUR 11 Developing Advanced Pointers

Using smart pointers for class members

HDU 4745——Two Rabbits【区间DP & 最长回文子序列】

4.6 two pointers

第4章 入门篇（2）——算法初步

4.6 two pointers

B1030 / A1085 完美数列

B1035 / A1089 Insert or Merge

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

A1029 Median

Input Specification:

Output Specification:

Sample Input:

Sample Output:

A1048 Find Coins

two pointers 双针法

4.6 two pointers

Move Zeroes——Two Pointers

two pointers

51nod 1495 中国好区间【2-pointers】

leetcode: 2 pointers

2021暑假Leetcode刷题——Two Pointers(2)

HOUR 11 Developing Advanced Pointers

Using smart pointers for class members

HDU 4745——Two Rabbits【区间DP & 最长回文子序列】

第4章入门篇（2）——算法初步