第148场双周赛：循环数组中相邻元素的最大差值、将数组变相同的最小代价、最长特殊路径、所有安放棋子方案的曼哈顿距离

🕗 发布于 2025-01-20 20:01 c++ 周赛 Lenyiin leetcode 算法

Q1、循环数组中相邻元素的最大差值

1、题目描述

给你一个循环数组 nums ，请你找出相邻元素之间的最大绝对差值。

**注意：**一个循环数组中，第一个元素和最后一个元素是相邻的。

2、解题思路

这个问题的核心是遍历循环数组并计算相邻元素之间的绝对差值。
由于数组是循环的，我们需要特别注意 第一个元素和最后一个元素 之间的差值。

步骤：

遍历数组中所有相邻元素对，计算它们之间的绝对差值。
需要考虑 第一个元素和最后一个元素 之间的差值，因为这是一个循环数组。
返回所有差值中的最大值。

3、代码实现

class Solution {
public:
    int maxAdjacentDistance(vector<int>& nums) {
        int n = nums.size(); // 获取数组的大小
        int diff = 0;        // 初始化最大差值为 0

        // 遍历数组中每一对相邻元素
        for (int i = 1; i < n; ++i) {
            // 计算当前相邻元素对的绝对差值, 并更新最大差值
            diff = max(diff, abs(nums[i] - nums[i - 1]));
        }

        // 计算第一个元素和最后一个元素之间的绝对差值
        diff = max(diff, abs(nums[0] - nums[n - 1]));

        return diff; // 返回最大绝对差值
    }
};

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n)，其中 n 是数组的大小。我们需要遍历数组一次来计算相邻元素的差值。

空间复杂度：O(1)，只使用了常量的额外空间。

Q2、将数组变相同的最小代价

1、题目描述

给你两个长度都为 n 的整数数组 arr 和 brr 以及一个整数 k 。你可以对 arr 执行以下操作任意次：

将 arr 分割成若干个 连续的 子数组，并将这些子数组按任意顺序重新排列。这个操作的代价为 k 。
选择 arr 中的任意一个元素，将它增加或者减少一个正整数 x 。这个操作的代价为 x 。

请你返回将 arr 变为 brr 的最小总代价。

子数组 是一个数组中一段连续非空的元素序列。

2、解题思路

思路分析

根据题目的描述，我们有两种可以影响总代价的操作：

调整元素：即对于 arr[i] 和 brr[i]，我们可以将 arr[i] 修改为 brr[i]，其代价为 |arr[i] - brr[i]|。
子数组操作：我们可以将 arr 按任意方式分割成连续的子数组，并将它们按任意顺序重新排列。这种操作的代价是 k。

目标是选择最佳的策略，使得总代价最小。

关键思路

直接修改：不进行子数组操作，直接通过调整元素将 arr 变为 brr，即每个元素都单独调整，代价为每个元素的差值的绝对值之和。
排序后再调整：我们可以尝试通过分割并重新排列 arr 和 brr 来降低代价。如果排序后 arr 和 brr 的元素完全相同，那么我们可以将其分割并重新排列，使得代价仅为 k。然后再计算调整的代价。

最小代价即为这两种策略的较小值：直接调整代价或分割并重新排列后的代价。

3、代码实现

class Solution {
public:
    long long minCost(vector<int>& arr, vector<int>& brr, long long k) {
        // 第一种情况: 直接调整每个元素的值, 代价为每个元素的差值绝对值之和
        long long ret1 = 0;
        for (int i = 0; i < arr.size(); ++i) {
            ret1 += abs(arr[i] - brr[i]);
        }

        // 第二种情况: 将 arr 和 brr 排序, 并尝试通过最小代价的操作来调整
        ranges::sort(arr);  // 排序 arr
        ranges::sort(brr);  // 排序 brr
        long long ret2 = k; // 重新排列的代价是 k
        for (int i = 0; i < arr.size(); ++i) {
            ret2 += abs(arr[i] - brr[i]);
        }

        // 返回两种情况的最小值
        return min(ret1, ret2);
    }
};

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n log n)，主要是排序的时间复杂度。

空间复杂度：O(1)，没有使用额外的空间。

给你一棵根节点为节点 0 的无向树，树中有 n 个节点，编号为 0 到 n - 1 ，这棵树通过一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和 vi 之间有一条长度为 lengthi 的边。同时给你一个整数数组 nums ，其中 nums[i] 表示节点 i 的值。

特殊路径 指的是树中一条从祖先节点往下到后代节点且经过节点的值 互不相同 的路径。

注意，一条路径可以开始和结束于同一节点。

请你返回一个长度为 2 的数组 result ，其中 result[0] 是最长特殊路径的长度，result[1] 是所有最长特殊路径中的最少节点数目。

2、解题思路

