byu_rself

LC.P1143[最长公共子序列] 方法一：动态规划12345678910111213141516class Solution { public int longestCommonSubsequence(String text1, String text2) { int n = text1.length(), m = text2.length(); int[][] f = new int[n + 1][m + 1]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { f[i][j] = f[i - 1][j - 1] + 1; } else { ...

LC.P1035[不相交的线] 方法一：动态规划12345678910111213141516class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int n = nums1.length, m = nums2.length; int[][] f = new int[n + 1][m + 1]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i ...

LC.P1156[单字符重复子串的最大长度] 方法一：滑动窗口1234567891011121314151617181920212223242526272829class Solution { public int maxRepOpt1(String text) { Map<Character, Integer> map = new HashMap<>(); int n = text.length(); // 统计各字符出现的次数 for (int i = 0; i < n; ++i) { char c = text.charAt(i); map.merge(c, 1, Integer::sum); } int ans = 0; for (int i = 0; i < n; ) { int j = i; whil ...

在实际项目中，经常会遇到需要封装多级树形结构对象的场景，现将主要过程记录一下。 总体思路 首先获取所有的根节点（顶级节点），即查询parentId = 0的节点。 通过getChildren()方法，封装每个根节点的子节点 递归调用getChildren()方法，逐层封装子节点 若有排序字段，则根据实际场景进行排序 返回结果 Java实体类123456789101112131415161718192021222324252627/** * 节点对象 */@Datapublic class Nodes { /** * 节点id */ private Long id; /** * 标题 */ private String title; /** * 父节点id */ private Long parentId; /** * 排序 */ private Integer sort; /** * 子节点 */ @ApiModelProperty(value = "子节点") private List&l ...

LC.P978[最长湍流子数组] 方法一：动态规划123456789101112131415class Solution { public int maxTurbulenceSize(int[] arr) { int n = arr.length, ans = 1; // f[i][j]表示以i结尾，且结尾状态为j的最长湍流子数组长度(0：上升,1：下降) int[][] f = new int[n][2]; f[0][0] = f[0][1] = 1; for (int i = 1; i < n; ++i) { f[i][0] = f[i][1] = 1; if (arr[i - 1] < arr[i]) f[i][0] = f[i - 1][1] + 1; // 上升 else if (arr[i - 1] > arr[i]) f[i][1] = f[i - 1][0] + 1; // 下降 ...

LC.P740[删除并获得点数] 方法一：动态规划(将问题转化为打家劫舍)12345678910111213141516class Solution { public int deleteAndEarn(int[] nums) { int max = Arrays.stream(nums).max().getAsInt(); int[] sum = new int[max + 1]; for (int num : nums) sum[num] += num; // 打家劫舍相同做法 int n = sum.length; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = sum[0]; for (int k = 2; k <= n; ++k) { dp[k] = Math.max(dp[k - 1], dp[k - 2] + sum[k - 1]); ...

LC.P198[打家劫舍] 方法一：动态规划12345678910111213class Solution { public int rob(int[] nums) { int n = nums.length; int[] f = new int[n + 1]; f[1] = nums[0]; for (int i = 2; i <= n; ++i) { // 1.不偷第 i 间房屋，总金额为 f[i - 1]; // 2.偷第 i 间房屋，总金额为 f[i - 2] + nums[i - 1]; f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]); } return f[n]; }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：空间优化1234567891011class Solution ...

LC.P2599[统计范围内的元音字符串数] 方法一：前缀和123456789101112131415161718192021class Solution { public int[] vowelStrings(String[] words, int[][] queries) { // Set<Character> set = new HashSet<>(List.of('a', 'e', 'i', 'o', 'u')); Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u'); int n = words.length; int[] sum = new int[n + 1]; for (int i = 1; ...

LC.P2517[礼盒的最大甜蜜度] 方法一：贪心+二分123456789101112131415161718192021222324class Solution { public int maximumTastiness(int[] price, int k) { Arrays.sort(price); int l = 0, r = price[price.length - 1] - price[0]; while (l < r) { int mid = (l + r + 1) >> 1; if (check(price, k, mid)) l = mid; else r = mid - 1; } return l; } private boolean check(int[] price, int k, int x) { int cnt = ...

LC.P1130[叶值的最小代价生成树] 方法一：记忆化搜索123456789101112131415161718192021222324252627class Solution { int[][] cache; int[][] g; public int mctFromLeafValues(int[] arr) { int n = arr.length; cache = new int[n][n]; g = new int[n][n]; for (int i = n - 1; i >= 0; --i) { g[i][i] = arr[i]; for (int j = i + 1; j < n; ++j) { g[i][j] = Math.max(g[i][j - 1], arr[j]); } } return dfs( ...