biweekly-contest-14

5112. 十六进制魔术数字

你有一个十进制数字，请按照此规则将它变成「十六进制魔术数字」：首先将它变成字母大写的十六进制字符串，然后将所有的数字 0 变成字母 O ，将数字 1 变成字母 I 。
如果一个数字在转换后只包含 {"A", "B", "C", "D", "E", "F", "I", "O"} ，那么我们就认为这个转换是有效的。
给你一个字符串 num ，它表示一个十进制数 N，如果它的十六进制魔术数字转换是有效的，请返回转换后的结果，否则返回 "ERROR" 。

示例 1：

输入：num = "257"
输出："IOI"
解释：257 的十六进制表示是 101 。

示例 2：**

输入：num = "3"
输出："ERROR"

提示：

• 1 <= N <= 10^12
• 给定字符串不会有前导 0 。
• 结果中的所有字母都应该是大写字母。

题解：

class Solution1 {
public:
    string toHexspeak(string num) {
        string result = "";
        long num_long = stol(num);
        while (num_long > 0)
        {
            int digit = num_long % 16;
            switch (digit)
            {
            case 0:
                result += "O";
                break;
            case 1:
                result += "I";
                break;
            case 10:
                result += "A";
                break;
            case 11:
                result += "B";
                break;
            case 12:
                result += "C";
                break;
            case 13:
                result += "D";
                break;
            case 14:
                result += "E";
                break;
            case 15:
                result += "F";
                break;
            default:
                return "ERROR";
            }
            num_long /= 16;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

5113. 删除区间

给你一个 有序的 不相交区间列表 intervals 和一个要删除的区间 toBeRemoved， intervals 中的每一个区间 intervals[i] = [a, b] 都表示满足 a <= x < b 的所有实数 x 的集合。
我们将 intervals 中任意区间与 toBeRemoved 有交集的部分都删除。
返回删除所有交集区间后， intervals 剩余部分的 有序 列表。

示例 1：

输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
输出：[[0,1],[6,7]]

示例 2：

输入：intervals = [[0,5]], toBeRemoved = [2,3]
输出：[[0,2],[3,5]]

提示：

• 1 <= intervals.length <= 10^4
• -10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

思路：

1. 合并区间的一种变形，不难

题解：

class Solution2 {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> result;
        for (auto m : intervals)
        {
            if (m[0] < toBeRemoved[0] && m[1] > toBeRemoved[1])
            {
                result.push_back({ m[0], toBeRemoved[0] });
                result.push_back({ toBeRemoved[1], m[1] });
            }
            else if (m[0] >= toBeRemoved[0] && m[1] <= toBeRemoved[1])
            {
                continue;
            }
            else
            {
                if (m[0] < toBeRemoved[0])
                    result.push_back({ m[0], min(m[1], toBeRemoved[0]) });
                else if (m[1] > toBeRemoved[1])
                    result.push_back({ max(toBeRemoved[1], m[0]), m[1] });
            }
        }
        return result;
    }
};

5114. 删除树节点

给你一棵以节点 0 为根节点的树，定义如下：

• 节点的总数为 nodes 个；
• 第 i 个节点的值为 value[i] ；
• 第 i 个节点的父节点是 parent[i] 。

请你删除节点值之和为 0 的每一棵子树。
在完成所有删除之后，返回树中剩余节点的数目。

示例：

输入：nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
输出：2

提示：

• 1 <= nodes <= 10^4
• -10^5 <= value[i] <= 10^5
• parent.length == nodes
• parent[0] == -1 表示节点 0 是树的根。

思路：

1. 建树
2. 将树中每个节点的值设置为以该树为根的子树所有节点之和
3. 对树进行遍历，遇到节点和为0的节点就跳过，统计所有和非0的节点数即为结果

题解：

class Solution {
public:
    map<int, vector<int>> _tree;
    vector<int> _sum;
    vector<int> _value;
    int _nodes;

    int dfs(int idx)
    {
        if (idx >= _nodes)
            return 0;
        if (_tree[idx].empty())
        {
            _sum[idx] = _value[idx];
            return _value[idx];
        }
        for (int i = 0; i < _tree[idx].size(); i++)
        {
            _sum[idx] += dfs(_tree[idx][i]);
        }
        return _sum[idx];
    }

    void iszero(int idx, int &curr)
    {
        if (idx >= _nodes)
            return;
        if (_sum[idx] == 0)
            return;
        curr++;
        for (int i = 0; i < _tree[idx].size(); i++)
        {
            iszero(_tree[idx][i], curr);
        }
    }

    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        _sum = vector<int>(value);
        _nodes = nodes;
        _value = value;
        for (int i = 0; i < parent.size(); i++)
            _tree[parent[i]].push_back(i);
        _sum[0] = dfs(0);
        int curr = 0;
        iszero(0, curr);
        return curr;
    }
};

5136. 矩形内船只的数目

(此题是 交互式问题 )
在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 1 艘船。
有一个函数 Sea.hasShips(topRight, bottomLeft) ，输入参数为右上角和左下角两个点的坐标，当且仅当这两个点所表示的矩形区域（包含边界）内至少有一艘船时，这个函数才返回 true ，否则返回 false 。
给你矩形的右上角 topRight 和左下角 bottomLeft 的坐标，请你返回此矩形内船只的数目。题目保证矩形内 至多只有 10 艘船。
调用函数 hasShips 超过400次 的提交将被判为 错误答案（Wrong Answer） 。同时，任何尝试绕过评测系统的行为都将被取消比赛资格。

示例：

输入：
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
输出：3
解释：在 [0,0] 到 [4,4] 的范围内总共有 3 艘船。

提示：

• ships 数组只用于评测系统内部初始化。你无法得知 ships 的信息，所以只能通过调用 hasShips 接口来求解。
• 0 <= bottomLeft[0] <= topRight[0] <= 1000
• 0 <= bottomLeft[1] <= topRight[1] <= 1000

思路：

1. 搜索y轴上所有有船的坐标
2. 在y轴上有船的坐标维度上，搜索x轴上的船数目，并求和

另一种思路：

1. 递归，如果当前区域有船，则分为四等分，搜索四个区域内的船数
2. 如果当前区域是一个点并且有船，则返回1，否则继续递归

题解：

class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        vector<int> x;
        vector<int> y;
        int result = 0;
        int top = topRight[0];
        int bottom = bottomLeft[0];
        int result = 0;

        bool flag = true;
        while (flag)
        {
            flag = false;
            int left = x.empty() ? bottomLeft[1] : x.back() + 1;
            int right = topRight[1];
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (sea.hasShips({ top, mid }, { bottom, left }))
                {
                    if (left == mid)
                    {
                        x.push_back(mid);
                        flag = true;
                        break;
                    }
                    else
                        right = mid;
                }
                else
                    left = mid + 1;
            }
        }

        for (int i = 0; i < x.size(); i++)
        {
            vector<int> y{};
            bool y_flag = true;
            while (y_flag)
            {
                y_flag = false;
                int bottom = y.empty() ? bottomLeft[0] : y.back() + 1;
                int top = topRight[0];
                while (bottom <= top)
                {
                    int mid = (bottom + top) / 2;
                    if (sea.hasShips({ mid, x[i] }, { bottom, x[i] }))
                    {
                        if (bottom == mid)
                        {
                            y.push_back(mid);
                            y_flag = true;
                            break;
                        }
                        else
                            top = mid;
                    }
                    else
                        bottom = mid + 1;
                }
            }
            result += y.size();
        }
        return result;
    }
};