飘儿斯朵瑞吉

Posted on Edited on In Disqus: 0 Comments

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

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;
}