1. Two Sum

整数の配列が与えられたとき、特定の目標に足し算されるような2つの数値のインデックスを返します。
各入力が正確に1つの解を持つと仮定して、同じ要素を2回使用することはできません。

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1_two_sum.py

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        h = {}
        for i, num in enumerate(nums):
            n = target - num
            if n not in h:
                h[num] = i
            else:
                return [h[n], i]

2. Add Two Numbers

2つの非負の整数を表す空ではない2つのリンクリストが与えられます。
数字は逆順に格納され、それぞれのノードには1桁の数字が含まれています。2つの数値を足し算して、リンクリストとして返します。
2つの数値には，0を除いて、先頭の0が含まれていないと仮定してもよい。

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

2_add_two_numbers.py

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        quotient = 0
        count = 0
                
        while l1 or l2 or quotient:            
            
            count += 1
            
            val1  = (l1.val if l1 else 0)
            val2  = (l2.val if l2 else 0)
            quotient, remainder = divmod(val1+val2 + quotient, 10)    
            
            if count == 1:
                first = ListNode(remainder)
                end = first
            else:
                end.next = ListNode(remainder)
                end = end.next                    
            
            l1 = (l1.next if l1 else None)
            l2 = (l2.next if l2 else None)
               
        return first

3. Longest Substring Without Repeating Characters

文字列が与えられたとき、文字を繰り返さずに最長の部分文字列の長さを求めなさい。

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

3_longest_substring_without_repeating_characters.py

class Solution:
    def lengthOfLongestSubstring(self, s):
        
        alphabet = {}

        start_id = 0
        max_length = 0

        for id, char in enumerate(s):

            if char in alphabet and alphabet[char] >= start_id:
                start_id = alphabet[char] + 1

            alphabet[char] = id
            length = id - start_id + 1

            if max_length < length:
                max_length = length

        return max_length

4. Median of Two Sorted Arrays

サイズmとnの2つのソートされた配列nums1とnums2がある。
2つの並べ替え配列の中央値を求めよ．全体の実行時間の複雑さは，O(log (m+n))でなければなりません。
nums1 と nums2 はどちらも空ではないと仮定してもよい。

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

4_median_of_two_sorted_arrays.py

