leetcode周赛130 | 题解速递
leetcode周赛题解，后面每周如果有时间就做周赛题目，不单独发leetcode的题目了，做多了感觉都可以在以前的题目里面找到类似的。
本期可以重点学习下10进制转-2进制，思路较琐碎。
第一题：1029. 可被 5 整除的二进制前缀
给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
示例 1：
输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。示例 2：
输入：[1,1,1]
输出：[false,false,false]示例 3：
输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]示例 4：
输入：[1,1,1,0,1]
输出：[false,false,false,false,false]提示：
1 <= A.length <= 30000A[i]为0或1
解题思路：
1、每次左进位，注意前面有0的时候要处理。
2、因为数值非常大，必须用大数取模迭代
源代码：
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<bool> prefixesDivBy5(vector<int> &A) {
vector<bool> v;
int s = 0;
for (auto i = 0; i < A.size(); ++i) {
if (s == 0 && A[i] == 0) {
v.push_back(true);
} else if (s == 0 && A[i] == 1) {
s = 1;
v.push_back(false);
} else if (s > 0 && A[i] == 0) {
s <<= 1;
s %= 5;
v.push_back(s == 0);
} else {
s <<= 1;
s += 1;
s %= 5;
v.push_back(s == 0);
}
}
return v;
}
};
int main() {
vector<int> A = {0, 1, 1, 1, 1, 1};
Solution s;
for (auto i : s.prefixesDivBy5(A)) {
cout << i << endl;
}
}第二题：1028. 负二进制转换
给出数字 N，返回由若干 "0" 和 "1"组成的字符串，该字符串为 N 的负二进制（base -2）表示。
除非字符串就是 "0"，否则返回的字符串中不能含有前导零。
示例 1：
输入：2
输出："110"
解释：(-2) ^ 2 + (-2) ^ 1 = 2示例 2：
输入：3
输出："111"
解释：(-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3示例 3：
输入：4
输出："100"
解释：(-2) ^ 2 = 4提示：
0 <= N <= 10^9
解题思路：
这道题感觉是最难的一道题，因为很难想到思路，在对数字进行多次二进制写之后发现了一点规律。
那就是对于奇数位，如有(-2)^3 = 2^4-2^3，偶数位因为能够消除负号就不做处理。
然后进位也要做比较多的处理。
解题代码：
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
char* baseNeg2(int N) {
int n = N;
int i = 0;
int c = 0;
int s[10000];
int k=0;
while (n) {
int mod = n % 2;
//当前位是否为1
if (mod > 0) {
//如果是奇数项
if (i % 2) {
if(c == 1){
//如果此时有进位，刚好抵消
c = 1;
s[k++] = 0;
}else{
//需要2个数
s[k++] = 1;
c = 1;
}
} else {
//偶数项 如2^2+2^2
if (c == 1) {
//该位置成0了，但是继续有进位
c = 1;
s[k++] = 0;
} else {
//一个2^2
s[k++] = 1;
}
}
} else {
//当前位没有值
if (c > 0) {
if(i % 2){
//直接放置一个1，抵消进位
s[k++] = 1;
c = 1;
}else{
s[k++] = 1;
c = 0;
}
} else {
//没有进位
s[k++] = 0;
}
}
n >>= 1;
++i;
}
if(c > 0){
if(i % 2){
s[k++] = 1;
s[k++] = 1;
}else{
s[k++] = 1;
}
}
char * cc = (char*)malloc(k+1);
cc[k] = 0;
int j=0;
for(int i=k-1; i>=0; --i){
cc[j++] = s[i]?'1':'0';
}
if(k == 0){
return "0";
}
return cc;
}
int main() {
char * s = baseNeg2(22);
printf("%s\n", s);
}第三题：1030. 链表中的下一个更大节点
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[5,5,0]示例 2：
输入：[2,7,4,3,5]
输出：[7,0,5,5,0]示例 3：
输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]提示：
- 对于链表中的每个节点，
1 <= node.val <= 10^9 - 给定列表的长度在
[0, 10000]范围内
解题思路：
搜索加剪枝
解题代码：
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
vector<int> nextLargerNodes(ListNode *head) {
vector<int> v;
vector<int> vals;
vector<int> tags;
ListNode *p = head;
int n = 0;
int max_tag = 0;
int last = 0;
while (p) {
if (p->val > last) {
for (int i = max_tag; i < v.size(); ++i) {
if (tags[i] == 0) {
if (vals[i] < p->val) {
tags[i] = 1;
v[i] = p->val;
vals[i] = p->val;
for (int j = max_tag; j < i; ++j) {
if (tags[j] == 1) {
max_tag = j;
} else {
break;
}
}
}
}
}
}
v.push_back(0);
vals.push_back(p->val);
tags.push_back(0);
last = p->val;
p = p->next;
}
return v;
}
};
int main() {
vector<int> A = {4, 6, 3, 2, 6, 3, 9, 9, 3};
ListNode *p = 0;
ListNode *h = 0;
for (auto i : A) {
auto v = new ListNode(i);
if (p == 0) {
p = v;
h = v;
} else {
p->next = v;
p = v;
}
}
Solution s;
for (auto i : s.nextLargerNodes(h)) {
cout << i << endl;
}
}第四题：1031. 飞地的数量
给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：
输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：
有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。示例 2：
输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：
所有 1 都在边界上或可以到达边界。提示：
1 <= A.length <= 5001 <= A[i].length <= 5000 <= A[i][j] <= 1- 所有行的大小都相同
解题思路：
从边开始搜索，注意一定要用set去重，不然会超时。
解题代码：
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
class Solution {
public:
int numEnclaves(vector<vector<int>>& A) {
int dir[4][2] = {
{-1, 0},
{1, 0},
{0, -1},
{0, 1}
};
set<int> q;
int r = A.size();
int c = A[0].size();
for(int i=0; i<A.size(); ++i){
if(A[i][0] == 1){
q.insert(i*c);
}
if(A[i][c-1]){
q.insert(i*c+c-1);
}
}
for(int i=0; i<c; ++i){
if(A[0][i]){
q.insert(i);
}
if(A[r-1][i]){
q.insert(c*(r-1)+i);
}
}
int f = 0;
while(!q.empty()){
int v = *q.begin();
q.erase(q.begin());
int i = v/c;
int j = v%c;
A[i][j] = 0;
for(int k=0; k<4; ++k){
int ni = i+dir[k][0]; //row
int nj = j+dir[k][1]; //col
if(ni > 0 && nj > 0 && ni < r && nj < c){
if(A[ni][nj]){
q.insert(ni*c+nj);
}
}
}
}
for(int i=0; i<r; ++i){
for(int j=0; j<c; ++j){
if(A[i][j]){
++f;
}
}
}
return f;
}
};
int main() {
vector<vector<int>> A = {{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}};
Solution s;
cout<<s.numEnclaves(A)<<endl;
}