树的表示与遍历：
- 题目给定的是一棵无向树，树的每条边有一个权重，即边的长度。我们可以利用邻接表来表示这棵树，其中每个节点有一个列表，表示与其相连的节点及边的长度。
特殊路径的定义：
- 一条特殊路径要求路径中节点的值互不相同。换句话说，路径上不能出现重复的节点值。
- 我们需要找到从根节点 0 到所有后代节点的路径中，满足该条件的最长路径。
深度优先搜索 (DFS)：
- 我们可以使用 DFS 来遍历树，并通过路径的长度和路径上的节点值来判断是否符合特殊路径的条件。
- 在 DFS 过程中，我们需要记录当前路径上的节点值，通过一个 unordered_map 来标记每个节点值最后出现的深度位置，从而避免路径中出现重复的节点值。
- 我们需要在每次递归时保持对路径长度的更新，并且通过比较路径的长度来更新结果。
结果计算：
- 维护一个变量 result 来记录当前的最大路径长度和最小节点数。
- 在递归时，对于每一条路径，我们会计算其长度，并检查是否是最大路径。如果是，我们还需要更新最小节点数。

3、代码实现

class Solution {
public:
    vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
        int n = nums.size();

        // 构建图的邻接表表示
        vector<vector<pair<int, int>>> graph(n);
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].emplace_back(v, w); // u -> v
            graph[v].emplace_back(u, w); // v -> u
        }

        // 初始化答案为最小值
        pair<int, int> result = {-1, 0};      // result.first: 最大路径长度, result.second: 最小节点数
        vector<int> pathLength = {0};         // 路径的累计长度
        unordered_map<int, int>lastSeenDepth; // 记录每个节点值的最后一次出现的深度

        // 深度优先搜索 (DFS) 函数, 计算特殊路径
        auto dfs = [&](auto&& dfs, int node, int parent, int lastSeen) -> void {
            int currentValue = nums[node]; // 当前节点的值
            int previousDepth = lastSeenDepth[currentValue]; // 当前值上次出现的深度

            // 更新当前路径中最大的深度
            lastSeen = max(lastSeen, previousDepth);

            // 更新答案, 计算当前路径长度和节点数
            result = max(result, make_pair(pathLength.back() - pathLength[lastSeen], lastSeen - (int)pathLength.size()));

            // 更新当前节点值的最后出现位置
            lastSeenDepth[currentValue] = pathLength.size();

            // 遍历所有邻接节点 (子节点)
            for (const auto& [nextNode, edgeWeight] : graph[node]) {
                // 避免访问父节点
                if (nextNode != parent) {
                    pathLength.push_back(pathLength.back() + edgeWeight);   // 更新路径长度
                    dfs(dfs, nextNode, node, lastSeen);                     // 递归访问子节点
                    pathLength.pop_back();                                  // 回溯, 恢复路径长度
                }
            }

            // 恢复当前节点值的上次出现深度
            lastSeenDepth[currentValue] = previousDepth;
        };

        // 从根节点 0 开始深度优先搜索 (DFS)
        dfs(dfs, 0, -1, 0);

        // 返回最长路径长度和最少节点数
        return {result.first, -result.second};
    }
};

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n)。树的每个节点和每条边都仅被访问一次，DFS 的复杂度为 O(n)，其中 n 是节点数。

空间复杂度：O(n)。使用邻接表 graph 存储树结构，pathLength 数组和 lastSeenDepth 哈希表分别需要 O(n) 的空间。

Q4、所有安放棋子方案的曼哈顿距离

1、题目描述

给你三个整数 m ，n 和 k 。

给你一个大小为 m x n 的矩形格子，它包含 k 个没有差别的棋子。请你返回所有放置棋子的 合法方案 中，每对棋子之间的曼哈顿距离之和。

一个 合法方案 指的是将所有 k 个棋子都放在格子中且一个格子里至多只有一个棋子。

由于答案可能很大，请你将它对 109 + 7 取余后返回。

两个格子 (xi, yi) 和 (xj, yj) 的曼哈顿距离定义为 |xi - xj| + |yi - yj| 。

2、解题思路

树的表示与遍历：
- 题目给定的是一棵无向树，树的每条边有一个权重，即边的长度。我们可以利用邻接表来表示这棵树，其中每个节点有一个列表，表示与其相连的节点及边的长度。
特殊路径的定义：
- 一条特殊路径要求路径中节点的值互不相同。换句话说，路径上不能出现重复的节点值。
- 我们需要找到从根节点 0 到所有后代节点的路径中，满足该条件的最长路径。
深度优先搜索 (DFS)：
- 我们可以使用 DFS 来遍历树，并通过路径的长度和路径上的节点值来判断是否符合特殊路径的条件。
- 在 DFS 过程中，我们需要记录当前路径上的节点值，通过一个 unordered_map 来标记每个节点值最后出现的深度位置，从而避免路径中出现重复的节点值。
- 我们需要在每次递归时保持对路径长度的更新，并且通过比较路径的长度来更新结果。
结果计算：
- 维护一个变量 result 来记录当前的最大路径长度和最小节点数。
- 在递归时，对于每一条路径，我们会计算其长度，并检查是否是最大路径。如果是，我们还需要更新最小节点数。

3、代码实现

