Leetcode Weekly Contest #130（1017-1020）思路与题解

Leetcode Weekly Contest #130

Contest 时间是3月31号，4道题的分值分别为 4,5,5,5，都不难，不过最后一道题因为自己鶸所以写了个弱智解法，虽然能AC但是复杂的情况其实是会WA的（只不过测试样例没有覆盖到 ~~要是 cf 的话就没了~~
这篇文章中给出的第四题的解法是大牛的解法。
Contest的地址在这里

1018. Binary Prefix Divisible By 5

题目大意

给定一个 0-1 序列 A ，要求返回一个数组，数组的第 i 个元素表示 A[0]~A[i] 组成的二进制串能不能被 5 整除。

思路

没什么好说的就...直接算就完事儿了，注意越界问题和数的递推。

代码

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) {
        int r = 0;
        vector<bool> result(A.size());
        for (int i = 0; i < A.size(); ++i) {
            r = (r << 1) + A[i];
            r %= 5;
            result[i] = (r == 0);
        }
        return result;
    }
};

1017. Convert to Base -2

题目大意

输入一个数 N，转换成 -2 进制数输出。

思路

对于任意 K 进制，它们的定义都是一样的，不过因为这个进制是负数，所以如果使用通常 K 进制的除法和求模来做要稍微注意一下取整的方向问题。

虽然是负数，由于其是二进制，所以当前位（求模操作）可以直接用位与来做，然后直接减掉模除 -2 来计算下一位即可（对照着 leetcode 给的样例解释看代码会比较清晰一些）。

代码

class Solution {
public:
    string baseNeg2(int N) {
        string result = "";
        if (N == 0) return "0";
        while (N != 0) {
            result = to_string(N & 1) + result;
            N -= (N & 1);
            N /= -2;
        }
        return result;
    }
};

1019. Next Greater Node In Linked List

题目大意

输入一个链表，要求输出一个数组，数组的第 i 个元素为 链表下标和值都比当前位置大的元素的值。

思路

直接朴素算..也是...不会 TLE 的（只不过在所有 submission 的时间排名比较靠后而已）。
要么就用 dp 吧

代码（朴素算法）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> result;
        while (head != NULL) {
            if (head->next == NULL) {
                result.emplace_back(0);
                break;
            }
            int v = head->val;
            for (auto j = head->next; j != NULL; j = j->next) {
                if (j->val > v) {
                    v = j->val;
                    break;
                }
            }
            if (v == head->val) v = 0;
            result.emplace_back(v);
            head = head->next;
        }
        return result;
    }
};

1020. Number of Enclaves

题目大意

输入一个由 0-1 组成的二维数组，上下或者左右相邻为连通，问不与边界连通的 1 的数量有多少个。

思路

直接用 bfs 或者 dfs 都行，对所有边界上的 1 进行 bfs 扫描，把扫描到的 1 变成 0，然后便利数组看看还剩下多少个 1 就是答案了。

代码

class Solution {
public:
    void bfs(int i, int j, vector<vector<int>> &A) {
        if (i < 0 || j < 0 || i > A.size() - 1 || j > A[0].size() - 1 || A[i][j] == 0) return;
        A[i][j] = 0;
        bfs(i - 1, j, A), bfs(i + 1, j, A), bfs(i, j - 1, A), bfs(i, j + 1, A);
    }
    int numEnclaves(vector<vector<int>>& A) {
        for (int i = 0; i < A.size(); ++i)
            bfs(i, 0, A), bfs(i, A[0].size() - 1, A);
        for (int j = 0; j < A[0].size(); ++j)
            bfs(0, j, A), bfs(A.size() - 1, j, A);
        
        int result = 0;
        for (int i = 0; i < A.size(); ++i)
            for (int j = 0; j < A[0].size(); ++j)
                if (A[i][j] == 1) result++;
        return result;
    }
};

Leetcode Weekly Contest #130（1017-1020）思路与题解