算法往年题复习（一）| 看不懂来 Gank 我

发布时间：2023年12月17日

数组逆序差的最大值

题目描述

给定一个数组A[0, 1, …, n ? 1]，请设计算法计算这个数组逆序差的最大值，即求max{A[i] - A[j]}, A[i] >= A[j], 0 <= i < j < n。写出算法思路与过程、分析时间复杂度。

算法思路与过程

在遍历数组中每一个元素的过程中，用一个变量存储前面元素的最大值maxValue，计算当前元素A[j]与maxValue之间逆序差的值，并更新全局逆序差的最大值。计算结束后，更新maxValue，即maxValue = max(maxValue, A[j])。

当数组的所有元素遍历结束，则得到全局逆序查的最大值。

实现代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++) {
        cin >> A[i];
    }
    int maxVal = A[0], res = INT_MIN;
    for(int j = 1; j < n; j++) {
        res = max(res, maxVal - A[j]);
        maxVal = max(maxVal, A[j]);
    }
    cout << res << endl;
    return 0;
}

时间复杂度

时间复杂度为 $O (n)$ 级别

类似题型

121. 买卖股票的最佳时机

将 K 个数组元素有序输出

题目描述

给定 K 个有序数组 $A_k[0,1, …, n_k ? 1], 1 ≤ k ≤ K$ ，请设计方法将这 K 个数组元素有序输出。写出算法思路与过程、分析时间复杂度。

算法思路与过程

维护一个大小 K 的小顶堆，可以使用优先队列来实现。初始的时候，将 K 个有序数组的第一个元素加入优先队列，建立小顶堆。此时，堆顶元素就是这 K 个有序数组的最小值。

为了便于操作，可以维护一个三元组，存储数组元素值、元素所属数组、元素所属数组的下标，将这个三元组作为小顶堆的基本单元。

后续重复执行以下操作直到优先队列为空：

将堆顶元素弹出，输出元素值
判断元素值所在数组是否一全部输出，若数组元素未全部输出，则将数组中的下一个元素信息加入优先队列；若数组元素已全部输出，则不进行入队操作。

实现代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

typedef tuple<int, int, int> Tri;
// 自定义比较类
struct Compare {
    bool operator()(const Tri& a, const Tri& b) {
        return get<0>(a) > get<0>(b);
    }
};

