【C++ 算法进阶】算法提升三

🕗 发布于 2024-10-18 17:13 c++ 算法 开发语言

距离二叉树节点为K的位置（类层序遍历建立父表）

题目

给定三个参数：

二叉树的头结点Hrad 树上某个节点targert 正数K

从target开始可以向上或者向下走

返回与target的距离为K的所有节点

题目分析

这道题的主要难点在于我们是要从二叉树上的某个节点target开始而不是直接从头节点开始

而一般的二叉树都是二叉链结构我们只能找到他的左右孩子节点

所以说我们这里要想个办法来记录每个子节点的父节点是谁

如何记录每个节点的父节点

我们这里可以直接采用先序遍历的方式遍历每个节点

在这里插入图片描述

我们在遍历每个节点的时候使用map来记录他左右孩子的父节点（使用指针来记录避免重复值问题）如果左右孩子为空则不记录

接下来我们就能得到一张记录每个节点父节点的map表

最后我们只需要找到target节点之后向下/向上找K的位置（使用队列）就能找到所有结果了

代码详解

// 定义二叉树节点类
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 定义二叉树节点类
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 记录每个二叉树节点的父节点
unordered_map<TreeNode*, TreeNode*> mapWhereFather;

void _FindFather(TreeNode* root) {
    if (root == nullptr)
    {
        return;
    }
    if (root->left != nullptr)
    {
        mapWhereFather[root->left] = root;
    }

    if (root->right != nullptr)
    {
        mapWhereFather[root->right] = root;
    }

    _FindFather(root->left);
    _FindFather(root->right);
}

void FindFather(TreeNode* root) { // root不为空
    // 首先记录下Root节点的父亲节点
    mapWhereFather[root] = nullptr;
    _FindFather(root);
}



// 找到与target距离为K的所有节点
vector<int> distanceK( TreeNode* target, int K) {
    vector<int> ans = {};
    queue<TreeNode*> q;
    q.push(target);
    while (K--)
    {
        int size = q.size();
        while (size--)
        {
            auto it = q.front();
            q.pop();

            if (mapWhereFather[it] != nullptr)
            {
                q.push(mapWhereFather[it]);
            }
            if (it->left != nullptr)
            {
                q.push(it->left);
            }
            if (it->right != nullptr)
            {
                q.push(it->right);
            }
        }
    }

    while (!q.empty())
    {
        auto it = q.front();
        q.pop();

        ans.push_back(it->val);
    }

    return ans;
}

