type：数学
image-20220628142602227.png
image-20220628142629543.png
type:模拟、字符串
image-20220628142802950.png
https://www.runoob.com/java/java-string.html
type:数学、采样
- 拒绝采样， 过滤红色部分的点
- 从pdf到cdf推导
image-20220628143039943.png
image-20220628143102635.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
Random random;
double xc, yc, r;
public Solution(double radius, double x_center, double y_center) {
random = new Random();
xc = x_center;
yc = y_center;
r = radius;
}
public double[] randPoint() {
double u = random.nextDouble();
double theta = random.nextDouble() * 2 * Math.PI;
double r = Math.sqrt(u);
return new double[]{xc + r * Math.cos(theta) * this.r, yc + r * Math.sin(theta) * this.r};
}
}
|
type: 差分数组、线段树
image-20220628143224257.png
image-20220628143241743.png
type: 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int minEatingSpeed(int[] piles, int h) {
int l_speed = 1, r_speed = 0;
for(int pile: piles){
r_speed = Math.max(r_speed, pile);
}
int k = r_speed;
while(l_speed < r_speed){
int speed = (r_speed - l_speed) / 2 + l_speed;
long time = 0;
for (int pile: piles){
int tmp = (int)Math.ceil((double)pile / speed);
time += tmp;
}
if(time <= h){
k = speed;
r_speed = speed;
}else{
l_speed = speed + 1;
}
}
return k;
}
}
|
type：数学、采样
先随机使用哪个矩形，再随机该矩形内的点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
int[][] rs;
int[] sum;
int size;
Random random = new Random();
public Solution(int[][] rects) {
rs = rects;
size = rs.length;
sum = new int [size+1];
for(int i=1;i<=size;++i){
int area = (rs[i - 1][2] - rs[i - 1][0] + 1) * (rs[i - 1][3] - rs[i - 1][1] + 1);
sum[i] = sum[i-1] + area;
}
}
public int[] pick() {
int val = random.nextInt(sum[size]) + 1;
int l = 0, r = size;
while(l < r){
int mid = l + (r-l) / 2;
if(sum[mid] >= val) r=mid;
else l = mid + 1;
}
int [] cur = rs[r-1];
int x = random.nextInt(cur[2] - cur[0] + 1) + cur[0];
int y = random.nextInt(cur[3] - cur[1] + 1) + cur[1];
return new int [] {x, y};
}
}
|
type: 矩阵、找规律
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 每层的索引和相等：
1. 假设矩阵无限大；
2. 索引和为{偶}数，向上遍历，{横}索引值递减，遍历值依次是(x,0),(x-1,1),(x-2,2),...,(0,x)
3. 索引和为{奇}数，向下遍历，{纵}索引值递减，遍历值依次是(0,y),(1,y-1),(2,y-2),...,(y,0)
每层的索引和:
0: (00)
1: (01)(10)
2: (20)(11)(02)
3: (03)(12)(21)(30)
4: (40)(31)(22)(13)(04)
5: (05)(14)(23)(32)(41)(50)
6: (60)(51)................(06)
按照“层次”遍历，依次append在索引边界内的值即可
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int[] findDiagonalOrder(int[][] mat) {
if (mat == null || mat.length == 0) {
return new int[]{};
}
int m = mat.length, n = mat[0].length;
int[] res = new int[m * n];
int sum = 0, idx = 0;
while(sum < m+n){
if(sum % 2 == 0){
int r = sum<m?sum:(m-1);
int c = sum - r;
while(r>=0 && c>=0 && r<m && c<n){
res[idx++] = mat[r][c];
r--;c++;
}
}else{
int c = sum<n?sum:(n-1);
int r = sum - c;
while(r>=0 && c>=0 && r<m && c<n){
res[idx++] = mat[r][c];
r++;c--;
}
}
sum++;
}
return res;
}
}
|
type: 二叉树
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
int max_depth, res;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return res;
}
void dfs(TreeNode node, int depth){
if(node == null){
return;
}
if(depth>max_depth){
max_depth = depth;
res = node.val;
}
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
}
}
|
BFS 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
int max_depth, res;
public int findBottomLeftValue(TreeNode root) {
Deque<TreeNode> q = new ArrayDeque<>();
q.addLast(root);
int res = 0;
while(!q.isEmpty()){
int num = q.size();
res = q.peek().val;
while(num>0){
TreeNode now = q.pollFirst();
if(now.left != null) q.addLast(now.left);
if(now.right != null) q.addLast(now.right);
num--;
}
}
return res;
}
}
|