Leetcode第14场双周赛

夜猫赛传送门

https://leetcode-cn.com/contest/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 Solution {
public:
    typedef long long ll;
    string toHexspeak(string num) {
        ll n=0;
        for(auto c:num){
            n*=10;
            n+=(c-'0');
        }
        stack<int> s;
        while(n){
            if(n%16>=2&&n%16<=9) return "ERROR";
            s.push(n%16);
            n/=16;
        }
        string ans;
        while(!s.empty()){
            if(s.top()==0) ans+='O';
            else if(s.top()==1) ans+='I';
            else ans+=(s.top()-10+'A');
            s.pop();
        }
        return ans;
    }
};

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

题解

设要删除的区间为[l,r)，等待被删除的区间为[x,y)分五种情况考虑

• y<=l||x>=r ，根本没有删除
• x=l&&r>=r，还剩下[r,y)这一段
• x<=l&&y>l&&y<=r，还剩下[x,l)这一段
• x>=l&&y<=r，全部都被删掉了
• x<l&&y<r，被切分成了两部分[x,l)和[r,y)

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& v, vector<int>& b) {
        int l=b[0],r=b[1];
        vector<vector<int>> ans;
        for(auto p:v){
            if(p[1]<=l||p[0]>=r) ans.push_back({p[0],p[1]});
            else if(p[0]<r&&p[1]>=r&&l<=p[0]) ans.push_back({r,p[1]});
            else if(p[0]<=l&&p[1]>l&&r>=p[1]) ans.push_back({p[0],l});
            else if(l<=p[0]&&r>=p[1]) continue;
            else if(l>p[0]&&r<p[1]){
                ans.push_back({p[0],l});
                ans.push_back({r,p[1]});
            }
        }
        sort(ans.begin(),ans.end(),[](vector<int>& a,vector<int>& b){
            if(a[0]==b[0]) return a[1]<b[1];
            else return a[0]<b[0];
        });
        return ans;
    }
};

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 是树的根。

题解

首先先建树，根据所给的信息用邻接表建树

然后建立一个新数组记录每一个节点的子树的节点个数

两趟DFS，第一趟首先进行递归求和和求子树的节点个数，第二趟直接把和为0的节点的子树的节点个数加入答案（其实可以一个DFS解决的，但是当时没有想到）

class Solution {
public:
    typedef pair<int,int> P;
    int d[10010],ans;
    long long w[10010];
    vector<int> g[10010];
    
    void add(int a,int b){
        g[a].push_back(b);
    }
    
    void dfs1(int u){
        for(auto v:g[u]){
            dfs1(v);
            w[u]+=w[v];
            d[u]+=d[v];
        }
    }
    
    void dfs2(int u){
        if(w[u]==0){
            ans+=d[u];
            return;
        }
        for(auto v:g[u]){
            dfs2(v);
        }
    }
    
    int deleteTreeNodes(int n, vector<int>& par, vector<int>& val) {
        ans=0;
        int root=-1;
        for(int i=0;i<n;i++){
            w[i]=val[i];
            if(par[i]!=-1)
                add(par[i],i);
            else root=i;
            d[i]=1;
        }
  
        dfs1(root);
        dfs2(root);
        return n-ans;
    }
};

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

题解

（GG于多打了一个分号QAQ）

这道题目是关于矩阵分割的题目，首先只有400次询问，所以我们肯定是需要进行二分的（而且由于最多只有10艘船，我们进行二分很可能会剪枝一大块区域）

首先我们定于左下角的坐标为(x1,y1)，右上角的坐标为(x2,y2)。那么我们首先进行二分找到(midx,midy)，这样我们就可以将大块的矩形分割成4个矩形递归操作，下面四个矩形的坐标是这样的（左下角在前，右上角在后）：

• (x1,y1),(midx,midy)
• (x,midy+1),(midx,y2)
• (midx+1,y1),(x2,midy)
• (midx+1,midy+1),(x2,y2)

加一是因为防止重复搜索

/**
 * // 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 s, vector<int> top, vector<int> bot) {
        int x1=bot[0],y1=bot[1];
        int x2=top[0],y2=top[1];
        if(y2==y1&&x2==x1&&s.hasShips({x2,y2},{x1,y1})) return 1;
        int mid_x=x2+x1>>1,mid_y=y2+y1>>1;
        int ans=0;
        if(mid_x>=x1&&mid_y>=y1&&s.hasShips({mid_x,mid_y},{x1,y1}))
            ans+=countShips(s,{mid_x,mid_y},{x1,y1});
        if(mid_x>=x1&&mid_y+1<=y2&&s.hasShips({mid_x,y2},{x1,mid_y+1}))
            ans+=countShips(s,{mid_x,y2},{x1,mid_y+1});
        if(mid_x+1<=x2&&mid_y>=y1&&s.hasShips({x2,mid_y},{mid_x+1,y1}))
            ans+=countShips(s,{x2,mid_y},{mid_x+1,y1});
        if(mid_x+1<=x2&&y2>=mid_y+1&&s.hasShips({x2,y2},{mid_x+1,mid_y+1}))
            ans+=countShips(s,{x2,y2},{mid_x+1,mid_y+1});
        return ans;
    }
};