On the shoulders of giants.

biweekly-contest-14

十六进制魔术数字

你有一个十进制数字,请按照此规则将它变成「十六进制魔术数字」:首先将它变成字母大写的十六进制字符串,然后将所有的数字 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 。
  • 结果中的所有字母都应该是大写字母。
题解

直接十进制转十六进制,然后 01 的情况特判,如果有其它数字那么打上标记。

时间复杂度:\(O(n)\)

class Solution {
public:
    bool flag = false;
    string result = "";
    
    void to16(long long num) {
        if(num == 0) return;
        to16(num / 16);
        int x = num % 16;
        if(x < 10) {
            if(x == 1) result += "I";
            else if(x == 0) result += "O";
            else flag = true;
        } else result += 'A' + (x - 10);
    }
    
    string toHexspeak(string num) {
        long long sum = 0;
        
        for(auto x : num) {
            sum = sum * 10 + x - '0';
        }
        
        to16(sum);
        
        if(flag) return "ERROR";
        else return result;
    }
};

删除区间

给你一个 有序的 不相交区间列表 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
题解

四种情况:

  • 区间完全被 toBeRemoved 包含,对答案无贡献;
  • toBeRemoved 完全被区间包含,那么区间两边为包含部分对答案有贡献;
  • 区间右边完全被 toBeRemoved 包含,那么区间左边对答案有贡献;
  • 区间左边完全被 toBeRemoved 包含,那么区间右边对答案有贡献;

最有排序以保证数据有序。

时间复杂度:\(O(n + n \log n)\)

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

删除树节点

给你一棵以节点 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 是树的根。
题解

先求出每棵子树的权值和、节点总数,然后找到离根节点最近且权值和为零的节点,最后通过节点总数更新答案。

时间复杂度:\(O(n^2)\)

class Solution {
public:
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        vector<int> sum(nodes), sz(nodes);
        set<int> s;
        int count = 0;
        
        for(int i = 0; i < nodes; i++) {
            int x = i;
            while(x != -1) {
                sz[x]++;
                sum[x] += value[i];
                x = parent[x];
            }
        }
        
        for(int i = 0; i < nodes; i++) {
            int x = i, p = -1;
            while(x != -1) {
                if(sum[x] == 0) p = x;
                x = parent[x];
            }
            if(p != -1) s.insert(p);
        }
        
        for(auto x : s) {
            count += sz[x];
        }
        
        return nodes - count;
    }
};

矩形内船只的数目

(此题是 交互式问题 )

在用笛卡尔坐标系表示的二维海平面上,有一些船。每一艘船都在一个整数点上,且每一个整数点最多只有 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
题解

二分法:把矩形分为 左上、左下、右上、右下 四个小矩形。如果小矩形内无船只,那在这个小矩形内就没有必要往下做了,如果有,那么重复上面的方法,直到矩形退化成一个点。

时间复杂度:\(O(\log^2 n)\)

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *   public:
 *     bool hasShips(vector<int> topRight, vector<int> bottomLeft);
 * };
 */

class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        if(topRight[0] < bottomLeft[0] || topRight[1] < bottomLeft[1]) return 0;
        if(topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) {
            return sea.hasShips(topRight, bottomLeft);
        }
        if(!sea.hasShips(topRight, bottomLeft)) return 0;
        int count = 0, midX, midY;
        midX = topRight[0] + bottomLeft[0] >> 1;
        midY = topRight[1] + bottomLeft[1] >> 1;
        count += countShips(sea, vector<int> {midX, midY}, bottomLeft);
        count += countShips(sea, vector<int> {topRight[0], midY}, vector<int> {midX + 1, bottomLeft[1]});
        count += countShips(sea, vector<int> {midX, topRight[1]}, vector<int> {bottomLeft[0], midY + 1});
        count += countShips(sea, topRight, vector<int> {midX + 1, midY + 1});
        return count;        
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注