LC.P902[最大为N的数字组合]
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[俄罗斯套娃信封问题]
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[区域和检索-数组可修改]
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[数组中字符串的最大值]
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[水域大小]
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[找出游戏的获胜者]
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[黑白翻转棋]
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) ...
LC.P522[最长特殊序列II]
LC.P522[最长特殊序列II]
方法一：贪心+双指针12345678910111213141516171819202122232425class Solution { public int findLUSlength(String[] strs) { int n = strs.length, ans = -1; for (int i = 0; i < n; ++i) { boolean flag = true; for (int j = 0; j < n; ++j) { if (i != j && isSubseq(strs[i], strs[j])) { flag = false; break; } } if (flag) ans ...
LC.P1177[构建回文串检测]
LC.P1177[构建回文串检测]
方法一：前缀和1234567891011121314151617181920212223class Solution { public List<Boolean> canMakePaliQueries(String s, int[][] queries) { int n = s.length(); int[][] sum = new int[n + 1][26]; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 26; ++j) { sum[i][j] = sum[i - 1][j]; } ++sum[i][s.charAt(i - 1) - 'a']; } List<Boolean> ans = new Arra ...