算法题-统计字符个数（Python题解）

文章目录

前言
思路
code

前言

先前笔试做了一道算法题，题目是这样子的：（PS：不用惊讶，是的，我不打算24今年考研了，一是，当初填报的学校不是我想要去的学校（当初想一战成硕，选了个稳点的学校），二是，最近经历了一些事情让我意识到，成为那个学校的研究生，并不能实现我的预想，大概率下可能还是会回到Java开发，或者其他的开发。至于算法工程师，基本上不用想了。那么竟然如此，在考研上继续浪费时间显然是不值得的。已经错过秋招了，没办法，现在只能想着补救了，或者春招了）当然后不后悔呢，说实话，绕了一圈有点后悔，错误的估计了当前形势。但是通过这段时间的备研，我觉得还是学到了不少东西的，最少除了开发，我把408好好过了过，对于里面的思想有了更深刻的理解。这对于以后的技术提高是有很大帮助的，当然花几个月的时间学那确实有点亏。当然也好在，技术一直没有落下，在暑假打比赛的时候就写了一大半的毕设。后面赶上也很快，复杂的部分都写完了。

那么废话不多说，先来看题吧：
在这里插入图片描述

思路

这里的话，我们可以直接先简单模拟一遍：
例如：X2Y3XZ ，设S为记录个数

1.-> X 此时：S={X:0} (第一次出现，记录为0，解析出后面的数字)
2. ->2 此时：S={X:2}（解析出了后面的数字）
3.->Y 此时：S={X:3,Y:3}
4.->X 此时：S={X:3,Y:3} （此时S[x]=S[x]+1,后面没有解析到数字时）
5.->Z 此时：S={X:3,Y:3,Z:1} (同理)

最后按序输出即可。

那么对于：
存在嵌套的情况：
例如：Z4(Y2(XZ2)3X3

先统计出括号内部的元素（先考虑单层括号的情况，此时先记录计算出里面的元素个数，方法同第一种情况一致。此时将这一组记录看作是一个元素，然后按照外层的方式再处理）
对于括号内有括号嵌套的情况，这里采用递归的方式继续进行处理，得到一组记录，然后再将这一组记录看作是一个元素，同上述处理。

那么思路上的话，我们就非常明确了，你可以发现，这个其实就是一个基本的模拟题，但是里面需要注意的细节是比较多的，但是不管怎么说，时间复杂度是0(n)的。所以这里我们就可以很快的写出代码。

code

ok,这里我们刚刚明确了思路，所以我们来看到代码：
（由于代码有注释，那么这里就不多废话了）



def count_chars(input_str):
    """
    负责统计字符个数
    :param input_str:
    :return:
    """
    char_count = {}
    count_chars_helper(input_str, 1, char_count)
    output = ""
    sorted_keys = sorted(char_count.keys())
    for key in sorted_keys:
        output += key + str(char_count.get(key))
    return output


def count_chars_helper(input_str, count, char_count):
    """
    处理括号翻倍的情况，匹配
    :param input_str:
    :param count:
    :param char_count:
    :return:
    """
    i = 0
    while i < len(input_str):
        c = input_str[i]
        if c == '(':
            #找到（XXXX)，然后方面记录里面的元素的个数，方面后面做统计累加
            end_index = find_matching_parenthesis(input_str, i)
            num = get_number_after_parenthesis(input_str, end_index + 1)
            # 处理嵌套括号的问题
            count_chars_helper(input_str[i + 1:end_index], count * num, char_count)
            i = end_index + len(str(num))
        elif c.isalpha():
            # 对统计出的这一组元素*后面的数字的处理，然后累加
            num = get_number_after_parenthesis(input_str, i + 1)
            char_count[c] = char_count.get(c, 0) + count * num
        i += 1


def find_matching_parenthesis(input_str, start_index):
    """
    找到与左括号匹配的右括号的位置
    :param input_str:
    :param start_index:
    :return:
    """
    count = 1
    for i in range(start_index + 1, len(input_str)):
        c = input_str[i]
        if c == '(':
            count += 1
        elif c == ')':
            count -= 1
            if count == 0:
                return i
    return -1


def get_number_after_parenthesis(input_str, start_index):
    """
    获取括号后面的数字
    :param input_str:
    :param start_index:
    :return:
    """
    end_index = start_index
    while end_index < len(input_str) and input_str[end_index].isdigit():
        end_index += 1
    return int(input_str[start_index:end_index]) if end_index > start_index else 1



if __name__ == "__main__":
    print(count_chars("X2Y3XZ"))
    print(count_chars("Z3X(XY)2"))
    print(count_chars("Z4(Y2(XZ2)3)2X2"))