ReeeStart

01/02/2019
LeetCode 928 Minimize Malware Spread II

Problem

⭐️⭐️⭐️⭐️⭐️

这题和Minimize Malware Spread I的区别是:

I: 问如果从initial中取掉一个server, 把这个server的病毒给清了, 那要对哪个server杀毒, 能使得最终Internet里被感染的结点数最少?
II: 问如果从Initial中取掉一个server, 把它从整个网络中拿掉, 要拿掉哪个server, 能使最终被感染的结点数最少?

Read More

01/02/2019
LeetCode 337 House Robber III

Problem

⭐️⭐️⭐️⭐️

House Robber III, 说现在houses是以binary tree的形式呈现, 小偷不能偷相邻的houses, 问最大的profit是多少?

Read More

01/02/2019
LeetCode 924 Minimize Malware Spread

Problem

⭐️⭐️⭐️⭐️

给一个matrix表示Internet中connect的结点, graph[i][j] = 1表示server i和server j是connect的. 然后再给一个数组initial表示中毒的server.

问如果从initial中取掉一个server, 把这个server的病毒给清了, 那要清楚哪个server能使得最终Internet里被感染的结点数最少?

Read More

01/02/2019
LeetCode 968 Binary Tree Camera

Problem

⭐️⭐️⭐️⭐️⭐️

Binary Tree Camera

说给一个二叉树, 然后要放camera, 每个camera可以cover结点自己, children, 以及parent. 问最少放几个camera能把整个二叉树给cover住.

Read More

01/02/2019
LeetCode 337 House Robber III

Problem

⭐️⭐️⭐️⭐️

House Robber III, 说现在houses是以binary tree的形式呈现, 小偷不能偷相邻的houses, 问最大的profit是多少?

Read More

01/02/2019
LeetCode 10 Regular Expression Matching (With Follow up)

Problem

⭐️⭐️⭐️⭐️⭐️

Regular Expression

Follow up: How about includes:

  1. ‘+’, one or more preceding character.
  2. ‘?’, one or none preceding character.
Read More

01/02/2019
LeetCode 44 Wildcard Matching

Problem

⭐️⭐️⭐️⭐️⭐️

Wildcard Matching

Read More

01/02/2019
Kadane's Algorithm

#解决什么问题?

Maximum subarray sum

#思想

dp[i] represents the maximum subarray sum ending with i-th element

dp[i] = Math.max(dp[i - 1] + A[i], A[i])

#应用

  • LeetCode 53 Maximum Subarray
  • LeetCode 918 Maximum Sum Circular Array

01/02/2019
LeetCode 918 Maximum Sum Circular Subarray

Problem

⭐️⭐️⭐️⭐️⭐️

Maximum subarray的follow up. 在可循环的array里找maximum subarray sum.

Read More

01/02/2019
GeeksForGeeks Maximum Sum in Circular Array Such That No Two Elements Are Adjacent

Problem

⭐️⭐️⭐️⭐️⭐️

求一个array, 如果可以循环的话, 非相邻元素能组成的最大sum.

Read More

01/02/2019
GeeksForGeeks Maximum Sum such that No Two Elements Are Adjacent

Problem

⭐️⭐️⭐️⭐️

求一个array中非连续元素能组成的最大sum.

Read More

01/02/2019
Binary Indexed Tree (Fenwick Tree)

#What’s the problem that Binary Indexed Tree trying to solve?

Prefix Sum

Range Sum可以通过prefix sum来求得. 但BIT并不是直接solve range sum, 而是解决prefix sum的问题.

#Two Main Function in Binary Indexed Tree

getParent(x) = x - (x & (-x)), used for query
getNext(x) = x + (x & (-x)), used for update

#Why it works?

因为每个数都可以用2进制来表示, 比如:

  • 7 = 2^2 + 2^1 + 2^0
  • 10 = 2^3 + 2^1

因此可以把这些2^x 看作是binary indexed tree中的一个结点. 每个结点的parent就是当前结点去掉最右边一位1的结果, 比如:

  • 7的parent是6,6的parent是4, 4的parent是0
  • 10的parent是8,8的parent是0

那么在每次query prefix sum的时候, 从当前结点一路往上getParent, 得到的path sum就是结果.
而在每次update的时候, 从当前结点一路update getNext, 注意getNext不一定是和当前结点在一条path上(但getParent一定是一条path).

#Code

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
class BIT {
private int[] A;
private int[] bit;
private int n;
public(int[] A) {
this.n = A.length;
this.A = A;
this.bit = new int[n];
}
public void update(int index, int value) {
int delta = value - A[index];
while (index < n) {
bit[index] += delta;
index += (index & (-index));
}
}
public int prefixSum(int index) {
int res = 0;
while (index < n) {
res += bit[index];
index -= (index & (-index));
}
return res;
}
}

#Reference:

https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
https://www.youtube.com/watch?v=WbafSgetDDk&t=980s
https://www.youtube.com/watch?v=CWDQJGaN1gY&t=1s

01/02/2019
LeetCode 32 Longest Valid Parentheses

Problem

⭐️⭐️⭐️⭐️⭐️

Longest Valid Parentheses substring

Read More

01/02/2019
LeetCode 37 Sudoku Solver

Problem

⭐️⭐️⭐️⭐️⭐️

Sudoku Solver

Read More

01/02/2019
LeetCode 407 Trapping Rain Water II

Problem

⭐️⭐️⭐️⭐️⭐️

Read More

01/02/2019
LeetCode 42 Trapping Rain Water

Problem

#####⭐️⭐️⭐️⭐️⭐️

Read More

12/27/2018
LeetCode 729 My Calendar I

#Problem

#⭐️⭐️⭐️

My Calendar I

#Solution

用一个tree set根据start time排序. 然后对于每一个add请求, 找floor和ceiling的interval, 看是否有重合.

#Code

#Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyCalendar {
private TreeSet<int[]> treeSet;
public MyCalendar() {
this.treeSet = new TreeSet<>((a, b) -> { return a[0] - b[0]; });
}
public boolean book(int start, int end) {
int[] curr = new int[] {start, end};
if (!treeSet.isEmpty()) {
int[] floor = treeSet.floor(curr);
int[] ceiling = treeSet.ceiling(curr);
if (floor != null && floor[1] > curr[0]) return false;
if (ceiling != null && ceiling[0] < curr[1]) return false;
}
treeSet.add(curr);
return true;
}
}

12/27/2018
LeetCode 840 Magic Squares in Grid

Problem

⭐️⭐️

Magic Squares in Grid

Read More

12/27/2018
LeetCode 775 Global and Local Inversions

Problem

⭐️⭐️⭐️

说有[0, N - 1]个distinct的数在一个数组里位置被打乱了. Global inversions就是对于任意i, j, 满足i < j && A[i] > A[j]. Local inversions就是对于任意i, A[i] > A[i + 1].

问Global inversions的数量和local inversions的数量是否一样.

Read More

12/27/2018
LeetCode 135 Candy

Problem

⭐️⭐️⭐️

每个人至少有一颗糖, 相邻两个小朋友rating高的有更多的糖.

Read More