域名的注册方式,系统优化大师官方下载,做网页用的网站,万网没备案怎么做网站Leetcode刷题:395. 至少有 K 个重复字符的最长子串、823. 带因子的二叉树 1. 395. 至少有 K 个重复字符的最长子串算法思路参考代码和运行结果 2. 823. 带因子的二叉树算法思路参考代码和运行结果 1. 395. 至少有 K 个重复字符的最长子串
题目难度#xff1a;中等 标签#… Leetcode刷题:395. 至少有 K 个重复字符的最长子串、823. 带因子的二叉树 1. 395. 至少有 K 个重复字符的最长子串算法思路参考代码和运行结果 2. 823. 带因子的二叉树算法思路参考代码和运行结果 1. 395. 至少有 K 个重复字符的最长子串
题目难度中等 标签分治、哈希表 题目如下 给你一个字符串 s 和一个整数 k 请你找出 s 中的最长子串 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。 如果不存在这样的子字符串则返回 0。 题目链接为395. 至少有 K 个重复字符的最长子串 题目示例如下 1. 输入s “aaabb”, k 3 输出3 解释最长子串为 “aaa” 其中 ‘a’ 重复了 3 次。 输入s “ababbc”, k 2 输出5 解释最长子串为 “ababb” 其中 ‘a’ 重复了 2 次 ‘b’ 重复了 3 次。 提示
1 s.length 104s 仅由小写英文字母组成1 k 10^5
算法思路
我的算法思路如下 题目要求找到s中最长子串(子串:即原字符串中一段连续的字符序列)且该子串中每一个字符出现的次数都应该大于或等于k。既然如此那么我们可以考虑原字符串s中那些字符出现次数少于k的字符然后以这些字符作为分隔分隔之后可能有多个字符串然后对这些字符串继续上述操作。直到某个字符串中的每一个字符出现次数均大于或等于k然后该字符串计算长度并比较大小即可。
画出示意图如下 原字符串s“ababbc”k2 原字符串中字符次数少于k的有字符 “c” 以字符“c”对原字符串s进行分隔操作得到ababb 对于“ababb”中每一个字符出现次数均大于或等于k于是结果ans max(len(“ababb”),ans)5ans初始值为0 原字符串s:“bbaaacbd”,k : 3 原字符串中字符少于k的字符有 “c”、“d” 利用上述字符对原字符串s进行分隔操作得“bbaaa”“b” 对于“bbaaa”其中字符出现次数少于k的有 “b” 对“bbaaa”进行分隔操作得“aaa” ”aaa“中字符出现次数均大于或等于kans max(ans,len(“aaa”))3 参考代码和运行结果
class Solution(object):def longestSubstring(self, s, k)::type s: str:type k: int:rtype: intmap {}for c in s:map[c] map.get(c,0) 1arr []for key in map:if map[key] k:arr.append(key)if len(arr) 0:return len(s)else:start 0ans 0n len(s)for i in range(n):c s[i]if c in arr:ans max(self.longestSubstring(s[start:i],k),ans)start i 1if start n:ans max(self.longestSubstring(s[start:],k),ans)return ans运行结果
2. 823. 带因子的二叉树
题目难度中等 题目标签动态规划、哈希表 题目如下 给出一个含有不重复整数元素的数组 arr 每个整数 arr[i] 均大于 1。 用这些整数来构建二叉树每个整数可以使用任意次数。其中每个非叶结点的值应等于它的两个子结点的值的乘积。 满足条件的二叉树一共有多少个答案可能很大返回 对 109 7 取余 的结果。 示例如下 1. 输入: arr [2, 4] 输出: 3 解释: 可以得到这些二叉树: [2], [4], [4, 2, 2] 输入: arr [2, 4, 5, 10] 输出: 7 解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]. 提示
1 arr.length 10002 arr[i] 109arr 中的所有值 互不相同
算法思路
首先arr中每个元素单独组成二叉树是满足题目要求现在考虑多个元素组合情况根节点和其左右节点值满足条件root.val root.left.val*root.right.val其左、右节点如果还有子节点那么也应该满足上述等式为此需要对原arr进行升序排序然后依次遍历arr中每个元素用map来记录arr中每一个元素满足上述等式次数。
示意图如下
参考代码和运行结果
参考代码如下
class Solution(object):def numFactoredBinaryTrees(self, arr)::type arr: List[int]:rtype: intmap {}arr.sort()for e in arr:map[e] map.get(e, 0) 1for k in map:if e % k 0 and map.get(e//k,None):v1 map[k]v2 map[e//k]map[e] v1 * v2return sum(map.values()) % (10**97)运行结果
