当前位置: 首页 > news >正文

【洛谷】The Blocks Problem、合并两个有序数组,补充pair(vector相关算法题p2)

文章目录

  • 88.合并两个有序数组
    • 题目描述
    • 题目解析
    • 代码
  • [UVA101 The Blocks Problem](https://www.luogu.com.cn/problem/UVA101)
    • 题目描述
    • 题目解析
    • 代码


88.合并两个有序数组

题目描述

在这里插入图片描述

题目解析

这道题有两个思路,一个是开辟一个m+n大小的数组然后遍历两个原数组按大小顺序尾插到新数组中,尾插完后再将新数组的值拷贝回原数组,但是这道题已经在第一个数组里为我们开好空间了,所以我们直接在原数组里操作就行了,思路是分别从两个数组的尾部开始遍历,因为从前遍历会发生数据的覆盖,跳出while循环后若是第二个数组还剩余,就将第二个数组中的数据拷贝到一数组。

代码

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int mcur = m - 1;int ncur = n - 1;int rcur = m + n - 1;while(mcur >= 0 && ncur >= 0){if(nums1[mcur] > nums2[ncur]){nums1[rcur--] = nums1[mcur--];}else {nums1[rcur--] = nums2[ncur--];}}while(ncur >= 0){nums1[rcur--] = nums2[ncur--];}}
};

UVA101 The Blocks Problem

题目描述

在这里插入图片描述

题目解析

这道题会用到pair,所以小编先介绍一下什么是pair,原理不用深究,知道怎么用就行了。

在这里插入图片描述

这道题先理解题意,我们以样例来解释,一共有10个位置,每个位置有一个木块。我们可以把每个位置理解成一个槽,每个槽装着木块,经过一系列操作后每个槽有可能没有木块,也有可能有多个木块垒在一起,示意图如下:

在这里插入图片描述

所以我们需要一个二维数组来存储数据,一维代表槽,二维代表槽中的木块,题目中说最多有25个木块也就是起始最多有25个槽,所以我们创建30个数组妥妥够了。
这道题看似有四个操作,其实总结就是两个,归位和移动,四个操作都有移动,所以我们每次循环都要移动,无非就是判断是否归位,我们分析题目知道当第一个单词为move需要将a上方木块归位,第二个单词为onto需要将b上方木块归位,所以我们需要写两个函数,归位clear和移动move,归位需要遍历a木块上方的所有木块,把木块尾插到木块初始的槽,木块本身的数值就是它其实槽的编号,move就是将a木块上方的木块及a木块全部尾插到b木块所在的槽。
而我们要执行上述两个操作首先需要先找到a b目标木块在哪,所以首先需要写一个find函数,这里find的返回值就需要用到pair,返回木块在哪个槽和在槽的哪个位置,需要注意题目要求当a与b在同一个槽是无需操作,所以我们在循环里需要加上这个判断,若为真就跳过当次循环。
而循环的设置也很有讲究,首先cin一个n读取木块数目,然后后续输入就一直都是 字符串 数字字符串数字的格式了,所以我们可以while(cin >> op1 >> a >> op2 >> b),当最后输入quit时由于不匹配就会跳出循环。
最后还需要依次打印结果。

代码

using namespace std;
#include <iostream>
#include <vector>const int N = 30;
vector<int> v[N];
int n;string op1, op2;
int a, b;
typedef pair<int, int> pii;pii find(int x)
{for (int i = 0; i < N; i++){for (int j = 0; j < v[i].size(); j++){if (v[i][j] == x){return { i,j };}}}
}void clear(int x1, int y1)
{//遍历a木块上方所有木块for (int i = y1 + 1; i < v[x1].size(); i++){//pos是待归位木块在那个槽,也就是木块本身的值是多少int pos = v[x1][i];v[pos].push_back(pos);}//并没有真的移除数据,需要resizev[x1].resize(y1 + 1);
}void move(int x1, int y1, int x2)
{//遍历目标木块及目标木块上方所有木块for (int i = y1; i < v[x1].size(); i++){//将目标木块尾插到b木块所在位置v[x2].push_back(v[x1][i]);}v[x1].resize(y1);
}int main()
{cin >> n;//初始化vectorfor (int i = 0; i < n; i++){v[i].push_back(i);}while (cin >> op1 >> a >> op2 >> b){//先找到a,b的位置pii p1 = find(a);int x1 = p1.first, y1 = p1.second;pii p2 = find(b);int x2 = p2.first, y2 = p2.second;//a与b在同一堆无需处理if (x1 == x2)continue;if (op1 == "move"){clear(x1,y1);}if (op2 == "onto"){clear(x2, y2);}move(x1, y1, x2);}for (int i = 0; i < n; i++){cout << i << ':';for (int j = 0; j < v[i].size(); j++){cout << " " << v[i][j];}cout << endl;}return 0;
}
http://www.xdnf.cn/news/1160173.html

相关文章:

  • Spring AI 集成阿里云百炼与 RAG 知识库,实现专属智能助手(框架思路)
  • 2025年终端安全管理系统的全方位解析,桌面管理软件的分析
  • Lua:小巧而强大的脚本语言,游戏与嵌入式的秘密武器
  • 智能体性能优化:延迟、吞吐量与成本控制
  • “融合进化,智领未来”电科金仓引领数字化转型新纪元
  • 前端JavaScript进阶
  • 基于大数据的旅游推荐系统 Python+Django+Hive+Vue.js
  • 文娱投资的逆势突破:博派资本的文化旅游综合体战略
  • 调试Claude code的正确姿势
  • XTTS实现语音克隆:精确控制音频格式与生成流程【TTS的实战指南】
  • 一维数组练题习~
  • 【1】YOLOv13 AI大模型-可视化图形用户(GUI)界面系统开发
  • 基础神经网络模型搭建
  • 【数据结构】栈和队列(接口超完整)
  • jQuery 插件
  • 本地部署 Claude 大语言模型的完整实践指南
  • 创建一个触发csrf的恶意html
  • 创新几何解谜游戏,挑战空间思维极限
  • ollama基本配置
  • 玄机——第六章 流量特征分析-蚂蚁爱上树
  • 2025最新 PostgreSQL17 安装及配置(Windows原生版)
  • 【Go语言-Day 22】解耦与多态的基石:深入理解 Go 接口 (Interface) 的核心概念
  • [硬件电路-59]:电源:电子存储的仓库,电能的发生地,电场的动力场所
  • 手写tomcat
  • API获取及调用(以豆包为例实现图像分析)
  • 用 Jetpack Compose 写 Android 的 “Hello World”
  • SSE和WebSocket区别到底是什么
  • linux shell从入门到精通(一)——为什么要学习Linux Shell
  • MongoDB多节点集群原理 -- 复制集
  • 《杜甫传》读书笔记与经典摘要(一)