网络网站制作技巧,郑州企业网站排行,php免费网站源码,濮阳网站建设陈帅LeetCode题目: 77. 组合216. 组合总和 III17. 电话号码的字母组合2537. 统计好子数组的数目(每日一题)516. 最长回文子序列1039. 多边形三角剖分的最低得分543. 二叉树的直径124. 二叉树中的最大路径和2246. 相邻字符不同的最长路径 其他:
今日总结 往期打卡 77. 组合 跳转: 7… LeetCode题目: 77. 组合216. 组合总和 III17. 电话号码的字母组合2537. 统计好子数组的数目(每日一题)516. 最长回文子序列1039. 多边形三角剖分的最低得分543. 二叉树的直径124. 二叉树中的最大路径和2246. 相邻字符不同的最长路径 其他:
今日总结 往期打卡 77. 组合 跳转: 77. 组合 学习: 代码随想录公开讲解 问题:
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路:
递归传入剩余需选个数,归零终止. 剪枝: 用需选个数可以求出遍历范围,及至少给以后的选择留出足够的数 因为使用dfs,一次只需要存储一条路径即可
使用迭代法需要储存大量的子状态. 而且因为空间需要提前预定义,所以不方便做剪枝. 其上下层之间的操作相对独立,没有明显练习,所以无法做递推.
复杂度:
时间复杂度: O ( k 2 ) O(k^2) O(k2)空间复杂度: O ( k ) O(k) O(k)
代码:
class Solution {int k;ListListInteger ans;private final ListInteger path new ArrayList();void dfs(int n){int d k-path.size();if(d0) {ans.add(new ArrayList(path));return;}for(int jn;jd;j--){path.add(j);dfs(j-1);path.remove(path.size()-1);}}public ListListInteger combine(int n, int k) {this.k k;ans new ArrayList();dfs(n);return ans;}
}216. 组合总和 III 跳转: 216. 组合总和 III 学习: 代码随想录公开讲解 问题:
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
思路:
递归的终止条件改为两个,和大于n或还需选择数为0
复杂度:
时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {ListListInteger ans ;ListInteger path new ArrayList();int sum 0;int n;void dfs(int k,int start){if(sumn) return;if(k0){if(sumn) ans.add(new ArrayList(path));return;}for(int istart;i9;i){sumi;path.add(i);dfs(k-1,i1);sum-i;path.remove(path.size()-1);}}public ListListInteger combinationSum3(int k, int n) {ans new ArrayList();this.n n;dfs(k,1);return ans;}
}17. 电话号码的字母组合 跳转: 17. 电话号码的字母组合 学习: 代码随想录公开讲解 问题:
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
思路:
终止条件为按过全部电话键,因为这题求的是全排列,所以没法做剪枝操作
复杂度:
时间复杂度: O ( 3 n ) O(3^n) O(3n)空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {private static final String[] MAPPING new String[]{ abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};ListString ans;private char[] path;void backtracking(char[] list,int index){if(indexlist.length){ans.add(new String(path));return;}int k list[index]-50;for(char c:MAPPING[k].toCharArray()){path[index] c;backtracking(list,index1);}}public ListString letterCombinations(String digits) {int n digits.length();ans new ArrayList();if(n0) return ans;path new char[n];backtracking(digits.toCharArray(),0);return ans;}
}2537. 统计好子数组的数目(每日一题) 跳转: 2537. 统计好子数组的数目 学习: 灵茶山艾府题解 问题:
给你一个整数数组 nums 和一个整数 k 请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i j 且 arr[i] arr[j] 那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
思路:
这题可以使用滑动窗口加哈希表,每次收缩到刚好满足条件,计算时加上被抛弃的前缀数 求的是选出两个相同元素,对于单个元素来讲,刚好是0,1,3,6,每次加一个n-1到n
复杂度:
时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( n ) O(n) O(n)
代码:
class Solution {public long countGood(int[] nums, int k) {int n nums.length;MapInteger,Integer map new HashMap();int sum 0;long ans 0;for(int i0,pre 0;in;i){summap.getOrDefault(nums[i],0);map.put(nums[i],map.getOrDefault(nums[i],0)1);while(sumk){map.put(nums[pre],map.get(nums[pre])-1);sum-map.get(nums[pre]);pre;// System.out.println(pre);}ansanspre;}return ans;}
}516. 最长回文子序列 跳转: 516. 最长回文子序列 学习: 灵茶山艾府题解 问题:
给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
思路:
题目中不要求连续,但给出了回文序列的条件. 满足条件就都选,不满足条件留使子串最大的一边 dp数组值的含义是当前区间内能选出的最大的回文子串长度
复杂度:
时间复杂度: O ( n 2 ) O(n^2) O(n2)空间复杂度: O ( n ) O(n) O(n)
代码(递推空间优化):
class Solution {public int longestPalindromeSubseq(String s) {int n s.length();int[] f new int[n];for(int in-1;i0;i--){f[i] 1;int pre 0;for(int ji1;jn;j){int tmp f[j];if(s.charAt(i)s.charAt(j)) f[j] pre2;else f[j] Math.max(f[j],f[j-1]);pre tmp;}}return f[n-1];}
}复杂度:
时间复杂度: O ( n 2 ) O(n^2) O(n2)空间复杂度: O ( n 2 ) O(n^2) O(n2)
代码(递归记忆化搜索):
class Solution {int[][] cache;int dfs(String s,int l,int r){if(lr) return 1;if(lr) return 0;if(cache[l][r]!-1) return cache[l][r];if(s.charAt(l)s.charAt(r)) return cache[l][r] dfs(s,l1,r-1)2;else return cache[l][r] Math.max(dfs(s,l1,r),dfs(s,l,r-1));}public int longestPalindromeSubseq(String s) {cache new int[s.length()][s.length()];for(int[] i:cache){Arrays.fill(i,-1);}return dfs(s,0,s.length()-1);}
}代码(递推):
class Solution {public int longestPalindromeSubseq(String s) {int n s.length();int[][] f new int[n][n];for(int in-1;i0;i--){for(int j0;jn;j){if(ij) f[i][j] 1;else if(ij) continue;else {if(s.charAt(i)s.charAt(j)) f[i][j] f[i1][j-1]2;else f[i][j] Math.max(f[i1][j],f[i][j-1]);}} }return f[0][n-1];}
}1039. 多边形三角剖分的最低得分 跳转: 1039. 多边形三角剖分的最低得分 学习: 灵茶山艾府题解 问题:
你有一个凸的 n 边形其每个顶点都有一个整数值。给定一个整数数组 values 其中 values[i] 是第 i 个顶点的值即 顺时针顺序 。
假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形该三角形的值是顶点标记的乘积三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。
返回 多边形进行三角剖分后可以得到的最低分 。
思路:
遍历区间找所有可能的三角形,每次划分继续二分区间遍历
复杂度:
时间复杂度: O ( n 2 ) O(n^2) O(n2)空间复杂度: O ( n 2 ) O(n^2) O(n2)
代码(递推):
class Solution {public int minScoreTriangulation(int[] values) {int n values.length;int[][] f new int[n][n];for(int i n-3;i0;i--){for(int ji2;jn;j){f[i][j] Integer.MAX_VALUE;for(int ki1;kj;k){f[i][j] Math.min(f[i][j],f[i][k]f[k][j]values[i]*values[k]*values[j]);}}}return f[0][n-1];}
}代码(递归):
class Solution {int[] v;int[][] cache;int dfs(int l,int r){if(rl1) return 0;if(cache[l][r]!0) return cache[l][r];int min Integer.MAX_VALUE1;for(int il1;ir;i){int tmp dfs(l,i)dfs(i,r)v[i]*v[l]*v[r];if(tmpmin) min tmp;}return cache[l][r]min;}public int minScoreTriangulation(int[] values) {int n values.length;cache new int[n][n];v values;return dfs(0,n-1);}
}543. 二叉树的直径 跳转: 543. 二叉树的直径 学习: 灵茶山艾府题解 问题:
给你一棵二叉树的根节点返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
思路:
当前最大是左最大右最大1 然后返回左右最大的一条数量
复杂度:
时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {int ans0;int dfs(TreeNode root){if(rootnull) return 0;int l dfs(root.left);int r dfs(root.right);ans Math.max(ans,lr);return Math.max(l,r)1;}public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}
}124. 二叉树中的最大路径和 跳转: 124. 二叉树中的最大路径和 学习: 灵茶山艾府题解 问题:
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root 返回其 最大路径和 。
思路:
dfs,上一题求数量改求和了 不过需要注意,子树如果为负不应该选,所以可以直接返回时和0比较一下
复杂度:
时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {int ansInteger.MIN_VALUE;int dfs(TreeNode root){if(rootnull) return 0;int l dfs(root.left);int r dfs(root.right);ans Math.max(ans,lrroot.val);return Math.max(Math.max(l,r)root.val,0);}public int maxPathSum(TreeNode root) {dfs(root);return ans;}
}2246. 相邻字符不同的最长路径 跳转: 2246. 相邻字符不同的最长路径 学习: 灵茶山艾府题解 问题:
给你一棵 树即一个连通、无向、无环图根节点是节点 0 这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树其中 parent[i] 是节点 i 的父节点由于节点 0 是根节点所以 parent[0] -1 。
另给你一个字符串 s 长度也是 n 其中 s[i] 表示分配给节点 i 的字符。
请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 并返回该路径的长度。
思路:
父节点的父节点一定比子节点的父节点小吗? 显然这题不是这样的,我们无法排出一个合理的顺序. 所以这题不能使用倒序遍历,只能自顶向下遍历.
题目中给的是父节点数组,所以需要构造和子节点的哈希.
复杂度:
时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {private ListInteger[] g;private char[] s;private int ans;int dfs(int x){int maxLen 0;for(int y:g[x]){int len dfs(y)1;if(s[y]!s[x]){ans Math.max(ans,maxLenlen);maxLen Math.max(maxLen,len);}}return maxLen;}public int longestPath(int[] parent, String s) {int n parent.length;this.s s.toCharArray();g new ArrayList[n];Arrays.setAll(g, e - new ArrayList());for(int i1;in;i){g[parent[i]].add(i);}dfs(0);return ans1;}
}总结
练习了组合回溯以及区间DP,树性DP
回溯算法模板框架:
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}往期打卡
代码随想录算法训练营第十八天
代码随想录算法训练营第十七天
代码随想录算法训练营周末三
代码随想录算法训练营第十六天
代码随想录算法训练营第十五天
代码随想录算法训练营第十四天
代码随想录算法训练营第十三天
代码随想录算法训练营第十二天
代码随想录算法训练营第十一天
代码随想录算法训练营周末二
代码随想录算法训练营第十天
代码随想录算法训练营第九天
代码随想录算法训练营第八天
代码随想录算法训练营第七天
代码随想录算法训练营第六天
代码随想录算法训练营第五天
代码随想录算法训练营周末一
代码随想录算法训练营第四天
代码随想录算法训练营第三天
代码随想录算法训练营第二天
代码随想录算法训练营第一天
