[数据结构与算法]算法趣题-Q14

一、问题描述

二、问题分析

? ? ? ? 解题石炉比较清晰，使用递归并计算其深度就行。问题在于如何更快地找到或者确认下一个国名，以及如何把末尾的字母大小写统一。

????????在Python的代码实现中，将所有的字母都大写，并且根据每个国名的首字母将其归类到字典中，使其在递归中可以更快地搜索；而在C/C++的代码中没有做对应的归类而是使用一个个遍历的办法进行搜索，并增加了一个标志标识该国名是否被使用过，而且在统一末尾字母时，只是将最后一个字符大写并附加到源字符串中，没有对字符串做整体的大写。

三、代码实现

1.C/C++实现

#include <iostream>
#include <map>
#include <cctype>

using namespace std;

string COUNTRY[] = { "Brazil", "Croatia", "Mexico",
                    "Cameron", "Spain", "Netherlands",
                    "Chile", "Australia", "Colombia",
                    "Greece", "Cote d'Ivoire", "Japan",
                    "Uruguay", "Costa Rica", "England",
                    "Italy", "Switzerland", "Ecuador",
                    "France", "Honduras", "Argentina",
                    "Bosnia and Herzegovina", "Iran", "Nigeria",
                    "Germany", "Portugal", "Ghana",
                    "USA", "Belgium", "Algeria",
                    "Russia", "Korea  Republic" };

map<string, bool> flags;  // 标识是否使用过

int tryNext(string last)
{
    int tmpL = 0;
    flags.at(last) = true;
    for (int i = 0; i < 32; i++)
    {
        if (flags.at(COUNTRY[i]) || (last[last.length() - 1] != COUNTRY[i][0]))
            continue;
        int newL = tryNext(COUNTRY[i]) + 1;
        tmpL = newL > tmpL ? newL : tmpL;
    }
    flags.at(last) = false;
    return tmpL;
}

int getLength()
{
    int tmpL = 0;
    for (int i = 0; i < 32; i++)
    {
        int newL = tryNext(COUNTRY[i]) + 1;
        tmpL = newL > tmpL ? newL : tmpL;
    }
    return tmpL;
}

int main()
{
    for (int i = 0; i < 32; i++)
    {
        int length = COUNTRY[i].length();
        COUNTRY[i] += toupper(COUNTRY[i].c_str()[length - 1]);
        flags[COUNTRY[i]] = false;
    }
    cout << getLength() << endl;
}

2.Python实现

# coding=utf-8

COUNTRY = ["Brazil", "Croatia", "Mexico",
           "Cameron", "Spain", "Netherlands",
           "Chile", "Australia", "Colombia",
           "Greece", "Cote d'Ivoire", "Japan",
           "Uruguay", "Costa Rica", "England",
           "Italy", "Switzerland", "Ecuador",
           "France", "Honduras", "Argentina",
           "Bosnia and Herzegovina", "Iran", "Nigeria",
           "Germany", "Portugal", "Ghana",
           "USA", "Belgium", "Algeria",
           "Russia", "Korea  Republic"]

m = {}  # 提取所有的首字符做成 map
for item in COUNTRY:
    tmp = item.upper()
    if tmp[0] in m.keys():
        m[tmp[0]].append(tmp)
    else:
        m[tmp[0]] = [tmp, ]


def get_length(ch):
    if ch not in m.keys() or len(m[ch]) == 0:
        return 0
    tmp_length = 0
    for country in m[ch]:
        m[ch].remove(country)
        tmp_length = max(tmp_length, get_length(country[-1]) + 1)
        m[ch].append(country)
    return tmp_length


if __name__ == '__main__':
    max_length = 0
    for key in m.keys():
        max_length = max(max_length, get_length(key))

    print(max_length)