一、折半查找
1. 写出基本思想
折半查找（Binary Search）又称二分查找，是一种在有序数组中查找某一特定元素的算法。
基本思想：
- 将数组中间位置的元素与待查找元素比较。
- 如果待查找元素等于中间位置的元素，则查找成功；
- 如果待查找元素小于中间位置的元素，则在数组的前半部分继续查找；
- 如果待查找元素大于中间位置的元素，则在数组的后半部分继续查找。
2. 代码实现
#include <iostream>
using namespace std;
// 二分查找算法，返回目标元素在数组中的索引，如果不存在则返回 -1
int binary_search(int arr[], int n, int key)
{
int low = 0, high = n - 1;
// 在区间 [low, high] 中进行二分查找
while (low <= high)
{
int mid = (low + high) / 2;
// 如果中间元素等于目标元素，则返回索引
if (arr[mid] == key)
return mid;
// 如果中间元素小于目标元素，则在右半部分查找
else if (arr[mid] < key)
low = mid + 1;
// 如果中间元素大于目标元素，则在左半部分查找
else
high = mid - 1;
}
// 目标元素不存在，返回 -1
return -1;
}
int main()
{
// 示例数组
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 5;
// 调用二分查找算法
int index = binary_search(arr, n, key);
// 输出结果
if (index == -1)
cout << "Element not found" << endl;
else
cout << "Element found at index " << index << endl;
return 0;
}
二、查找链表节点
已知一个单链表，结构体定义为：
struct ListNode
{
int val;
ListNode *next;
ListNode(int x): val(x), next(NULL) {}
};
要求：
1.实现一个函数，找出单向链表中倒数第 k 个节点。返回该节点的值。
int kthToLast(ListNode* head, int k)
{
}
2.实现一个函数，将数组转换成单链表。
ListNode *createListNode(int vals[], int n)
{
}
3.编写主函数并调试。
输入格式
第一行包含数组长度 N 和 k 。
第二行包含 N 个整数。
输出格式
共一行，输出结果。
数据范围
0 ≤ k ≤ N ≤ 1000000
0 ≤ 节点值 ≤ 10000
输入样例
5 2
6 9 5 12 3
输出样例
12
代码
#include <iostream>
using namespace std;
// 定义链表节点结构
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 使用快慢指针求倒数第 k 个节点的值
int kthToLast(ListNode *head, int k)
{
ListNode *fast = head, *slow = head;
while (k--)
fast = fast->next;
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow->val;
}
// 使用遍历求倒数第 k 个节点的值
int kthToLast2(ListNode *head, int k)
{
int n = 0;
for (ListNode *p = head; p; p = p->next)
n++;
ListNode *p = head;
for (int i = 0; i < n - k; i++)
p = p->next;
return p->val;
}
// 创建带虚拟头节点的链表
ListNode *createListNode(int vals[], int n)
{
ListNode *dummy = new ListNode(0), *cur = dummy; // 带虚拟头节点
for (int i = 0; i < n; i++)
{
cur->next = new ListNode(vals[i]);
cur = cur->next;
}
return dummy->next;
}
// 创建不带虚拟头节点的链表
ListNode *createListNode2(int vals[], int n)
{
if (n == 0)
return NULL;
ListNode *head = new ListNode(vals[0]), *cur = head; // 不带虚拟头节点
for (int i = 1; i < n; i++)
{
cur->next = new ListNode(vals[i]);
cur = cur->next;
}
return head;
}
// 打印链表
void show(ListNode *head)
{
for (ListNode *p = head; p; p = p->next)
cout << p->val << ' ';
cout << endl;
}
int main()
{
// 示例数组
int a[] = {6, 9, 5, 12, 3};
int n = sizeof(a) / sizeof(a[0]);
// 创建链表
ListNode *head = createListNode2(a, n);
// 输出结果
cout << kthToLast(head, 2) << endl;
cout << kthToLast2(head, 2) << endl;
return 0;
}
三、共享栈
#include <iostream>
using namespace std;
const int maxsize = 100; // 假设数组大小为100
struct SharedStack {
int e[maxsize]; // 共享存储区
int top0; // 栈s0的栈顶指针
int top1; // 栈s1的栈顶指针
SharedStack() : top0(-1), top1(maxsize) {} // 初始化栈顶指针
};
// 栈s0的入栈操作
void push0(SharedStack &stack, int x) {
if (stack.top0 + 1 < stack.top1) {
stack.e[++stack.top0] = x; // 栈s0的栈顶指针移动，并赋值
} else {
cout << "Stack Overflow for s0" << endl;
}
}
// 栈s0的出栈操作
int pop0(SharedStack &stack) {
if (stack.top0 >= 0) {
return stack.e[stack.top0--]; // 返回栈s0的栈顶元素，并移动栈顶指针
} else {
cout << "Stack Underflow for s0" << endl;
return -1; // 栈空，返回一个特定值表示错误
}
}
// 栈s1的入栈操作
void push1(SharedStack &stack, int x) {
if (stack.top1 - 1 > stack.top0) {
stack.e[--stack.top1] = x; // 栈s1的栈顶指针移动，并赋值
} else {
cout << "Stack Overflow for s1" << endl;
}
}
// 栈s1的出栈操作
int pop1(SharedStack &stack) {
if (stack.top1 < maxsize) {
return stack.e[stack.top1++]; // 返回栈s1的栈顶元素，并移动栈顶指针
} else {
cout << "Stack Underflow for s1" << endl;
return -1; // 栈空，返回一个特定值表示错误
}
}
int main() {
SharedStack stack;
// 入栈和出栈示例操作
push0(stack, 1);
push0(stack, 2);
push1(stack, 11);
push1(stack, 12);
cout << "Pop from s0: " << pop0(stack) << endl;
cout << "Pop from s1: " << pop1(stack) << endl;
cout << "Pop from s0: " << pop0(stack) << endl;
cout << "Pop from s1: " << pop1(stack) << endl;
return 0;
}
这段C++代码使用结构体实现了共享栈的结构和入栈出栈操作。两个栈的栈顶指针分别向中间移动，确保在栈满和栈空的情况下不会越界。
四、最大不相交区间数量
设有n个机器的集合E={1,2,…n},其中每个机器都要求使用同一资源，而在同一时间内只有一个机器能使用这一资源。每个机器i都有一个要求使用该资源的起始时间si和一个结束时间 fi,且 si<fi。如果选择了机器i,则它在半开时间区间[si,fi)内占用资源。若区间[si, fi)与区间[sj,fj)不相交，则称机器i与机器j是相容的。也就是说，当si≥fj或sj≥fi时，机器i与机器j相容。现在要求使用贪心算法在所给的机器集合中选出最大的相容机器子集合。
题目实际描述的是：acwing908.最大不相交区间数量
题目描述
给定 N 个闭区间 ai,bi，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1≤N≤105
−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
// 定义区间结构体
struct Interval {
int a, b;
// 重载小于运算符，按照区间右端点升序排序
bool operator< (const Interval& t) const {
return b < t.b;
}
};
Interval intervals[N];
int n, res;
int main() {
// 输入区间数
cin >> n;
// 输入每个区间的左右端点
for (int i = 0; i < n; i++)
cin >> intervals[i].a >> intervals[i].b;
// 按右端点升序排序区间
sort(intervals, intervals + n);
// 贪心算法：每次选择右端点最小的区间
for (int i = 0; i < n; i++) {
int j = i + 1;
while (j < n && intervals[j].a <= intervals[i].b)
j++; // 找到与当前区间相交的下一个区间
res++; // 选择当前区间
i = j - 1; // 跳过已选择的区间
}
// 输出可选取区间的最大数量
cout << res << endl;
return 0;
}
算法思想：
- 定义结构体
Interval表示闭区间，重载小于运算符按照右端点升序排序。 - 输入区间数和每个区间的左右端点。
- 将区间按右端点升序排序。
- 使用贪心算法，从左往右遍历排序后的区间，每次选择右端点最小的区间，并跳过与当前区间相交的下一个区间。
- 输出可选取区间的最大数量。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
struct Interval
{
int a, b;
// 重载小于运算符，按照区间右端点升序排序
bool operator< (const Interval &t) const
{
return b < t.b;
}
} q[N];
int main()
{
int n;
cin >> n;
// 输入每个区间的左右端点
for (int i = 0; i < n; i++)
cin >> q[i].a >> q[i].b;
// 按右端点升序排序区间
sort(q, q + n);
int res = 0;
for (int i = 0; i < n; i++)
{
int j = i + 1;
while (j < n && q[j].a <= q[i].b)
j++; // 找到与当前区间相交的下一个区间
res++; // 选择当前区间
i = j - 1; // 跳过已选择的区间
}
// 输出所需的点的最小数量
cout << res << endl;
return 0;
}
算法思想：
- 定义结构体 Interval 表示闭区间，重载小于运算符按照右端点升序排序。
- 输入区间数和每个区间的左右端点。
- 将区间按右端点升序排序。
- 使用贪心算法，从左往右遍历排序后的区间，每次选择右端点最小的区间，并跳过与当前区间相交的下一个区间。
- 输出所需的点的最小数量。
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
PII q[N];
bool cmp(PII a, PII b)
{
return a.y < b.y;
}
int main()
{
int n;
cin >> n;
// 输入每个区间的左右端点
for (int i = 0; i < n; i++)
cin >> q[i].x >> q[i].y;
// 按右端点升序排序区间
sort(q, q + n, cmp);
int res = 0;
for (int i = 0; i < n; i++)
{
int j = i + 1;
while (j < n && q[j].x <= q[i].y)
j++; // 找到与当前区间相交的下一个区间
res++; // 选择当前区间
i = j - 1; // 跳过已选择的区间
}
// 输出所需的点的最小数量
cout << res << endl;
return 0;
}
- 升序：
sort(q, q + n); // 需要重载 <
sort(q, q + n, cmp); // 需要自定义 cmp()函数
- 降序：
sort(q, q + n, greater<>()); // 需要重载 >
sort(q, q + n, cmp); // 需要自定义 cmp()函数
降序例子：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
struct Interval
{
int a, b;
// 重载大于运算符，按照区间右端点降序排序
bool operator> (const Interval &t) const
{
return b > t.b;
}
} q[N];
int main()
{
int n;
cin >> n;
// 输入每个区间的左右端点
for (int i = 0; i < n; i++)
cin >> q[i].a >> q[i].b;
// 按右端点降序排序区间
sort(q, q + n, greater<>());
for (int i = 0; i < n; ++i)
cout << q[i].a << ' ' << q[i].b << endl;
cout << endl;
return 0;
}
%%%
五小时前😯
😵😵