剑指offer题的部分python实现

斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        a=0
        b=1
        for i in range(n):
            a,b = b,a+b 
        return a 

不要用递归，会超过限制导致超时通不过

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

不要用递归，会超时：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 1:
            return 1
        if number == 2:
            return 2
        return self.jumpFloor(number - 1) + self.jumpFloor(number - 2)

正确解法：

def jumpFloor(self, number):
    # write code here
    if number == 1:
        return 1
    if number == 2:
        return 2
    a, b = 1, 2
    i = 2
    while i < number:
        a, b = b, a + b
        i += 1
    return b

两个栈实现一个队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路

• 栈A用来作入队列
• 栈B用来出队列，当栈B为空时，栈A全部出栈到栈B,栈B再出栈（即出队列）

代码

class Solution:
    def __init__(self):
        self.stackA = []
        self.stackB = []
         
    def push(self, node):
        # write code here
        self.stackA.append(node)
         
    def pop(self):
        # return xx
        if self.stackB:
            return self.stackB.pop()
        elif not self.stackA:
            return None
        else:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
            return self.stackB.pop()

链表中倒数第K个节点

输入一个链表，输出该链表中倒数第k个结点。

分析

Python 设置两个指针，p1，p2，先让p2走k-1步，然后再一起走，直到p2为最后一个 时，p1即为倒数第k个节点

代码

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head==None or k<=0:
            return None
        #设置两个指针，p2指针先走（k-1）步，然后再一起走，当p2为最后一个时，p1就为倒数第k个 数
        p2=head
        p1=head
        #p2先走，走k-1步，如果k大于链表长度则返回 空，否则的话继续走
        while k>1:
            if p2.next!=None:
                p2=p2.next
                k-=1
            else:
                return None
        #两个指针一起 走，一直到p2为最后一个,p1即为所求
        while p2.next!=None:
            p1=p1.next
            p2=p2.next
        return p1

反转链表

输入一个链表，反转链表后，输出新链表的表头。

分析

遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。需要考虑链表只有1个元素的情况。图中有具体的每步迭代的思路，最后输出pre而不是cur是因为最后一次迭代后cur已经指向None了，而pre是完整的反向链表。

代码

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            return pHead
        
        prev = None
        cur = pHead
        while cur is not None:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        return prev

合并两个有序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

分析

• 比较两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前移动一个结点。
• 步骤一结果会有一个链表先遍历结束，或者没有
• 第三个链表尾结点指向剩余未遍历结束的链表
• 返回第三个链表首结点

代码

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        #初始化
        tmp = ListNode(0)
        pHead = tmp        
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                tmp.next = pHead1
                pHead1 = pHead1.next
            else:
                tmp.next = pHead2
                pHead2 = pHead2.next
            tmp = tmp.next
        if not pHead1:
            tmp.next = pHead2
        if not pHead2:
            tmp.next = pHead1
        return pHead.next

找数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

分析

第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即为敌人，同归于尽,count–；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一半即可。

代码

class Solution:
    """第二种，假设有这个数字，那么它的数量一定比其它所有数字之和还要多，按照这个思路得出num，然后验证
    """
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        num = numbers[0]
        count = 1
        for i in range(1, len(numbers)):
            if numbers[i] == num:
                count += 1
            else:
                count -= 1
            if count == 0:
                num = numbers[i]
                count = 1
        count = 0
        for i in numbers:
            if i == num:
                count += 1
        return num if count > len(numbers) / 2.0 else 0

或者

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        last = 0
        last_count = 0
        
        for num in numbers:
            if last_count == 0:
                last = num
                last_count += 1
            else:
                if num == last:
                    last_count += 1
                else:
                    last_count -= 1
        if last_count == 0:
            return 0
        else:
            last_count = 0
            for num in numbers:
                if num == last:
                    last_count += 1
            return last if last_count > len(numbers) // 2 else 0

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

分析&代码

class Solution:
    # 层次遍历
    def levelOrder(self, root):
        # write your code here
        # 存储最后层次遍历的结果
        res = []
        # 层数
        count = 0
        # 如果根节点为空，则返回空列表
        if root is None:
            return count
        # 模拟一个队列储存节点
        q = []
        # 首先将根节点入队
        q.append(root)
        # 列表为空时，循环终止
        while len(q) != 0:
            # 使用列表存储同层节点
            tmp = []
            # 记录同层节点的个数
            length = len(q)
            for i in range(length):
                # 将同层节点依次出队
                r = q.pop(0)
                if r.left is not None:
                    # 非空左孩子入队
                    q.append(r.left)
                if r.right is not None:
                    # 非空右孩子入队
                    q.append(r.right)
                tmp.append(r.val)
            if tmp:
                count += 1  # 统计层数
            res.append(tmp)
        return count

二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

分析

中序遍历的结果就是有序序列

代码

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        self.res=[]
        self.dfs(pRoot)
        return self.res[k-1] if 0<k<=len(self.res) else None
    def dfs(self,root):
        if not root:return
        self.dfs(root.left)
        self.res.append(root)
        self.dfs(root.right)

单链表去重

给定一个单链表，对其中元素进行去重

分析

• 给定一个头结点，把当前元素指针cur指向它
• 依次遍历啊链表中所有元素，如果有重复则删除对应节点
• 将cur指针后移一位，重复上面的过程直到链表尾

代码

def delete_repeat(self):
    # head指向头节点
    if self.is_empty():
        return
    elif self.length() < 3:
        return
    else:
        node = self.head
        while node.next is not None:
            prev_node = node
            cmp_node = node.next
            while cmp_node.next is not None:
                if node.val == cmp_node.val:  # 找到重复节点
                        prev_node.next = cmp_node.next
                        cmp_node = cmp_node.next
                else:
                    cmp_node = cmp_node.next
                    prev_node = prev_node.next
            node = node.next
        if cmp_node.val == node.val:
            prev_node.next = None