企业官网建设流程全解析

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

9/7 940. 不同的子序列 II

动态规划 dp[i] 代表以s[i]结尾的子序列数目
如果a<b 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]间的最近的不同字符dp
res[0,25]分别记录a~z最近的位置

defdistinctSubseqII(s):""" :type s: str :rtype: int """res=[-1]*26MOD=10**9+7n=len(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 ans=0foriinrange(26):ifres[i]!=-1:ans=(ans+dp[res[i]])%MODreturnans

9/8 3870. 统计范围内的逗号

1000开始有1个逗号 因为n<100000
最多一个数就一个逗号 统计有多少个大于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-x+1 直到 x>n。

defcountCommas(n):""" :type n: int :rtype: int """ans=0x=1000whilex<=n:ans+=n-x+1x*=1000returnans

9/10 2265. 统计值等于子树平均值的节点数

递归 统计左右子树的总和和节点数，如果当前节点的值等于子树的平均值，则计数加1。

classTreeNode(object):def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightdefaverageOfSubtree(root):""" :type root: TreeNode :rtype: int """globalans ans=0defcheck(node):ifnotnode:return0,0left_sum,left_count=check(node.left)right_sum,right_count=check(node.right)total_sum=node.val+left_sum+right_sum total_count=1+left_count+right_countiftotal_sum//total_count==node.val:globalans ans+=1returntotal_sum,total_count check(root)returnans

9/11 3483. 不同三位偶数的数目

从 digits 里选三个不同下标组成三位数，个位必须是偶数，百位不能为 0，求不同数值的个数。
数组长度不超过 10，三层枚举所有下标组合，用集合去重后返回大小即可。

deftotalNumbers(digits):""" :type digits: List[int] :rtype: int """s=set()n=len(digits)foriinrange(n):ifdigits[i]%2:continueforjinrange(n):ifj==i:continueforkinrange(n):ifk==iork==jordigits[k]==0:continues.add(digits[k]*100+digits[j]*10+digits[i])returnlen(s)

9/12

9/13