myAtoi Algorithm Analysis

🔍 アルゴリズム概要

Step 1

先頭空白スキップ

Step 2

符号判定

Step 3

数字変換

Step 4

範囲調整

計算量分析

時間計算量: O(n) - 文字列を一度走査

空間計算量: O(1) - 固定サイズの変数のみ

📝 Step 1: 先頭空白文字のスキップ

例: " -042"

' '

i=0

' '

-

0

4

2

→ スキップ後

' '

-

i=3

0

4

2

while i < len(s) and s[i]==' ' : i +=1 # 空白文字をスキップ

➕➖ Step 2: 符号の判定

符号判定パターン

負の符号

-

検出

4

2

sign = -1, i++

正の符号

+

検出

1

2

sign = 1, i++

符号なし

4

数字

2

sign = 1 (デフォルト)

                        if s[i] == '-': sign = -1 i += 1 elif s[i] == '+': sign = 1 i += 1 #
                        符号がない場合はsign = 1のまま
                    

🔢 Step 3: 数字の変換処理

例: "1337c0d3" → 1337

1

i=0

3

7

c

0

d

3

変換プロセス

i=0: '1'

result = 0 * 10 + 1 = 1

i=1: '3'

result = 1 * 10 + 3 = 13

i=2: '3'

result = 13 * 10 + 3 = 133

i=3: '7'

result = 133 * 10 + 7 = 1337

i=4で'c'に遭遇 → 変換終了

                        while i < len(s) and s[i].isdigit(): digit=int(s[i]) #
                        オーバーフローチェック if result> (INT_MAX - digit) // 10: return INT_MIN if
                        sign == -1 else INT_MAX result = result * 10 + digit i += 1
                    

⚠️ オーバーフロー対策

INT_MIN: -2³¹ = -2,147,483,648

範囲

INT_MAX: 2³¹-1 = 2,147,483,647

🚨 オーバーフロー検出ロジック

条件: result > (INT_MAX - digit) // 10

例: "2147483648" (INT_MAX + 1)

result = 214748364

digit = 8

(2147483647 - 8) // 10 = 214748363

214748364 > 214748363 ✓

オーバーフロー検出!

対応

sign == 1 なので

return INT_MAX

= 2,147,483,647

                        # 事前チェックでオーバーフローを防ぐ if result > (INT_MAX - digit) // 10:
                        return INT_MIN if sign == -1 else INT_MAX # この時点で安全に計算可能 result
                        = result * 10 + digit
                    

📊 実例による詳細分析

例1: "42"

4

2

Step 1: 空白なし

Step 2: 符号なし (sign=1)

Step 3: 42 変換

結果: 42

例2: " -042"

' '

-

0

4

2

Step 1: 空白スキップ

Step 2: '-' 検出 (sign=-1)

Step 3: 042 → 42 変換

結果: -42

例3: "words and 987"

w

o

r

d

s

Step 1: 空白なし

Step 2: 'w'は符号でない

Step 3: 最初から非数字

結果: 0

例4: "0-1"

0

-

1

Step 1: 空白なし

Step 2: '0'は符号でない

Step 3: '0'のみ変換、'-'で停止

結果: 0

⚡ パフォーマンス分析

時間計算量: O(n)

最良ケース

最初の文字が非数字

例: "abc123"

O(1)

平均ケース

部分的に数字を含む

例: "123abc"

O(k) (k: 数字の個数)

最悪ケース

全て有効な数字

例: "2147483647"

O(n)

空間計算量: O(1)

使用する変数は固定:

i: インデックス
sign: 符号
result: 結果
digit: 現在の数字

🎯 エッジケース対応

空文字列

入力: ""

出力: 0

理由: 数字が読み取れない

空白のみ

入力: " "

出力: 0

理由: 符号や数字がない

符号のみ

入力: "+" or "-"

出力: 0

理由: 数字が続かない

範囲外の値

入力: "2147483648"

出力: 2147483647

理由: INT_MAXでクランプ