LeetCode1-5

## Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

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

Solution:

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

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

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

Solution:

divmod(x, y): 返回商和余数 (x//y, x%y).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
carry = 0 # 进位，初始值为0
result = n = ListNode(0)
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
carry, val = divmod(carry, 10)
n.next = ListNode(val)
n = n.next
return result.next

## Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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.

Solution:

class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
used = {}
start = max_length = 0
for i, c in enumerate(s):
if c in used and start <= used[c]:
start = used[c] + 1
else:
max_length = max(max_length, i - start + 1)
used[c] = i
return max_length

## Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

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

The median is 2.0

Example 2:

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

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

Solution:

(L + R)/2 = (A[(N-1)/2] + A[N/2])/2
N        Index of L / R
1               0 / 0
2               0 / 1
3               1 / 1
4               1 / 2
5               2 / 2
6               2 / 3
7               3 / 3
8               3 / 4

[6 9 13 18]  ->   [# 6 # 9 # 13 # 18 #]    (N = 4)
position index     0 1 2 3 4 5  6 7  8     (N_Position = 9)

[6 9 11 13 18]->   [# 6 # 9 # 11 # 13 # 18 #]   (N = 5)
position index      0 1 2 3 4 5  6 7  8 9 10    (N_Position = 11)

 [# 1 # 2 # 3 # (4/4) # 5 #]

[# 1 / 1 # 1 # 1 #]   

class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
INT_MAX = 999999999
INT_MIN = -INT_MAX
n1 = len(nums1)
n2 = len(nums2)
if n1 < n2:
return self.findMedianSortedArrays(nums2, nums1)
low, high = 0, n2 * 2
while low <= high:
mid2 = (low + high) // 2  # cut 2
mid1 = n1 + n2 - mid2  # cut 1
l1 = INT_MIN if mid1 == 0 else nums1[(mid1 - 1) // 2]
l2 = INT_MIN if mid2 == 0 else nums2[(mid2 - 1) // 2]
r1 = INT_MAX if mid1 == n1 * 2 else nums1[mid1 // 2]
r2 = INT_MAX if mid2 == n2 * 2 else nums2[mid2 // 2]
if l1 > r2:
low = mid2 + 1
elif l2 > r1:
high = mid2 - 1
else:
return (max(l1, l2) + min(r1, r2)) / 2
return -1


## Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example2:

Input: "cbbd"

Output: "bb"

Solution:

class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
l = len(s)
if l < 2:
return s
start = 0
max_length = 1
for i, c in enumerate(s):
if l - i <= max_length // 2:
break
j = k = i
while k < l - 1 and s[k + 1] == s[k]:
k += 1  # Skip duplicate characters.
while j > 0 and k < l - 1 and s[k + 1] == s[j - 1]:
j -= 1
k += 1
new_length = k - j + 1
if new_length > max_length:
max_length = new_length
start = j
return s[start:start + max_length]

⬆️

LeetCode-32 2018-10-22