August

08-30 按权重随机选择

🧩 二分

class Solution {

    int[] pre;
    int total;

    public Solution(int[] w) {
        int n = w.length;
        pre = new int[n];
        pre[0] = w[0];
        for (int i = 1; i < n; ++ i) {
            pre[i] = pre[i - 1] + w[i];
        }
        total = Arrays.stream(w).sum();
    }

    public int pickIndex() {
        int x = (int)(Math.random() * total) + 1;
        return binarySearch(x);
    }

    private int binarySearch(int x) {
        int i = 0, j = pre.length - 1;
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (pre[mid] < x) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        return i;
    }
}

08-29 所有奇数长度子数组的和

🧩 前缀和

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        for (int i = 1; i <= n; ++ i) {
            pre[i] = pre[i - 1] + arr[i - 1];
        }
        int ans = 0;
        for (int i = 1; i <= n; i += 2) {
            for (int j = i; j <= n; ++ j) {
                ans += pre[j] - pre[j - i];
            }
        }
        return ans;
    }
}

⚡ 计算一个数字在多少个奇数长度的数组中出现过

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int len = arr.length;
        int n;
        int sum = 0;
        int leftOdd, leftEven, rightOdd, rightEven;

        for (int i = 0; i < len; ++i) {
            leftOdd = (i + 1) / 2;
            leftEven = (i + 2) / 2;
            rightOdd = (len - i) / 2;
            rightEven =  (len - i + 1) / 2;
            n = leftEven*rightEven + leftOdd*rightOdd;
            sum += arr[i] * n;
        }
        return sum;
    }
}

08-28 一维数组的动态和

🧩 求前缀和

class Solution {
    public int[] runningSum(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; ++ i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

08-27 数据流的中位数⭐

🧩 双堆

class MedianFinder {
    Queue<Integer> q1;
    Queue<Integer> q2;

    /** initialize your data structure here. */
    public MedianFinder() {
        q2 = new PriorityQueue<>(); // 小顶堆
        q1 = new PriorityQueue<>((x, y) -> y - x); // 大顶堆
    }

    public void addNum(int num) {
        if (q1.size() > q2.size()) {
            q1.offer(num);
            q2.offer(q1.poll());
        } else {
            q2.offer(num);
            q1.offer(q2.poll());
        }
    }

    public double findMedian() {
        if (q1.size() == q2.size()) {
            return (double)(q1.peek() + q2.peek()) / 2;
        } else {
            return (double)q1.peek();
        }
    }
}

08-24 K站中转内最便宜的航班⭐⭐

🧩 Bellman Ford

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = 10000 * 101 + 1;
        // f[i][j] 表示从src出发经过i次中转到达j的最小代价
        int[][] f = new int[k + 2][n];
        for (int i = 0; i <= k + 1; ++ i) {
            Arrays.fill(f[i], INF);
        }

        // 核心
        f[0][src] = 0;
        for (int t = 1; t < k + 2; ++ t) {
            for (int[] flight : flights) {
                int i = flight[0], j = flight[1], cost = flight[2];
                f[t][j] = Math.min(f[t][j], f[t - 1][i] + cost);
            }
        }

        // 遍历求最小值
        int ans = INF;
        for (int t = 0; t < k + 2; ++ t) {
            ans = Math.min(ans, f[t][dst]);
        }
        return ans == INF ? -1 : ans; 
    }
}

08-23 获取生成数组中的最大值

🧩 模拟

class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0) return 0;

        int[] nums = new int[n + 1];
        nums[1] = 1;
        for (int i = 2; i <= n; ++ i) {
            nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
        }
        return Arrays.stream(nums).max().getAsInt();
    }
}

08-22 逃脱阻碍者⭐

🧩 曼哈顿距离

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int[] source = {0, 0};
        int distance = manhattanDistance(source, target);

        for (int[] ghost : ghosts) {
            int ghostDistance = manhattanDistance(ghost, target);
            if (ghostDistance <= distance) return false;
        }
        return true;
    }

    // 求曼哈顿距离
    // dist(A,B) 表示 A 点和 B 点的曼哈顿距离，曼哈顿距离的计算方法如下：
    // dist(A,B)= ∣xA − xB∣+∣yA − yB∣
    private int manhattanDistance(int[] point1, int[] point2) {
        return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
    }
}

08-21 压缩字符串

🧩 前后双指针

