Leetcode每日一题 —— 3483. 不同三位偶数的数目

直接暴力循环。不过看到一种更优解，根据100-998中的每一个偶数去查digits能否生成(用一个int[10]整理digits中每一个0-9的数字有几个)，这样无论digits多少时间复杂度都是O(n + 450)，而不是现在的O(n^3),不过这道题目限定n <= 10，所以时间复杂度也差不多```
public class Solution {
public int TotalNumbers(int[] digits) {
IList<int> possibleNumbers = new List<int>();
for (int i = 0; i < digits.Length; i++)
{
if (digits[i] == 0) continue;
for (int j = 0; j < digits.Length; j++)
{
if (j == i) continue;
for (int k = 0; k < digits.Length; k++)
{
if (digits[k] % 2 != 0 || k == i || k == j) continue;
possibleNumbers.Add(digits[i]100 + digits[j]10 + digits[k]);
}
}
}

return possibleNumbers.Distinct().Count();
}
}

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        ans = set()
        for i, x in enumerate(digits):
            if not(x & 1):
                for j, y in enumerate(digits):
                    if j != i:
                        for k, z in enumerate(digits):
                            if z and k != j and k != i:
                                ans.add(z*100 + y*10 + x)
        return len(ans)
                

做的极其丑陋

算术评级 2 第 152 场双周赛 Q1 难度分 1324```
class Solution:
def totalNumbers(self, digits: List[int]) -> int:
ans=set()
n=len(digits)
count=Counter(digits)
for i in range(n):
if digits[i]==0: continue
for j in range(n):
for k in range(n):
if digits[k]%2==1: continue
cur_num = digits[i]100+digits[j]10+digits[k]
if cur_num not in ans:
count_cur=defaultdict(int)
count_cur[digits[i]]+=1
count_cur[digits[j]]+=1
count_cur[digits[k]]+=1
flag=True
for k,v in count_cur.items():
if v>count[k]:
flag=False
break
if flag:
ans.add(cur_num)
return len(list(ans))

组合数学：最后一位必然是02468其中一个，前两位能组成多少合法组合？

第一位不能是0 + 第二位任选

注意重复（11/22/33）只能算一次，这里偷懒分开算了```
class Solution:
def totalNumbers(self, digits: List[int]) -> int:
ans = 0
cnt = [0] * 10
for x in digits:
cnt[x] += 1

for d in (0, 2, 4, 6, 8):
if cnt[d] > 0:
cnt[d] -= 1

same = 0
z = non_z = 0

for i in range(10):
if cnt[i] > 0:
if i == 0:
z += 1
else:
non_z += 1

if i != 0 and cnt[i] >= 2:
same += 1
# 两个数位不同 -> 第一位非0 第二位任选但不同
# 两个数位相同 -> same
tmp = non_z * (z + non_z - 1) + same
ans += tmp

cnt[d] += 1

return ans

看到大伙都这么丑陋我就释怀了。。。有没有灵光一现做法。```
class Solution {
public:
int totalNumbers(vector<int>& digits) {
unordered_set<int> s;
int n = digits.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(j == i) continue;
for(int k = 0; k < n; k ++) {
if((k == i) || (k == j)) continue;
if(digits[k] % 2 == 0 && digits[i]) {
s.insert(digits[i] 100 + digits[j] 10 + digits[k]);
}
}
}
}
return s.size();
}
};

Kotlin每日打卡（组合数学，固定个位偶数，分别处理十位非零，最后处理百位非零）：```
class Solution {
fun totalNumbers(digits: IntArray): Int {
val digitCounts = IntArray(10)
for (digit in digits) {
digitCounts[digit]++
}

var totalNonZeroTypes = 0
var singleCountNonZeroTypes = 0
for (digit in 1..9) {
if (digitCounts[digit] > 0) {
totalNonZeroTypes++
if (digitCounts[digit] == 1) {
singleCountNonZeroTypes++
}
}
}

var ans = 0
for (lastDigit in 0..8 step 2) {
if (digitCounts[lastDigit] == 0) {
continue
}

val originalCountOfLastDigit = digitCounts[lastDigit]
digitCounts[lastDigit]--

var availableNonZeroTypes = totalNonZeroTypes
var availableSingleNonZeroTypes = singleCountNonZeroTypes

if (lastDigit > 0) {
if (originalCountOfLastDigit == 1) {
availableNonZeroTypes--
availableSingleNonZeroTypes--
} else if (originalCountOfLastDigit == 2) {
availableSingleNonZeroTypes++
}
}

val hasZeroAvailable = digitCounts[0] > 0
if (hasZeroAvailable) {
ans += availableNonZeroTypes
}

val availableMultiNonZeroTypes = availableNonZeroTypes - availableSingleNonZeroTypes
ans += availableSingleNonZeroTypes * (availableNonZeroTypes - 1)
ans += availableMultiNonZeroTypes * availableNonZeroTypes

digitCounts[lastDigit]++
}

return ans
}
}