距离二叉树节点为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. 前面的最长子串+1（子串里无当前位置字符）
2. 当前字符到上一个重复字符的位置（子串里有当前位置字符）

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

代码详解

需要注意的有两点

1. 我们的dp数组需要预先初始化大小 不然会报错
2. 我们可以使用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;

    
上一篇：Redis底层和缓存雪崩，击穿，穿透-2.Redis数据结构—inset

下一篇：华为云成功牵头立项智能化开发工具IEEE国际标准