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

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

image.png

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

展开讨论

第一题 十六进制魔术数字
这道题是简单的进制转换
还有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++的代码
记得关注哦!!!

展开全部 8 讨论