讨论/题目交流/🐱 第 14 场夜喵双周赛/
🐱 第 14 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 十六进制魔术数字
5 分 - 删除区间
5 分 - 删除树节点
7 分 - 矩形内船只的数目

展开讨论
共 8 个讨论

这次是用python打的比赛,python不怎么熟悉,大家将就着看下

第一题:

没啥难度,转成十六进制后该干嘛干嘛

class Solution:
    def toHexspeak(self, num: str) -> str:
        s = hex(int(num))[2:].upper()
        def change(c):
            if c == '0':
                return 'O'
            elif c == '1':
                return 'I'
            else:
                return c
        if len(list(filter(lambda c: c not in 'ABCDEF01', s))) != 0:
            return "ERROR"
        return "".join(list(map(lambda c: change(c), s)))

第二题:

主要难度在枚举两个区间的所有相交情况

  • A和B相离
  • A在B里
  • B在A里
  • A盖住了B的左边部分
  • A盖住了B的右边部分
class Solution:
    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
        def cross(a, b):
            if a[0] >= b[1] or a[1] <= b[0]:
                return [a]
            elif a[0] >= b[0] and a[1] <= b[1]:
                return []
            elif a[0] >= b[0] and a[1] > b[1]:
                return [[b[1], a[1]]]
            elif a[0] < b[0] and a[1] <= b[1]:
                return [[a[0], b[0]]]
            else:
                return [[a[0], b[0]], [b[1], a[1]]]
            
        ret = []
        for x in intervals:
            ret += cross(x, toBeRemoved)
        return ret

第三题:

两遍dfs,
第一遍dfs,统计出每个结点为根的子树和
第二遍dfs,统计删除子树和为0的结点,子树和为0的结点就不进行dfs了

注意,需要提前建立邻接表,否则会超时

class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        children = list(map(lambda c: [], range(0, nodes)))
        for i in range(1, nodes):
            children[parent[i]].append(i)
        num_sub = [0] * nodes
        def dfs1(node):
            num_sub[node] += value[node]
            for child in children[node]:
                num_sub[node] += dfs1(child)
            return num_sub[node]
        dfs1(0)
        def dfs2(node):
            if num_sub[node] == 0:
                return 0
            ret = 1
            for child in children[node]:
                ret += dfs2(child)
            return ret
        return dfs2(0)

第四题:

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

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

class Solution(object):
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        def find(bottomLeft, topRight):
            if not sea.hasShips(topRight, bottomLeft):
                return 0
            
            if bottomLeft.x == topRight.x and bottomLeft.y == topRight.y:
                return 1
            
            sub = []
            mid_x = (bottomLeft.x + topRight.x) // 2
            mid_y = (bottomLeft.y + topRight.y) // 2
            if bottomLeft.x == topRight.x:
                sub = [[bottomLeft, Point(mid_x, mid_y)], [Point(mid_x, mid_y + 1), topRight]]
            elif bottomLeft.y == topRight.y:
                sub = [[bottomLeft, Point(mid_x, mid_y)], [Point(mid_x + 1, mid_y), topRight]]
            else:
                sub = [[bottomLeft, Point(mid_x, mid_y)], [Point(bottomLeft.x, mid_y + 1), Point(mid_x, topRight.y)], [Point(mid_x + 1, bottomLeft.y), Point(topRight.x, mid_y)], [Point(mid_x + 1, mid_y + 1), topRight]]
            
            ret = 0
            for x in sub:
                ret += find(x[0], x[1])
            return ret
            
        return find(bottomLeft, topRight)
11

为什么用js交一直是这个错误啊..

Line ?: SyntaxError: Unexpected end of JSON input
7

自我感觉,第二题和第四题的代码比较简洁,贴一下
第 2 题,直接判断 当前区间和要删除区间的关系,

    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& del) {
        vector<vector<int>> res;
        for (auto &it : intervals) {
            // 当前区间和待删除区间  没有任何交集
            if (it[1] <= del[0] || del[1] <= it[0]) res.push_back(it);
            // 当前区间在待删除区间的左侧发生了一点交集
            if (del[0] <= it[1] && del[0] > it[0]) res.push_back({it[0], del[0]});
            //  当前区间在待删除区间的右侧发生了一点交集
            if (del[1] <= it[1] && del[1] > it[0]) res.push_back({del[1], it[1]});
        }
        return res;
    }

第四题 把区间分成四个区域,然后递归即可,

    int countShips(Sea sea, vector<int> up, vector<int> down) {
        // 当前区域不合理
        if (down[0] > up[0] || down[1] > up[1]) return 0;
        // 当前区域没有船
        if (!sea.hasShips(up, down)) return 0;
        // 当前区域只有一个点,并且有船
        if (up[0] == down[0] && up[1] == down[1]) return 1;

        // 计算坐标
        int lowx = down[0], highx = up[0], lowy = down[1], highy = up[1];
        int midx = (lowx + highx) / 2, midy = (lowy + highy) / 2;
        // 分成 4 个小矩形
        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});
    }
4

扔个python3的题解:
https://space.bilibili.com/99436001

1

第一题 十六进制魔术数字
这道题是简单的进制转换
还有atoll的练习...
code:

