2025-09-11：不同三位偶数的数目。用go语言，给定一个数字列表 digits，从中挑出三个不重复的元素，按百位-十位-个

福大大架构师每日一题

发布于 2025-12-18 11:25:06

1060

2025-09-11：不同三位偶数的数目。用go语言，给定一个数字列表 digits，从中挑出三个不重复的元素，按百位-十位-个位拼成一个三位数。要求百位不能是 0，个位必须是偶数，每个数组元素最多只能用一次。问能组成多少个不同的满足条件的三位数（相同数值只计一次）。

3 <= digits.length <= 10。

0 <= digits[i] <= 9。

输入： digits = [1,2,3,4]。

输出： 12。

解释：可以形成的 12 个不同的三位偶数是 124，132，134，142，214，234，312，314，324，342，412 和 432。注意，不能形成 222，因为数字 2 只有一个。

题目来自力扣3483。

根据代码和题目描述，以下是生成所有不同三位偶数的详细过程：

步骤描述：

1. 问题分析：给定一个数字列表（可能包含重复数字，但每个元素最多使用一次），需要从中选择三个不同的位置（不重复使用元素）组成三位数。要求百位不能为0，个位必须是偶数（0,2,4,6,8），且相同的数值只计一次（去重）。
2. 回溯函数（backtrack）：
- • 初始化：创建used布尔数组（长度与digits相同）来标记每个数字是否已被使用；创建results集合（使用map[int]bool）来存储唯一的三位数。
- • 回溯过程：递归生成所有可能的三位数排列：
  - • 基准情况：当当前构建的数字序列current长度达到3时，检查百位是否为0（不能为0）和个位是否为偶数（满足条件则将该数字加入results集合）。
  - • 递归情况：遍历所有数字，对于每个未使用的数字：
    - • 标记该数字为已使用。
    - • 将该数字加入当前序列current。
    - • 递归调用backtrack。
    - • 回溯：从current中移除该数字，并标记为未使用。
- • 结果返回：回溯结束后，results集合的大小即为唯一三位偶数的数量。
3. 去重机制：使用map存储数字（键为数值，值为true），自动处理重复值（相同数值只存储一次）。
4. 主函数：初始化输入（例如[1,2,3,4]），调用totalNumbers并输出结果。

时间复杂度和额外空间复杂度：

• 时间复杂度：O(n! / (n-3)!) = O(n^3) 最坏情况（n=10时最多1098=720次递归调用），但实际由于去重和剪枝（百位不为0、个位为偶数）可能减少一些分支。但最坏情况下仍为排列数（P(n,3)）。
• 额外空间复杂度：
- • 递归栈深度最大为3（因为只选3个数字），所以递归栈空间为O(1)。
- • used数组：O(n)（n为输入长度，最大10）。
- • results集合：最坏情况下存储所有可能的三位数（最多P(n,3)个，但实际由于去重和条件限制会少一些），因此空间为O(P(n,3)) = O(n^3)（n=10时最多720个，但实际更少）。
- • 因此总额外空间复杂度为O(n^3)（主要由结果集合占用）。

总结：时间复杂度为O(n^3)，额外空间复杂度为O(n^3)。

Go完整代码如下：

package main

import (
    "fmt"
)

func totalNumbers(digits []int)int {
    n := len(digits)
    used := make([]bool, n)
    results := make(map[int]bool)

    var backtrack func(current []int)
    backtrack = func(current []int) {
        iflen(current) == 3 {
            if current[0] != 0 && current[2]%2 == 0 {
                num := current[0]*100 + current[1]*10 + current[2]
                results[num] = true
            }
            return
        }
        for i := 0; i < n; i++ {
            if !used[i] {
                used[i] = true
                current = append(current, digits[i])
                backtrack(current)
                current = current[:len(current)-1]
                used[i] = false
            }
        }
    }

    backtrack([]int{})
    returnlen(results)
}

func main() {
    digits := []int{1, 2, 3, 4}
    result := totalNumbers(digits)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def totalNumbers(digits):
    n = len(digits)
    used = [False] * n
    results = set()

    def backtrack(current):
        iflen(current) == 3:
            if current[0] != 0 and current[2] % 2 == 0:
                num = current[0] * 100 + current[1] * 10 + current[2]
                results.add(num)
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(digits[i])
                backtrack(current)
                current.pop()
                used[i] = False

    backtrack([])
    returnlen(results)


if __name__ == "__main__":
    digits = [1, 2, 3, 4]
    print(totalNumbers(digits))