// 测试用例
int main() {
    // 创建一个二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    TreeNode* target = root->left; // 目标节点为2
    int K = 1;

    FindFather(root);
    // 获取与target距离为K的所有节点
    vector<int> result = distanceK(target, K);

    // 输出结果
    cout << "与目标节点距离为 " << K << " 的节点为: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

能力差为K的人（贪心双指针）

题目

给定一个数组arr 代表每个人的能力值再给定一个非负数K 如果两个人的能力差值正好为K 那么可以凑在一起比赛每一局比赛只有两个人
返回最多可以同时有多少场比赛

题目分析

要解决这道题目其实就是要想到一个小的贪心点那就是

在数组有序的情况下我们能最快的得到能力相差为K的各组数据

因为在数组有序的情况下我们从左往右遍历一定是从小到大有序的出现自然差值为K的一对数据也是最先出现（对于左指针来说）

想到这一点之后我们使用双指针解决即可

代码详解

我们这里使用一个bool数组来表示这个数据有没有被使用

当然我们也可以使用 map<vector<int>, bool>来判断一样的效果

int main() {
int count = 0;
vector<int> arr = { 3 , 7, 1 , 5 , 3 ,3 , 5};
vector<int> arrbool = { 0 , 0, 0 , 0 , 0 ,0 , 0};

sort(arr.begin(), arr.end());

for (auto x : arr)
{
cout << x << endl;
}


int left = 0;
int right = 0;

while (right < arr.size())
{
if (left == right)
{
right++;

if (right == arr.size())
{
break;
}
}

if (arrbool[left] == 1)
{
left++;
if (left == arr.size())
{
break;
}
}


if (arr[right] - arr[left] == 2)
{
if (arrbool[left] == 0 && arrbool[right] == 0)
{
arrbool[right] = 1;
arrbool[left] = 1;
count++;
}
}
else
{
left++;
right++;
}
}


cout << count << endl;
return 0;
}

字符串最长无重复子串（经典动态规划）

题目

本题为LC原题

在这里插入图片描述

题目分析

这是一道经典的动态规划模型问题思路是这样

在这里插入图片描述

假设有如上图的一个字符串我们可以假设从最左边的字符开始每个字符作为最长无重复子串的大小是多少

有了最左边的数据之后我们求第二个是不是就很简单了只有两种可能

前面的最长子串+1（子串里无当前位置字符）
当前字符到上一个重复字符的位置（子串里有当前位置字符）

那么我们的代码就很好写了

代码详解

需要注意的有两点

我们的dp数组需要预先初始化大小不然会报错
我们可以使用map中的count函数来查找一个key是否存在

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 首先建立一张dp表表示前面每个字符的最长无重复子串 建立一个map表表示上一次本字符出现的位置
        if (s.empty()) return 0; // 如果字符串为空，直接返回 0
        
        int N = s.size();
        vector<int> dp(N); // 初始化 dp 向量，并分配大小为 N
        map<char , int> mapIndex = {};
        int ans = 0;

        dp[0] = 1;
        mapIndex[s[0]] = 0;

        for (int x = 1; x < s.size() ; x++) {
            int p1 = dp[x-1] + 1;
            
            // p2
            int p2 = 0; 
            if (mapIndex.count(s[x]) == 1) {
               p2 = (x - mapIndex[s[x]]) > p1 ? p1 : x - mapIndex[s[x]];
            }else {
                p2 = dp[x-1] + 1;
            }

            mapIndex[s[x]] = x;
            dp[x] = p2;
        }

        for (auto x : dp) {
            if (x > ans) {
                ans = x;
            }
        }

        return ans;
    }
};

边框全是1的正方形面积（预处理数组）

题目

此题为LC原题题目如下

在这里插入图片描述

题目分析

在矩阵中任意点一个点再加上边长我们就能确定一个唯一的正方形

在矩阵中选点我们肯定避免不了那么我们就要想想能不能快速的确定一个正方形的边长

这里就想到了预处理数组

我们可以找出这个正方形往右和往下的可能性最大值之后我们只需要验证这个可能性即可

关于找最大值的方式其实就是确定往右和往下有多少个连续的1

代码详解

我们这里要注意最后一段因为

                // 检查每个可能的正方形边长
                for (int side = maxPossibleSide; side > 0; side--) {
                    // 确保没有越界
                    if (i + side - 1 < N && j + side - 1 < M) {
                        // 检查边界条件，确保下边和右边也满足
                        if (right[i + side - 1][j] >= side && down[i][j + side - 1] >= side) {
                            maxborder = max(maxborder, side);  // 更新最大边长
                            break;  // 找到当前 (i, j) 的最大正方形，跳出循环
                        }
                    }
                }

