记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录9/7 940. 不同的子序列 II9/8 3870. 统计范围内的逗号9/9 3871. 统计范围内的逗号 II9/10 2265. 统计值等于子树平均值的节点数9/11 3483. 不同三位偶数的数目9/129/139/7 940. 不同的子序列 II动态规划 dp[i] 代表以s[i]结尾的子序列数目如果ab s[a]s[b] 则dp[a],dp[b]会存在重复的子序列但是dp[a]必定是dp[b]的真子集 只要将dp[a]中的s[a]变为s[b]及全部包含进了dp[b]所以对于dp[i]只要记录[0~i-1]间的最近的不同字符dpres[0,25]分别记录a~z最近的位置defdistinctSubseqII(s): :type s: str :rtype: int res[-1]*26MOD10**97nlen(s)dp[1]*nfori,cinenumerate(s):forjinrange(26):ifres[j]!-1:dp[i](dp[i]dp[res[j]])%MOD res[ord(s[i])-ord(a)]i ans0foriinrange(26):ifres[i]!-1:ans(ansdp[res[i]])%MODreturnans9/8 3870. 统计范围内的逗号1000开始有1个逗号 因为n100000最多一个数就一个逗号 统计有多少个大于999的数即刻defcountCommas(n): :type n: int :rtype: int returnmax(0,n-999)9/9 3871. 统计范围内的逗号 II从右边每三位插一个逗号不足四位没有逗号。[1,999] 贡献 0[1000,999999] 贡献 1[1000000,999999999] 贡献 2依此类推。从 1000 起每次乘 1000所有 x 的数各再贡献一个逗号累加 n-x1 直到 xn。defcountCommas(n): :type n: int :rtype: int ans0x1000whilexn:ansn-x1x*1000returnans9/10 2265. 统计值等于子树平均值的节点数递归 统计左右子树的总和和节点数如果当前节点的值等于子树的平均值则计数加1。classTreeNode(object):def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightdefaverageOfSubtree(root): :type root: TreeNode :rtype: int globalans ans0defcheck(node):ifnotnode:return0,0left_sum,left_countcheck(node.left)right_sum,right_countcheck(node.right)total_sumnode.valleft_sumright_sum total_count1left_countright_countiftotal_sum//total_countnode.val:globalans ans1returntotal_sum,total_count check(root)returnans9/11 3483. 不同三位偶数的数目从 digits 里选三个不同下标组成三位数个位必须是偶数百位不能为 0求不同数值的个数。数组长度不超过 10三层枚举所有下标组合用集合去重后返回大小即可。deftotalNumbers(digits): :type digits: List[int] :rtype: int sset()nlen(digits)foriinrange(n):ifdigits[i]%2:continueforjinrange(n):ifji:continueforkinrange(n):ifkiorkjordigits[k]0:continues.add(digits[k]*100digits[j]*10digits[i])returnlen(s)9/129/13