LC 233 小于等于 n 的非负整数中数字 1 出现的个数
(N int)
| 1004 | |
| 1005 | // LC 233 小于等于 n 的非负整数中数字 1 出现的个数 |
| 1006 | func countDigitOne(N int) int { |
| 1007 | if N < 0 { |
| 1008 | return 0 |
| 1009 | } |
| 1010 | s := strconv.Itoa(N) |
| 1011 | n := len(s) |
| 1012 | dp := make([]int, n) |
| 1013 | for i := range dp { |
| 1014 | dp[i] = -1 |
| 1015 | } |
| 1016 | var f func(p, cnt int, limitUp bool) int |
| 1017 | f = func(p, cnt int, limitUp bool) (res int) { |
| 1018 | if p == n { |
| 1019 | return cnt |
| 1020 | } |
| 1021 | if !limitUp { |
| 1022 | dv := &dp[p] |
| 1023 | if *dv >= 0 { |
| 1024 | return *dv + cnt*int(math.Pow10(n-p)) |
| 1025 | } |
| 1026 | defer func() { *dv = res }() |
| 1027 | } |
| 1028 | up := 9 |
| 1029 | if limitUp { |
| 1030 | up = int(s[p] & 15) |
| 1031 | } |
| 1032 | for d := 0; d <= up; d++ { |
| 1033 | tmp := cnt |
| 1034 | if d == 1 { |
| 1035 | tmp++ |
| 1036 | } |
| 1037 | res += f(p+1, tmp, limitUp && d == up) |
| 1038 | } |
| 1039 | return |
| 1040 | } |
| 1041 | return f(0, 0, true) |
| 1042 | } |
| 1043 | |
| 1044 | // LC 235 |
| 1045 | func lowestCommonAncestor(root, p, q *TreeNode) (ancestor *TreeNode) { |