const int MOD = 1'000'000'007;
const int MAX = 100'000;

// 定义阶乘和阶乘的逆元
long long fact[MAX];     // fact[i] 表示 i 的阶乘
long long inv_fact[MAX]; // inv_fact[i] 表示 i 的阶乘的逆元

// 快速幂函数, 计算 x 的 n 次方 % MOD
long long mod_pow(long long x, int n) {
    long long result = 1;
    while (n) {
        if (n % 2) {
            result = (result * x) % MOD;
        }
        x = (x * x) % MOD;
        n /= 2;
    }
    return result;
}

// 预计算阶乘和阶乘逆元
auto init = [] {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    inv_fact[MAX - 1] = mod_pow(fact[MAX - 1], MOD - 2); // 使用费马小定理计算逆元
    for (int i = MAX - 2; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
    return 0;
}();

// 组合数公式计算 C(n, m) % MOD
long long comb(int n, int m) {
    if (m < 0 || m > n) {
        return 0;
    }
    return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}

// 计算曼哈顿距离的和
class Solution {
public:
    int distanceSum(int m, int n, int k) {
        // 计算所有的曼哈顿距离之和
        long long total_distance = calculateTotalDistance(m, n);

        // 计算选择k个位置的方式
        long long ways_to_choose_k_positions = comb(m * n - 2, k - 2);

        // 结果是两者的乘积, 取模
        return (total_distance * ways_to_choose_k_positions) % MOD;
    }

private:
    // 计算曼哈顿距离之和
    long long calculateTotalDistance(int m, int n) {
        long long row_distance = m * (1LL * n * n - 1) + n * (1LL * m * m - 1);
        long long total_distance = m * n * row_distance / 6;
        return total_distance % MOD;
    }
};

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n)。树的每个节点和每条边都仅被访问一次，DFS 的复杂度为 O(n)，其中 n 是节点数。

空间复杂度：O(n)。使用邻接表 graph 存储树结构，pathLength 数组和 lastSeenDepth 哈希表分别需要 O(n) 的空间。

原文地址：https://blog.csdn.net/mmlhbjk/article/details/145249474

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Android Audio——使用AudioRecord录制音频
下一篇：2024年博客成长记：成就、挑战与未来展望

Qt常用控件之输入类控件
本篇博客详细讲解了 Qt 的输入类控件，例如QLineEdit、QTextEdit、QComboBox、QSpinBox、QDateTimeEdit、QDial、QSlider
阅读更多2025-01-20
【Linux系统】Ext系列磁盘文件系统二：引入文件系统
（需要查看目录寻找所需知识点）本节讲解：1、4KB数据块；2、分区；3、inode；4、块组 Block group 中的结构区域：inode table / Data Blocks / inode
阅读更多2025-01-20
Social LSTM：Human Trajectory Prediction in Crowded Spaces | 文献翻译
行人遵循不同轨迹以避免障碍物和容纳同行者。任何在这种场景中巡航的自动驾驶车辆都需要能够遇见行人的未来位置并相应地调整其路线以避免碰撞。轨迹预测问题能够被看作一个顺序生成任务，其中我们对基于行人过去的位
阅读更多2025-01-20
C/C++:数组定义方式及指针加法
输出数组b最后一个元素的地址。
阅读更多2025-01-20
通过图形界面展现基于本地知识库构建RAG应用
1. 本地 embedding 模型不影响召回效率， CPU 性能足够，建议采用2. 本地 (chat)大模型对内容的理解非常有限，实际工作中可以采用 LLMs Gateway 切换，RAG环境建议采
阅读更多2025-01-20
RIME-CNN-LSTM-Attention多变量多步时序预测Matlab实现
RIME-CNN-LSTM-Attention多变量多步时序预测Matlab实现
阅读更多2025-01-20
自然语言处理（GloVe）：原理、特点、应用、技术、相关学术分享
自然语言处理（GloVe）：原理、特点、应用、技术、相关学术分享
阅读更多2025-01-20
深度学习图像算法中的网络架构：Backbone、Neck 和 Head 详解
深度学习图像算法中的网络架构：Backbone、Neck 和 Head 详解
阅读更多2025-01-20
TrueNas Webui页面自定义
把拉取的truenas的项目代码通过xftp7传输到远程，这样vscode里可以直接打开传输过去的项目，然后再按照readme文档里运行的命令运行项目即可自行更改。通过这些步骤，你可以在 TrueNA
阅读更多2025-01-20
2024年12月蓝桥杯Scratch12月stema选拔赛真题—小星星
2024年12月蓝桥杯Scratch12月stema选拔赛真题—小星星
阅读更多2025-01-20

第148场双周赛：循环数组中相邻元素的最大差值、将数组变相同的最小代价、最长特殊路径、所有安放棋子方案的曼哈顿距离

Q1、循环数组中相邻元素的最大差值

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q2、将数组变相同的最小代价

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q3、最长特殊路径

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

Q4、所有安放棋子方案的曼哈顿距离

1、题目描述

2、解题思路

3、代码实现

4、复杂度分析

相关文章