byu_rself

LC.P1833[雪糕的最大数量] 方法一：排序+贪心123456789101112131415class Solution { public int maxIceCream(int[] costs, int coins) { Arrays.sort(costs); int ans = 0; for (int cost : costs) { if (coins >= cost) { coins -= cost; ++ans; } else { break; } } return ans; }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(logn)$

LC.P2477[到达首都的最少油耗] 方法一：DFS12345678910111213141516171819202122232425262728293031323334class Solution { List<Integer>[] g; int seats; long ans; public long minimumFuelCost(int[][] roads, int seats) { this.seats = seats; int n = roads.length + 1; g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] road : roads) { int a = road[0], b = road[1]; g[a].add(b); g[b].add(a); ...

LC.P427[建立四叉树] 方法一：DFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869/*// Definition for a QuadTree node.class Node { public boolean val; public boolean isLeaf; public Node topLeft; public Node topRight; public Node bottomLeft; public Node bottomRight; public Node() { this.val = false; this.isLeaf = false; this.topLeft = null; this.topRight = null; ...

LC.P2055[蜡烛之间的盘子] 方法一：二分+前缀和1234567891011121314151617181920212223242526272829303132333435363738class Solution { public int[] platesBetweenCandles(String s, int[][] queries) { int n = s.length(), m = queries.length; int[] ans = new int[m], sum = new int[n + 1]; List<Integer> list = new ArrayList<>(); for (int i = 0; i < n; ++i) { char c = s.charAt(i); if (c == '|') list.add(i); sum[i + 1] = sum ...

LC.P1038[从二叉搜索树到更大和树] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { ...

LC.P1423[可获得的最大点数] 方法一：滑动窗口逆向思维1234567891011121314class Solution { // 求 k 张点数的最大和，等价于求 n - k 张连续的牌的最小和 public int maxScore(int[] cardPoints, int k) { int n = cardPoints.length, m = n - k, sum = 0; for (int i = 0; i < m; ++i) sum += cardPoints[i]; int total = sum, minSum = sum; for (int i = m; i < n; ++i) { total += cardPoints[i]; sum += cardPoints[i] - cardPoints[i - m]; minSum = Math.min(minSum, sum); ...

LC.P2661[找出叠涂元素] 方法一：哈希表1234567891011121314151617181920class Solution { public int firstCompleteIndex(int[] arr, int[][] mat) { int m = mat.length, n = mat[0].length; Map<Integer, int[]> map = new HashMap<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { map.put(mat[i][j], new int[]{i, j}); } } int[] row = new int[m], col = new int[n]; for (in ...

LC.P1657[确定两个字符串是否接近] 方法一：计数+排序1234567891011121314151617181920class Solution { public boolean closeStrings(String word1, String word2) { int n = word1.length(), m = word2.length(); if (n != m) return false; int[] cnt1 = new int[26], cnt2 = new int[26]; for (int i = 0; i < n; ++i) { ++cnt1[word1.charAt(i) - 'a']; ++cnt2[word2.charAt(i) - 'a']; } for (int i = 0; i < 26; ++i) { ...

KMP KMP算法的大致思路：进行模式匹配时，主串指针不回溯，只有模式串回溯，时间复杂度为 $O(n + m)$，其中 $n$ 为主串长度， $m$ 为模式串长度 构建next数组123456789101112131415void getNext(String pp, int[] next) { int m = pp.length(); // 使下标从 1 开始 pp = " " + pp; char[] p = pp.toCharArray(); for (int i = 1, j = 0; i < m; ) { if (j == 0 || p[i] == p[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; // 匹配失败 } } } KMP模式匹配12345 ...

LC.P2336[无限集中的最小数字] 方法一：有序集合12345678910111213141516171819202122232425class SmallestInfiniteSet { TreeSet<Integer> set = new TreeSet<>(); public SmallestInfiniteSet() { for (int i = 1; i <= 1000; ++i) { set.add(i); } } public int popSmallest() { return set.pollFirst(); } public void addBack(int num) { set.add(num); }}/** * Your SmallestInfiniteSet object will be instantiate ...