Leetcode每日一题 —— 3876. 构造奇偶一致的数组 II

写复杂了（

class Solution {

public:

    bool uniformArray(vector<int>& nums1) {

        sort(nums1.begin(),nums1.end());

        auto judget = [&](bool f) -> bool {

            bool ok = false;

            for(int i = 0; i < nums1.size(); i++) {

                if(nums1[i] % 2 == 1) {

                    if(!f && !ok) {

                        return false;

                    }

                    ok = true;

                } else if(!ok && f) {

                    return false;

                }

            }

            return true;

        };

        return judget(0) | judget(1);

    }

};

相比昨天多了一个要求：相减操作后必须是正整数。

我们要进行操作的话，要不把整个数组变成偶数，要不把整个数组变成奇数。但是观察发现，只要有一个奇数存在，就不可能全部变成偶数（同偶异奇决定）。

因此我们只用考虑全变成奇数的操作，全变成奇数时，根据题目条件限制，最小的奇数肯定是不会有变化的，因此我们可以看看其他所有偶数减去这个最小奇数能不能得到正整数，依此判断。

class Solution {

public:

    bool uniformArray(vector<int>& nums1) {

        // 这回要求如果相减，获得的值必须是正整数

        // 位于每个位置 i，我需要看有没有更小的数字让当前值变成符合要求的奇数或者偶数

        // 可以发现，如果 nums1 中有奇数，是不可能全变成偶数的，只能想办法全变成奇数



        // 如果存在奇数，那么最小的奇数肯定不会变，我们所有变成奇数的运算都可以利用这个最小的奇数

        bool allEven=true;

        int minOdd=1000000001;

        for(int num:nums1){

            if((num&1)==1){

                // 遇到奇数

                allEven=false;

                minOdd=min(minOdd,num);

            }

        }

        if(allEven){

            // 全部已经是偶数，直接为 true

            return true;

        }

        // 否则尝试全变成奇数

        for(int num:nums1){

            if((num&1)==0&&num-minOdd<1){

                // 是偶数且运算得不到正整数

                return false;

            }

        }

        return true;

    }

};

今天的题目中所有的数必须要是同奇偶，但是只能由大的数减去小的数或者维持本来的数。因此数组中最小的数不能通过减法改变奇偶性，于是数组中所有处理后的数都需要和数组中最小的数奇偶性相同。这里会有两种情况：

• 最小数为奇数：任何情况都可以达成条件，因为奇数 = 奇数，偶数 - 最小的奇数 = 奇数


• 最小数为偶数：数组中不能出现奇数，因为数组中最小的奇数只能减去偶数，但奇数 - 偶数 = 奇数，无论如何都不能变成偶数

//代码可以只用一次循环解决（但是懒了）

    public bool UniformArray(int[] nums1)

    {



        int minVal = nums1.Min();

        if (minVal % 2 == 1) return true;

        return !nums1.Any(x => x % 2 == 1);

    }

Kotlin每日打卡（脑筋急转弯，在昨天easy题上构造）：

class Solution {

    fun uniformArray(nums1: IntArray): Boolean {

        var minEvenNum = Int.MAX_VALUE

        var minOddNum = Int.MAX_VALUE

        for (num in nums1) {

            if (num and 0x1 == 1) {

                minOddNum = minOf(minOddNum, num)

            } else {

                minEvenNum = minOf(minEvenNum, num)

            }

        }

        return minOddNum == Int.MAX_VALUE || minOddNum < minEvenNum

    }

}