byu_rself

LC.P2485[找出中枢整数] 方法一：数学12345678910class Solution { public int pivotInteger(int n) { for (int x = 1; x <= n; ++x) { int a = (1 + x) * x / 2; int b = (x + n) * (n - x + 1) / 2; if (a == b) return x; } return -1; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

Offer.P6[从尾到头打印链表] 方法一：递归1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { List<Integer> list; public int[] reversePrint(ListNode head) { list = new ArrayList<>(); reverse(head); int n = list.size(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) &# ...

LC.P902[最大为N的数字组合] 方法一：数位DP1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { String[] digits; char[] s; int[] dp; public int atMostNGivenDigitSet(String[] digits, int n) { this.digits = digits; s = Integer.toString(n).toCharArray(); dp = new int[s.length]; Arrays.fill(dp, -1); return f(0, true, false); } /** * @param i 构造第 i 位数字 * @param isLimit 当前是否受到了 n 的约束 * @par ...

LC.P354[俄罗斯套娃信封问题] 方法一：动态规划123456789101112131415161718192021222324class Solution { public int maxEnvelopes(int[][] envelopes) { int n = envelopes.length; if (n == 0) return 0; Arrays.sort(envelopes, (a, b) -> { if (a[0] != b[0]) return a[0] - b[0]; // 按宽度升序 else return b[1] - a[1]; // 按高度降序 }); int[] f = new int[n]; Arrays.fill(f, 1); int ans = 1; for (int i = 1; i < n; ++i) { ...

123456789101112131415161718192021222324252627282930313233343536373839{ int[] tree; // 找到x的二进制数的最后一个1所表示的二进制 int lowbit(int x) { return x & -x; } // 在树状数组 x 位置中增加值 u void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tree[i] += u; } // 查询前缀和的方法 int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i]; return ans; }}// 初始化「树状数组，要默 ...

LC.P307[区域和检索-数组可修改] 方法一：树状数组12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class NumArray { int[] tree; int[] nums; int n; private int lowbit(int x) { return x & -x; } private void add(int x, int val) { for (int i = x; i <= n; i += lowbit(i)) { tree[i] += val; } } private int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowb ...

LC.P2496[数组中字符串的最大值] 方法一：模拟1234567891011121314151617181920class Solution { public int maximumValue(String[] strs) { int ans = 0; for (String s : strs) { boolean flag = false; for (char c : s.toCharArray()) { if (c >= 'a' && c <= 'z') { flag = true; break; } } if (flag) { ans = Math ...

Interview.P1619[水域大小] 方法一：DFS1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { int m, n; int[][] land; public int[] pondSizes(int[][] land) { this.land = land; m = land.length; n = land[0].length; List<Integer> list = new ArrayList<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (land[i][j] == 0) { list ...

LC.P1823[找出游戏的获胜者] 方法一：队列+模拟123456789101112131415class Solution { public int findTheWinner(int n, int k) { Deque<Integer> queue = new ArrayDeque<>(); for (int i = 1; i <= n; ++i) { queue.offer(i); } while (queue.size() > 1) { for (int i = 1; i < k; ++i) { queue.offer(queue.poll()); } queue.poll(); } return queue.peek(); } ...

LCP.P33[黑白翻转棋] 方法一：BFS123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657class Solution { int m, n; String[] chessboard; public int flipChess(String[] chessboard) { m = chessboard.length; n = chessboard[0].length(); this.chessboard = chessboard; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (chessboard[i].charAt(j) ...