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
文字 '(', ')', '{', '}', '[' および ']' だけを含む文字列が与えられた場合、入力された文字列が有効かどうかを判断します。
入力文字列は、以下の場合に有効です。
1. オープンブラケットは、同じ種類のブラケットで閉じなければなりません。
2. 開いているカッコは、正しい順序で閉じなければなりません。
空の文字列も有効とみなされることに注意してください。
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