剣指offerシリーズ-面接問題-5-スペースの置き換え(python)

文書ディレクトリ

1. タイトル

2. 解題構想

2.1考え方1

2.2考え方2

3. コード実装

3.1解法一

3.2解法二

4. まとめ

5. 参考文献

1.テーマ
文字列のスペースを「%20」に置き換える関数を実装してください.たとえば、「We Are Happy.」と入力します.We%20 Are%20 Happyが出力されます.
実際、URLに特殊文字(スペース、二重引用符、'#'など)があると、ブラウザが渡すパラメータが正しく認識されない可能性があります.そのため、これらの特殊文字を先に変換してからサーバに渡す必要があります.python 2のurllib.urlencode()は、クエリ文字列(dict)をサーバに変換するか、urllib.quoteを使用して文字列を直接変換します.
python 3ではurllib.parse.urlparse()メソッドを使用する必要があります.
2.問題の解き方 ， 。
問題を解く鍵は次のとおりです.
スペースは1文字のみで、"%20"は3文字であるため、スペースを"%20"に置き換えると、元のスペースの後の文字列の文字は2つ後ろに移動する必要があります.元の文字列の位置をできるだけ少なく移動する方法は、時間の複雑さを低減する鍵です.
2.1考え方1
直接前から後ろに回り、スペースに遭遇した場合は'%20'で置き換え、このスペースの後のすべての文字を2グリッド後ろに移動してループします.
時間複雑度O(n 2),空間複雑度S(1).
2.2考え方2
まず遍歴して、文字列のスペースの数を計算し、置換後の文字列の長さを事前に割り当てます.
後ろから先へ行って、文字列の中の文字の位置を事前に決めて、余分な文字を移動しません.
時間複雑度O(n),空間複雑度S(1).
3.コード実装
3.1解法一
pythonでのstrタイプは可変オブジェクトであるため,その場で修正することはできないが,アルゴリズムではlistオブジェクトを用いて置き換える.pythonでもリストに申請することはできません.pythonが自分でやったので、この考えを理解すればいいです.
構想1のコード実現:

class Solution:
    def __init__(self):
        pass

    def replace_blank(self, string):
        """    
        :param string
        :return None
        """
        if not isinstance(string, list):
            raise TypeError('string must be list type!')
        
        for char in string:
            if char == ' ':
                char = '%20'

        return ''.join(string)
                

if __name__ == '__main__':
    string = list('we are happy.')
    s = Solution()
    print(s.replace_blank(string))

3.2解法二
pythonのlistをcのstrとして使用します.
構想2のコードは以下のように実現される.

class Solution:
    def __init__(self):
        pass

    def replace_blank(self, string):
        """    
        :param string
        :return None
        """
        if not isinstance(string, list):
            raise TypeError('string must be list type!')

        blank_count = 0
        for i in string:
            if i == ' ':
                blank_count += 1
        
        new_length = len(string) + 2 * blank_count
        new_string = [None for i in range(new_length)]
        #          ，           ，            。
        index_old = len(string) - 1
        index_new = len(new_string) - 1

        while index_old >= 0 and index_new >= index_old:
            if string[index_old] == ' ':
                new_string[index_new] = '0'
                index_new -= 1
                new_string[index_new] = '2'
                index_new -= 1
                new_string[index_new] = '%'
                index_new -= 1
            else:
                new_string[index_new] = string[index_old]
                index_new -= 1
            index_old -= 1
        print(new_string)
        return ''.join(new_string)


if __name__ == '__main__':
    string = list('we are happy.')
    s = Solution()
    print(s.replace_blank(string))

4.まとめ
文字列を移動後に置き換えると、多くの文字が繰り返し移動し、時間の複雑さが大幅に増加します.
最後の文字列の長さを決定した後、後ろから前に置き換えると、要素の重複移動が回避され、すべての文字列が最大1回、一歩前進します.
5.参考文献
[1]剣指offer叢書[2]剣指Offer-有名企業の面接官が典型的なプログラミング問題を詳しく話す