class Solution {
    public int compress(char[] chars) {
        int n = chars.length;
        int left = 0, write = 0;
        for (int read = 0; read < n; ++ read) {
            if (read == n - 1 || chars[read] != chars[read + 1]) {
                chars[write] = chars[read];
                ++ write;

                int num = read - left + 1;
                if (num > 1) {
                    int start = write;
                    while (num > 0) {
                        chars[write++] = (char)(num % 10 + '0');
                        num /= 10;
                    }
                    reverse(chars, start, write - 1);
                }
                left = read + 1;
            }
        }
        return write;
    }

    // 翻转字符串
    private void reverse (char[] chars, int left, int right) {
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            ++ left;
            -- right;
        }
    }
}

08-20 反转字符串 II

class Solution {
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int k_2 = 2 * k;
        for (int i = 0; i < n; i += k_2) {
            int j = i + k - 1;
            if (j < n) reverse(chars, i, j);
            else reverse(chars, i, n - 1);
        }
        return new String(chars);
    }

    private void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            ++ left;
            -- right;
        }
    }
}

08-19 反转字符串中的元音字母

🧩 双指针

class Solution {
    Set<Character> vowels = new HashSet<Character>(){{
        add('a');
        add('A');
        add('e');
        add('E');
        add('i');
        add('I');
        add('o');
        add('O');
        add('u');
        add('U');
    }};

    public String reverseVowels(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int i = 0, j = n - 1;
        while (i < j) {
            while (i < j && !vowels.contains(chars[i])) ++ i;
            while (i < j && !vowels.contains(chars[j])) -- j;
            char tmp = chars[i];
            chars[i] = chars[j];
            chars[j] = tmp;
            ++ i;
            -- j;
        }
        return new String(chars);
    }
}

08-17 学生出勤记录 I

class Solution {
    public boolean checkRecord(String s) {
        int timeA = 0, timeL = 0;
        for (char c : s.toCharArray()) {
            if (c == 'A') ++ timeA;
            if (c == 'L') ++ timeL;
            else timeL = 0;
            if (timeA >= 2) return false;
            if (timeL >= 3) return false;
        }
        return true;
    }
}

08-03 最短无序连续子数组

🧩 排序+双指针 O(nlogn)

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        System.arraycopy(nums, 0, arr, 0, n);
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) ++ i;
        while (j >= i && nums[j] == arr[j]) -- j;
        return j + 1 - i;
    }
}

🧩 双指针+线性扫描 O(n)

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) ++ i;
        while (j > i && nums[j] >= nums[j - 1]) -- j;
        if (i == j) return 0;

        int min = nums[i], max = nums[j];
        int l = i, r = j;
        for (int u = l; u <= r; ++ u) {
            if (nums[u] < min) {
                while (i >= 0 && nums[u] < nums[i]) -- i;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while (j < n && nums[u] > nums[j]) ++ j;
                max = j < n ? nums[j] : MAX;
            }
        }
        return j - i - 1; // (j - 1) - (i + 1) + 1
    }
}

08-02 网络延迟时间⭐⭐

🧩 Dijkstra算法

class Solution {
    private final int INF = Integer.MAX_VALUE / 2;
    public int networkDelayTime(int[][] times, int n, int k) {
        // 预处理
        int[][] g = new int[n][n];
        for (int i = 0; i < n; ++ i) {
            Arrays.fill(g[i], INF);
        }
        for (int[] t : times) {
            int x = t[0] - 1, y = t[1] - 1;
            g[x][y] = t[2];
        }

        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        // 起点
        dist[k - 1] = 0;
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; ++ i) {
            int x = -1;
            // 找出当前距离起始点的最短距离点
            for (int y = 0; y < n; ++ y) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            used[x] = true;
            // 使用找到的最短距离点更新其他点
            for (int y = 0; y < n; ++ y) {
                dist[y] = Math.min(dist[y], g[x][y] + dist[x]);
            }
        }
        // 遍历距离dist数组找到最大值
        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;
    }
}

08-01 矩阵中战斗力最弱的 K 行

🧩 二分 + 优先队列

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
            if (x[1] == y[1]) return x[0] - y[0];
            return x[1] - y[1];
        });
        // 二分获取每行战斗力并插入小根堆
        int n = mat.length, m = mat[0].length;
        for (int i = 0; i < n; ++ i) {
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (mat[i][mid] == 0) r = mid - 1;
                else l = mid;
            }
            if (mat[i][l] == 0) l = -1;
            pq.offer(new int[]{i, l + 1});
        }
        // 小根堆中获取结果
        int[] ans = new int[k];
        for (int i = 0; i < k; ++ i) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}