# 使用两个指针，a 先遍历 k-1，之后一起遍历，直到a 指针到最后一个节点，则 b 为倒数 k 节点
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def find_k_to_tail(self, head, k):
        if not head and k <= 0:
            return None
        a_head = head
        b_head = None
        for i in range(k - 1):
            if a_head.next != None:
                a_head = a_head.next
            else:
                return None
        b_head = head
        while a_head.next != None:
            a_head = a_head.next
            b_head = b_head.next
        return b_head.val
    def find_k_to_tail2(self, head, k):
        if not head and k <= 0:
            return None
        a_head = head
        while a_head and (k - 1) >= 0:
            a_head = a_head.next
            k -= 1
        while a_head:
            a_head = a_head.next
            head = head.next
        return head.val
a = ListNode(1)
a.next = ListNode(2)
a.next.next = ListNode(3)
a.next.next.next = ListNode(4)
a.next.next.next.next = ListNode(5)
s = Solution()
print s.find_k_to_tail2(a, 3)

def reorder(nums, func):
    left, right = 0, len(nums) - 1
    while left < right:
        while not func(nums[left]):
            left += 1
        while func(nums[right]):
            right -= 1
        if left < right:
            nums[left], nums[right] = nums[right], nums[left]
def is_even(num):
    return (num & 1) == 0

def reorder2(nums):
    left = [num for num in nums if num & 1 != 0]
    right = [num for num in nums if num & 1 == 0]
    return left + right
nums = [1,2,3,4,5,6,7]
print reorder2(nums)

class ListNode(object):
    def __init__(self, x=None):
        self.val = x
        self.next = None
    def __del__(self):
        self.val = None
        self.next = None
class Solution(object):
    def delete_list(self, list_head, to_delete):
        if not list_head or not to_delete:
            return False
        if to_delete.next != None:
            next_node = to_delete.next
            to_delete.val = next_node.val
            to_delete.next = next_node.next
            next_node.__del__()
        elif list_head == to_delete:
            list_head.__del__()
            to_delete.__del__()
        else:
            list_node = list_head
            while list_node.next != to_delete:
                list_node = list_node.next
            list_node.next = None
            to_delete.__del__()
node1 = ListNode(10)
node2 = ListNode(11)
node3 = ListNode(13)
node4 = ListNode(15)
node1.next = node2
node2.next = node3
node3.next = node4
# Solution().delete_list(node1, node4)
Solution().delete_list(node1, node3)
print(node1.next.next.val)

# 将数组转换为字符
def print_number(number):
    is_beginning_0 = True
    num_len = len(number)
    for i in range(num_len):
        if is_beginning_0 and number[i] != "0":
            is_beginning_0 = False
        if not is_beginning_0:
            print("%c" % number[i], end="")
    print("")
# 边界条件：n > 0
def print_1_to_max_of_n1(n):
    if n <= 0:
        return 
    
    number = ["0"] * n
    while not increment(number):
        print_number(number)
# 从最后一位开始计算，如果 最后一位增长为10，则重置为 0，且进位；如果首位增长为 10，则溢出
def increment(number):
    is_carry = 0
    is_overflow = False
    sum = 0
    num_len = len(number)
    for i in range(num_len - 1, -1, -1):
        sum = int(number[i]) + is_carry
        if i == num_len - 1:
            sum += 1
        
        if sum >= 10:
            if i == 0:
                is_overflow = True
            else:
                sum -= 10
                number[i] = str(sum)
                is_carry = 1
        else:
            number[i] = str(sum)
            break
    return is_overflow
        
def print_1_to_max_of_n2(n):
    if n <= 0:
        return
    
    number = ["0"] * n
    for i in range(10):
        number[0] = str(i)
        print_1_to_max_of_n_recursively(number, n, 0)
# 始终找到最后一位，并将其计算
def print_1_to_max_of_n_recursively(number, num_len, index):
    if index == num_len - 1:
        print_number(number)
        return
    for i in range(10):
        number[index + 1] = str(i)
        print_1_to_max_of_n_recursively(number, num_len, index +1)
