Weekly Contest 130
1029. Binary Prefix Divisible By 5
Given an array
A
of0
s and1
s, considerN_i
: the i-th subarray fromA[0]
toA[i]
interpreted as a binary number (from most-significant-bit to least-significant-bit.)Return a list of booleans
answer
, whereanswer[i]
istrue
if and only ifN_i
is divisible by 5.
Example 1:
Input: [0,1,1]
Output: [true,false,false]
Explanation:
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.Example 2:
Input: [1,1,1]
Output: [false,false,false]Example 3:
Input: [0,1,1,1,1,1]
Output: [true,false,false,false,true,false]Example 4:
Input: [1,1,1,0,1]
Output: [false,false,false,false,false]
Note:
1 <= A.length <= 30000
A[i]
is0
or1
Approach #1:
class Solution {
public:
vector<bool> prefixesDivBy5(vector<int>& A) {
int n = A.size();
vector<bool> ans;
int temp = 0;
for (int i = 0; i < n; ++i) {
temp = (temp << 1) + A[i];
if (temp % 5 == 0) ans.push_back(true);
else ans.push_back(false);
temp %= 5;
} return ans;
}
};
1028. Convert to Base -2
Given a number
N
, return a string consisting of"0"
s and"1"
s that represents its value in base-2
(negative two).The returned string must have no leading zeroes, unless the string is
"0"
.
Example 1:
Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2Example 2:
Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3Example 3:
Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4
Note:
0 <= N <= 10^9
Approach #1:
1030. Next Greater Node In Linked List
We are given a linked list with
head
as the first node. Let's number the nodes in the list:node_1, node_2, node_3, ...
etc.Each node may have a next larger value: for
node_i
,next_larger(node_i)
is thenode_j.val
such thatj > i
,node_j.val > node_i.val
, andj
is the smallest possible choice. If such aj
does not exist, the next larger value is0
.Return an array of integers
answer
, whereanswer[i] = next_larger(node_{i+1})
.Note that in the example inputs (not outputs) below, arrays such as
[2,1,5]
represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
Example 1:
Input: [2,1,5]
Output: [5,5,0]Example 2:
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]Example 3:
Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]
Note:
1 <= node.val <= 10^9
for each node in the linked list.- The given list has length in the range
[0, 10000]
.
Approach #1:
/**
* 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> temp;
while (head != NULL) {
temp.push_back(head->val);
head = head->next;
} int len = temp.size(); vector<int> ans; for (int i = 0; i < len; ++i) {
bool flag = false;
for (int j = i+1; j < len; ++j) {
if (temp[j] > temp[i]) {
ans.push_back(temp[j]);
flag = true;
break;
}
}
if (!flag) ans.push_back(0);
} return ans;
}
};
1031. Number of Enclaves
Given a 2D array
A
, each cell is 0 (representing sea) or 1 (representing land)A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
Example 1:
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation:
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.Example 2:
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation:
All 1s are either on the boundary or can reach the boundary.
Note:
1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
- All rows have the same size.
Approach #1:
class Solution {
public:
int numEnclaves(vector<vector<int>>& A) {
int ans = 0;
row = A.size(), col = A[0].size(); for (int i = 0; i < row; ++i)
for (int j = 0; j < col; ++j)
if (i == 0 || i == row-1 || j == 0 || j == col-1)
if (A[i][j] == 1)
dfs(A, i, j); for (int i = 0; i < row; ++i)
for (int j = 0; j < col; ++j)
if (A[i][j] == 1)
ans++; return ans;
} private:
int row, col;
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void dfs(vector<vector<int>>& A, int x, int y) {
A[x][y] = 0;
for (int i = 0; i < 4; ++i) {
int dx = x + dirs[i][0];
int dy = y + dirs[i][1];
if (dx < 0 || dy < 0 || dx >= row || dy >= col) continue;
if (A[dx][dy] == 1) dfs(A, dx, dy);
}
}
};
最新文章
- 如何在Node.js中合并两个复杂对象
- iOS、Xcode监测键盘的显示和隐藏变化,并获得键盘高度,改变tableView的frame和偏移
- [css3]水平垂直居中
- (转)IC验证概述
- javascript事件大全4
- DB2中ixf文件的导入导出
- Oracle游标、参数的使用例子
- Vanya and Triangles 暴力枚举
- mysql explain 命令简解
- jconsole 连接 eclipse启动项
- 快速搭建appium自动测试环境
- 【视频编解码&#183;学习笔记】11. 提取SPS信息程序
- 为何没有asia/beijing时区?
- 【Nginx】-NO.141.Nginx.1 -【Nginx】
- Promise学习使用
- topcoder srm 701 div1 -3
- 如何创建并运行java线程 , 多线程使用
- maven中scope标签详解
- this inspection reports usage of the default file template for file header
- 【转】WinForm基础
热门文章
- centos一键安装lnmp成功后无法访问ip(解决办法)
- CF 1023D Array Restoration - 线段树
- lib文件反汇编
- OpenSCManager
- c++之boost share_ptr
- [SoapUI] 在执行某个TestSuite之前先执行login或者其他什么前置步骤
- 8.15 session 有效时间, session在数据查询中最后不用
- hive 报错 java.lang.RuntimeException: Unable to instantiate org.apache.hadoop.hive.metastore.HiveMetaStoreClient
- 2018.07.04 POJ 1696 Space Ant(凸包卷包裹)
- hdu-1141