Codility每周一课：P92.2 SocksLaundering

0.png

P92.2 SocksLaundering
From drawers containing both clean and dirty socks, choose socks to launder in order to obtain the maximum number of clean pairs of socks.

P92.2 洗袜子
给定一些不同颜色的干净、脏袜子，如何洗袜子使得成双的袜子最多

鲍勃去旅行，他想尽可能地多带几双干净的袜子。每只袜子都有颜色，一双袜子的颜色应该相同。袜子分为2类：干净的和脏的。鲍勃只有一次洗袜子的机会，他的洗衣机一次最多能洗K只袜子。他想挑选一些脏袜子来洗，保证洗完后使得干净的、成双的袜子数量最多。有些颜色袜子可能无法与其他袜子搭配，因此鲍勃可能会丢掉一些。

鲍勃有N只干净的袜子和M只脏的袜子，分别在数组C和D中描述。袜子的颜色表示为整数（相等的数字表示相同的颜色）。

例如，假设有4只干净的袜子和5只脏的袜子：

image

如果鲍勃的洗衣机最多能洗2双袜子，那么他最多能穿3双干净的袜子。他可以洗一只红袜子和一只绿袜子，分别是1号和2号。然后他会有两双红袜子和一双绿袜子。

编写函数：

def solution(K，C，D)

给定一个整数K（洗衣机一次可以清洗的袜子的最大数量），两个数组C和D（分别表示N个干净袜子和M个脏袜子的颜色），则返回鲍勃可以在旅行中穿的袜子的最大双数。

例如，假设K=2，C=[1，2，1，1]和D=[1，4，3，2，4]，函数应该返回3。

假设：

K是区间[0..50]内的整数；
数组C,D的每个元素都是区间[1..50]内的整数；
C和D不是空的，每个元素最多包含50个元素。

在解决方案中，关注正确性，性能不是评估的重点。

解题思路

首先计算干净袜子中可以组成的双数，剩下的不能组成双的就是剩下一只，记录下这些袜子的颜色。然后在脏袜子中优先选择这些颜色的来洗。每洗一只，最终的袜子数就多1，相应的K就减少1。如果K不小于2，然后再洗剩下的脏袜子，当没有脏袜子，或者K小于2的时候，就停止计算。

Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 92：Tasks from Indeed Prime 2016 College Coders challenge
# P 92.2 SocksLaundering


def solution(K, C, D):
    """
    :param K: 洗衣机一次可以洗的袜子的最大只数
    :param C: 干净袜子
    :param D: 脏袜子
    :return: 可以得到的最大的干净袜子的双数
    """
    # 首先获得干净袜子中的双数
    pair_sock = 0
    sock_dict = {}
    for i in list(set(C)):
        count = C.count(i)
        pairs = count // 2
        pair_sock += pairs
        rest = count % 2
        if rest:
            sock_dict[i] = 1

    # 脏袜子
    sock_dict_dark = {}
    for j in D:
        if j in sock_dict_dark:
            sock_dict_dark[j] += 1
        else:
            sock_dict_dark[j] = 1

    # 开始洗袜子
    if K == 0:
        return pair_sock
    for h in sock_dict:
        if h in sock_dict_dark:
            pair_sock += 1
            sock_dict_dark[h] -= 1
            if sock_dict_dark[h] <= 1:
                del sock_dict_dark[h]
            K -= 1
            if K == 0:
                return pair_sock

    #  计算sock_dict_dark里面的最大双数
    if K < 2 or len(sock_dict_dark) == 0:
        return pair_sock

    for r in sock_dict_dark:
        number = sock_dict_dark[r]
        n = number // 2
        d = min(n, K // 2)
        K -= 2 * d
        pair_sock += d
        if K <= 1:
            break
    return pair_sock

结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image

最后编辑于：2019.03.21 13:53:26