因为我们上面实际上只确定了两条边还有两条需要确认下

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int N = grid.size();
        int M = grid[0].size();

        vector<vector<int>> right(N, vector<int>(M, 0));  // 初始化 RIGHT 数组
        vector<vector<int>> down(N, vector<int>(M, 0));   // 初始化 DOWN 数组

        // 填充 RIGHT 数组
        for (int i = 0; i < N; i++) {
            int maxRight = 0; // 每行的 maxRight 计数器
            for (int j = M - 1; j >= 0; j--) { // 从右向左
                if (grid[i][j] == 1) {
                    maxRight += 1;
                } else {
                    maxRight = 0;
                }
                right[i][j] = maxRight;
            }
        }

        // 填充 DOWN 数组
        for (int j = 0; j < M; j++) {
            int maxDown = 0; // 每列的 maxDown 计数器
            for (int i = N - 1; i >= 0; i--) { // 从下向上
                if (grid[i][j] == 1) {
                    maxDown += 1;
                } else {
                    maxDown = 0;
                }
                down[i][j] = maxDown;
            }
        }

        int maxborder = 0; // 最大边长
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 0) {
                    continue; // 如果当前位置是0，跳过
                }

                // 找出从 (i, j) 出发的最大可能边长
                int maxPossibleSide = min(right[i][j], down[i][j]);

                // 检查每个可能的正方形边长
                for (int side = maxPossibleSide; side > 0; side--) {
                    // 确保没有越界
                    if (i + side - 1 < N && j + side - 1 < M) {
                        // 检查边界条件，确保下边和右边也满足
                        if (right[i + side - 1][j] >= side && down[i][j + side - 1] >= side) {
                            maxborder = max(maxborder, side);  // 更新最大边长
                            break;  // 找到当前 (i, j) 的最大正方形，跳出循环
                        }
                    }
                }
            }
        }

        return maxborder * maxborder; // 返回最大正方形的面积
    }
};

两两配队问题（贪心 + 处理数据技巧）

如果说一个数据只有两种状态（存在不存在或者其他互斥状态）我们可以只计算其中的一种状态来推算出另外一种状态

题目

给定一个正数组arr 代表每个人的体重

给定一个正整数limit 代表每艘船能够承载的重量

每艘船最多坐两人并且不能超过载重

现在要让所有人都过河返回最小的用船数

题目分析

这是一个比较经典的贪心问题

我们想要两个人坐船不超过载重最佳情况是一个人在 limit/2的左边并且离中心点尽可能的近一个人在limit/2的右边并且离中心点尽可能的近

那么我们就可以使用这样子的思路来解决这个问题

假设数据如下图所示（limit为10 以limit/2为分界）

在这里插入图片描述

此时我们便可以在分界线左右两个位置设置两个指针

在这里插入图片描述

此时我们让左右两个数相加看看是否超过limit

如果超过则左指针左移直到不超过为止
如果不超过则右指针右移直到超过再往左移一格

其中第一步的目的是找到左数组中能够组成limit的最极限位置

第二步的目的是为了找到与极限位置相匹配的右数组中的极限位置

代码详解

这里我们可以通过vector 来记录没有使用过的数量也可以使用一个int类型参数来记录

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minBoats(vector<int>& arr, int limit) {
    if (arr.empty()) {
        return 0;
    }
    int N = arr.size();

    // 如果最重的人超过了船的载重限制，则无法解决
    if (arr[N - 1] > limit) {
        return -1;
    }

    int lessR = -1;
    
    // 找到<= limit / 2 的最右位置
    for (int i = N - 1; i >= 0; i--) {
        if (arr[i] <= (limit / 2)) {
            lessR = i;
            break;
        }
    }

    // 如果没有任何人的体重 <= limit / 2，那么每个人需要单独一条船
    if (lessR == -1) {
        return N;
    }

    int L = lessR;
    int R = lessR + 1;
    int noUsed = 0; // 没有配对成功的人数
    while (L >= 0) {
        int solved = 0; // 当前[L] 能让R配对的次数
        while (R < N && arr[L] + arr[R] <= limit) {
            R++;
            solved++;
        }
        // 如果没有任何一个R和当前L配对成功
        if (solved == 0) {
            noUsed++;
            L--;
        } else {
            // L往前移动solved个位置，因为solved个数被配对了
            L = max(-1, L - solved);
        }
    }

    // 左半区总人数，即 <= limit / 2 区域的人数
    int all = lessR + 1;

    // 能配对成功的人数
    int used = all - noUsed;

    // >limit/2 区域中没配对成功的人数
    int moreUnsolved = (N - all) - used;

    return used + ((noUsed + 1) >> 1) + moreUnsolved;
}

