箭指offer笔记2

代码质量

Q. 数值的整数次方：实现函数double Power(double base, int exponent)，不得使用哭函数，不需要考虑大数问题。
A. 需要考虑特殊情况

• base = 0：0的任何次方均为0
• exponent = 0：任何数的0次方均为1，注意0^0没有数学意义，输出0或1均可
• exponent < 0：可以先对exponent取绝对值，求完幂次方后取倒数
• exponent 为小数：非法

$$
a^n = a^{n/2} \cdot a^{n/2} (n为偶数)
$$

$$
a^n = a^{(n-1)/2} \cdot a^{(n-1)/2} \cdot a (n为奇数)
$$

def PowerWithBitOperation(base: float, exponent: int):
    if base == 0:
        return 0
    if exponent == 1:
        return base

    # 用位运算来替换除以2的操作
    result = PowerWithBitOperation(base, exponent>>1)
    # 奇数偶数均需乘方
    result *= result
    # & 0x1替代取余操作，如果是奇数则需要再乘base
    if result & 0x1 == 1:
        result *= base

    return result

---

Q. 打印从1到最大的n位数
A. 思路：为了避免int溢出，需要用字符串模拟加法。本质上是一个全排列问题，一共n位数字，每一位数字可以排放0～9。

def Print1ToMaxOfNDigit(n: int):
    if n <= 0:
        return
    # list打印时第0位为最高位
    number = ['0' for i in range(n)]
    for i in range(10):
    	# 排放最高位，0不排放
        if i == 0:
            number[0] = str('')
        else:
            number[0] = str(i)
        Print1ToMaxOfNDigitRecursively(number, n, 0)

def Print1ToMaxOfNDigitRecursively(number: list, n: int, index: int):
	# 递归终点
    if index == n-1:
        print(number)
        return

    for i in range(10):
    	# 向下一位排放0～9
        number[index+1] = str(i)
        # 放好index+1后，向下一位递归
        Print1ToMaxOfNDigitRecursively(number, n, index+1)

---

Q. 给定单向链表的头指针pHead和一个节点指针pToBeDelete，在O(1)时间内删除链表的节点.
A. 思路：

• 常规思想：从pHead开始遍历，直到当前指针p->next == pToBeDelete时，执行p->next = pToBeDelete->next，但这样的复杂度为O(n)
• 解题思路：我们要删除节点pToBeDelete，可以把pToBeDelete->next的内容拷贝给pToBeDelete，再执行pToBeDelete->next = pToBeDelete->next->next，实现删除pToBeDelete->next即可。需要注意pToBeDelete为尾指针以及头节点的情况。

def deleteNode(head: ListNode, pToBeDelete: ListNode):
    # 待删除节点不是尾节点的情况
    if pToBeDelete.next != None:
        pToBeDelete.value = pToBeDelete.next.value
        pToBeDelete.next = pToBeDelete.next.next

    # 待删除节点为头节点且链表只有一个节点
    elif head.next == None:
        del head
        return None

    # 待删除节点为尾节点，只能通过遍历删除
    else:
        pTemp = head.next
        while pTemp.next != pToBeDelete:
            pTemp = pTemp.next

        pTemp.next = None

    return head

---

Q. 删除有序链表中的重复节点。
A. 思路：双指针，注意头节点重复的情况。

def deleteDuplocation(head: ListNode):
    if head == None:
        return
    if head.next == None:
        return head

    pPre = head
    pNext = head.next

    # 当pNext与pPre相等时，pNext向后移动，直到不同时，令pPre与pNext相连。
    while True:
        while pNext != None and pPre.value == pNext.value:
            pNext = pNext.next

        pPre.next = pNext
        if pNext == None:
            break
        else:
            pNext = pNext.next
            pPre = pPre.next

    return head

---

Q. 调整数组顺序使奇数位于偶数前面
A. 思路：双指针，分别从两端遍历。(拓展：可以把判断条件更换为独立判断函数，从而增加泛用性)

