【20210407华为机试】第一题：N个小朋友分组 Python和C++实现

题目描述

幼儿园老师安排小朋友做游戏，现在需要给N个小朋友进行分组，老师让每个同学写一个名字，代表这位小朋友想和谁分到一组，请问老师在满足所有小朋友意愿的情况下，最多可以将班级分成多少组？

输入描述：

第一行输入N，0<N<100000
接下来是N行代表每个小朋友希望和谁分到一组，如“John Jack”，代表John希望和Jack分到一组，两个名字之间以空格分隔，名字本身不存在空格。

输出描述：

分组的最多数量

示例1

输入
6
Jack Tom
Alice John
Jessica Leonie
Tom Alice
John Jack
Leonie Jessica

输出
2

示例2

输入
3
Xiaoming Xiaohong
Xiaohong Xiaoqiang
Xiaoqiang Xiaoming

输出
1

代码思路

采用两个hashmap存储，一个存储小朋友key要与小朋友val的组队情况，一个存储小朋友是否被组队。

data_map =  {
    'a'    :'b',
              'b'    :'a',
              'c'    :'a'}
visit_map = {
    'a'    :False,
              'b'    :False,
              'c'    :False }

Python 代码

class Solution0407_hw_01(object):
    def __init__(self):
        super(Solution0407_hw_01, self).__init__()
        self.data_map  = {
   }
        self.visit_map = {
   }


    def input_data(self, Debug=False):
        if Debug:
            self.data_map =  {
    'Jack'    :'Tom',
                               'Alice'   :'John',
                               'Jessica' :'Leonie',
                               'Tom'     : 'Alice',
                               'John'    :'Jack',
                               'Leonie'  :'Jessica'}
            self.visit_map = {
    'Jack'    :False,
                               'Alice'   :False,
                               'Jessica' :False,
                               'Tom'     :False,
                               'John'    :False,
                               'Leonie'  :False }
        else:
            nums = input("input n = ")

            for i in range(int(nums)):
                sample = input(f"idx {i + 1} name such as 'Jack Tom' : ")
                key, val = sample.split(" ")
                self.data_map[key]  = val
                self.visit_map[key] = False

    def output_info(self):
        counts = self.dfs()
        print(f"all gropus : {counts}")

    def dfs(self):
        count = 0
        add_count = False
        for key, val in self.data_map.items():
        
            # [Jack Tom]
            # visit[Tom] not False
            while not self.visit_map[val]:
                self.visit_map[val] = True
                key = val
                val = self.data_map[key]
                add_count = True

            if add_count:
                add_count = False
                count += 1

        return count



if __name__ == '__main__':
    soluter = Solution0407_hw_01()
    # Debug=True 方便调试
    # soluter.input_data(Debug=True)
    # Debug=False 手动输入
    soluter.input_data(Debug=False)
    soluter.output_info()

C++ 代码

#include <iostream>
#include <stdio.h>
#include <map>
#include <limits>
#include <vector>

using namespace std;


class Solution_hw_01
{
   
public:
    Solution_hw_01() {
   }
    // 输入数据
    void input_data(bool debug=false);
    // 结果显示
    void output_info();
    // 计算数量
    int dfs();
    // 分割字符 string -> vector<string> 如 "Tom Jack" -> ["Tom", "Jack"]
    vector<string> split(string s);

private:
    map<string, string> data_map;
    map<string, bool> visit_map;
};

void Solution_hw_01::input_data(bool debug)
{
   
    if(debug)
    {
   
        this->data_map.insert(make_pair("Jack"    ,"Tom"    ));
        this->data_map.insert(make_pair("Alice"   ,"John"   ));
        this->data_map.insert(make_pair("Jessica" ,"Leonie" ));
        this->data_map.insert(make_pair("Tom"     ,"Alice"  ));
        this->data_map.insert(make_pair("John"    ,"Jack"   ));
        this->data_map.insert(make_pair("Leonie"  ,"Jessica"));


        this->visit_map.insert(make_pair("Jack"    ,false));
        this->visit_map.insert(make_pair("Alice"   ,false));
        this->visit_map.insert(make_pair("Jessica" ,false));
        this->visit_map.insert(make_pair("Tom"     ,false));
        this->visit_map.insert(make_pair("John"    ,false));
        this->visit_map.insert(make_pair("Leonie"  ,false));

    }
    else
    {
   
        //input data

        int n;
        printf("input num n : ");
        cin >> n;

        // Tom jack
        string input_str;
        // cin.ignore(numeric_limits<streamsize>::max(), '\n');
        cin.ignore();
        for(int i = 0; i < n; i++)
        {
   
            printf("input %d names such as Tom Jack : ", i+1);
            getline(cin, input_str);

            vector<string> db_str = this->split(input_str);
            this->data_map.insert(make_pair(db_str[0], db_str[1]));
            this->visit_map.insert(make_pair(db_str[0], false));
        }
        return;
    }
}

int Solution_hw_01::dfs()
{
   
    int count = 0;
    bool add_count = false;

    string key;
    string val;
    for(auto item : this->data_map)
    {
   
//        cout << "key : " << item.first << " val : " << item.second << endl;
        key = item.first;
        val = item.second;

        while (!this->visit_map[val])
        {
   
            this->visit_map[val] = true;
            key = val;
            val = this->data_map[key];

            // 标记可以添加
            add_count = true;
        }


        //计数
        if(add_count)
        {
   
            count++;
            add_count = false;
        }
    }

    return count;
}

void Solution_hw_01::output_info()
{
   
    int counts = this->dfs();
    cout << "all gropus : " << counts << endl;
}

vector<string> Solution_hw_01::split(string s)
{
   
    vector<string> ret;

    int mid = -1;
    for(int i = 0; i < s.size(); i++)
    {
   
        if(s[i] == ' ')
        {
   
            mid = i;
            break;
        }
    }

    string ret1, ret2;
    ret1.append(s, 0, mid);
    ret2.append(s, mid+1, s.size()-mid-1);

    ret.push_back(ret1);
    ret.push_back(ret2);
    return ret;
}


int main(int argc, char *argv[])
{
   
    Solution_hw_01 sol;
    // true : 方便用于调试
//    sol.input_data(true);
    // false : 可以键盘输入
    sol.input_data(false);
    sol.output_info();

    return 0;
}