LeetCode Biweekly Contest 14

LeetCode Biweekly Contest 14.

问题 1

题目链接

整数转换为 16 进制字符串：

  • Python 用自带的 hex 函数。
  • C++ 用 stringstream 中的 hex。

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def toHexspeak(self, num: str) -> str:
        num = hex(int(num))[2:]

        num = num.replace('1', 'I').replace('0', 'O').upper()

        for x in num:
            if x not in {"A", "B", "C", "D", "E", "F", "I", "O"}:
                return 'ERROR'

        return num

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string toHexspeak(string num) {
        auto n = stol(num);
        stringstream st;
        st << hex << uppercase << n;  // 用 hex + uppercase 进行转换
        string s(st.str());
        for (auto i = 0; i < s.size(); ++i) {
            if (s[i] > '1' && s[i] <= '9') return "ERROR";
            if (s[i] == '0') s[i] = 'O';
            if (s[i] == '1') s[i] = 'I';
        }
        return s;
    }
};

问题 2

题目链接

解法：遍历判断与每个 interval 起始/结束时间的关系。
复杂度：时间复杂度 O(n)，空间复杂度 O(n)。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def removeInterval(self, intervals: List[List[int]],
                       toBeRemoved: List[int]) -> List[List[int]]:
        res = []

        s, e = toBeRemoved

        for i, interval in enumerate(intervals):
            i_s, i_e = interval
            if s >= i_e or e <= i_s:
                res.append(interval)
            else:
                if i_s < s <= i_e:
                    res.append([i_s, s])
                if i_s <= e < i_e:
                    res.append([e, i_e])

        return res

C++

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
class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals,
                                       vector<int>& toBeRemoved) {
        vector<vector<int>> res;

        int s = toBeRemoved[0], e = toBeRemoved[1];

        for (int i = 0; i < intervals.size(); i++){
            int i_s = intervals[i][0], i_e = intervals[i][1];

            if (s >= i_e || e <= i_s){
                res.push_back(vector<int>{i_s, i_e});
            } else {
                if (i_s < s && s <= i_e) {
                    res.push_back(vector<int>{i_s, s});
                }
                if (i_s <= e && e < i_e) {
                    res.push_back(vector<int>{e, i_e});
                }
            }

        }

        return res;
    }
};

问题 3

题目链接

解法：DFS，利用返回值计数。

复杂度：时间复杂度 O(n)，空间复杂度 O(n)。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        nei = collections.defaultdict(list)

        for i, x in enumerate(parent):
            if x != -1:
                nei[x].append(i)

        self.n = nodes

        def dfs(i):
            res = value[i]
            ces = 1
            for x in nei[i]:
                s, c = dfs(x)
                res += s
                ces += c if s != 0 else 0

            return (res, ces) if res != 0 else (res, 0)

        s, c = dfs(0)

        return c

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> nodeNum(vector<int>& value, int node, unordered_map<int, vector<int>>& nei) {
        int sum = value[node], count = 1;
        for (auto &child : nei[node]) {
            vector<int> res = nodeNum(value, child, nei);
            sum += res[0];
            count += (res[0] == 0) ? 0 : res[1];
        }
        return {sum, sum == 0 ? 0 : count};
    }
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        int root = -1;
        unordered_map<int, vector<int>> nei;

        for (int i = 0; i < parent.size(); ++i) {
            nei[parent[i]].push_back(i);
            if (parent[i] == -1) root = i;
        }
        vector<int> res = nodeNum(value, root, nei);
        return res[1];
    }
};

问题 4

题目链接
解法：两个坐标二分搜索。

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def countShips(self, sea: 'Sea', P: 'Point', Q: 'Point') -> int:
        res = 0
        if P.x >= Q.x and P.y >= Q.y and sea.hasShips(P, Q):
            if P.x == Q.x and P.y == Q.y: return 1
            mx, my = (P.x + Q.x) // 2, (P.y + Q.y) // 2
            res += self.countShips(sea, P, Point(mx + 1, my + 1))
            res += self.countShips(sea, Point(mx, P.y), Point(Q.x, my + 1))
            res += self.countShips(sea, Point(mx, my), Q)
            res += self.countShips(sea, Point(P.x, my), Point(mx + 1, Q.y))
        return res

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        int res = 0;

        if (topRight[0] >= bottomLeft[0] && topRight[1] >= bottomLeft[1] 
            && sea.hasShips(topRight, bottomLeft)) {
            if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) {
                return 1;
            }
            int mx = (topRight[0] + bottomLeft[0]) / 2;
            int my = (topRight[1] + bottomLeft[1]) / 2;
            res += countShips(sea, topRight, {mx+1, my+1});
            res += countShips(sea, {mx, topRight[1]}, {bottomLeft[0], my+1});
            res += countShips(sea, {mx, my}, bottomLeft);
            res += countShips(sea, {topRight[0], my}, {mx+1, bottomLeft[1]});
        }

        return res;
    }
};

留言

2019-12-01
▲