2843-统计对称整数的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目 。

示例 1：

**输入：** low = 1, high = 100
**输出：** 9
**解释：** 在 1 到 100 范围内共有 9 个对称整数：11、22、33、44、55、66、77、88 和 99 。

示例 2：

**输入：** low = 1200, high = 1230
**输出：** 4
**解释：** 在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。

提示：

  • 1 <= low <= high <= 104

请看 视频讲解 。

[sol-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        ans = 0
        for i in range(low, high + 1):
            s = str(i)
            n = len(s)
            ans += n % 2 == 0 and sum(map(int, s[:n // 2])) == sum(map(int, s[n // 2:]))
        return ans
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for (int i = low; i <= high; i++) {
            char[] s = Integer.toString(i).toCharArray();
            int n = s.length;
            if (n % 2 > 0) {
                continue;
            }
            int sum = 0;
            for (int j = 0; j < n / 2; j++) {
                sum += s[j];
            }
            for (int j = n / 2; j < n; j++) {
                sum -= s[j];
            }
            if (sum == 0) {
                ans++;
            }
        }
        return ans;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int countSymmetricIntegers(int low, int high) {
        int ans = 0;
        for (int i = low; i <= high; i++) {
            auto s = to_string(i);
            int n = s.length();
            if (n % 2 == 0 && accumulate(s.begin(), s.begin() + n / 2, 0) == accumulate(s.begin() + n / 2, s.end(), 0)) {
                ans++;
            }
        }
        return ans;
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func countSymmetricIntegers(low int, high int) (ans int) {
	for i := low; i <= high; i++ {
		s := strconv.Itoa(i)
		n := len(s)
		if n%2 > 0 {
			continue
		}
		sum := 0
		for _, c := range s[:n/2] {
			sum += int(c)
		}
		for _, c := range s[n/2:] {
			sum -= int(c)
		}
		if sum == 0 {
			ans++
		}
	}
	return
}
[sol-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var countSymmetricIntegers = function (low, high) {
    let ans = 0;
    for (let i = low; i <= high; i++) {
        const s = i.toString();
        const n = s.length;
        if (n % 2) {
            continue;
        }
        const m = n >> 1;
        let sum = 0;
        for (let j = 0; j < m; j++) {
            sum += s.charCodeAt(j);
        }
        for (let j = m; j < n; j++) {
            sum -= s.charCodeAt(j);
        }
        if (sum === 0) {
            ans++;
        }
    }
    return ans;
};

复杂度分析

  • 时间复杂度：\mathcal{O}((\textit{high} - \textit{low})\log \textit{high})。
  • 空间复杂度：\mathcal{O}(\log \textit{high})。

思考题

你能用 数位 DP 解决本题吗？

时间复杂度可以做到 \mathcal{O}(\log^2 \textit{high})。

 Comments
On this page
2843-统计对称整数的数目
  1. 思考题