Skip to content

Commit 50a0106

Browse files
lintcoderlintcoder
committed
5 problems solved.
1 parent e5650c7 commit 50a0106

File tree

5 files changed

+222
-0
lines changed

5 files changed

+222
-0
lines changed

‎src/1010.cpp

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
int numPairsDivisibleBy60(vector<int>& time) {
2+
int len = time.size();
3+
if (len == 1)
4+
return 0;
5+
6+
vector<int> vec(60);
7+
for (int i = 0; i < len; ++i)
8+
{
9+
vec[time[i]%60]++;
10+
}
11+
12+
int sum = 0;
13+
sum += vec[0]*(vec[0]-1)/2 + vec[30]*(vec[30]-1)/2;
14+
for (int i = 1; i <= 29; ++i)
15+
{
16+
sum += vec[i]*vec[60-i];
17+
}
18+
19+
return sum;
20+
}

‎src/1018.cpp

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
vector<bool> prefixesDivBy5(vector<int>& A) {
2+
int len = A.size();
3+
int sum = 0;
4+
vector<bool> vec(len);
5+
for (int i = 0; i < len; ++i)
6+
{
7+
sum = sum*2 + A[i];
8+
sum %= 5;
9+
if (sum%5 == 0)
10+
vec[i] = true;
11+
else
12+
vec[i] = false;
13+
}
14+
15+
return vec;
16+
}

‎src/783.cpp

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
int minDiffInBST(TreeNode* root) {
2+
int mindiff = INT_MAX;
3+
int ct = 0;
4+
int m = 0, n = 0;
5+
search(root, mindiff, m, n, ct);
6+
7+
return mindiff;
8+
}
9+
10+
void search(TreeNode* node, int& mindiff, int& m, int& n, int& ct)
11+
{
12+
if (node->left != nullptr)
13+
search(node->left, mindiff, m, n, ct);
14+
if (ct == 0)
15+
{
16+
m = node->val;
17+
++ct;
18+
}
19+
else if (ct == 1)
20+
{
21+
n = node->val;
22+
int diff = n-m;
23+
if (diff < mindiff)
24+
mindiff = diff;
25+
++ct;
26+
}
27+
else
28+
{
29+
m = n;
30+
n = node->val;
31+
int diff = n-m;
32+
if (diff < mindiff)
33+
mindiff = diff;
34+
}
35+
if (node->right != nullptr)
36+
search(node->right, mindiff, m, n, ct);
37+
}

‎src/830.cpp

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
vector<vector<int>> largeGroupPositions(string S) {
2+
int len = S.size();
3+
if (len <= 2)
4+
return {};
5+
6+
int ct = 1;
7+
int c = S[0];
8+
int i = 1;
9+
int p = 0, q = 0;
10+
vector<vector<int>> res;
11+
while (i < len)
12+
{
13+
if (S[i] == c)
14+
{
15+
++ct;
16+
q = i;
17+
}
18+
else
19+
{
20+
if (ct >= 3)
21+
{
22+
res.push_back({p, q});
23+
}
24+
p = i;
25+
q = i;
26+
c = S[i];
27+
ct = 1;
28+
}
29+
++i;
30+
}
31+
if (ct >= 3)
32+
res.push_back({p, q});
33+
34+
return res;
35+
}

‎src/994.cpp

Lines changed: 114 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,114 @@
1+
int orangesRotting(vector<vector<int>>& grid) {
2+
int row = grid.size();
3+
int col = grid[0].size();
4+
if (row == 1 && col == 1)
5+
return grid[0][0] == 1 ? -1 : 0;
6+
7+
int ct = 0;
8+
vector<vector<int>> flag(row, vector<int>(col, 0));
9+
while (true)
10+
{
11+
bool flag2 = false;
12+
for (int i = 0; i < row; ++i)
13+
{
14+
for (int j = 0; j < col; ++j)
15+
{
16+
if (flag[i][j] == 0 && grid[i][j] == 2)
17+
{
18+
flag2 |= search(grid, row, col, flag, i, j);
19+
}
20+
}
21+
}
22+
if (!flag2)
23+
break;
24+
else
25+
++ct;
26+
flag.assign(row, vector<int>(col, 0));
27+
}
28+
29+
for (int i = 0; i < row; ++i)
30+
{
31+
for (int j = 0; j < col; ++j)
32+
if (grid[i][j] == 1)
33+
return -1;
34+
}
35+
36+
return ct;
37+
}
38+
39+
bool search(vector<vector<int>>& grid, int row, int col, vector<vector<int>>& flag, int m, int n)
40+
{
41+
deque<pair<int,int>> dq;
42+
dq.push_back(make_pair(m, n));
43+
int len = 1;
44+
bool status = false;
45+
while (len != 0)
46+
{
47+
for (int i = 0; i < len; ++i)
48+
{
49+
int p = dq[i].first, q = dq[i].second;
50+
flag[p][q] = 1;
51+
grid[p][q] = 0;
52+
if (p > 0 && flag[p-1][q] == 0 && grid[p-1][q] != 0)
53+
{
54+
if (grid[p-1][q] == 1)
55+
{
56+
grid[p-1][q] = 2;
57+
status = true;
58+
}
59+
else
60+
{
61+
grid[p-1][q] = 0;
62+
dq.push_back(make_pair(p-1, q));
63+
}
64+
flag[p-1][q] = 1;
65+
}
66+
if (p < row-1 && flag[p+1][q] == 0 && grid[p+1][q] != 0)
67+
{
68+
if (grid[p+1][q] == 1)
69+
{
70+
grid[p+1][q] = 2;
71+
status = true;
72+
}
73+
else
74+
{
75+
grid[p+1][q] = 0;
76+
dq.push_back(make_pair(p+1, q));
77+
}
78+
flag[p+1][q] = 1;
79+
}
80+
if (q > 0 && flag[p][q-1] == 0 && grid[p][q-1] != 0)
81+
{
82+
if (grid[p][q-1] == 1)
83+
{
84+
grid[p][q-1] = 2;
85+
status = true;
86+
}
87+
else
88+
{
89+
grid[p][q-1] = 0;
90+
dq.push_back(make_pair(p, q-1));
91+
}
92+
flag[p][q-1] = 1;
93+
}
94+
if (q < col-1 && flag[p][q+1] == 0 && grid[p][q+1] != 0)
95+
{
96+
if (grid[p][q+1] == 1)
97+
{
98+
grid[p][q+1] = 2;
99+
status = true;
100+
}
101+
else
102+
{
103+
grid[p][q+1] = 0;
104+
dq.push_back(make_pair(p, q+1));
105+
}
106+
flag[p][q+1] = 1;
107+
}
108+
}
109+
dq.erase(dq.begin(), dq.begin()+len);
110+
len = dq.size();
111+
}
112+
113+
return status;
114+
}

0 commit comments

Comments
 (0)