byu_rself

LC.P1006[笨阶乘] 方法一：栈12345678910111213141516171819202122232425class Solution { public int clumsy(int n) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(n--); int index = 0; // * / + - while (n > 0) { if (index % 4 == 0) { stack.push(stack.pop() * n); } else if (index % 4 == 1) { stack.push(stack.pop() / n); } else if (index % 4 == 2) { ...

LC.P1276[不浪费原料的汉堡制作方案] 方法一：数学求解二元一次方程即可 1234567891011class Solution { public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) { if (tomatoSlices % 2 != 0 || tomatoSlices < cheeseSlices * 2 || cheeseSlices * 4 < tomatoSlices) { return new ArrayList<>(); } List<Integer> ans = new ArrayList<>(); ans.add(tomatoSlices / 2 - cheeseSlices); ans.add(cheeseSlices * 2 - tomatoSlices / 2); ...

LC.P662[二叉树最大宽度] 方法一：BFS123456789101112131415161718192021222324252627282930313233343536373839/** * 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.P2866[美丽塔II] 方法一：单调栈+动态规划123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Solution {public long maximumSumOfHeights(List<Integer> maxHeights) { int n = maxHeights.size(); Deque<Integer> stack = new ArrayDeque<>(); int[] left = new int[n], right = new int[n]; Arrays.fill(left, -1); Arrays.fill(right, n); for (int i = 0; i < n; ++i) { int x = maxHeight ...

LC.P357[统计各位数字都不同的数字个数] 方法一：乘法原理123456789101112class Solution { public int countNumbersWithUniqueDigits(int n) { if (n == 0) return 1; int ans = 10; for (int i = 2, last = 9; i <= n; ++i) { int cur = last * (10 - i + 1); ans += cur; last = cur; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$ 方法二：数位DP12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class ...

LC.P2828[判别首字母缩略词] 方法一：模拟12345678910111213class Solution { public boolean isAcronym(List<String> words, String s) { if (words.size() != s.length()) { return false; } for (int i = 0; i < s.length(); ++i) { if (words.get(i).charAt(0) != s.charAt(i)) { return false; } } return true; }} 时间复杂度：$O(n)$，$n$为$words$的长度 空间复杂度：$O(1)$

LC.P470[用Rand7()实现Rand10()] 方法一：数学12345678910111213/** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */class Solution extends SolBase { public int rand10() { int first, second; while ((first = rand7()) > 6); // 拒绝7，对[1,6]采样，把奇数和偶数作为采样结果，每种概率为0.5 while ((second = rand7()) > 5); // 拒绝6,7，对[1,5]采样，有五种结果，每种概率为0.2 return (first & 1) == 1 ? second : 5 + second; ...

LC.P1901[寻找峰值II] 方法一：二分查找1234567891011121314151617181920212223class Solution { public int[] findPeakGrid(int[][] mat) { int m = mat.length; int left = 0, right = m - 1; while (left < right) { int i = left + right >> 1; int j = maxPos(mat[i]); if (mat[i][j] > mat[i + 1][j]) right = i; else left = i + 1; } return new int[]{left, maxPos(mat[left])}; } private int ma ...

LC.P319[灯泡开关] 方法一：数学12345class Solution { public int bulbSwitch(int n) { return (int) Math.sqrt(n); }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P172[阶乘后的零] 方法一：数学12345678910class Solution { public int trailingZeroes(int n) { int ans = 0; while (n > 0) { ans += n / 5; n = n / 5; } return ans; }} 时间复杂度：$O(logn)$ 空间复杂度：$O(1)$