int main() {
    vector<int> arr = {1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5};
    int weight = 6;
    // 排序，确保数组是升序的
    sort(arr.begin(), arr.end());
    
    // 计算最小的船数
    cout << minBoats(arr, weight) << endl;

    return 0;
}

自由之路（动态规划）

题目

本题为LC原题题目如下

在这里插入图片描述

题目分析

这其实是一个比较简单的动态规划问题

我们只需要确定当前位置的字符和将要到达目标位置的字符之后计算他们的距离即可这里需要注意的是需要到达的字符可能不止一个所以说我们要用 unordered_map<char, vector<int>> 来存储

计算出当前位置的最小拨号次数之后只需要调用递归即可

代码详解

#include <iostream>
#include <unordered_map>
#include <vector>
#include <climits>
#include <cmath>
#include <string>

using namespace std;

class Solution {
public:
    // 字符和位置的映射
    unordered_map<char, vector<int>> charMap;
    // 缓存
    vector<vector<int>> memo;

    /**
     * 最少操作次数
     * @param ring
     * @param key
     * @return
     */
    int findRotateSteps(string ring, string key) {
        int m = ring.length();
        int n = key.length();
        memo = vector<vector<int>>(m, vector<int>(n, 0));

        // 将字符和位置形成对应关系
        for (int i = 0; i < m; i++) {
            charMap[ring[i]].push_back(i);
        }
        return process(ring, 0, key, 0);
    }

    /**
     * 暴力递归 + 缓存
     * @param ring 转盘
     * @param r 指针当前指的位置
     * @param key 密码
     * @param k 当前要输的字符
     * @return
     */
    int process(string& ring, int r, string& key, int k) {
        // base case 完成输入
        if (k == key.length()) {
            // 不需要再转了,返回0
            return 0;
        }

        // 缓存减少重复计算
        if (memo[r][k] != 0) {
            return memo[r][k];
        }

        int n = ring.length();
        int res = INT_MAX;

        // 在ring里可能有重复的字符,因此index可能有好几个值,通过遍历的方式,去每个位置都做计算
        for (int index : charMap[key[k]]) {
            // 需要输入的字符和指针所指的字符的距离
            int step = abs(index - r);
            // 选择顺时针还是逆时针拨动,选择操作次数最少的
            step = min(step, n - step);
            // 将指针拨到当前需要输入的字符位置,再进行下一次拨动,记录下一次拨动需要的操作的次数
            int nextStep = process(ring, index, key, k + 1);
            // 要选择整体操作最少次数的,额外要加1,按确认也是一次操作
            res = min(res, 1 + step + nextStep);
        }

        memo[r][k] = res;
        return res;
    }
};

int main() {
    Solution solution;
    string ring = "godding";
    string key = "gd";

    // 输出最少操作次数
    cout << solution.findRotateSteps(ring, key) << endl;

    return 0;
}

原文地址：https://blog.csdn.net/meihaoshy/article/details/142927537

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

上一篇：闲置宽带赚网费（点心云/网心云)收益测评
下一篇：视频智能分析平台LiteAIServer摄像机视频分析软件下载水土识别算法方案

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

【C++ 算法进阶】算法提升三

距离二叉树节点为K的位置 （类层序遍历 建立父表）

题目

题目分析

代码详解

能力差为K的人 （贪心 双指针）

题目

题目分析

代码详解

字符串最长无重复子串 （经典动态规划）

题目

题目分析

代码详解

边框全是1的正方形面积 （预处理数组）

题目

题目分析

代码详解

两两配队问题 （贪心 + 处理数据技巧）

题目

题目分析

代码详解

自由之路 （动态规划）

题目

题目分析

代码详解

相关文章

距离二叉树节点为K的位置（类层序遍历建立父表）

能力差为K的人（贪心双指针）

字符串最长无重复子串（经典动态规划）

边框全是1的正方形面积（预处理数组）

两两配队问题（贪心 + 处理数据技巧）

自由之路（动态规划）