Leetcode Weekly Contest #129（1013-1016）思路与题解

Leetcode Weekly Contest #129

共四道题，这次四道题的分值分别为 4, 4, 5, 5，原始地址在这里，总体不算难，最后一题看了一下 discuss 写了一个较好的解法。

1013. Partition Array Into Three Parts With Equal Sum

题目大意

给定一个整数数组，确定其能否被划分为三个非空的子区间使得三个区间内的和相等。
原题链接

解法

很朴素的一道题，直接累加一遍看看全部求和能不能被 3 整除，如果可以的话那就从头扫描划分。
如果有存在多种划分方式，也不影响划分过程，直接做划分即可。

代码

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum = 0;
        for (auto i : A)
            sum += i;
        if (sum % 3 != 0) return false;
        int cnt = 0;
        sum /= 3;
        int s = 0;
        for (auto i : A) {
            s += i;
            if (s == sum) {
                cnt++;
                s = 0;
            }
        }
        return cnt == 3 && s == 0;
    }
};

1015. Smallest Integer Divisible by K

题目大意

给定一个小于 10ˆ5 的正整数 K，找到一个最小的数 N 使得 N 能被 K 整除且 N 只由数字 1 组成，输出 N 的位数，如果不存在输出 -1。
原题链接

解题思路

首先直接判断 K 能被 2 或 5 整除，如果是的话，则其的倍数不可能只包含数字 1，直接返回结果 -1。另外如果 K 是 1 的话，直接返回结果 1。
然后我们从 2 开始循环构造 i 位的 N，判断其是否能被 K 整除，如果可以的话返回 i，否则令 i = i + 1，直到 i 取到最大值（可以写死循环）。

Discuss 上面有人给出了证明说是上述第二步的循环至多只用进行 K 次，而且只要 K 不是 2 或 5 的倍数，N 一定存在。

证明
如果 K 是 2 或 5 的倍数，显然 N 不存在（易证）
假设 K 不是 2 或 5 的倍数，设序列 [1, 11, 111, ....] 为序列 A，要证明序列 A 的前 K 项一定存在一个数能被 K 整除。
反证法，假设序列 A 的前 K 项目不存在这样的数，那么 A[1..K] 中一定不存在模 K 为 0 的数，而这之中有 K 个数，他们模 K 的结果一定是 1..K-1，因此由鸽巢原理，一定存在两个数它们模 K 的结果相等，不妨设它们分别是 A_i < A_j。
因此 (A_j - A_i) 一定能被 K 整除，但由于 (A_j - A_i) 末尾有 i 个 0，其一定是 10 的倍数，而 K 不是 2 或 5 的倍数，因此 (A_j - A_i) 不可能被 K 整除，得出矛盾。
综上，序列 A 的前 K 项一定存在一个数能被 K 整除。

代码

class Solution {
public:
    int smallestRepunitDivByK(int K) {
        if (K == 1) return 1;
        int n = 0;
        if (K % 2 == 0 || K % 5 == 0) return -1;
        for (int i = 1; i <= K; ++i) {
            n = (10 * n + 1) % K;
            if (n % K == 0) return i;
        }
        return -1;
    }
};

1014. Best Sightseeing Pair

题目大意

给定一个数组描述若干个景点的分数，任意两对景点之间的评分由 A[j]+A[i]-(j-i) 计算，求最大的景点对的评分。

解题思路

这题不难，用dp（动态规划）解决，dp数组内容的意义为当前位置作为后一个景点时的最大评分。

代码

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int score[50001];
        score[0] = A[0];
        for (int i = 1; i < A.size(); ++i) {
            score[i] = score[i - 1] - 1 + A[i] - A[i - 1];
            score[i] = max(score[i], A[i] + A[i - 1] - 1);
        }
        int mx = 0;
        for (int i = 0; i < A.size(); ++i)
            mx = max(mx, score[i]);
        return mx;
    }
};

1016. Binary String With Substrings Representing 1 To N

题目大意

给定一个由 01 构成的字符串和一个正整数 N，判断 1-N 共 N 个数的二进制表示是不是都可以在字符串中找到这样的子串。

解题思路

循环，以字符串的每一个非 0 位置作为开始向后取子串，把子串对应的数字记录下来，最后扫描一遍看看 1-N 中的所有数是不是都被记录过。

思考了一下，这个过程跟 RK 算法的字符串匹配思路非常接近。
我看的 RK 算法的相关文章链接
然后是我朋友的解法：
把 1-N 共 N 个数的二进制表示转换为字符串，然后每一个都用 O(n) 的字符串匹配算法（KMP）去源字符串中匹配。
两种思路其实都可以看作字符串匹配，不过因为 KMP 我总是记不住还容易出错...所以我直接写了第一种解法，写完没测试直接提交就 AC 了

代码

class Solution {
public:
    bool queryString(string S, int N) {
        vector<bool> map(N + 1);
        int start = 0;
        int sum = 0, end;
        for (int start = 0; start < S.size(); ++start) {
            if (S[start] == '0') continue;
            end = start;
            sum = 0;
            while (end < S.size()) {
                sum = sum << 1;
                sum = sum + S[end] - '0';
                if (sum > N) break;
                map[sum] = true;
                end++;
            }
        }
        
        for (int i = 1; i <= N; ++i) {
            if (map[i] == false) return false;
        }
        return true;
    }
};

Leetcode Weekly Contest #129（1013-1016）思路与题解