Leetcode-第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 。
结果中的所有字母都应该是大写字母。

解法1：模拟

将10进制转换成16进制

注意：1.转化时用longlong 不然会溢出，2.最后要reverse字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string toHexspeak(string num) {
        long long s=stol(num);
        string str[6]={"A","B","C","D","E","F"};
        string res="";
        while(s)
        {
            int temp=s%16;
            if(temp>=10)
            {
                res+=str[temp-10];
            }
            else if(temp==0)
            {
                res+='O';
            }
            else if(temp==1)
            {
                res+='I';
            }
            else if(temp>=2&&temp<=9)
                return  "ERROR";
            s=s/16;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

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：模拟

思路：模拟查找重叠区间，要想好思路，不然会很乱

1.若interval[1]<=toBeRemoved[0]，则不在删除区间内，添加进结果数组

2.若interval[0]>=toBeRemoved[1]，则不在删除区间内，添加进结果数组

3.在前面的情况不满足下，若interval[0]<toBeRemoved[0],前面已经讨论interval[1]在删除区间右边的情况,现在还有两种情况

  • ​ interval[1]<=toBeRemoved[1],添加{interval[0],toBeRemoved[0]}
  • ​ interval[1]>toBeRemoved[1],再添加{toBeRemoved[1],interval[1]}

4.在前面的情况不满足下，若interval[0]<toBeRemoved[1]

  • interval[1]<=toBeRemoved[1],直接将跳过这一段应删除的区间
  • nterval[1]>toBeRemoved[1]，添加{toBeRemoved[1],interval[1]}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        vector<vector<int>> res;
        int n=intervals.size();
        for(int i=0;i<n;i++)
        {
            if(intervals[i][1]<=toBeRemoved[0]||intervals[i][0]>=toBeRemoved[1])
            {
                res.push_back(intervals[i]);
                continue;
            }
            else if(intervals[i][0]<toBeRemoved[0])
            {
                res.push_back({intervals[i][0],toBeRemoved[0]});
                if(intervals[i][1]>toBeRemoved[1])
                {
                    res.push_back({toBeRemoved[1],intervals[i][1]});
                }
            }
            else if(intervals[i][0]<toBeRemoved[1])
            {
                if(intervals[i][1]<=toBeRemoved[1])
                    continue;
                else
                {
                    res.push_back({toBeRemoved[1],intervals[i][1]});
                }
            }
        }
        return res;
    }
};

5114. 删除树节点

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

节点的总数为 nodes 个；
第 i 个节点的值为 value[i] ；
第 i 个节点的父节点是 parent[i] 。
请你删除节点值之和为 0 的每一棵子树。

在完成所有删除之后，返回树中剩余节点的数目。

 

示例：

img

输入：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：两次DFS

第一次dfs将和为0的子树标记

第二次dfs求剩余的节点数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    int n;
    map<int,vector<int>> pindex;
    vector<bool> used;
public:
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        n=nodes;
        used=vector<bool>(n,false);
        for(int i=0;i<n;i++)
        {
            pindex[parent[i]].push_back(i);
        }
        dfs1(parent,value,0);
        return dfs2(0);
    }
    int dfs1(vector<int>& parent, vector<int>& value,int i)
    {
        int sum=value[i];
        if(!pindex.count(i))
        {
            if(sum==0)
            {
                used[i]=true;
            }
            return sum;
        }
        vector<int> temp=pindex[i];
        for(int j=0;j<temp.size();j++)
        {
            int index=temp[j];
            sum+=dfs1(parent,value,index);
        }
        if(sum==0)
        {
            used[i]=true;
        }
        return sum;
    }
    int dfs2(int i)
    {
        int sum=1;
        if(!pindex.count(i))
            return 1;
        vector<int> temp=pindex[i];
        for(int j=0;j<temp.size();j++)
        {
            int index=temp[j];
            if(used[index])
                continue;
            sum+=dfs2(index);
        }
        return sum;
    }
};

5136. 矩形内船只的数目

(此题是 交互式问题 )

在用笛卡尔坐标系表示的二维海平面上，有一些船。每一艘船都在一个整数点上，且每一个整数点最多只有 1 艘船。

有一个函数 Sea.hasShips(topRight, bottomLeft) ，输入参数为右上角和左下角两个点的坐标，当且仅当这两个点所表示的矩形区域（包含边界）内至少有一艘船时，这个函数才返回 true ，否则返回 false 。

给你矩形的右上角 topRight 和左下角 bottomLeft 的坐标，请你返回此矩形内船只的数目。题目保证矩形内 至多只有 10 艘船。

调用函数 hasShips 超过400次 的提交将被判为 错误答案（Wrong Answer） 。同时，任何尝试绕过评测系统的行为都将被取消比赛资格。

 

示例：

img

输入：
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：二分

分成四部分，左上，左下，右上，

二分，矩阵的二分，划成了4个小矩阵，分别对这4个小矩阵进行探测，如果没有船，就不继续探测了，如果有船，那么递归探测

递归的终止条件是：矩阵只剩下一个点，那么这个点就有一艘船

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * // 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(bottomLeft[0]>topRight[0]||bottomLeft[1]>topRight[1])
            return 0;
        if(!sea.hasShips(topRight,bottomLeft)) return 0;
        if(topRight[0]==bottomLeft[0]&&topRight[1]==bottomLeft[1])
            return 1;
        int lowx=bottomLeft[0],lowy=bottomLeft[1],highx=topRight[0],highy=topRight[1];
        int midx=(lowx+highx)/2,midy=(lowy+highy)/2;
        return countShips(sea,{highx,highy},{midx+1,midy+1})+countShips(sea,{midx,midy},{lowx,lowy})+countShips(sea,{midx,highy},{lowx,midy+1})+countShips(sea,{highx,midy},{midx+1,lowy});
    }
};