class Solution:
    def findMedianSortedArrays(self,nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        sorted_joined = sorted(nums1 + nums2)
        if len(sorted_joined) % 2 == 0:
            index = int(len(sorted_joined) / 2)
            return (sorted_joined[index] + sorted_joined[index-1])/2.0
        else:
            index = (int(len(sorted_joined)/2))
            return sorted_joined[index]

5. Longest Palindromic Substring

文字列 s が与えられたとき、s の中で最も長い回文の部分文字列を見つけなさい。
s の最大長は1000であると仮定してもよい。

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

5_longest_palindromic_substring.py

class Solution:
    
    #   Manacher's algorithm
    
    def longestPalindrome(self, s):
        
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range (1, n-1):
            P[i] = (R > i) and min(R - i, P[2*C - i])
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1
            if i + P[i] > R:
                C, R = i, i + P[i]
        maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
        return s[(centerIndex  - maxLen)//2: (centerIndex  + maxLen)//2]

参考文献

GeeksforGeeks:Manacher’s Algorithm

6. ZigZag Conversion

"PAYPALISHIRING"という文字列は、このように所定の行数にジグザグパターンで書かれています。
(読みやすくするために、このパターンを固定フォントで表示するとよいでしょう)

P   A   H   N
A P L S I I G
Y   I   R

そして、一行ずつ読んでいくと "PAHNAPLSIIGYIR"。
文字列を受け取り、行数を指定してこの変換を行うコードを書いてください。

string convert(string s, int numRows);

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

P   A   H   N
A P L S I I G
Y   I   R

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

6_zigzag_conversion.py

class Solution:
    def convert(self, s, numRows):
        if numRows == 1:
            return s
        step = 1
        pos = 1
        lines = {}
        for c in s:
            if pos not in lines:
                lines[pos] = c
            else:
                lines[pos]+=c
            pos+=step
            if pos==1 or pos==numRows:
                step*=-1
        sol = ""
        for i in range(1, numRows+1):
            try:
                sol+=lines[i]
            except:
                return sol
        return sol

7. Reverse Integer

32ビット符号付き整数が与えられたとき、整数の逆数を計算します。

Input: 123
Output: 321

Input: -123
Output: -321

Input: 120
Output: 21

7_reverse_integer.py

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x > 0: 
            a =  int(str(x)[::-1])  
        if x <=0:
            a = -1 * int(str(x*-1)[::-1])  
        mina = -2**31  
        maxa = 2**31 - 1  
        if mina <= a <= maxa:
              return a
        else:
             return 0

8. String to Integer (atoi)

文字列を整数に変換する atoi を実装する。

この関数はまず、最初の空白以外の文字が見つかるまで必要なだけの空白文字を破棄します。そして、この文字から始めて、オプションの最初のプラスまたはマイナス記号の後に可能な限り多くの数字を続けて取り、それらを数値として解釈します。

文字列には、積分数を形成する文字の後に追加の文字を含めることができますが、これらの文字は無視され、この関数の動作には何の影響もありません。

strの最初の空白以外の文字列が有効な整数ではない場合、あるいは、 strが空であるか、空白文字しか含まれていないためにそのような文字列が存在しない場合、変換は実行されません。

有効な変換ができなかった場合、0の値が返されます。

注意

スペース文字 '' ' のみが空白文字とみなされます。
32ビット符号付き整数の範囲内の整数しか格納できない環境を扱っていると仮定します。
[−2^(31), 2^(31) − 1]. 数値が表現可能な範囲外の場合、INT_MAX (2^(31) - 1) または INT_MIN (-2^(31)) が返されます。

Input: "42"
Output: 42

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

8_string_to_integer_(atoi).py

class Solution(object):
    def is_num(self, str):
        try:
            float(str)
        except ValueError:
            return False
        else:
            return True
    
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        
        word = str.strip().split()      # extraction
        
        #==================================================
        
        if not word:
            return 0                    # case: ""

        #==================================================
        
        else:
            word = word[0]
            char = list(word)
            sign = 1
            
            #===============================================
            
            if char[0] == "-":          # minus sign
                if len(char) == 1:      # case: "-"
                    return 0            # [RETURN]
                else:
                    #char = char[1:]     # without sign
                    end_id = 2          # end id
                    sign = -1           # sign
                    
            #===============================================        

            elif char[0] == "+":        # plus sign
                if len(char) == 1:      # case: "+"
                    return 0            # [RETURN]
                else:
                    #char = char[1:]     # without sign
                    end_id = 2          # end id
                    
            #===============================================
            
            else:
                end_id = 1              # end id
                
            #===============================================

            for id in range(end_id, len(word)+1):
                
                if not self.is_num(word[0:id]):
                    if id == end_id:
                        return 0
                    break
                num = word[0:id]
            
            #===============================================

            a = int(float(num))
            
            #===============================================
            
            mina = -2**31
            maxa = 2**31 - 1
            
            #===============================================

            if mina <= a <= maxa:
                return a
            elif mina > a:
                return mina
            else:
                return maxa

9. Palindrome Number

整数が回文かどうかを判定します。
整数は、後ろ向きと前向きが同じ読み方をすると回文になります。

Input: 121
Output: true

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

9_palindrome_number.py

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        return str(x) == str(x)[::-1]

10. Regular Expression Matching

入力文字列 (s) とパターン (p) が与えられた場合、'.' と '*' をサポートした正規表現マッチングを実装します。

'.'：任意の1文字にマッチします。
'*'：前の要素のうち、0個以上の要素にマッチします。

マッチングは入力文字列全体をカバーしなければなりません（部分的なものではありません）。

注意

s は空、もしくは、小文字の a-z だけを含むことができます。
p は空、もしくは、小文字の a-z と . や * のような文字のみを含むことができます。

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

10_regular_expression_matching.py

class Solution(object):
    def isMatch(self, text, pattern):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)

11. Container With Most Water

n 個の非負の整数 a1, a2, ..., an があるとき，それぞれ座標 (i, ai) の点を表す．x軸と一緒に容器を形成する2本の線を求め，その容器が最も多くの水を含むようにしなさい．

注意

容器を斜めにしてはいけない、ｎは２以上である。

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

11_container_with_most_water.py

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        water = 0
        head = 0
        tail = len(height) - 1

        for cnt in range(len(height)):

            width = abs(head - tail)

            if height[head] < height[tail]:   
                res = width * height[head]
                head += 1
            else:
                res = width * height[tail]
                tail -= 1

            if res > water:
                water = res

        return water

14. Longest Common Prefix

文字列の配列の中から、最も長い共通接頭辞文字列を見つける関数を書きます。
共通接頭辞がない場合は、空の文字列 "" を返します。

Input: ["flower","flow","flight"]
Output: "fl"

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

注意

すべての入力は小文字のa-zである。

14_longest_common_prefix.py

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        prefix = ""
        
        if len(strs)==0: return prefix

        for i in range(len(min(strs))):
            
            c=strs[0][i]
            
            if all(a[i]==c for a in strs):
                
                prefix+=c
                
            else:
                
                break
                
        return prefix

16. 3Sum Closest

n 個の整数の配列 nums と整数のターゲットが与えられた場合、nums の中から和がターゲットに最も近くなるような 3 つの整数を求めます。3つの整数の和を返します．それぞれの入力が正確に1つの解を持つと仮定してもよい。

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

条件

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

16_3sum_closest.py

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        diff = float('inf')
        nums.sort()
        for i in range(len(nums)):
            lo, hi = i + 1, len(nums) - 1
            while (lo < hi):
                sum = nums[i] + nums[lo] + nums[hi]
                if abs(target - sum) < abs(diff):
                    diff = target - sum
                if sum < target:
                    lo += 1
                else:
                    hi -= 1
            if diff == 0:
                break
        return target - diff

19. Remove Nth Node From End of List

リンクされたリストが与えられた場合、リストの末尾からn番目のノードを削除し、その先頭を返します。

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

注意

与えられたnは常に有効です。

19_remove_nth_node_from_end_of_list.py

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        length, count, dummy = 1, 1, head
        while dummy.next:
            length, dummy = length + 1, dummy.next
        dummy = head
        if length == n: return head.next
        while count < length - n:
                count, dummy = count + 1, dummy.next
        dummy.next = dummy.next.next
        return head

20. Valid Parentheses

文字 '(', ')', '{', '}', '[' および ']' だけを含む文字列が与えられた場合、入力された文字列が有効かどうかを判断します。

入力文字列は、以下の場合に有効です。

オープンブラケットは、同じ種類のブラケットで閉じなければなりません。
開いているカッコは、正しい順序で閉じなければなりません。

空の文字列も有効とみなされることに注意してください。

Input: "()"
Output: true

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

20_valid_parentheses.py

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

22. Generate Parentheses

n組の括弧が与えられたとき、形の整った括弧のすべての組み合わせを生成する関数を書きなさい。

例えば、n = 3が与えられると、解の集合は次のようになります。

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

22_generate_parentheses.py

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = []
        def backtrack(S = '', left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append(S)
                return
            if left < n:
                backtrack(S+'(', left+1, right)
            if right < left:
                backtrack(S+')', left, right+1)

        backtrack()
        return ans