print_number(["0", "1", "1"])
print_1_to_max_of_n1(2)
print_1_to_max_of_n2(2)

# 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
# 考虑边界情况，base = 0, exponent < 0, exponent = 0 场景。
def equal_zero(num):
    if abs(num - 0.0) < 0.0000001:
        return True
def power(base, exponent):
    if equal_zero(base):
        result = False
    if exponent == 0:
        result = 1
    result = power(base, abs(exponent) >> 1)
    result *= result
    if abs(exponent) & 1 == 1:
        result *= base
    if exponent < 0:
        result = 1.0 / result
    return result
power_value(2, 2)

# Copyright (c) 2015 Marin Atanasov Nikolov <dnaeon@gmail.com>
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer
#    in this position and unchanged.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
# IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
"""
Core module
"""
import socket
import random
import struct
import time
__all__ = ['Tracer']
class Tracer(object):
    def __init__(self, dst, hops=30):
        """
        Initializes a new tracer object
        Args:
            dst  (str): Destination host to probe
            hops (int): Max number of hops to probe
        """
        self.dst = dst # 目标地址：域名或 IPv4 地址
        self.hops = hops 
        self.ttl = 1
        # Pick up a random port in the range 33434-33534
        # 对应上述解释，随机选择一个 > 30000 的端口用于连接
        self.port = random.choice(range(33434, 33535))
    def run(self):
        """
        Run the tracer
        Raises:
            IOError
        """
        try:
            dst_ip = socket.gethostbyname(self.dst) # 解析域名
        except socket.error as e:
            raise IOError('Unable to resolve {}: {}', self.dst, e)
        text = 'traceroute to {} ({}), {} hops max'.format(
            self.dst,
            dst_ip,
            self.hops
        )
        print(text)
        while True:
            startTimer = time.time()
            receiver = self.create_receiver() # 创建接收 socket 实例
            sender = self.create_sender() # 创建发送 socket 实例
            sender.sendto(b'', (self.dst, self.port)) # 向目标地址指定端口发送报文
            addr = None
            try:
                data, addr = receiver.recvfrom(1024) # 获取发送 ICMP 超时报文，并解析地址
                entTimer = time.time()
            except socket.error:
                pass
                # raise IOError('Socket error: {}'.format(e))
            finally:
                receiver.close()
                sender.close()
            if addr: # 如果获取到地址，则打印相应信息及用时
                timeCost = round((entTimer - startTimer) * 1000, 2)
                print('{:<4} {} {} ms'.format(self.ttl, addr[0]), timeCost)
                if addr[0] == dst_ip:
                    break
            else:
                print('{:<4} *'.format(self.ttl))
            self.ttl += 1 # 增加 TTL，获取下一跳地址
            if self.ttl > self.hops:
                break
    def create_receiver(self):
        """
        Creates a receiver socket
        Returns:
            A socket instance
        Raises:
            IOError
        """
        s = socket.socket(
            family=socket.AF_INET, # 指定 proto family 为 IPv4
            type=socket.SOCK_RAW, # 指定接收 socket 类型为 raw，这里是因为普通的 socket 类型无法处理 ICMP 报文
            proto=socket.IPPROTO_ICMP # 指定 socket 协议为 ICMP 协议，type 与 proto 需要特定的组合，不允许任意配置
        )
        timeout = struct.pack("ll", 5, 0)
        s.setsockopt(socket.SOL_SOCKET, socket.SO_RCVTIMEO, timeout)
        try:
            s.bind(('', self.port))
        except socket.error as e:
            raise IOError('Unable to bind receiver socket: {}'.format(e))
        return s
    def create_sender(self):
        """
        Creates a sender socket
        Returns:
            A socket instance
        """
        s = socket.socket(
            family=socket.AF_INET, # 指定 proto family 为 IPv4
            type=socket.SOCK_DGRAM, # 指定发送的类型为 UDP，即发送广播消息
            proto=socket.IPPROTO_UDP # 指定协议为 IP UDP 
        )
        s.setsockopt(socket.SOL_IP, socket.IP_TTL, self.ttl)
        return s