8000 bitmap · qinyafee/leetcode@73c3f0c · GitHub
[go: up one dir, main page]
Skip to content

Commit 73c3f0c

Browse files
qinyafeeqinyafee
committed
bitmap
Signed-off-by: Yafei <yafee.qin@gmail.com>
1 parent 387d6d4 commit 73c3f0c

File tree

7 files changed

+146
-75
lines changed

7 files changed

+146
-75
lines changed

‎NoIncluded.md

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,6 @@ Candy
5858
## 没刷的M
5959
H-Index II
6060
Best Time to Buy and Sell Stock with Cooldown
61-
Range Sum Query - Mmutable
6261
Binary Search Tree Iterator
6362
Construct Binary Tree from Preorder and Inorder Traversal
6463
Construct Binary Tree from Inorder and Postorder Traversal
@@ -78,7 +77,6 @@ KMP
7877
Decode Ways
7978
Range Sum Query - Mutable 线段树/树状数组，+1
8079
Insertion Sort List
81-
Single Number II
8280

8381
## 易错题
8482
Minimum Depth of Binary Tree

‎algorithms/cpp/candy/candy.cpp

Lines changed: 117 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -1,48 +1,102 @@
1+
// 规则定义： 设学生 A 和学生 B 左右相邻，A在 B左边；
2+
// 左规则： 当 ratingsB>ratingsA时，B的糖比 A的糖数量多。
3+
// 右规则： 当 ratingsA>ratingsB时，A的糖比 B的糖数量多。
4+
// 相邻的学生中，评分高的学生必须获得更多的糖果 等价于 所有学生满足左规则且满足右规则。
5+
// 两边扫描即可
6+
// 链接：https://leetcode.cn/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/
7+
8+
#include <algorithm>
9+
#include <iostream>
10+
#include <vector>
11+
using namespace std;
12+
class Solution {
13+
public:
14+
int candy(vector<int>& ratings) {
15+
const int n = ratings.size();
16+
// if(n == 0) return 0;
17+
// if(n == 1) return 1;
18+
vector<int> assign(n);
19+
// 左扫描
20+
int inc = 1; //高分递增起点
21+
for (int i = 1; i < n; i++) {
22+
if (ratings[i] > ratings[i - 1]) {
23+
assign[i] = max(inc++, assign[i]);
24+
} else {
25+
inc = 1;
26+
}
27+
}
28+
// 右扫描
29+
inc = 1;
30+
for (int i = n - 2; i >= 0; i--) {
31+
if (ratings[i] > ratings[i + 1]) {
32+
assign[i] = max(inc++, assign[i]);
33+
} else {
34+
inc = 1;
35+
}
36+
}
37+
// 最开始每人至少一颗
38+
int sum = accumulate(&assign[0], &assign[0] + n, n);
39+
return sum;
40+
}
41+
};
42+
int main() {
43+
// clang-format off
44+
vector<int> ratings{ 5, 4, 1, 9, 7, 2, 3, 2, 1, 7 };
45+
// 0 0 0 1 0 0 1 0 0 1
46+
// 2 1 0 2 1 0 2 1 0 1 //10+10
47+
//vector<int> ratings{};
48+
// 0 0 0 1 0 0 1 0 0 1
49+
// 2 1 0 2 1 0 2 1 0 1 //10+10
50+
// clang-format on
51+
Solution solution;
52+
cout << solution.candy(ratings) << '\n';
53+
return 0;
54+
}
55+
156
// Source : https://oj.leetcode.com/problems/candy/
257
// Author : Hao Chen
358
// Date : 2014-10-12
459

5-
/**********************************************************************************
6-
*
7-
* There are N children standing in a line. Each child is assigned a rating value.
8-
*
9-
* You are giving candies to these children subjected to the following requirements:
10-
*
11-
* Each child must have at least one candy.
12-
* Children with a higher rating get more candies than their neighbors.
13-
*
14-
* What is the minimum candies you must give?
15-
*
16-
*
17-
**********************************************************************************/
60+
/**********************************************************************************
61+
*
62+
* There are N children standing in a line. Each child is assigned a rating value.
63+
*
64+
* You are giving candies to these children subjected to the following requirements:
65+
*
66+
* Each child must have at least one candy.
67+
* Children with a higher rating get more candies than their neighbors.
68+
*
69+
* What is the minimum candies you must give?
70+
*
71+
*
72+
**********************************************************************************/
1873

1974
#include <stdlib.h>
2075
#include <time.h>
2176
#include <iostream>
2277
#include <vector>
2378
using namespace std;
2479

25-
26-
void print(vector<int> &v);
80+
void print(vector<int>& v);
2781

