byu_rself

LC.P1335[工作计划的最低难度] 方法一：动态规划+记忆化搜索123456789101112131415161718192021222324252627282930313233343536class Solution { int[] jobDifficulty; int[][] cache; public int minDifficulty(int[] jobDifficulty, int d) { int n = jobDifficulty.length; if (n < d) return -1; this.jobDifficulty = jobDifficulty; this.cache = new int[d][n]; for (int i = 0; i < d; ++i) { Arrays.fill(cache[i], -1); } return dfs(d - 1, n - 1); ...

LC.P1044[最长重复子串] 方法一：字符串哈希+二分12345678910111213141516171819202122232425262728293031323334353637class Solution { static final int hash = 1313131; long[] h, p; int n; public String longestDupSubstring(String s) { n = s.length(); h = new long[n + 1]; // 哈希数组 p = new long[n + 1]; // 次方数组 p[0] = 1; for (int i = 1; i <= n; ++i) { p[i] = p[i - 1] * hash; h[i] = h[i - 1] * hash + s.charAt(i - 1); } S ...

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