飘儿斯朵瑞吉

Posted on | Edited on | In | | Views:
Symbols count in article: 6.9k | Reading time ≈ 7 mins.

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

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