二元搜尋法老是不熟
今天看到了篇 大補貼文章
https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1

啊～9/20了 google還沒給我確定時間的邀約信～ＨＲ妳還活著嗎Q__Q

Maximum Length of Repeated Subarray

Q: https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/

/**
    dp[x][y]: nums1 x index & nums2 y index max length
    dp[x-1][y-1] = dp[x][y] + (nums1[x-1] == nums[y-1]);
 */
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int ans = 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = nums1.length - 1; i >= 0; i--) {
            for (int j = nums2.length - 1; j >= 0; j--) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i+1][j+1] + 1;
                    if (ans < dp[i][j]) {
                        ans = dp[i][j];
                    }
                }
            }
        }
        return ans;
    }
}

Race Car

Q: https://leetcode.com/problems/race-car/
沒啥想法 先暴力解

class Solution {

    public int racecar(int target) {
        // int[0]: position, int[1]: speed
        Queue<int[]> q = new LinkedList<>();
        int step = 0;
        Set<int[]> visited = new HashSet<>();
        q.offer(new int[] {0, 1});
        while(true) {
            List<int[]> states = new ArrayList<>();
            while(!q.isEmpty()) {
                states.add(q.poll());
            }
            boolean reached = false;
            for (int[] state : states) {
                visited.add(state);
                int position = state[0];
                int speed = state[1];
                if (position == target) {
                    reached = true;
                } 
                // A status
                int[] stateA = new int[]{ position + speed, speed * 2};
                if (!visited.contains(stateA)) {
                    q.offer(stateA);
                }
                if (speed > 0) {
                    int[] stateB = new int[]{position, -1};
                    if (!visited.contains(stateB)) {
                        q.offer(stateB);
                    }
                } else {
                    int[] stateB = new int[]{position, 1};
                    if (!visited.contains(stateB)) {
                        q.offer(stateB);
                    }
                }
            }
            if (reached) {
                break;
            }
            step++;
        }
        return step;
    }
}

恩 time limit了==

看了下解答
可以用Djks配合2指數bits的方式實作 真神奇

class Solution {
    public int racecar(int target) {
        int K = 33 - Integer.numberOfLeadingZeros(target - 1);
        int barrier = 1 << K;
        int[] dist = new int[2 * barrier + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[target] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<Node>(
            (a, b) -> a.steps - b.steps);
        pq.offer(new Node(0, target));

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int steps = node.steps, targ1 = node.target;
            if (dist[Math.floorMod(targ1, dist.length)] > steps) continue;

            for (int k = 0; k <= K; ++k) {
                int walk = (1 << k) - 1;
                int targ2 = walk - targ1;
                int steps2 = steps + k + (targ2 != 0 ? 1 : 0);

                if (Math.abs(targ2) <= barrier && steps2 < dist[Math.floorMod(targ2, dist.length)]) {
                    pq.offer(new Node(steps2, targ2));
                    dist[Math.floorMod(targ2, dist.length)] = steps2;
                }
            }
        }

        return dist[0];
    }
}

class Node {
    int steps, target;
    Node(int s, int t) {
        steps = s;
        target = t;
    }
}