byu_rself

LC.P1072[按列翻转得到最大值等行数] 方法一：哈希表123456789101112131415class Solution { public int maxEqualRowsAfterFlips(int[][] matrix) { int ans = 0, n = matrix[0].length; Map<String, Integer> map = new HashMap<>(); for (int[] row : matrix) { char[] s = new char[n]; for (int i = 0; i < n; ++i) { // 将以1开头的行翻转 s[i] = (char) (row[0] ^ row[i]); } ans = Math.max(ans, map.merge(Stri ...

LC.面试题01.09[字符串轮转] 方法一：模拟12345class Solution { public boolean isFlipedString(String s1, String s2) { return s1.length() == s2.length() && (s1 + s1).contains(s2); }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$

LC.P187[重复的DNA序列] 方法一：滑动窗口+哈希表1234567891011class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> ans = new ArrayList<>(); Map<String, Integer> map = new HashMap<>(); for (int i = 0; i + 10 <= s.length(); ++i) { String cur = s.substring(i, i + 10); if (map.merge(cur, 1, Integer::sum) == 2) ans.add(cur); } return ans; }} 时间复杂度：每次检查以s[i]为结尾 ...

LC.P1054[距离相等的条形码] 方法一：计数+排序1234567891011121314151617181920class Solution { public int[] rearrangeBarcodes(int[] barcodes) { int n = barcodes.length; int max = Arrays.stream(barcodes).max().getAsInt(); Integer[] index = new Integer[n]; for (int i = 0; i < n; ++i) { index[i] = barcodes[i]; } int[] cnt = new int[max + 1]; for (int x : barcodes) ++cnt[x]; Arrays.sort(index, (a, b) -> cnt[a] == cnt[b] ? a ...

LinuxLinux基础命令pwd 功能：显示用户当前所在的目录 格式：pwd ls 功能：对于目录，该命令列出该目录下的所有子目录与文件。对于文件，将列出文件名以及其他信息 格式：ls [选项][目录或文件] 常用选项表： 选项 说明 -a 查看当前目录下的文件，包括隐藏文件 -l 长格式显示文件 -lh 以方便阅读的长格式显示 cd功能：改变工作目录。将当前工作目录改变到指定的目录下 格式：cd 目录名 常用命令： 命令 说明 cd ../ 返回上一级目录 cd ~ 切换到家目录 cd / 切换到根目录 man 功能：Linux的命令有很多参数，我们不可能全记住，我们可以通过查看联机手册获取帮助。访问Linux手册页的命令是man 格式：man 其他命令 grep 功能：用于查找文件里符合条件的字符串 格式：grep [选项] '查找字符串' 文件名 选项 说明 -a 将binary文件以text文件的方式查找数据 -c 计算找到 ‘查找字符串’ 的次数 -i 忽略大小写 ...

LC.P2441[与对应负数同时存在的最大正整数] 方法一：哈希表1234567891011class Solution { public int findMaxK(int[] nums) { Set<Integer> set = new HashSet<>(); int ans = -1; for (int num : nums) set.add(num); for (int x : set) { if (set.contains(-x)) ans = Math.max(ans, x); } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$

LC.P380[O(1)时间插入、删除和获取随机元素] 方法一：Map+List12345678910111213141516171819202122232425262728293031323334353637383940414243class RandomizedSet { Map<Integer, Integer> map; List<Integer> list; Random random; public RandomizedSet() { map = new HashMap<>(); list = new ArrayList<>(); random = new Random(); } public boolean insert(int val) { if (map.containsKey(val)) return false; map.put(val, list.size()); ...

LC.P1330[翻转子数组得到最大的数组值] 方法一：数学123456789101112131415class Solution { public int maxValueAfterReverse(int[] nums) { int ans = 0, d = 0, n = nums.length; int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int i = 1; i < n; ++i) { int a = nums[i - 1], b = nums[i]; int dab = Math.abs(a - b); ans += dab; max = Math.max(max, Math.min(a, b)); min = Math.min(min, Math.max(a, b)); d = Math.m ...

性质 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 ...