2882
/*
2983
* The soluiton is O(2n) run-time complexity
3084
*
3185
* For example:
3286
*
33-
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
87+
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
3488
*
3589
* 1) Go through the ratings from left to right.
3690
*
37-
* Find the each increasing sub-array, giving the minimal candy
91+
* Find the each increasing sub-array, giving the minimal candy
3892
*
39-
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
93+
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
4094
* ------> -> ------> -> --->
4195
* candy[] = { 1, 2, 3, 1, 1, 2, 3, 1, 1, 2 }
4296
*
4397
* 2) Go through the raings from right to left.
4498
*
45-
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
99+
* ratings[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 }
46100
* <- <- <------ <- <------ <-
47101
* prev_candy[] = { 1, 2, 3, 1, 1, 2, 3, 1, 1, 2 }
48102
* +1 +1
@@ -51,56 +105,56 @@ void print(vector<int> &v);
51105
* 3) total candy is 19
52106
*
53107
*/
54-
int candy(vector<int> &ratings) {
55-
56-
vector<int> candyCnt(ratings.size()) ;
57-
//allocate candies, considering the minimal rating on the left
58-
candyCnt[0] = 1;
59-
for(int i = 1; i < ratings.size(); i++){
60-
candyCnt[i] = ratings[i] > ratings[i-1] ? candyCnt[i-1]+1 : 1;
61-
}
62-
print(candyCnt);
63-
//modify the allocation, considering the minimal rating on the right
64-
int totalCandy = candyCnt[ratings.size()-1];
65-
for(int i = ratings.size()-2; i >= 0; i--){
66-
candyCnt[i] = (ratings[i] > ratings[i+1] && candyCnt[i+1]+1 > candyCnt[i]) ? candyCnt[i+1]+1 : candyCnt[i];
67-
//count total candies by the way
68-
totalCandy += candyCnt[i];
69-
}
70-
print(candyCnt);
71-
return totalCandy;
108+
int candy(vector<int>& ratings) {
109+
vector<int> candyCnt(ratings.size());
110+
// allocate candies, considering the minimal rating on the left
111+
candyCnt[0] = 7E71 1;
112+
for (int i = 1; i < ratings.size(); i++) {
113+
candyCnt[i] = ratings[i] > ratings[i - 1] ? candyCnt[i - 1] + 1 : 1;
114+
}
115+
print(candyCnt);
116+
// modify the allocation, considering the minimal rating on the right
117+
int totalCandy = candyCnt[ratings.size() - 1];
118+
for (int i = ratings.size() - 2; i >= 0; i--) {
119+
candyCnt[i] = (ratings[i] > ratings[i + 1] && candyCnt[i + 1] + 1 > candyCnt[i])
120+
? candyCnt[i + 1] + 1
121+
: candyCnt[i];
122+
// count total candies by the way
123+
totalCandy += candyCnt[i];
124+
}
125+
print(candyCnt);
126+
return totalCandy;
72127
}
73128

74-
void generateRatings(vector<int> &ratings, int n) {
75-
srand(time(0));
76-
for (int i=0; i<n; i++) {
77-
ratings.push_back(rand()%10);
78-
}
129+
void generateRatings(vector<int>& ratings, int n) {
130+
srand(time(0));
131+
for (int i = 0; i < n; i++) {
132+
ratings.push_back(rand() % 10);
133+
}
79134
}
80135

81-
void print(vector<int> &v) {
82-
for(int i=0; i<v.size(); i++){
83-
cout << v[i] << " ";
84-
}
85-
cout << endl;
136+
void print(vector<int>& v) {
137+
for (int i = 0; i < v.size(); i++) {
138+
cout << v[i] << " ";
139+
}
140+
cout << endl;
86141
}
87142

88-
int main(int argc, char**argv)
89-
{
90-
int n = 10;
91-
if (argc>1){
92-
n = atoi(argv[1]);
93-
}
94-
vector<int> ratings;
95-
generateRatings(ratings, n);
96-
print(ratings);
143+
int main(int argc, char** argv) {
144+
int n = 10;
145+
if (argc > 1) {
146+
n = atoi(argv[1]);
147+
}
148+
vector<int> ratings;
149+
generateRatings(ratings, n);
150+
print(ratings);
97151

98-
cout << candy(ratings) << endl;
152+
cout << candy(ratings) << endl;
99153

100-
cout << "--------------------" << endl;
101-
int r[] = { 5, 6, 7, 4, 1, 2, 3, 2, 1, 7 };
102-
vector<int> ra(r, r+sizeof(r)/sizeof(r[0]));
103-
print(ra);
104-
cout << candy(ra) << endl;
105-
return 0;
154+
cout << "--------------------" << endl;
155+
int r[] = {5, 6, 7, 4, 1, 2, 3, 2, 1, 7};
156+
vector<int> ra(r, r + sizeof(r) / sizeof(r[0]));
157+
print(ra);
158+
cout << candy(ra) << endl;
159+
return 0;
106160
}

‎algorithms/cpp/climbStairs/climbStairs.cpp

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,28 @@ class Solution {
4949
// return dp[n-1];
5050
// }
5151
};
52+
53+
// Problem2 变态跳台阶
54+
// 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
55+
56+
// 分析
57+
// 易知 f(n)=f(n-1)+f(n-2)+……f(1)
58+
// f(n-1)=f(n-2)+……f(1)
59+
// 两式相减得f(n)=2f(n-1)
60+
61+
class Solution {
62+
public:
63+
int jumpFloorII(int number) {
64+
if (number <= 0) {
65+
return -1;
66+
} else if (number == 1) {
67+
return 1;
68+
} else {
69+
{ return 2 * jumpFloorII(number - 1); }
70+
}
71+
}
72+
};
73+
5274
// 爬楼梯变种总结
5375
// https://blog.csdn.net/wjhshuai/article/details/68952756
5476
// 上n个台阶，每次一步或两步，求走法数量，简单DP。

‎algorithms/cpp/countCompleteTreeNodes/CompleteBinaryTreeInserter.cpp

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -35,8 +35,9 @@ class CBTInserter {
3535
node = node->left;
3636
}
3737
}
38+
// 处理循环的最后一次,bits=0
3839
if (idx & 1) {
39-
node->right = new TreeNode(val);
40+
node->right = new TreeNode(val); // 此时node是上一层最后一个元素
4041
} else {
4142
node->left = new TreeNode(val);
4243
}
@@ -92,5 +93,3 @@ class CBTInserter {
9293
};
9394

9495
// Source : https://leetcode.com/problems/count-complete-tree-nodes/
95-
96-

‎algorithms/cpp/countCompleteTreeNodes/CountCompleteTreeNodes.cpp

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,10 +35,10 @@ class Solution {
3535
// 其中最高位是 1，其余各位从高到低表示从根节点到第 k 个节点的路径，
3636
// 0 表示移动到左子节点，1表示移动到右子节点。
3737
bool exists(TreeNode* root, int level, int k) {
38-
int bits = 1 << (level - 1); // 从第l-1位开始找，对应第l=1层
38+
int bits = 1 << (level - 1); // 从第l-1位开始找，对应第1层
3939
TreeNode* p = root;
4040
while (p != nullptr && bits > 0) {
41-
if (!(bits & k)) {
41+
if (!(bits & k)) { // 遍历k中的某一位=0
4242
p = p->left;
4343
} else {
4444
p = p->right;

‎algorithms/cpp/bitMap/bitmap.cpp renamed to ‎algorithms/other/bitmap.cpp

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,8 @@
11
// 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快 速判断一个数是否在这40亿个数中。
22
// https://blog.csdn.net/archyli/article/details/78573362
33
// 【腾讯】
4-
// 一个整数是4个字节，40亿个整数就是160亿个字节，也就相当于16G内存，就一般的计算机而言很难实现这个加载，所以我们可以采取以下两种方案，一种是分割，一种是位图。
54

6-
// 方法：
5+
// 分析：一个整数是4个字节(uint32_t)，40亿个整数就是160亿个字节，也就相当于16G内存，就一般的计算机而言很难实现这个加载
76
// ①分割，hash求余
87
// 采用分割处理，把40亿个数分批次处理完毕，当然可以实现我们最终的目标，但是这样做时间复杂度未免优点太高。
98
// ②位图BitMap
@@ -18,7 +17,6 @@ using namespace std;
1817
class BitMap {
1918
public:
2019
BitMap(size_t range) {
21-
//此时多开辟一个空间
2220
_bits.resize(range / 32 + 1); // 申请的位图大小， 4E9/32+1 = 119MB
2321
}
2422
void Set(size_t x) {
@@ -50,7 +48,7 @@ void TestBitMap() {
5048

5149
bm.Set(136);
5250
bm.Set(1);
53-
bm.Set(static_cast<uint32_t>(-1));//如果是有符号数，先转换成无符号
51+
bm.Set(static_cast<uint32_t>(-1)); //如果是有符号数，先转换成无符号
5452
cout << bm.Test(136) << endl;
5553
bm.Reset(136);
5654
cout << bm.Test(136) << endl;

‎algorithms/other/shortest-path-bfs.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11

22
// 宽度优先搜索 最短路径
33
// 对于图搜索的问题，既可以使用bfs也可以使用dfs方法来解决，
4-
// 使用bfs求得的解一定是步数最少的，而dfs则不一定，因此本题更宜使用bfs法
4+
// 使用bfs求得的解一定是步数最少的，而dfs则不一定
55

66
#include <cmath>
77
#include <cstdio>

0 commit comments

Comments
 (0)
0