leetcode_443

题目描述

给定一组字符，使用原地算法将其压缩。

压缩后的长度必须始终小于或等于原数组长度。

数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。

在完成原地修改输入数组后，返回数组的新长度。

解题思路

  1. 倒序遍历数组 -> 解决正序原地修改导致程序无法进行的问题

  2. 初始化计数器为1

  3. 遍历数组找到，并增加计数器直到当前字符与前一字符不相等则压缩一次字符串

  4. 重置计数器

  5. 当索引位置到第一个字符时由于前一字符为空应直接结束

代码示例

  1. 倒序的方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    class Solution:
        def compress(self, chars: list) -> int:
            '''
            @description: Given an array of characters, compress it in-place.
            @param {list} ["a","a","b","b","c","c","c"]
            @return: length of input list
            '''

            count = 1
            length = len(chars)
            for index in range(length-1, -1, -1):
                if index > 0 and chars[index] == chars[index-1]:
                    count += 1
                else:
                    end = index+count
                    chars[index: end] = [chars[index]] if count == 1 else [
                        chars[index]] + list(str(count))
                    count = 1
            return len(chars)

  2. 正序方式, 需要在最后删除所有在中间步骤添加的None

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
        def compress(self, chars: list) -> int:
            count = 1
            for index, char in enumerate(chars):
                if index < len(chars)-1 and char == chars[index+1]:
                    count += 1
                else:
                    # temp_l.append(char) if count == 1 else temp_l.extend([char, str(count)])
                    # print(chars)
                    temp_char = [char] if count == 1 else [char] + list(str(count))
                    interval = index+1 - (index-count+1)
                    temp_char += [None for i in range(interval-len(temp_char))]
                    chars[index-count+1: index+1] = temp_char
                    count = 1

            for i in range(len(chars)-1, -1, -1):
                if chars[i] is None:
                    del chars[i]
            print(chars)
            return len(chars)

思考

执行用时 : 64 ms , 在所有Python3提交中击败了 98.03% 的用户
内存消耗 : 13.1 MB , 在所有Python3提交中击败了 91.67% 的用户

总结 : 看似简单的一道算法题做起来感觉并不简答
期间尝试了各种方法但是总是不完美
最后觉得这个方法应该理解起来以及代码写起来是比较简单的

最后 : 算法题一定要多思考，顺着自己的思路才能找到答案