class Solution {
public:
    string toHexspeak(string num) {
        long long n = atoll(num.c_str());
        int m;
        int k = 0;
        string str;
        if (n == 0) {
            return "O";
        }
        while (n > 0) {
            m = n % 16;
            n /= 16;
            if (m > 9)
                str.push_back('A' + m - 10);
            else if (m != 1 and m != 0)
                return "ERROR";
            else
                str.push_back(m ? 'I' : 'O');
        }
        reverse(str.begin(), str.end());
        return str;
    }
};

第二题 删除区间
这道题分4种情况:
1.

      intervals
      |--   --|
---------------------
   |--         --|
     toBeRemoved
     intervals
|--              --|
-------------------
  |--         --|
    toBeRemoved
     intervals
|--       --| or --|
-------------------
      |--   --|
     toBeRemoved

除123的所有情况
code:

class Solution {
    vector<vector<int>> ans;
    vector<int> tmp;
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        ans.clear();
        for (auto inter : intervals) {
            if (inter[0] >= toBeRemoved[0] and inter[1] <= toBeRemoved[1]) {
                continue;	
			}
            else if (inter[0] < toBeRemoved[0] and inter[1] > toBeRemoved[1]) {
                tmp.clear();
                tmp.push_back(inter[0]);
                tmp.push_back(toBeRemoved[0]);
                ans.push_back(tmp);
                tmp.clear();
                tmp.push_back(toBeRemoved[1]);
                tmp.push_back(inter[1]);
                ans.push_back(tmp);
            }
            else if (inter[0] < toBeRemoved[0]) {
                tmp.clear();
                tmp.push_back(inter[0]);
                tmp.push_back(min(toBeRemoved[0],inter[1]));
                ans.push_back(tmp);
            }
            else {
                tmp.clear();
                tmp.push_back(max(toBeRemoved[1],inter[0]));
                tmp.push_back(inter[1]);
                ans.push_back(tmp);
            }
        }
        return ans;
    }
};

第三题 删除树节点
我觉得他应该当T2...
太水了!
连爆搜都可以!!!
我这里用的是邻接表.
code:

class Solution {
    int head[10005], next[10005], val[10005], son[10005];
    int dfs(int x) {
        son[x] = 1;
        for (int i = head[x]; i; i = next[i]) {
            son[x] += work(i);
            val[x] += val[i];
        }
        if (!val[x]) son[x] = 0;
        return son[x];
    }
public:
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        memset(head, 0, sizeof(head));
        for (i = 1; i < nodes; i++) {
            next[i] = head[parent[i]];
            head[parent[i]] = i;
        }
        for (i = 0; i < nodes; i++) val[i] = value[i];
        return dfs(0);
    }
};

第四题 矩形内船只的数目
又到与众不同的题了...
乍一瞧,交互是神马???
读完题,啊.......
其实就是在代码某处加上一个东东.
照样码,难度T3你认为T4是什么???
code:

/**
 * // 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 (!sea.hasShips(topRight, bottomLeft)) return 0;
        if (bottomLeft[0] == topRight[0] and bottomLeft[1] == topRight[1]) return 1;
        int l1 = bottomLeft[0];
		int r1 = topRight[0];
		int l2 = bottomLeft[1];
		int r2 = topRight[1];
		int m1 = l1 + r1 >> 1;
		int m2 = l2 + r2 >> 1;
		int ret = 0;
        if (r1 - l1 > r2 - l2) {
            bottomLeft[0] = l1;
            topRight[0] = m1;
            ret += countShips(sea,topRight,bottomLeft);
            bottomLeft[0] = m1 + 1;
            topRight[0] = r1;
            ret += countShips(sea, topRight, bottomLeft);
        }
        else {
            bottomLeft[1] = l2;
            topRight[1] = m2;
            ret += countShips(sea, topRight, bottomLeft);
            bottomLeft[1] = m2 + 1;
            topRight[1] = r2;
            ret += countShips(sea, topRight, bottomLeft);
        }
        return ret;
    }
};

广告
小白二号在每次比赛都写题解
我也要写!!!
至于有些网友说小白二号一些题解写的是其他乱搞的Java
于是我每次双周赛(周赛没空...)都会写全C++的代码
记得关注哦!!!

Java 题解:


第四题的输入参数,先输入右上角,后输入左下角,坑死我了。
明明就那么点代码,怎么算都是 0。

居然是输入参数写反了,hasShips 估计发现输入参数不正确直接返回 false。 生无可恋.jpg

一开始忘了时间,还好压线做完了...

  1. 字符串处理,偷懒用了%lx没自己写进制转换
  2. 处理好交错,互相包含的三种情况就可以了,注意边界
  3. 看数据规模这么小直接写的层序遍历,没多想
  4. 二分法。leetcode之前有过一道类似的题(找山峰),如果做过就可以很快完成。

好难受啊,第三题这样写为什么卡我内存o(╥﹏╥)o

class Solution {
public:
    vector<int> G[10005];
    pair<int,int> dfs(int root,vector<int> value){
        int sum = value[root],size = 1;
        for(auto to:G[root]){
            pair<int,int> p = dfs(to,value);
            sum += p.first;
            size += p.second;
        }
        if(sum == 0) return make_pair(0,0);
        else{
            return make_pair(sum,size);
        }
    }
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        for(int i = 1;i<parent.size();i++){
            G[parent[i]].push_back(i);
        }
        return dfs(0,value).second;
    }
};