飘儿斯朵瑞吉
迎难而上,祝我好运。面朝大海,春暖花开。
valid square
- 给二维平面上的四个点,判断能否组成正方形。lc593
- 对于这些点计算两两之间的距离,如果最大的长度出现两次且剩余的4个长度都相等,则可以构成正方形。
1 | public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) { |
- follow-up: 给一大堆点,求总共可以组成多少个正方形。
- 暴力法,四重循环固定四个点,然后调用上面的函数判断是否组成一个正方形。
- 优化1:先把所有坐标存入Set,然后双重循环固定两个点作为一个边,然后求对边的那两个点(注意两侧都有可能),看是否都在set中,是则可以组成一个正方形。去重直接除以2.
- 优化2:可以将两个点作为对角线来找另外两个点。
CallBack Eventfire
- 给一个Event类,它可能会fire。Event对象中可以register一些callback,当Event执行fire的时候,所有这些callback都需要依次执行,之后再register的callback就直接执行。先实现一个单线程的版本。
1 | class Callback { |
- 如何实现一个加锁机制保证执行的atomicity. 首先看看上面的register。如果在执行check fired之后,Event突然fire了,那当前这个cb还是会进入queue,那就永远不会执行了。因此考虑给register加锁,同时对fire也加锁,保证只有拿到锁才能执行。
1 | public void register(callback_t cb) { |
- 但是上面这个可能效率比较差,因为run可能得执行很久,这样别的线程一直要等待锁。必须保证检查是否fired这个判断不被抢占,同时在run之前就释放掉。而加入queue的操作则必须收到锁的保护,不能还没加进去就已经fire了,那之后又永远执行不了了。
1 | public void register(callback_t cb) { |
happy number
- 朴素做法,直接严格按照定义来做。可能需要证明的是为什么这些数字最终会回到一个较小的范围内(单调递减性)。
1 | public boolean isHappy(int n) { |
- 最终所有的non-happy都会进入一个环,因此考虑使用快慢指针判断环的做法,一旦有环就直接返回false了。
1 | public boolean isHappy(int n) { |
画圆
- 给一个半径,以原点为圆心,返回所有圆上的点的坐标(近似),这些坐标都是整数。类似于在电脑屏幕的pixel上显示一个完整的圆。
- 基本方法:通过循环以半径正方形,产生所有点。
1 | private static List<int[]> drawCircle(int r) { |
- 注意到圆的对称性,因此可以只研究1/8个圆
1 | private static List<int[]> drawCircle(int r) { |
实现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 | public int checkSequence(String S) { |