快照数组与时间戳（版本控制设计）

快照数组（LeetCode 1146）

class SnapshotArray {
    private List<int[]>[] arr;   // arr[idx] = [(snap_id, val), ...]
    private int snapId = 0;

    @SuppressWarnings("unchecked")
    public SnapshotArray(int length) {
        arr = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            arr[i] = new ArrayList<>();
            arr[i].add(new int[]{0, 0});   // 初始值 0 in snap 0
        }
    }

    public void set(int index, int val) {
        List<int[]> list = arr[index];
        if (list.getLast()[0] == snapId) {
            list.getLast()[1] = val;    // 同一个 snap 更新
        } else {
            list.add(new int[]{snapId, val});
        }
    }

    public int snap() { return snapId++; }

    public int get(int index, int snapId) {
        List<int[]> list = arr[index];
        // 二分找最后一个 snap_id <= snapId 的记录
        int lo = 0, hi = list.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (list.get(mid)[0] <= snapId) lo = mid;
            else hi = mid - 1;
        }
        return list.get(lo)[1];
    }
}

思路：稀疏存储（只记录变化的时刻），查询时二分找最接近的历史版本。

基于时间的键值存储（LeetCode 981）

class TimeMap {
    private Map<String, List<int[]>> map = new HashMap<>();
    // 每个 key -> [(timestamp, value), ...] 按时间有序

    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>())
           .add(new int[]{timestamp, value.hashCode()});
        // 注意：实际存 value 字符串
    }

    // 简化版：直接存字符串
    private Map<String, TreeMap<Integer, String>> store = new HashMap<>();

    public void set2(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) return "";
        Map.Entry<Integer, String> entry = store.get(key).floorEntry(timestamp);
        return entry == null ? "" : entry.getValue();
    }
}

floorEntry(timestamp) 找到 <= timestamp 的最大 key，正是"最近的设置"。

版本控制设计（Git 简化版）

支持 checkout(version) 和 commit 的版本控制系统。

class VersionControl {
    private int currentVersion;
    private Map<Integer, int[]> versions = new HashMap<>();

    // 二分搜索找最早的 bad version
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    boolean isBadVersion(int v) { /* API */ return false; }
}

设计地下城（LeetCode 174）

DP：从右下角往左上方推导所需最低初始血量。

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length, n = dungeon[0].length;
    int[][] dp = new int[m][n];  // dp[i][j] = 到达(i,j)所需最低血量
    dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);
    for (int i = m - 2; i >= 0; i--)
        dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);
    for (int j = n - 2; j >= 0; j--)
        dp[m-1][j] = Math.max(1, dp[m-1][j+1] - dungeon[m-1][j]);
    for (int i = m - 2; i >= 0; i--)
        for (int j = n - 2; j >= 0; j--) {
            int need = Math.min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = Math.max(1, need - dungeon[i][j]);
        }
    return dp[0][0];
}