飘儿斯朵瑞吉

迎难而上,祝我好运。面朝大海,春暖花开。

valid square

  • 给二维平面上的四个点,判断能否组成正方形。lc593
  • 对于这些点计算两两之间的距离,如果最大的长度出现两次且剩余的4个长度都相等,则可以构成正方形。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
long[] distances = new long[] {getDistance(p1, p2),
getDistance(p1, p3),
getDistance(p1, p4),
getDistance(p2, p3),
getDistance(p2, p4),
getDistance(p3, p4)};
Map<Long, Integer> map = new HashMap<>();
long max = 0l;
long min = Long.MAX_VALUE;
for (long d : distances) {
map.put(d, map.getOrDefault(d, 0) + 1);
max = Math.max(max, d);
min = Math.min(min, d);
}
return map.get(max) == 2 && map.get(min) == 4 && map.size() == 2
&& 2 * min == max; // !!!
}
private long getDistance(int[] p1, int[] p2) {
int xDiff = Math.abs(p1[0] - p2[0]);
int yDiff = Math.abs(p1[1] - p2[1]);
return (long)xDiff * xDiff + (long)yDiff * yDiff;
}
  • follow-up: 给一大堆点,求总共可以组成多少个正方形。
  • 暴力法,四重循环固定四个点,然后调用上面的函数判断是否组成一个正方形。
  • 优化1:先把所有坐标存入Set,然后双重循环固定两个点作为一个边,然后求对边的那两个点(注意两侧都有可能),看是否都在set中,是则可以组成一个正方形。去重直接除以2.
  • 优化2:可以将两个点作为对角线来找另外两个点。

CallBack Eventfire

  • 给一个Event类,它可能会fire。Event对象中可以register一些callback,当Event执行fire的时候,所有这些callback都需要依次执行,之后再register的callback就直接执行。先实现一个单线程的版本。
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 Callback {
...
public void run();
}

class EventSystem {
public boolean fired = false;
private Queue<Callback> queue;
public EventSystem() {
queue = new LinkedList<>();
}

public void register(Callback cb) {
if (fired) {
cb.run();
} else {
queue.offer(cb);
}
}

public void fire() {
while (!queue.empty()) {
Callback cb = queue.poll();
cb.run();
}
fired = true;
}
}
  • 如何实现一个加锁机制保证执行的atomicity. 首先看看上面的register。如果在执行check fired之后,Event突然fire了,那当前这个cb还是会进入queue,那就永远不会执行了。因此考虑给register加锁,同时对fire也加锁,保证只有拿到锁才能执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void register(callback_t cb) {
lock.acquire();
if (fired) {
cb.run();
} else {
queue.add(cb);
}
lock.release();
}
public void fire() {
lock.acquire();
while (!queue.empty()) {
Callback cb = queue.poll();
cb.run();
}
fired = true;
lock.release();
}
  • 但是上面这个可能效率比较差,因为run可能得执行很久,这样别的线程一直要等待锁。必须保证检查是否fired这个判断不被抢占,同时在run之前就释放掉。而加入queue的操作则必须收到锁的保护,不能还没加进去就已经fire了,那之后又永远执行不了了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void register(callback_t cb) {
lock.acquire();
if (fired) {
lock.release();
cb.run();
} else {
queue.add(cb);
lock.release();
}
}

public void fire() {
lock.acquire();
while (!queue.empty()) {
Callback cb = queue.poll();
lock.release();
cb.run();
lock.acquire();
}
fired = true;
lock.release();
}

happy number

  • 朴素做法,直接严格按照定义来做。可能需要证明的是为什么这些数字最终会回到一个较小的范围内(单调递减性)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isHappy(int n) {
int r = 0, sum = 0;
if (n == 1 || n == 7) {
return true;
} else if (n < 10) {
return false;
} else {
while (n != 0) {
r = n % 10;
sum += r * r;
n /= 10;
}
}
return isHappy(sum);
}
  • 最终所有的non-happy都会进入一个环,因此考虑使用快慢指针判断环的做法,一旦有环就直接返回false了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isHappy(int n) {
int slow, fast;
slow = fast = n;
while (true) {
slow = digitSquareSum(slow);
fast = digitSquareSum(fast);
fast = digitSquareSum(fast);
if (fast == 1)
return true;
if (slow == fast)
return false;
}
}

public int digitSquareSum(int n) {
int sum = 0, tmp;
while (n != 0) {
tmp = n % 10;
sum += tmp * tmp;
n /= 10;
}
return sum;
}

画圆

  • 给一个半径,以原点为圆心,返回所有圆上的点的坐标(近似),这些坐标都是整数。类似于在电脑屏幕的pixel上显示一个完整的圆。
  • 基本方法:通过循环以半径正方形,产生所有点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static List<int[]> drawCircle(int r) {
List<int[]> list = new ArrayList<>();
int l = -r;
int u = r;
for (int i = l; i <= u; i++) {
for (int j = u; j >= l; j--) {
int diff = i * i + j * j - r * r;
if (diff ) {
list.add(new int[] { i, j });
}
}
}
return list;
}
  • 注意到圆的对称性,因此可以只研究1/8个圆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static List<int[]> drawCircle(int r) {
List<int[]> list = new ArrayList<>();
double end = r / 0.141;
int y = r;
for (int x = 0; x <= end; x++) {
int diff = x * x + y * y - r * r;
if (diff )
}
return list;
}
private static void addPoints(int x, int y, List<int[]> list) {
list.add(new int[] {x, y});
list.add(new int[] {-x, y});
list.add(new int[] {x, -y});
list.add(new int[] {-x, -y});

list.add(new int[] {y, x});
list.add(new int[] {-y, x});
list.add(new int[] {y, -x});
list.add(new int[] {-y, -x});
}

实现O(1) Set

  • 实现一个只含有1~N的integer set,支持add, remove, contains, clear, iterate.
  • 方法一:直接使用bucket数组,add, remove, contains都是O(1),但是clear和iterate都是O(N)
  • 方法二:使用类似于sequential的数组,即元素按照插入顺序append,add就直接O(1)插到结尾即可,remove, contains都需要线性搜索找到对应位置O(count),clear就直接把链表头设置为空即可O(1),iterate则是O(count).
  • follow-up: 如何实现add, remove, contains, clear全O(1),iterate O(count)?
  • sequential数组作为主体,每当add一个元素,就把当前count作为该元素的索引存入bucket数组。例如插入顺序是[2,0,1],在bucket中就存放插入的这些元素的索引[1,2,0]. remove时在bucket中拎出这个元素的索引,在sequential数组就可以直接访问到,此时可以直接将该元素和末尾元素swap,然后将长度缩小,同时在bucket中也对应修改一下索引即可。contains则是直接通过bucket看看存放的索引是否valid(可以用负数标记为invalid)。clear则是直接将长度设为0,那么之后再add就又会从0开始append到sequential数组了。iterate则是遍历sequential即可。

计算parlindrone数

  • 给一个String,求其中一共包含多少个回文子串。
  • 类似于lc 647,给一个DP做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int checkSequence(String S) {
if (S == null || S.length() == 0) {
return 0;
}
int len = S.length(), count = 0;
boolean[][] dp = new boolean[len][len];
for (int right = 0; right < len; right++) {
dp[right][right] = true;
count++;
for (int left = right - 1; left >= 0; left--) {
if (S.charAt(left) == S.charAt(right) && (left + 1 == right || dp[left + 1][right - 1])) {
dp[left][right] = true;
count++;
}
}
}
return count;
}