《剑指offer》 Day5

数值的整数次方

题目：实现函数 double power（double base, int exponent），求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

实现乘方的运算，考虑的情况包括：

• 底数为零，指数是负数
• 底数为零，指数也为零，这样的数没有意义，输出结果可以为0也可以为1
• 底数不为零，指数大于等于零
• 底数不为零，指数小于零

def power(base, exponent):
    
    # 判断底数是不是等于零并且指数为负
    if equal_zero(base) and (exponent < 0):
        raise ZeroDivisionError

    if exponent == 0:
        return 1
    
    # 判读指数位是否为负数
    abs_flag = False
    if exponent < 0:
        abs_flag = True
        exponent = int(-exponent)
    
    res = power_with_unsigned_exponent(base, exponent)
    if abs_flag:
        res = 1.0/res
    return res
# 判读浮点数是否等于零
def equal_zero(num):
    if abs(num) <= 0.00000001:
        return True
    return False

# 计算指数是正的时候的值
def power_with_unsigned_exponent(base, abs_exponent):
    res = 1.0
    for i in range(abs_exponent):
        res *= base
    
    return res

在不考虑大数的情况下，上述的解法，如果exponent为32的话，那么就需要执行31次乘法。那么如果我们要算 $num^{32}$num32 的话，如果知道 $num^{16}$num16，那么 $num^{32} = num^{16} \times num^{16}$num32=num16×num16。进一步的 $num^{16} = num^{8} \times num^{8}$num16=num8×num8，依次类推这样就可以大大的缩减乘法的次数。

def power_with_unsigned_exponent2(base:float, abs_exponent:int) -> float:
    
    if abs_exponent == 0:
        return 1.0
    if abs_exponent == 1:
        return base
    
    res = power_with_unsigned_exponent2(base, abs_exponent >> 1)
    res *= res
    
    if abs_exponent & 0x1 == 1:
        res *= base
    return res

打印从1到最大的n位数

题目：输入数字n，按顺序打印出从1到最大的n为十进制数。比如输入3，怎打印1、2、3一直到最大的3位数999.

python中已经对数进行了处理，所以我们可以直接写代码

def print_max_digits(n:int) -> None:
    if n <= 0:
        print(None)
    for i in range(10**n):
        print(i)

为了可以了解大数运算的机理，用python实现一下

def print_max_digits(n:int) -> None:
    '''打印从1到n的数
    '''
    if n <= 0:
        return
    
    global number
    number = ['0']*n
    
    while not increment(number):
        pirint_number(number)
        
def increment(number:list) -> bool:
    '''累加，并判断是否为最大值
    '''
    is_overflow = False
    n_take_over = 0
    n_length = len(number)
    
    for i in range(n_length-1, -1, -1):
        # 把每一位的值赋值给n_sum
        n_sum = int(number[i]) - 0 + n_take_over
        # 个位加1
        if i == n_length-1:
            n_sum += 1
        # 满10进位
        if n_sum >= 10:
            # 判读是否为最后一位
            if i == 0:
                is_overflow = True
            else:
                # 进位操作
                n_sum -= 10
                n_take_over = 1
                number[i] = str(0 + n_sum)
        else:
            # 无进位操作
            number[i] = str(0 + n_sum)
            break
    return is_overflow


def pirint_number(number:list) -> None:
    """打印数字
    在初始化数字中，前面的位进行了补'0'的操作，所以打印前要把前面的'0'去掉
    """
    is_beginning_0 = True
    n_length = len(number)
    
    for i in range(n_length):
        if is_beginning_0 and number[i] != '0':
            is_beginning_0 = False
            
        if not is_beginning_0:
            print(f'{number[i]}', end='')
    print()

同样的还可以采用递归的操作来进行输出打印，即0~9的随机数组合，遍历所有的情况。

def print_max_digits(n:int) -> None:
    if n <= 0:
        return 
    
    number = ['0']*n
    
    for i in range(10):
        number[0] = str(i)
        print_max_digits_recursively(number, n, 0)

def print_max_digits_recursively(number:list, length:int, index:int) -> None:
    # 跳出递归
    if index == length-1:
        print_number(number)
        return
    # 各位数随机组合
    for i in range(10):
        number[index+1] = str(i)
        print_max_digits_recursively(number, length, index+1)

def print_number(number:list) -> None:
    """打印数字
    在初始化数字中，前面的位进行了补'0'的操作，所以打印前要把前面的'0'去掉
    """
    is_beginning_0 = True
    n_length = len(number)
    
    for i in range(n_length):
        if is_beginning_0 and number[i] != '0':
            is_beginning_0 = False
            
        if not is_beginning_0:
            print(f'{number[i]}', end='')
    print()

删除链表的节点

题目一：在O(1)时间内删除链表节点

给定一个单项链表的头指正和一个节点指针，定义一个函数在O(1)时间内删除该节点。

# 定义节点类
class ListNode():
    def __init__(self, elem = None):
        self.elem = elem
        self.next = None

def delete_node(p_head:ListNode, p_delete_node:ListNode) -> ListNode:
    """删除链表中指定节点，并返回产生新链表的头节点
    """
    if (not p_head) or (not p_delete_node):
        return 
    
    # 要删除节点不是尾结点
    if (p_delete_node.next):
        # 先把下一个节点的值copy过来
        p_delete_node.elem = p_delete_node.next.elem
        # 改变当前节点要指向的地址
        p_delete_node.next = p_delete_node.next.next
    # 链表中只有一个节点
    elif p_delete_node == p_head:
        p_head = None
        p_delete_node = None
    # 链表中有多个节点，删除尾结点
    else:
        cur = p_head
        while cur.next != p_delete_node:
            cur = cur.next
        cur.next = None 
    return p_head
        
l1 = ListNode()
#l2 = ListNode(2)
#l3 = ListNode(3)
#l4 = ListNode(4)
#l5 = ListNode(5)

#l1.next = l2
#l2.next = l3
#l3.next = l4
#l4.next = l5


l = delete_node(l1, l1)

题目二：删除链表中重复的节点。

需要考虑的包括：

• 中间节点重复
• 头节点重复
• 尾结点重复
• 全重复、无重复

class ListNode():
    def __init__(self, elem=None):
        self.elem = elem
        self.next = None

def delete_duplication(p_head:ListNode) -> ListNode:
    '''删除链表中重复的元素，并返回删除后链表的头节点
    '''
    
    if not p_head:
        return
    
    p_pre_node = None
    p_node = p_head
    
    while p_node.next:
        p_next = p_node.next
        
        need_delete = False
        # 判读是否为重复的节点
        if (p_next != None) and (p_next.elem == p_node.elem):
            need_delete = True
        # 如果不是，指向下一个节点
        if not need_delete:
            p_pre_node = p_node
            p_node = p_node.next
        # 需要删除的节点
        else:
            value = p_node.elem
            p_del = p_node
            
            # 要删除的节点不是尾结点并且值相等
            while p_del.elem == value:
                p_next = p_del.next
                p_del = p_next
            # 是否为头节点
            if p_pre_node == None:
                p_head = p_next
            else:
                p_pre_node.next = p_next
            p_node = p_next
    
    return p_head

l1 = ListNode(1)
l2 = ListNode(1)
l3 = ListNode(1)
l4 = ListNode(1)
l5 = ListNode(1)
l6 = ListNode(1)
l7 = ListNode(1)

l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l5
l5.next = l6
l6.next = l7


l = delete_duplication(l1)