Python 算法姿势之字符串操作篇（二）

压缩字符串

实现一个算法来压缩一个字符串。压缩的要求如下：

• 需要判断压缩能不能节省空间，仅在压缩后字符串比原字符串长度更短时进行压缩。
• 压缩的格式是将连续相同字符替换为字符+数字形式，例如 "AAABCCDDDD" 变为 "A3BC2D4"。
• 判断传入的字符串是否需要进行压缩，如果不需要压缩，返回原字符串；
• 如果需要压缩，返回压缩后的字符串；
• 如果传入的字符串是 None 或者空字符串，返回 None 或者空字符串。

class CompressString(object):
    def __init__(self, str1):
        self.str1 = str1

    def compress(self):
        if self.str1 is None or not self.str1:
            return self.str1
        result = ''
        prev_char = self.str1[0]
        count = 0
        for char in self.str1:
            if char == prev_char:
                count += 1
            else:
                result += self._calc_partial_result(prev_char, count)
                prev_char = char
                count = 1
        result += self._calc_partial_result(prev_char, count)
        return result if len(result) < len(self.str1) else self.str1

    def _calc_partial_result(self, prev_char, count):
        return prev_char + (str(count) if count > 1 else '')


if __name__ == '__main__':
    aaa = CompressString("AAABCCDDDD")
    print(aaa.compress())

反转字符串中的字符

实现一个算法来实现反转字符数组的功能。反转的要求如下：

• 将字符数组的字符进行反转，例如 ['b', ' ', 'a', 'r'] 变成 ['r', 'a', ' ', 'b']。
• 将字符数组替换为反转后的数组。
• 对于传入的字符数组，将字符数组的字符进行反转和替换，并返回替换后的字符数组;
• 如果传入的字符数组是 None 或者空字符数组，返回 None 或者空字符数组。

class ReverseString(object):
    def __init__(self, chars):
        self.chars = chars


    def reverse(self):
        if self.chars:
            size = len(self.chars)
            for i in range(size // 2):
                self.chars[i], self.chars[size - 1 - i] = \
                    self.chars[size - 1 - i], self.chars[i]
        return self.chars


if __name__ == '__main__':
    aaa = ReverseString(['b', ' ', 'a', 'r'])
    print(aaa.reverse())

查找两个总和为特定值的索引

给定一个数组，找到两个总和为特定值的索引。

• 例如给定数组 [1, 2, 3, -2, 5, 7]，给定总和 7，则返回索引 [1, 4]。
• two_sum 函数接受两个参数，nums 用于指定传入的数组，val 用于指定和的值;
• two_sum 函数输出含两个索引的数组，或者 TypeError、 ValueError。
• 对于传入的数组 nums，返回总和为 val 的两个值的索引;
• 如果数组中没有和为目标值的元素，则返回 None。
• 如果传入的数组 nums 或者目标值 val 为 None，需要使用 raise 语句显示 TypeError。
• 如果传入的数组为空数组，需要使用 raise 语句显示 ValueError。

class Solution(object):
    def __init__(self, nums, val):
        self.nums = nums
        self.val = val

    def two_sum(self):
        if self.nums is None or self.val is None:
            raise TypeError('nums or target cannot be None')
        if not self.nums:
            raise ValueError('nums cannot be empty')
        cache = {}
        for index, num in enumerate(self.nums):
            cache_val = self.val - num
            if num in cache:
                return [cache[num], index]
            else:
                cache[cache_val] = index
        return None


if __name__ == '__main__':
    aaa = Solution([1, 2, 3, -2, 5, 7], 7)
    print(aaa.two_sum())