def reverse_list(node)
previous_node = None
while node:
node_next = node.next
node.next = previous_node
previous_node = node
node = node_next
return previous_node
def find_mid(head)
if not head or not head.next:
return head
slow = head
fast = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow
#4个member return 2nd
- remove all nodes in a head
def remove_vowel(head)
fake_node = ListNode(None)
fake_next = head
curr = fake_node
while curr.next:
if curr.next.val in ['a', 'e']:
curr.next = curr.next.next
else:
curr.next = curr.next.next
return fake_node.next
- add two linkedlist 大数相加
64位: 64个二进制，CPU可进行的最大位数的运算
def add(head1, head2)
a = reverse_list(head1)
b = reverse_list(head2)
fake_node = ListNode('fake_head')
cur_node = fake_head
carry = 0
while a and b
temp = a.val + b.val +carry
carry = temp / 10
cur_node.next = ListNode(temp_sum % 10)
cur_node = cur_node.next
a = a.next
b = b.next
while a
temp = a.val + carry
carry = temp / 10
curr_node.next = ListNode(carry % 10)
curr_node = curr_node.next
a = a.next
while b
temp = b.val + carry
carry = temp / 10
curr_node.next = ListNode(carry % 10)
curr_node = curr_node.next
b = b.next
if carry > 0:
cur_node.next = ListNode(carry)
return reverse_list(fake_head.next)
#time O(n) space O(n)
- determine if a list is palindrome(回文)
def is_palindrome(head):
fake_head = ListNode('fake_head')
fake_head.next = head
mid_node_prev = find_mid(fake_node)
mid_node = mid_node_prev.next
mid_node_prev.next = None
head1 = head
head2 = reverse_list(mid_node)
while head1 and head2:
if head1.val != head2.val:
return False
head1 = head1.next
head2 = head2.next
return True
#time O(n) space O(1)
- takes a nonnegative integer and returns the largest integer whose square is less than or equal to the given integer
#binary search in [1, n/2]
def square_root(n):
if n<=0:
return n
left, right = 0, n/2
while left < right - 1: #建议所有binary search都这么写，一定会返回[left, right]两个元素的list
mid = left + (right - left)/2 #avoid overflow
mid_sq = mid*mid
if mid == n:
return mid
if mid < n:
left = mid
else:
right = mid
return right if right*right <= n else left
- what if the input is a real number?
def square_root_real(n, eps):
left, right = 1.0, n*1.0/2
if n < 1.0:
left, right = n*1.0, 1.0
while True:
mid = left + (right - left) / 2
midsq = mid*mid
if abs(midsq - n)/n < eps:
return mid
elif midsq > n:
right = mid
else:
left = mid
return left