def ReorderOddEven(data: list):
    if data == None or len(data) == 0:
        return

    j = len(data) - 1
    i = 0
    while i!=j and i <j:
        if data[i] % 2 == 0 and data[j] % 2 == 1:
            data[i], data[j] = data[j], data[i]
            i += 1
            j -= 1

        elif data[i] % 2 == 1 and data[j] % 2 == 1:
            i += 1

        elif data[i] % 2 == 0 and data[j] % 2 == 0:
            j -= 1

        else:
            i += 1
            j -= 1

    return data

---

Q. 链表倒数第k个节点(相关题目：求链表中间节点)
A. 双指针法，第一个指针先走k步，然后两个指针一起走（第一个指针一次走两步，第二个一次走一步）。

def FindKthToTail(head: ListNode, k: int):
    if head == None or head.value == None or k <= 0:
        return

    p1 = head
    p2 = head
    for i in range(k):
        if p2.next != None:
            p2 = p2.next
        else:
            return

    while p2 != None:
        p1 = p1.next
        p2 = p2.next

    print(p1.value)
    return p1.value

---

Q. 链表中环的入口节点
A. 双指针法：

• 首先确定链表中是否有环：双指针，p1一次走一步，p2一次走两步，如果重合了就存在环路；
• 确认环的长度：假设p1p2重合的地方为pt，当p1再次走回pt时，则获得环的长度T；
• 让p1p2重置回头节点，p2先走T步，再一次向前走，p1p2相遇的位置即为环的入口。

---

Q. 反转链表，输入链表的头节点，反转该链表。
A. 思路：

• 如果要反转i->j->k->m…
• 先 记录k->…
• 再 掉转i->j为i<-j, 链表变为i->j k->m->…
• 再 记录反转链表j->i…
• 再 滑动正向链表k->m…
• p1=i, p2=j, p3=k

def ReverseList(head: ListNode):
    if head == None or head.value == None:
        return
    if head.next == None:
        return head

    # i
    p1 = head
    # j
    p2 = head.next
    p1.next = None
    while p2 != None:
    	# 记录k->...
        p3 = p2.next
        # 掉转i->j为i<-j
        p2.next = p1
        # 滑动反转链表j->i...
        p1 = p2
        # 滑动正向链表k->m...
        p2 = p3

    return p1

---

Q. 反转链表，递归实现
A.

• 先通过递归寻找到最后一个节点；
• i->j->…->k
• last承接反转完之后的头节点；
• i->j<-…<-k，此时j为last，i为head；
• head.next即为j，执行head.next.next = head实现i<-j<-…<-k；
• 最后返回当前链表的头节点

def reverse(ListNode head):
    if head.next == None:
    	return head
   	last = reverse(head.next)
    head.next.next = head
    head.next = None
    return last

---

Q. 合并两个排序的链表：输入两个递增排序的链表，合并后使得新链表的顺序仍然为递增。
A. 递归实现，每次滑动value更小的一根链表

def MergeList(p1: ListNode, p2: ListNode):
    if p1 == None:
        return p2
    elif p2 == None:
        return p1

    pNew = ListNode()
    if p1.value <= p2.value:
        pNew = p1
        pNew.next = MergeList(p1.next, p2)
    else:
        pNew = p2
        pNew.next = MergeList(p1, p2.next)

    return pNew

---

Q. 输入两个二叉树A和B，判断B是不是A的子结构。例如：

   A      B
   8      8
 8   7   9 2
9 2

A. 思路：

• 首先在A之中搜索与B的根节点值相同的入口节点；
• 如果找不到就递归A.left A.right；
• 找到相同根节点后（注意浮点数的判断）进入判断函数；
• 如果当前节点处相同，就分别递归A和B的左右子树；
• 如果B遍历空的话则寻找到，如果A遍历空的话则未能找到。

def HasSubtree(t1: TreeNode, t2: TreeNode):
    result = False
    if t1 != None and t2 != None:
        if t1.value == t2.value:
            result = DoesTreeEqual(t1, t2)
        if not result:
            result = HasSubtree(t1.left, t2)
        if not result:
            result = HasSubtree(t1.right, t2)

    return result

def DoesTreeEqual(t1: TreeNode, t2: TreeNode):
    if t2 == None:
        return True
    if t1 == None:
        return False

    result = False
    if t1.value == t2.value:
        result = DoesTreeEqual(t1.left, t2.left) and DoesTreeEqual(t1.right, t2.right)

    return result