leecode168 周赛

leecode5291 统计位数为偶数的数字

给你一个整数数组 nums，请你返回其中位数为偶数的数字的个数。

输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字

输入：nums = [555,901,482,1771]
输出：1 
解释： 
只有 1771 是位数为偶数的数字。

1 <= nums.length <= 500
1 <= nums[i] <= 10^5

思路 1：c++，位数是除以 10，而判断是否偶数是对 2 取余判断是否为 0。

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int findNumbers(vector<int>& nums) {
    int res=0;
    for(auto num: nums){
        int weishu=1;
        while(num / 10 > 0){
            weishu ++;
            num /= 10;
        }
        cout<<weishu<<endl;
        if(weishu % 2 == 0){
            res ++;
        }
    }
    return res;
}

int main(){
    vector<int> test1 = {12,345,2,6,7896};
    int res = findNumbers(test1);
    cout<<res<<endl;
    return 0;
}

思路 2：Python，遍历 nums 里的数字。将数字转换为 string。判断 string 的长度对 2 取余是否为 0，是 0 则取 1，否则取 0（表示位数不是偶数）。再将是偶数的数字求和 sum。

def findNumbers(nums: List[int]) -> int:
        return sum(1 if len(str(x)) % 2 == 0 else 0 for x in nums)

leecode5292 划分数组为连续数字的集合

给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
如果可以，请返回 True；否则，返回 False。

实例1
输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

示例2
输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
输出：true
解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。

示例3 
输入：nums = [3,3,2,2,1,1], k = 3
输出：true

示例4
输入：nums = [1,2,3,4], k = 3
输出：false
解释：数组不能分成几个大小为 3 的子数组。

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

思路 1：简单基本思路，将 nums 里的最小取出来，然后每次取 [min,min+k] 的值，不断从原 nums 里去除掉。如果可以这样去空原 nums 则返回 true，否则只要有值不在 nums 里，则返回 false。（但这个方法的时间复杂度太高 $O (kn^2)$ ）

# -*- coding:utf-8 -*-
def isPossibleDivide(nums, k):
	"""
	:type nums: List[int]
	:type k: int
	:rtype: bool
	"""
	if (len(nums) % k != 0):
		return False

	while (len(nums) != 0):
		# each list
		for x in range(min(nums), min(nums)+k):
			if x in nums:
				nums.remove(x)
			else:
				return False
	return True


if __name__ == '__main__':
	nums = [3,2,1,2,3,4,3,4,5,9,10,11]
	k = 3
	res = isPossibleDivide(nums,k)
	print(res)

进一步，用 hash 优化查找 x in nums。(c++ 中的 map 是平衡二叉树)，排序时间复杂度 $O (nlogn)$ ，

#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

bool isPossibleDivide(vector<int>& nums, int k) {
    if (nums.size() % k != 0) {
        return false;
    }
    
    sort(nums.begin(), nums.end());
    map<int,int> hash;
    for(auto num:nums) hash[num]++;
    int groups = nums.size() / k;
    //group nums
    for (int i=0; i<groups; i++) {
        int min_index = 0;
        while (hash[nums[min_index]] == 0) {
            min_index++;
        }
        //if min~min+k is not in nums, false
        int start = nums[min_index];
        for (int j=start; j<start+k; j++) {
            if (hash[j] == 0) {
                return false;
            }
            else hash[j]--;
        }
    }
    return true;
}

int main(){
    vector<int> test2 = {1,2,3,2,3,3,4,4,5,9,10,11};
    int res2 = isPossibleDivide(test2,3);
    cout<<res2<<endl;
    return 0;
}

思路 3。新学习了 multiset。避免了 while 这一段找 min_index（见上），直接在 multiset 里查找并去掉，时间要短一点点，但空间用的要更多（因为 multiset 允许存储重复元素）

bool isPossibleDivide2(vector<int>& nums, int k) {
    if (nums.size() % k != 0) {
        return false;
    }
    multiset<int> s;
    for(auto num:nums) s.insert(num);
  	//multiset<int> s(a.begin(), a.end());
    for (int i=0; i<nums.size() / k; i++) {
        int min = *s.begin();
        for (int j=min; j<min+k; j++) {
            if (s.find(j) == s.end()) {
                return false;
            }
            s.erase(s.find(j));
        }
    }
    return true;
}