数据结构与算法实习第一阶段
目录
7-1 符号配对
知识点：栈
思路：先输入数据，将所有的符号保存下来，其它的可以丢掉。然后遍历，用tmp保留当前的符号，遇到左符号，压栈，当遇到右括号，把它跟栈顶元素做比较，有如下情况：
- 如 [ { ] ，右符号]与最近左符号{不匹配，说明{缺少正确右符号。
- 如 ]{，右符号]左边没有符号，说明缺少正确左符号[。
- 如{]，第一不匹配的是{ ，右符号]与左符号{不匹配，说明{缺少右符号}
所以如果遇到不匹配的情况，设置flag=1，退出遍历。接下来判断：
- 如果栈是空的，且flag==0，那我们输出yes
- 如果栈为空，但是flag标记了1，那我们输出
tmp - 如果栈不是空的，输出栈顶即可
代码：
#include<iostream>
using namespace std;
class MyStack {
private:
char *stk; //起始地址
int top; //始终指向栈顶元素
int MAXN;//栈的最大存储容量
public:
MyStack(int size) ; //构造函数，初始化一个栈时需要指定初始大小
~MyStack() ;//析构函数
int push(char x);
int pop();
char getTop();
int isEmpty ()const;
};
MyStack::MyStack(int size) {
MAXN = size;
stk = new char[MAXN];
top = -1;
}
MyStack::~MyStack() {
delete stk;
}
int MyStack::push(char x) {
if (top >= MAXN - 1)return -1;
stk[++top] = x;
return 0;
}
int MyStack::pop() {
if (top == -1)return 0;
// *x = stk[top--];
top--;
return 1;
}
char MyStack::getTop() {
if (top == -1)return NULL;//null要大写
return stk[top];
}
int MyStack::isEmpty()const {
return top == -1;
}
int main()
{
// 保存符号
char str[300];
char signs[300];
int signsPos = -1;
while(cin.getline(str,300)){
if(str[0]=='.' && !str[1]){
break;
}
for(int i=0; str[i]; i++)
{
if(str[i]=='(' || str[i]== '[' || str[i]=='{' || str[i]==')' || str[i]=='}' || str[i]==']'){
signs[++signsPos] = str[i];
}
else if(str[i]=='/' && str[i+1]=='*')
{
signs[++signsPos] = 'l';// 将/*替换为l
i++;
}
else if(str[i]=='*' && str[i+1]=='/')
{
signs[++signsPos] = 'r';
i++;
}
}
}
// 判断
MyStack myStack(300);
int flag=0;
char tmp;
for(int i=0; i<=signsPos; i++)
{
if(signs[i]=='(' || signs[i]=='{' || signs[i]=='[' || signs[i]=='l')
{
myStack.push(signs[i]);
}
else if(signs[i]==')')
{
char top = myStack.getTop();
if(top=='('){
myStack.pop();
}
else
{
tmp=signs[i];
flag = 1;
break;
}
}
else if(signs[i]=='}')
{
char top = myStack.getTop();
if(top == '{'){
myStack.pop();
}
else
{
tmp = signs[i];
flag = 1;
break;
}
}
else if(signs[i]==']')
{
char top = myStack.getTop();
if(top=='['){
myStack.pop();
}
else
{
tmp = signs[i];
flag = 1;
break;
}
}
else if(signs[i] == 'r')
{
char top = myStack.getTop();
if(top == 'l')
{
myStack.pop();
}
else
{
tmp = signs[i];
flag = 1;
break;
}
}
}
if(!flag && myStack.isEmpty()) printf("YES\n");
else
{
printf("NO\n");
if(!myStack.isEmpty())
{
char top = myStack.getTop();
if(top == '['){
printf("[-?\n");
}
else if(top == '('){
printf("(-?\n");
}
else if(top == '{'){
printf("{-?\n");
}
else if(top == 'l'){
printf("/*-?\n");
}
}
else
{
if(tmp ==']'){
printf("?-]");
}
else if(tmp == ')'){
printf("?-)");
}
else if(tmp == 'r'){
printf("?-*/");
}
else if(tmp == '}'){
printf("?-}");
}
putchar('\n');
}
}
return 0;
}
7-2 网红点打卡攻略
类型：模拟
思路：按照题目要求来就行了。
细节：
- 使用邻接矩阵存储路径。
- 路费使用
long long储存。 - 用数组
vis[105]记录已搜索的节点。
代码：
//
// Created by 孙百乐 on 2022/6/25.
//
#include<iostream>
using namespace std;
class HotSpots {
public:
int N;
int M;
int **path;
HotSpots(int N, int M);
~HotSpots();
void insertPath(int a, int b, int cost);
int getCost(int a, int b); // 不存在路径，返回-1
long long isValid(int *a, int n); // 无效返回0，有效，返回所有花费
};
HotSpots::HotSpots(int n, int m) {
N = n;
M = m;
path = new int*[205];
for(int i=0;i<205;i++){
path[i] = new int[205];
}
}
HotSpots::~HotSpots() {
delete path;
}
void HotSpots::insertPath(int a, int b, int cost) {
if(a < b){
path[a][b] = cost;
}else{
path[b][a] = cost;
}
}
int HotSpots::getCost(int a, int b) {
if(a < b){
return path[a][b];
}else{
return path[b][a];
}
}
long long HotSpots::isValid(int *arr, int n) {
// cout << "arr[i]";
// for(int i=0;i<n;i++){
// cout << arr[i] << ' ';
// }
// cout << endl;
if(n!=N)return 0;
bool vis[205] = {false};
int pre = 0;
long long sum = 0;
bool flag = true;
for(int i=0; i<n; i++){
if(this->getCost(pre, arr[i]) && !vis[arr[i]]){
sum += this->getCost(pre, arr[i]);
pre = arr[i];
vis[arr[i]] = true;
} else {
flag = false;
}
}
if(this->getCost(arr[n-1],0) && flag){
sum += this->getCost(arr[n-1], 0);
} else {
// cout << "NO";
return 0;
}
return sum;
}
int main(){
int N, M;
cin >> N >> M;
HotSpots hotSpots(N, M);
// 输入路径
for(int i=0; i<M; i++){
int a, b, cost;
cin >> a >> b >> cost;
hotSpots.insertPath(a, b, cost);
}
// 开始判断
int minIndex, validCnt=0;
long long minCost = 1e9 + 1;
int lines;
cin >> lines;
for (int i=0; i<lines; i++){
int n;
cin >> n;
int *arr = new int[n];
for(int j=0;j<n;j++){
cin >> arr[j];
}
long long curCost = hotSpots.isValid(arr, n);
if(curCost > 0){
validCnt++;
if(curCost < minCost){
minIndex = i;
minCost = curCost;
}
}
}
cout << validCnt << endl;
cout << minIndex+1 << " " << minCost;
return 0;
}
7-3 树的同构
知识点：二叉树及其遍历、递归
思路：对于输入数据，先构建树，找到其根节点（入度为0）。
树的存储结构：
struct TreeNode
{
char Element;
int Left;
int Right;
} T1[10], T2[10];
递归地判断是否同构，输入两树的根节点，有如下情况：
- 两颗树都是空，返回true
- 一棵为空，另一棵不为空，返回false
- 根节点不同，返回false
- 左子树同时为空，递归判断右子树
- 左子树不为空且左边元素相同，递归判断左子树&右子树
- 左子树不为空且左边元素不同，递归判断左子树&右子树（交换顺序）
代码：
#include <stdio.h>
// 参考数据结构-浙江大学https://www.bilibili.com/video/BV1JW411i731?p=39&vd_source=e483d09b4b274b0564d9461541870776
#define Null -1
struct TreeNode
{
char Element;
int Left;
int Right;
} T1[10], T2[10];
int BuildTree(struct TreeNode T[]){
int N, Root = Null;
int *check = new int[N];
for(int i=0;i<N;i++) check[i]=0;
scanf("%d\n", &N);
if(N){
int cl,cr;
for(int i=0; i<N; i++){
scanf("%c %c %c", &T[i].Element, &cl, &cr);
getchar();
if(cl != '-'){
T[i].Left = cl - '0';
check[T[i].Left] = 1;
} else T[i].Left = Null;
if(cr != '-'){
T[i].Right = cr - '0';
check[T[i].Right] = 1;
} else T[i].Right = Null;
}
for(Root=0; Root<N; Root++)
if (!check[Root]) break;
}
return Root;
}
bool Isomorphic(int R1, int R2){
if (R1 == Null && R2 == Null){ // 两颗树都是空
return true;
}
if (((R1 == Null)&&(R2 != Null ) || ((R1 != Null)&&(R2 == Null)))){ // 一棵为空，另一棵不为空
return false;
}
if (T1[R1].Element != T2[R2].Element) // 根节点不同
return false;
if (T1[R1].Left == Null && T2[R2].Left == Null) // 左子树同时为空
return Isomorphic(T1[R1].Right, T2[R2].Right);
if ((T1[R1].Left!=Null && T2[R2].Left!=Null) && (T1[T1[R1].Left].Element == T2[T2[R2].Left].Element)) // 左子树不为空且左边元素相同
return Isomorphic(T1[R1].Left, T2[R2].Left) && Isomorphic(T1[R1].Right,T2[R2].Right);
else
return Isomorphic(T1[R1].Right, T2[R2].Left) && Isomorphic(T1[R1].Left, T2[R2].Right);
}
int main() {
int R1, R2;
R1 = BuildTree(T1);
R2 = BuildTree(T2);
if(Isomorphic(R1, R2)) printf("Yes\n");
else printf("No\n");
return 0;
}
7-4 最短工期
知识点：拓扑排序
思路：
-
用邻接矩阵储存路径，用
degrees[105]记录节点的入度。 -
以下是拓扑排序的过程：不断找出入度为0的点，记录个数
cnt，然后标记为-1（不重复访问），直到没有入度为0的点为止。 -
在这个过程中，用
f[105]记录从初始节点到当前节点的最长路径，比如f[i]表示从初始节点到第i个节点的最长路径。（动态规划的思想） -
最后判断，如果
cnt == N，即所有任务都能被完成，输出最长路径，否则输出impossible
细节:
- 因为存在值为0的边，所以邻接矩阵的初始值赋值为-1，表示不能到达
f[105]赋初始值为0- 已搜索过的入度为0的点，标记为-1，防止重复搜索
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
class Project {
public:
int N, M;
int path[105][105];
int degrees[105];
Project(int N, int M);
~Project();
void insertPath(int from, int to, int weight);
int findFarthest(); // 如果有任务不能完成，返回0，否则返回最长路径
};
Project::Project(int n, int m) {
N = n;
M = m;
for(int i=0; i<105; i++){
for(int j=0; j<105; j++){
path[i][j] = -1; // 不能等于0，因为存在两节点连通但是距离为0
}
}
for(int i=0; i<105; i++)
degrees[i]=0;
}
Project::~Project() {
}
void Project::insertPath(int from, int to, int weight) {
path[from][to] = weight;
degrees[to]++;
}
int Project::findFarthest() {
// cout << "degress" << endl;
// for(int i=0;i<105;i++){
// cout << degrees[i] << ' ';
// }
// cout << endl;
// cout << "N " << N << endl;
int cnt=0, res=0;
int f[105];
for(int i=0;i<105;i++)f[i]=0;
while(1)
{
int flag = 0;
for(int i=0; i<N; i++)
{
if(degrees[i] == 0)
{
degrees[i] = -1; //防止重复计算
flag = 1; //是否存在新的入度为0的点
// cout << "rudu" << i << " " << endl;
cnt++; //入度为0点也就是加入拓扑序列的总个数
for(int j=0; j<N; j++)
if(path[i][j] != -1)
{
degrees[j]--; //入度减一
f[j] = max(f[j], f[i] + path[i][j]);
res = max(res, f[j]);
}
}
}
// cout << "flag" << flag << endl;
if(flag == 0) break;
}
if(cnt != N) return 0;
else return res;
}
int main() {
int N, M;
cin >> N >> M;
Project p(N, M);
for(int i=0; i<M; i++){
int from, to, weight;
cin >> from >> to >> weight;
p.insertPath(from, to, weight);
}
int res = p.findFarthest();
// cout << "res" << res << endl;
if (res) {
cout << res;
}
else {
cout << "Impossible" << endl;
}
// cout << "wanshierle";
return 0;
}
7-5 三足鼎立
知识点：快速排序/堆排序、二分法
思路：输入数组arr[]，先将数组排序，遍历每个元素，对于arr[i]：已知三角形的两边有P和arr[i]，则第三边的范围是P-arr[i] < 第三条边 < P+arr[i]。用二分法搜索，从左到右第一个比P-arr[i]大的点的位置left，和从右到左第一个比P+arr[i]小的点的位置right，如果right - left >= 0，那么符合要求的节点的个数就是right - left + 1，累计一下这个值。
细节：
left = myUpperBound(P-arr[i]>=0?P-arr[i]:arr[i]-P, arr, i+1, n-1);// 从左向右，第一个大于左边界的数right = myLowerBound(P+arr[i], arr, i+1, n-1) - 1;// 从右向左，第一个小于右边界的数- 如果
P-arr[i] < 0，则换成arr[i] - P - 排序使用堆排序，时间复杂度O(nlogn)
代码：
#include <iostream>
using namespace std;
long long myLowerBound(long long target, long long *arr, long long start, long long last){
last+=1;
while (start < last)
{
long long mid = (start + last) / 2;
if (arr[mid] >= target)
{
last = mid;
}
else
{
start = mid + 1;
}
}
return start;
}
long long myUpperBound(long long target, long long *arr, long long start, long long last){
last += 1;
while (start < last)
{
long long mid = (start + last) / 2;
if (arr[mid] <= target)
{
start = mid + 1;
}
else
{
last = mid;
}
}
return start;
}
// 下浮
void Heapify(long long arr[], int n, int i){
// arr 存储堆的数组，n 数组长度， i 维护节点的下标
int largest = i; // 假设最大节点
int lson = 2 * i + 1;
int rson = 2 * i + 2;
if (lson < n && arr[largest] < arr[lson]){
largest = lson;
}
if (rson < n && arr[largest] < arr[rson]){
largest = rson;
}
if(largest != i){
long long tmp;
tmp = arr[largest];
arr[largest] = arr[i];
arr[i] = tmp;
Heapify(arr, n, largest);
}
}
// 堆排序入口
void HeapSort(long long arr[], int n){
// 建堆，从底往上构建
int i;
for(i = n / 2 - 1; i >= 0; i--){ // 从最后一个元素的父节点开始
Heapify(arr, n, i);
}
// 排序
for(i = n - 1; i > 0; i--){
long long tmp;
tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
Heapify(arr, i, 0);
}
}
int main() {
long long n, cnt = 0;
long long P;
cin >> n >> P;
long long arr[100005];
for(long long i=0; i<n; i++){
cin >> arr[i];
}
HeapSort(arr, n);
// qsort(arr, n, sizeof(arr[0]), cmpfunc);
// cout << "test" << myLowerBound(0, arr, 0, n-1) << endl;
for( long long i=0; i<n-1; i++ ){
// cout << i << " ";
long long left = myUpperBound(P-arr[i]>=0?P-arr[i]:arr[i]-P, arr, i+1, n-1); // 从左向右，第一个大于左边界的数
long long right = myLowerBound(P+arr[i], arr, i+1, n-1) - 1; // 从右向左，第一个小于右边界的数
if(right >= left) cnt += right-left+1;
// cout << arr[i]<<" "<<P-arr[i] << "left"<< left << " " << P+arr[i]<< "right" << right << " "<< right-left << endl;
}
cout << cnt;
return 0;
}