剑指offer 解题思路简述总结篇1-10_剑指offer解题思路速览

• 面试题3，数组中重复的数字

方法一：排序后从头开始依次比较相邻的两个是否相等，相等即重复，nlogn

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        pre = nums[0]
        for index in range(1, len(nums)):
            if pre == nums[index]:
                return pre
            pre = nums[index]

方法二：利用新的存储空间set类型，挨个取数据看是否已经存在set中，存在return，不存在add，n

方法三：从头开始遍历num，将每个数的数值x和它的下表i进行比较，不等则将num[i]和num[x]进行比较，相等则return，不相等则交换，交换后仍重复上述过程，直到数值和下表相等，n

class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            while nums[i] != i:
                if nums[nums[i]] == nums[i]:
                    return nums[i]
                nums[nums[i]] , nums[i] = nums[i] , nums[nums[i]]
        
        return None
 

• 面试题4，二维数组中的查找

方法：从右上角的数x开始比较，若需要查找的数大于x，则行数加1，若小，则列数减1

也可以选左下角

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if len(array[0])==0:return False
        hang = len(array[0])
        lie = len(array[1])
        i=0
        j=lie-1
        while(i<hang and j>=0):
            if array[i][j]==target:return True
            if array[i][j]>target:
                j=j-1
            else:
                i=i+1
            
        return False   

• 面试题5，替换空格

方法1:‘We are happy’.replace(' ','%20')

方法2：遍历空格的数量，求出字符串变化之后的长度，从字符串的后面开始复制和替换，设置两个指针，一个是变换后的长度的最后p1，一个是字符串的最后p2，当碰到空格，p1处加上替换字符，p2处往前挪一个，当p1和p2只向同一个位置说明可以结束。字符串都是不可变的类型，这个方法的意义在哪里。。。。

方法3:将字符串变成list，从头开始遍历把‘ ’换成‘%20’；或者建一个空list，扫瞄到空格就append‘%20’，否则就append对应的s

class Solution(object):
    def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        s = list(s)
        for i in range(len(s)):
            if s[i] == ' ':
                s[i] = '%20'
        return ''.join(s)

相似题目：

• 面试题6，从尾到头打印链表

方法一：从头读取链表，保存在list中，每次指定位置insert新的节点值list.insert(位置，数值)

方法二：用俩个list，一个从头到尾存储值，结束后，pop出每个值到另一个list中

方法三：在方法二前半段的基础上直接调用reverse()或者[::-1]

• 面试7，重建二叉树

方法：递归，每次从根据前序遍历中的根节点将中序遍历和前序遍历分成两部分，递归处理这两部分

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0 or len(tin)  == 0:
            return None
         
        if len(pre) == 1:
            return TreeNode(pre[0])
        root = TreeNode(pre[0])
         
        index = tin.index(pre[0])
        left_pre = pre[1:index+1]
        left_tin = tin[0:index]
        root.left = self.reConstructBinaryTree(left_pre, left_tin)
         
        right_pre = pre[index+1:]
        right_tin = tin[index+1:]
        root.right = self.reConstructBinaryTree(right_pre, right_tin)
        return root

• 面试题8:二叉树的下一个节点

方法：分情况讨论，如果有右子树的话，找到右子树中的左子叶节点，如果没有的话，找到第一个该节点是其左子节点的节点

class Solution:
    def GetNext(self, pNode):
        # write code here
        if not pNode:
            return None
        if pNode.right: #有右子树
            res = pNode.right
            while res.left:
                res = res.left
            return res
        while pNode.next:#无右子树，则找第一个当前节点是父节点左孩子的节点
            temp = pNode.next
            if temp.left == pNode:
                return temp
            pNode = temp#沿着父节点向上遍历
        return None

• 面试题9:两个栈实现队列

方法：分别创建两个list，stack1和stack2，append方法直接往stack1中append，delete方法中先判断stack2是否为空，是的话将stack1中的元素全部压到stack2中，输出stack2的栈顶元素

# -*- coding:utf-8 -*-
#栈1进栈，栈2出栈
#当栈2为空，现将栈1的全部放入栈2
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if self.stack2==[]:
            while self.stack1!=[]:
                temp=self.stack1.pop()
                self.stack2.append(temp)
        return self.stack2.pop()

相似问题：两个队列实现栈

方法：分别创建两个list，queue1和queue2，append方法直接往queue1中append，delete方法先 把queue1中的元素放入到queue2中只剩一个元素，弹出该元素，完成后将queue1和queue2互换，以供下一次用

• 面试题10:斐波那契数列

方法：不要用递归，当n大于2开始，设置m,n两个数，temp=m+n，m=n，n=temp

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

相似问题：

方法：和斐波那契数列一模一样

方法：1-1,2-2,3个台阶时是2个台阶的2倍，4个台阶的时候是3个台阶的2倍

方法：斐波那契数列