Posts

Clash 规则配置 编辑规则 增加规则： 1 2 3 4 rules: - 'DOMAIN-KEYWORD,aliyuncs,DIRECT' - 'DOMAIN-SUFFIX,bilibili.com,DIRECT' - 'DOMAIN-KEYWORD,aliyuncs,DIRECT'

合并区间 解题思路 按照左端点排序 维护一个当前正在合并的区间 依次扫描所有区间 Java 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 Solution { public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0) { return new int[0][2]; } Arrays.sort(intervals, (a, b) -> { if (a[0] != b[0]) return Integer.compare(a[0], b[0]); return Integer.compare(a[1], b[1]); }); List<int[]> res = new ArrayList<>(); int start = intervals[0][0], end = intervals[0][1]; for (int i = 1; i < intervals.length; i ++) { int s = intervals[i][0], e = intervals[i][1]; if (s <= end) { end = Math.max(end,e); } else { res.add(new int[]{start, end}); start = s; end = e; } } res.add(new int[]{start, end}); return res.toArray(new int[res.size()][]); } } Python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals: return [] intervals.sort(key=lambda x: (x[0], x[1])) res = [] start, end = intervals[0] for s, e in intervals[1:]: if s <= end: end = max(end, e) else: res.append([start,end]) start, end = s, e res.append([start, end]) return res JS 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 /** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { if (!intervals || intervals.length === 0) { return []; } intervals.sort((a, b) => (a[0] - b[0]) || (a[1] - b[1])); const res = []; let [start, end] = intervals[0]; for (let i = 1; i < intervals.length; i ++) { const [s, e] = intervals[i]; if (s <= end) { end = Math.max(end, e); } else { res.push([start, end]); start = s; end = e; } } res.push([start, end]); return res; }; Go 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 29 func merge(intervals [][]int) [][]int { if len(intervals) == 0 { return [][]int{} } sort.Slice(intervals, func(i, j int) bool { if intervals[i][0] != intervals[j][0] { return intervals[i][0] < intervals[j][0] } return intervals[i][1] < intervals[j][1] }) res := make([][]int, 0, len(intervals)) start, end := intervals[0][0], intervals[0][1] for i := 1; i < len(intervals); i ++ { s, e := intervals[i][0], intervals[i][1] if s <= end { if e > end { end = e } } else { res = append(res, []int{start, end}) start, end = s, e } } res = append(res, []int{start, end}) return res }

思路 用第一行作为列标记，matrix[0][j] == 0 表示第 j 列最终要清零。 用第一列作为行标记，matrix[i][0] == 0 表示第 i 行最终要清零。 第一行、第一列可能原本就包含 0，需要额外保存两个变量标识 Java 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean row0 = false, col0 = false; for (int j = 0; j < n; j ++) { if (matrix[0][j] == 0) { row0 = true; break; } } for (int i = 0; i < m; i ++) { if (matrix[i][0] == 0) { col0 = true; break; } } for (int i = 1; i < m; i ++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m; i ++) { for (int j = 1; j < n; j ++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } if (row0) { for (int j = 0; j < n;j ++) { matrix[0][j] = 0; } } if (col0) { for (int i = 0; i < m;i ++) { matrix[i][0] = 0; } } } }

题目 解题思路 思路 1： 三次反转 右移 k 位等价为：把数组分成两段 A|B ，B 是最后 K 个，结果是 B|A ...

题目 解题思路 设数组长度为 n: 要找的答案一定在 [1, n+1] 里面。 把数组当做一个哈希表，值 x 放在 x - 1 的位置。 ...

题目 不定长滑动窗口 + 计数哈希 右指针扩张窗口，直到覆盖了 t 的全部需求 一旦覆盖成功，左指针尽量收缩，变短 在收缩过程中持续更新最优答案 当收缩到不再满足条件时，再继续右扩 Java 解法 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public String minWindow(String s, String t) { int m = s.length(), n = t.length(); if (n > m) return ""; int[] need = new int[128]; for (int i = 0; i < n; i ++) { need[t.charAt(i)] ++; } int missing = n; int bestLen = Integer.MAX_VALUE; int bestL = 0; int l = 0; for (int r = 0; r < m; r ++) { char c = s.charAt(r); if (need[c] > 0) { missing--; } need[c]--; while(missing == 0) { int len = r - l + 1; if (len < bestLen) { bestLen = len; bestL = l; } char leftChar = s.charAt(l); need[leftChar]++; if (need[leftChar] > 0) { missing ++; } l ++; } } return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen); } } Python 解法 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 29 30 31 32 33 34 35 36 class Solution: def minWindow(self, s: str, t: str) -> str: if len(t) > len(s): return "" need = [0] * 128 for ch in t: need[ord(ch)] += 1 missing = len(t) best_len = float("inf") best_l = 0 l = 0 for r, ch in enumerate(s): idx = ord(ch) if need[idx] > 0: missing -= 1 need[idx] -= 1 while missing == 0: cur_len = r - l + 1 if cur_len < best_len: best_len = cur_len best_l = l left_idx = ord(s[l]) need[left_idx] += 1 if need[left_idx] > 0: missing += 1 l += 1 return "" if best_len == float("inf") else s[best_l: best_l + best_len] JS 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 /** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { if (t.length > s.length) return ""; const need = new Array(128).fill(0); for(let i = 0; i < t.length; i ++) { need[t.charCodeAt(i)] ++; } let missing = t.length; let bestLen = Infinity; let bestL = 0; let l = 0; for (let r = 0; r < s.length; r ++) { const idx = s.charCodeAt(r); if (need[idx] > 0) { missing --; } need[idx]--; while(missing === 0) { const len = r - l + 1; if (len < bestLen) { bestLen = len; bestL = l; } const leftIdx = s.charCodeAt(l); need[leftIdx]++; if (need[leftIdx] > 0) { missing ++; } l++; } } return bestLen === Infinity ? "" : s.slice(bestL, bestL + bestLen); }; Go 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 29 30 31 32 33 34 35 36 37 38 39 40 41 func minWindow(s string, t string) string { if len(t) > len(s) { return "" } need := make([]int, 128) for i:=0; i < len(t); i ++ { need[t[i]] ++ } missing := len(t) bestLen := 1<<30 bestL := 0 l := 0 for r := 0; r < len(s); r++ { c := s[r] if need[c] > 0 { missing-- } need[c]-- for missing == 0 { if r-l+1 < bestLen { bestLen = r-l+1 bestL = l } left := s[l] need[left]++ if need[left] > 0 { missing ++ } l++ } } if bestLen == 1 << 30 { return "" } return s[bestL : bestL + bestLen] }

mindmap

基础用法 uv 安装包

牛车水 交通方式： 地铁紫线 NE Line - Chinatown站 峇峇娘惹海南鸡饭I娘惹菜 白切甘榜海南鸡 ...