网站建设公司.,如何汇报网站建设,网站子目录,弄个直播平台大概要多少钱文章目录 53. 最大子数组和解法1——DP解法2——分治#xff08;维护区间、类似线段树的思想#xff09; 2216. 美化数组的最少删除数#xff08;贪心#xff09;2304. 网格中的最小路径代价1410. HTML 实体解析器#xff08;模拟#xff09;2824. 统计和小于目标的下标对… 文章目录 53. 最大子数组和解法1——DP解法2——分治维护区间、类似线段树的思想 2216. 美化数组的最少删除数贪心2304. 网格中的最小路径代价1410. HTML 实体解析器模拟2824. 统计和小于目标的下标对数目简单Q11457. 二叉树中的伪回文路径828. 统计子串中的唯一字符——贡献法 53. 最大子数组和
https://leetcode.cn/problems/maximum-subarray/description/?envTypedaily-questionenvId2023-11-20 提示
1 nums.length 10^5 -10^4 nums[i] 10^4
进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
解法1——DP
class Solution {public int maxSubArray(int[] nums) {int ans Integer.MIN_VALUE, s 0;for (int x: nums) {s x;ans Math.max(ans, s);if (s 0) s 0;}return ans;}
}解法2——分治维护区间、类似线段树的思想
https://leetcode.cn/problems/maximum-subarray/?envTypedaily-questionenvId2023-11-20
class Solution {public int maxSubArray(int[] nums) {return getInfo(nums, 0, nums.length - 1).mSum;}public Status getInfo(int[] a, int l, int r) {if (l r) {return new Status(a[l], a[l], a[l], a[l]);}int m (l r) 1;Status lSub getInfo(a, l, m);Status rSub getInfo(a, m 1, r);return pushUp(lSub, rSub);}public Status pushUp(Status l, Status r) {int iSum l.iSum r.iSum;int lSum Math.max(l.lSum, l.iSum r.lSum);int rSum Math.max(r.rSum, r.iSum l.rSum);int mSum Math.max(Math.max(l.mSum, r.mSum), l.rSum r.lSum);return new Status(lSum, rSum, mSum, iSum);}
}class Status {// 左端点最大子段和、右端点最大子段和、最大子段和、区间和int lSum, rSum, mSum, iSum;public Status(int lSum, int rSum, int mSum, int iSum) {this.lSum lSum;this.rSum rSum;this.mSum mSum;this.iSum iSum;}
}2216. 美化数组的最少删除数贪心
https://leetcode.cn/problems/minimum-deletions-to-make-array-beautiful/description/?envTypedaily-questionenvId2023-11-21 提示
1 nums.length 10^5 0 nums[i] 10^5
只要需要删除就删除好了。 为什么—— 因为假设不这样做而是删除完整的一组两个连续相同的数字结果不会比删除nums[i1]和nums[i2]更好。 举例1.1.2.3.3.4.4.5 删除1.1之后为2.3.3.4.4.5最后变成2.3.3.4.4.5 删除1之后为1.2.3.3.4.4.5最后变成1.2.3.4.4.5 结果是一样的。 我们考虑连续的两组a,b,c,d 四个数字。 假设ab此时有两种选择 1.删除b 2.删除a和b
对于第一种方法如果删除b有两种情况1.a c,2.a!c。 考虑更差的情况需要同时删除c得到ad。 如果a d此时abcd四个数字均相同两种删法结果一样。否则保留ad删除2个。
对于第二种方法删除a和b得到cd。考虑更差情况c和d一样还需要多删除一个。
因此删除b的方法更优即需要删除就删除一个。
class Solution {public int minDeletion(int[] nums) {int n nums.length;int last 0, ans 0; // last记录上一个下标for (int i 1; i n; i) {if (nums[i] nums[last]) {ans;} else {last i 1;i last;}}if ((n - ans) % 2 1) ans;return ans;}
}2304. 网格中的最小路径代价
https://leetcode.cn/problems/minimum-path-cost-in-a-grid/description/?envTypedaily-questionenvId2023-11-22 提示 m grid.length n grid[i].length 2 m, n 50 grid 由从 0 到 m * n - 1 的不同整数组成 moveCost.length m * n moveCost[i].length n 1 moveCost[i][j] 100
时间复杂度: O ( m ∗ n 2 ) O(m∗n^2) O(m∗n2) 空间复杂度: O ( m ∗ n ) O(m∗n) O(m∗n)
class Solution {public int minPathCost(int[][] grid, int[][] moveCost) {int m grid.length, n grid[0].length;int[][] dp new int[m][n];System.arraycopy(grid[0], 0, dp[0], 0, n);for (int i 1; i m; i) { // 枚举每一层Arrays.fill(dp[i], Integer.MAX_VALUE / 2);for (int j 0; j n; j) { // 枚举每一列for (int k 0; k n; k) { // 枚举上一层的每一列dp[i][j] Math.min(dp[i][j], dp[i - 1][k] moveCost[grid[i - 1][k]][j] grid[i][j]);}}}return Arrays.stream(dp[m - 1]).min().getAsInt();}
}1410. HTML 实体解析器模拟
https://leetcode.cn/problems/html-entity-parser/description/?envTypedaily-questionenvId2023-11-23 提示
1 text.length 10^5 字符串可能包含 256 个ASCII 字符中的任意字符。
模拟即可里面用到了类似分组循环的技巧。
class Solution {public String entityParser(String text) {StringBuilder ans new StringBuilder();MapString, String m Map.of(quot, \,apos, ,amp, ,gt, ,lt, ,frasl, /);for (int i 0; i text.length(); i) {if (text.charAt(i) ) {int j i 1;while (j text.length() text.charAt(j) ! ;) j;String k text.substring(i 1, j);if (m.containsKey(k)) {ans.append(m.get(k));i j;}else ans.append(text.charAt(i));} else ans.append(text.charAt(i));}return ans.toString();}
}2824. 统计和小于目标的下标对数目简单Q1
https://editor.csdn.net/md/?articleId134503372 提示 1 nums.length n 50 -50 nums[i], target 50
class Solution {public int countPairs(ListInteger nums, int target) {int ans 0, n nums.size();for (int i 0; i n; i) {for (int j i 1; j n; j) {if (nums.get(i) nums.get(j) target) ans;}}return ans;}
}1457. 二叉树中的伪回文路径
https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/description/?envTypedaily-questionenvId2023-11-25
提示
给定二叉树的节点数目在范围 [1, 10^5] 内 1 Node.val 9
如果能够构成回文串那么利用异或的性质最多只有一位有1。也就是最多只有一个数字出现了奇数次。
class Solution {int ans 0;public int pseudoPalindromicPaths (TreeNode root) {dfs(root, 0);return ans;}public void dfs(TreeNode root, int x) {x ^ 1 root.val;if (root.left null root.right null) {if (x 0 || Integer.bitCount(x) 1) ans;}if (root.left ! null) dfs(root.left, x);if (root.right ! null) dfs(root.right, x);}
}一个相关题目可见2791. 树中可以形成回文的路径数位于【力扣周赛】第 355 场周赛构造二分答案异或前缀 状态压缩⭐树中可以形成回文的路径数
828. 统计子串中的唯一字符——贡献法
https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/description/?envTypedaily-questionenvId2023-11-26 提示
1 s.length 10^5 s 只包含大写英文字符
每个字符可以作为唯一字符的范围是从 【前一个该字符出现的位置后一个该字符出现的位置】。 假设当前字符的位置是i它的可用范围是 ( l , r ) (l,r) (l,r)不包括 l l l 和 r r r那么它的贡献是 ( i − l ) ∗ ( r − l ) (i-l)*(r-l) (i−l)∗(r−l)。
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n)
class Solution {public int uniqueLetterString(String s) {// 计算每个字符的贡献int n s.length(), ans 0;// 将相同字符的下标放入同一列表MapCharacter, ListInteger m new HashMap();for (int i 0; i n; i) {char ch s.charAt(i);if (!m.containsKey(ch)) {m.put(ch, new ArrayList());m.get(ch).add(-1);}m.get(ch).add(i);}// 计算答案for (ListInteger ls: m.values()) {ls.add(n);for (int i 1; i ls.size() - 1; i) {ans (ls.get(i) - ls.get(i - 1)) * (ls.get(i 1) - ls.get(i));}}return ans;}
}
