byu_rself

性质 Trie的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie的形状都是唯一的。 查找或插入一个长度为L的单词，访问next数组的次数最多为L+1，和Trie中包含多少个单词无关。 Trie的每个结点中都保留着一个字母表，这是很耗费空间的。如果Trie的高度为n，字母表的大小为m，最坏的情况是Trie中还不存在前缀相同的单词，那空间复杂度就为$O(m^n)$ 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445class Trie { Trie[] next; boolean isEnd; public Trie() { next = new Trie[26]; isEnd = false; } // 从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符 ...

LC.P1016[子串能表示从1到N数字的二进制串] 方法一：暴力12345678class Solution { public boolean queryString(String s, int n) { for (int i = 1; i <= n; ++i) { if (!s.contains(Integer.toBinaryString(i))) return false; } return true; }} 时间复杂度：$O(min(m,n) \times mlogmin(m,n))$，其中$m$为s的长度。 空间复杂度：$O(logn)$ 方法二：数学+滑动窗口12345678910111213141516171819202122class Solution { public boolean queryString(String s, int n) { if (n == 1) return ...

LC.P648[单词替换] 方法一：字典树1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { public String replaceWords(List<String> dictionary, String sentence) { Trie trie = new Trie(); for (String s : dictionary) trie.insert(s); StringBuilder builder = new StringBuilder(); for (String word : sentence.split(" ")) { builder.append(trie.query(word)).append(" "); } return ...

LC.P208[实现Trie(前缀树)] 性质： Trie的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie的形状都是唯一的。 查找或插入一个长度为L的单词，访问next数组的次数最多为L+1，和Trie中包含多少个单词无关。 Trie的每个结点中都保留着一个字母表，这是很耗费空间的。如果Trie的高度为n，字母表的大小为m，最坏的情况是Trie中还不存在前缀相同的单词，那空间复杂度就为$O(m^n)$ 123456789101112131415161718192021222324252627282930313233343536373839404142434445class Trie { Trie[] next; boolean isEnd; public Trie() { next = new Trie[26]; isEnd = false; } // 从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的 ...

LC.P1015[可被K整除的最小整数] 方法一：Set遍历1234567891011121314class Solution { public int smallestRepunitDivByK(int k) { if (k % 2 == 0 || k % 5 == 0) return -1; int x = 1 % k, cnt = 1; Set<Integer> set = new HashSet<>(); while (x > 0) { x = (x * 10 + 1) % k; if (set.contains(x)) return -1; set.add(x); ++cnt; } return cnt; }} 时间复杂度：$O(k)$ 空间复杂度：$O(k)$ 方法二：数学12345678910cl ...

LC.P2034[股票价格波动] 方法一：哈希表+有序集合123456789101112131415161718192021222324252627282930313233343536373839404142434445class StockPrice { int cur; Map<Integer, Integer> timePriceMap; // key: timestamp value: price TreeMap<Integer, Integer> priceTimeCntMap; // key: price value: 时间戳数量 public StockPrice() { cur = 0; timePriceMap = new HashMap<>(); priceTimeCntMap = new TreeMap<>(); } public void update(int timestamp, int price ...

LC.P1606[找到处理最多请求的服务器] 方法一：有序集合+优先队列12345678910111213141516171819202122232425class Solution { public List<Integer> busiestServers(int k, int[] arrival, int[] load) { int n = arrival.length, max = 0; int[] cnt = new int[k]; TreeSet<Integer> available = new TreeSet<>(); for (int i = 0; i < k; ++i) available.add(i); PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]); for (int i = 0; i < n; ...

LC.P2437[有效时间的数目] 方法一：乘法原理12345678910111213141516class Solution { public int countTime(String time) { return count(time.substring(0, 2), 24) * count(time.substring(3, 5), 60); } private int count(String time, int x) { int ans = 0; char[] s = time.toCharArray(); for (int i = 0; i < x; ++i) { if ((s[0] == '?' || i / 10 == s[0] - '0') && (s[1] == '?' || i % 10 == s[1] - '0')) ...

LC.P857[雇佣K名工人的最低成本] 方法一：优先队列(大根堆)123456789101112131415161718192021222324252627class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length, sum = 0; Integer[] index = IntStream.range(0, n).boxed().toArray(Integer[]::new); // 等价于 // Integer[] index = new Integer[n]; // for (int i = 0; i < n; ++i) index[i] = i; // 定义 ri = wage[i] / quality[i] Arrays.sort(index, (a, b) -> wage[a] * ...

LC.P1263[推箱子] 方法一：BFS+双端队列1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556class Solution { int m, n; char[][] grid; static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; public int minPushBox(char[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int si = 0, sj = 0, bi = 0, bj = 0; for (int i = 0; i < ...