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

输入规模小，直接暴力就能过。

class Solution {

public:

    int totalNumbers(vector<int>& digits) {

        // 找到得到的不同三位偶数的数量

        // 输入规模很小，可以直接暴力

        // 末位肯定得是一个偶数

        unordered_set<int> nSet;

        int n=digits.size();

        int res=0;

        for(int k=0;k<n;k++){

            if((digits[k]&1)==1){

                continue;

            }

            for(int j=0;j<n;j++){

                if(j==k){

                    continue;

                }

                int num=digits[k]+digits[j]*10;

                for(int i=0;i<n;i++){

                    if(j==i||k==i||digits[i]==0){

                        // 不能有前导零

                        continue;

                    }

                    int tmp=num+digits[i]*100;

                    if(nSet.count(tmp)==0){

                        res++;

                        nSet.insert(tmp);

                    }

                }

            }

        }

        return res;

    }

};

直接暴力循环。不过看到一种更优解，根据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

    }

}