int main()
{
    int k;
    cin >> k;
    vector<vector<int>> A(k);
    for(int i = 0; i < k; i++) {
        int n;
        cin >> n;
        vector<int> nums(n);
        for(int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        A[i] = nums;
    }
    // 小顶堆
    priority_queue<Tri, vector<Tri>, Compare> q;
    // 初始化最小堆
    for(int i = 0; i < k; i++) {
        if( A[i].size() )  q.push(make_tuple(A[i][0], i, 0));
    }
    
    while( !q.empty() ) {
        auto t = q.top();
        int num = get<0>(t), idx = get<1>(t), i = get<2>(t);
        q.pop();
        cout << num << " ";
        i++;
        if( i < A[idx].size() ) {
            q.push(make_tuple(A[idx][i], idx, i));
        }
    }
    return 0;
}

时间复杂度

建堆操作的时间复杂度： $O (k)$

递归式： $T (k) = 2 T (k /2) + l o g k$ ，可以用主定理得出上述建堆操作的时间复杂度

单次插入操作的时间复杂度： $O (l o g k)$

返回堆顶元素的时间复杂度： $O (1)$

删除堆顶元素的时间复杂度： $O (l o g k)$

整体的时间复杂度： $O (Nl o g K)$ ，这里的 N 是总的元素个数

类似题型

23. 合并 K 个升序链表

二叉搜索树

题目描述

给定一棵二叉搜索树，请设计算法找到树中与关键字 x 的差的绝对值最小的节点。二叉搜索树中任一中间结点的关键字都比左孩子大，且比右孩子小。写出算法思路与过程、分析时间复杂度。

算法思路与过程

采用递归的思路求解该问题，先比价关键字 x 与搜索树的根值：

若x == root -> val：差的绝对值最小的节点一定是根节点，直接返回
若x < root -> val：差的绝对值最小的节点可能存在于包括当前节点的左子树，也可能是当前节点的父节点
- 若当前节点的左子树为空，比较当前节点与当前节点的父节点，取差的绝对值最小的节点，即min(abs(x - root -> val), abs(x - pVal)
- 若当前节点的左子树不为空，继续递归求解左子树
若x > root -> val：差的绝对值最小的节点可能存在于包括当前节点的右子树，也可能是当前节点的父节点
- 若当前节点的右子树为空，比较当前节点与当前节点的父节点，取差的绝对值最小的节点，即min(abs(x - root -> val), abs(x - pVal)
- 若当前节点的右子树不为空，继续递归求解右子树。

实现代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct node {
    node *left, *right;
    int val;
    node(int x) : val(x), left(nullptr), right(nullptr) {}
} *Node;

// 二叉搜索树插入操作
// 二叉搜索树不允许出现两个重复元素
Node insert(Node root, int val)
{
    if( !root ) root = new node(val);
    else if( val < root -> val )  root -> left = insert(root -> left, val);
    else if( val > root -> val )  root -> right = insert(root -> right, val);
    return root;
}

// 找绝对值最小的节点
// pVal是父节点的值
int solve(Node root, int x, int pVal)
{
    int t = abs(x - root -> val);
    if( x == root -> val ) {
        return 0;
    }
    else if( x < root -> val ) {
        if( root -> left == nullptr )  return min(t, abs(x - pVal));
        return solve(root -> left, x, root -> val);
    }
    else {
        if( root -> right == nullptr )  return min(t, abs(x - pVal));
        return solve(root -> right, x, root -> val);
    }
}

int main()
{
    int n, x;
    cin >> n >> x;
    Node root = nullptr;
    // 输入二叉搜索树
    while( n-- ) {
        int t;
        cin >> t;
        root = insert(root, t);
    }
    cout << solve(root, x, root -> val) << endl;
    return 0;
}

时间复杂度

时间复杂度为 $O (l o g n)$ 量级

涉及知识点

二叉搜索树

天然气输气管道网络

题目描述

在这里插入图片描述

算法思路与过程

采用贪心的策略：若 s 到 t 的最安全传输路径经过 w，那么从 s 到 t 的最安全传输路径一定为从 s 到 w 的最安全传输路径加上从 w 到 t 的最安全传输路径。

贪心思路正确性证明：（反证法）

记从 s 到 t 的最大安全概率为P(s, t)，假设存在一条从 s 经过 w 到达 t 的最安全路径，但是安全概率不等于P(s, w) * P(w, t)，即P(s, t) > P(s, w) * P(w, t)。那么我们可以将最安全路径分成两部分L1 = (s...w)和L2 = (w...t)，因此P(s, t) = P(L1) * P(L2)。

可得，P(s, t) = P(L1) * P(L2) > P(s, w) * P(w, t)。可以得出P(L1) > P(s, w)和P(L2) > P(w, t)至少有一条成立，与原假设P(s, w)和P(w, t)分别是 s 到 w 和 w 到 t 的最安全概率矛盾。原命题得证。

因此这道题可以采用 Dijkstra 的思想求解该问题。用dp[i]表示从起点 s 到节点 i 的安全传输的最大概率，用path[i]记录经过节点i最安全路径的上一节点。初始置dp[s] = 1，其他节点dp[i] = 0。

用集合st存储当前以确定最安全概率的点。

遍历所有节点，找不在集合st中，找与起点s安全概率最大的点v，更新点v所有邻接节点i的最大安全概率dp[i]，并用path记录安全路径。更新完毕后，将节点v加入集合st。

当所有节点都加入集合st后，根据根据path记录的路径信息，便可以从path[t]开始，反向输出最安全路径。

实现代码

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

typedef pair<double, int> PII;
const int N = 1010, M = 20020;
int n, m;  // 节点数和边数
int s, t;  // 起点和终点
int h[N], e[M], ne[M], idx;
double p[M], dp[N];
int pre[N];
bool st[N];  // 判断节点是否已加入集合

void insert(int a, int b, double c)
{
    e[idx] = b;
    p[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

double dijkstra()
{
    memset(dp, 0, sizeof(dp));
    memset(pre, -1, sizeof(pre));
    memset(st, false, sizeof(st));
    dp[s] = 1;  // 初始化起点
    // first：节点s到i的安全概率
    // second：节点编号
    // 大顶堆
    priority_queue<PII, vector<PII>, less<PII>> heap;
    // 将起始节点加入堆中
    heap.push({1, s});
    while( heap.size() > 0 ) {
        // 取出最安全的节点
        auto [val, idx] = heap.top();
        heap.pop();
        // 当前节点未加入集合
        if( !st[idx] ) {
            st[idx] = true;
            // 更新后继节点
            for(int i = h[idx]; i != -1; i = ne[i]) {
                int j = e[i];
                if(dp[j] < val * p[i]) {
                    dp[j] = val * p[i];
                    pre[j] = idx;
                    // 这里不更新堆中元素，而是直接插入堆
                    // 因为旧值比新值小，新值会优先取，旧值后续会被pop出去
                    heap.push({dp[j], j});
                }
            }
        }
    }
    return dp[t];
}

int main()
{
    cin >> n >> m >> s >> t;
    memset(h, -1, sizeof(h));  // 初始化邻接表
    // 构建图
    for(int i = 0; i < m; i++) {
        int a, b;
        double c;
        cin >> a >> b >> c;
        insert(a, b, 1 - c);
    }
    cout << dijkstra() << endl;
    // 输出路径
    stack<int> path;
    int tmp = t;
    while( pre[tmp] != -1 ) {
        path.push(tmp);
        tmp = pre[tmp];
    }
    cout << s;
    while( !path.empty() ) {
        cout << "-->" << path.top();
        path.pop();
    }
    return 0;
}

输入样例：

时间复杂度

若使用朴素 Dijkstra 算法，时间复杂度为 $O(V^2)$ 级别

若使用堆优化版的 Dijkstra 算法，时间复杂度为 $O (El o g V)$ 级别

涉及知识点

Dijkstra 算法

化学品存放

题目描述

某单位要在仓库里选择存放化学品的房间 ${r_1, r_2, ..., r_n\}$ 。如下图所示，这些房间首尾相连围成一个圈，且有些房间已经堆满杂物，不能再放化学品。考虑到安全性，这些化学品不能同时存放在两个相邻的房间（但杂物和化学品可以），不然会发生危险。假设房间 i 的空间容量为 $c_i$ ，请计算在保证安全的情况下，最多能存放多少化学品？请写出算法思路与过程、分析时间复杂度。

算法思路与过程

法一

由于首尾连成一个圈，所以首尾不能同时存放化学用品，可以通过简化成分别计算首尾不相连的r[1...n-1]和r[2...n]这两种情况所能存放化学品的最大值，两种情况再取最大值。

状态定义：dp[i]表示r[1...i]最大能存放化学品的数量。

状态转移：

若r[i]存放杂物，则dp[i] = maxdp[i-1]
若r[i]不存放化学品，则dp[i] = dp[i-1]
若r[i]存放化学品，则dp[i] = dp[i-2] + r[i]

法二

与上一种方法类似，同样是分成首尾不相连的r[1...n-1]和r[2...n]两种子情况，二者求最值。不同之处在于，这里使用动态规划中的状态机模型进行分析，然后对状态进行压缩。

状态定义：

dp[i][0]：第 i 间存放杂物的最大值
dp[i][1]：第 i 间不存放化学品的最大值
dp[i][2]：第 i 间不存放化学品的最大值

根据上述的状态定义，我们可以绘制如下的状态转移模型图：

在这里插入图片描述

根据状态机模型图可以发现，第i间的状态只与第i - 1间的状态有关，且存放杂物和不存放化学品的两个状态可以进行合并，因此可以得到如下的状态压缩后的定义：

dp[0]：当前状态不存放化学品【包含了杂物的情况，只能不存放】
dp[1]：当前状态存放化学品

在这里插入图片描述

状态转移方程：

第 i 间房有杂物：保持原状态，此时的dp[1]的含义其实是上一个存放化学品房间的最大值【dp[j][1]，其中j < i】
第 i 间房没有杂物：
- 不存放化学品：dp[0] = max(dp[0], dp[1])
- 存放化学品：dp[1] = dp[0] + r[i]

实现代码

法一代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int solve(const vector<int>& r, const vector<bool>& flag, int begin, int n)
{
    vector<int> dp(n + 1, 0);
    for(int i = begin; i < begin + n; i++) {
        // 第i个房间存放杂物
        if( flag[i] ) {
            dp[i] = dp[i-1];
        }
        // 不存放杂物，则考虑是否存化学品，取最大值
        else {
            dp[i] = max(dp[i-1], dp[i-2] + r[i]);
        }
    }
    return dp[begin + n - 1];
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> r(n + 1);
    vector<bool> flag(n + 1, false);
    for(int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    int x;
    // 存放杂物房间的编号
    for(int i = 1; i <= m; i++) {
        cin >> x;
        flag[x] = true;
    }
    cout << max(solve(r, flag, 1, n - 1), solve(r, flag, 2, n - 1)) << endl;
    return 0;
}

法二代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int solve(const vector<int>& r, const vector<bool>& flag, int begin, int n)
{
    vector<int> dp(2, 0);
    for(int i = begin; i < begin + n; i++) {
        // 第i个房间存放杂物
        if( flag[i] ) {
            continue;
        }
        // 不存放杂物
        else {
            dp[0] = dp[0] + dp[1];
            dp[1] = dp[0] + r[i];
        }
    }
    return max(dp[0], dp[1]);
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> r(n + 1);
    vector<bool> flag(n + 1, false);
    for(int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    int x;
    // 存放杂物房间的编号
    for(int i = 1; i <= m; i++) {
        cin >> x;
        flag[x] = true;
    }
    cout << max(solve(r, flag, 1, n - 1), solve(r, flag, 2, n - 1)) << endl;
    return 0;
}

时间复杂度

两种方法的时间复杂度都是 $O (n)$ 级别，不同之处在于法一的空间复杂度为 $O (n)$ ，法二的空间复杂度为 $O (1)$

涉及知识点

状态机模型：

摄像头布置

题目描述

在这里插入图片描述

算法思路与过程

先将所有监测点位置从小到大排序
依次遍历每个检测点：
- 若当前摄像头个数为 0，或当前摄像头的右端点位置right小于监测点p[i]的位置：摄像头个数加1，即cnt++。同时，让新增摄像头左端点的位置等于p[i]，更新右端点right的位置。计算公式为right = p[i] + 2 * sqrt(r*r - h*h)
- 当前监测点的右端点位置right大于等于监测点p[i]的位置：继续遍历。

贪心正确性证明

每个摄像头的监控范围其实可以看成一个在数轴上长度为2 * sqrt(r*r - h*h)的区间。

数学归纳法证明

设监测点的个数为 $n$ ，且按照监测点位置递增的顺序排序p[i] <= p[i+1]

当 $n = 1$ 时，显然只需要一个区间就可以覆盖，贪心法得到的解是最优解。

假设当 $n = k$ 时，贪心法得到的解是最优解，即最少需要cnt个区间解可以覆盖所有的监测点。

当 $n = k + 1$ 时：

若第k + 1个点已经被前cnt个区间覆盖了，那么贪心法不会增加新的区间，因此贪心法得到的解为最优解。
若第k + 1个点没有被前cnt个区间覆盖，那么贪心法会增加一个新的区间，使它的左端点恰好是第k+1个点的位置。而这个区间是必须的，因为若将第cnt个区间向右移动，使其恰好覆盖第k+1个点，那么原第cnt个区间覆盖端点中，至少有一个最左端点此时无法被覆盖。

综上所述，贪心算法得到的解是最优解。

在这里插入图片描述

实现代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
    int n;
    double r, h;
    cin >> n >> r >> h;
    vector<double> p(n);
    for(int i = 0; i < n; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());
    int cnt = 0;
    double right;
    for(auto t : p) {
        if( cnt == 0 || right < t ) {
            cnt++;
            right = t + 2 * sqrt(r*r - h*h);   
        }
    }
    cout << cnt << endl;
    return 0;
}

时间复杂度

时间开销主要在排序，因此整体的时间复杂度为 $O (n l o g n)$ 级别

涉及知识点

贪心

修建围栏

题目描述

给定 $n \times m$ 的矩阵格子，每个格子要么养了羊，要么种有庄稼，要么是空地。羊可以上下左右移动去吃庄稼。如何在格子的边界上修建最少的围栏，阻挡羊使得庄稼不被吃掉。一个格子有四个边界可以修建 4 个围栏，假定整个矩阵的四周边界已经修建好围栏。请设计算法求最少需要修建的围栏数。写出算法思路与过程、分析时间复杂度。

算法思路与过程

由于羊可以上下左右移动去吃庄稼，因此，我们只需要将羊围起来或者将庄稼围起来即可。

由于能力有限，这里暂时不讨论将空地也包裹住，使需要的围栏数减少的情况【挖个坑，日后有缘再填】

具体算法思路如下：

以将羊围起来为例，遍历图中的所有方格，并用一个矩阵记录图中方格是否被遍历过。

若当前方格没有被遍历过，且当前方格是羊，则进行深度优先搜索：

遍历与当前方格邻接的方格。

若邻接的方格是羊，则不需要用围栏将这两个方格隔开，调用 DFS 继续搜索邻接方格。
若邻接的方格不是羊，则需要用一个围栏将这两个方格隔开。
若邻接的是墙，则不需要额外围栏围起来。

每遍历一个节点，都需要将该节点记录，避免 DFS 过程中重复遍历。

实现代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010, M = 1010;
int g[N][M];
bool st[N][M];

int n, m;
// 1：围羊
// 2：围庄稼
int cnt[3] = {0, 0, 0};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

// t是要围的目标
void dfs(int r, int c, int t)
{
    st[r][c] = true;
    for(int i = 0; i < 4; i++) {
        int tx = r + dx[i], ty = c + dy[i];
        if(tx >= 0 && tx < n && ty >=0 && ty < m && !st[tx][ty]) {
            // 不一致，加堵墙隔开
            if(g[tx][ty] != t) {
                cnt[t]++;
            }
            else {
                dfs(tx, ty, t);
            }
            st[tx][ty] = true;
        }
    }
}

int main()
{
    cin >> n >> m;
    // 0: 空地
    // 1: 羊
    // 2: 庄稼
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    // 围羊
    memset(st, false, sizeof(st));
    for(int i =0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if( !st[i][j] &&  g[i][j] == 1) {
                dfs(i, j, 1);
            }
        }
    }
    // 围庄稼
    memset(st, false, sizeof(st));
    for(int i =0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if( !st[i][j] &&  g[i][j] == 2) {
                dfs(i, j, 2);
            }
        }
    }
    
    cout << min(cnt[1], cnt[2]) << endl;
    return 0;
}

时间复杂度

时间复杂度为 $O (NM)$ 级别

涉及知识点

DFS or BFS

文章来源:https://blog.csdn.net/qq_45931691/article/details/135050768
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

算法往年题复习（一）| 看不懂来 Gank 我

文章目录

数组逆序差的最大值

题目描述

算法思路与过程

实现代码

时间复杂度

类似题型

将 K 个数组元素有序输出

题目描述

算法思路与过程

实现代码

时间复杂度

类似题型

二叉搜索树

题目描述

算法思路与过程

实现代码

时间复杂度

涉及知识点

天然气输气管道网络

题目描述

算法思路与过程

实现代码

时间复杂度

涉及知识点

化学品存放

题目描述

算法思路与过程

法一

法二

实现代码

法一代码

法二代码

时间复杂度

涉及知识点

摄像头布置

题目描述

算法思路与过程

贪心正确性证明

实现代码

时间复杂度

涉及知识点

修建围栏

题目描述

算法思路与过程

实现代码

时间复杂度

涉及知识点