二刷剑指offer (上）——1- 20题

1 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        if not array:
            return False
        if not array[0]:
            return False
        lenth = len(array[0])
        for i in range(len(array)):
            if target == array[i][0]:
                return True
            elif i<len(array)-1 and target <= array[i+1][lenth-1] and target >= array[i][0]:
                for j in array[i]:
                    if j == target:
                        return True
                for j in array[i+1]:
                    if j == target:
                        return True
            elif i == len(array):
                for j in array[i-1]:
                    if j == target:
                        return True
        return False

误区：对于每一行或者每一列是递增的，但是不等于对于整体是递增的

思路：每两行，开始跟最后一个元素是最大和最小的，因此每次都比较两行，确定位置后找出是否含有该数

易错点：不仅空array要判断，空array[0]即  [[]]  这种情况同样需要判断；注意数组最后一位是array[len(arrray)-1)]，从而避免溢出；二维数组每一行是一个单位；and判断也有顺序，比如先判断i<len-1再进行后面判断，否则报错；等于是两个等号，不能手滑。

官方思路：

* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，

* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移

* 要查找数字比左下角数字小时，上移

即找出分布规律，不断地缩小查找范围

2 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

def replaceSpace(self, s):
        s = s.split(' ')   #此时s变为list
        strs = '%20'.join(s)   #list变为字符串       
        return strs

思路：利用split对空格进行了切分，再利用join函数将List连接成字符串。实际上是python特有的一种解法。

注意：由于是一个字符变为三个字符，因此每个空格都要将str往后移动两位腾出空间，因此时间复杂度高。书中采用的先统计空格数目，确定总长度，之后两个指针向前移动。字符串是不可变对象,你不能用下标赋值的方式去改变字符串 。

逆序遍历：一种方法理解起来绕一点，从列表最后一位下标的元素往前循环，步长为-1，直到数组下标为0的元素。从效率上来说比前一种更好，因为不需要更多的内存开销来存放reversed(list)副本。

>>> for i in range(len(lista)-1,-1,-1):
    print(lista[i])  

range(start, stop[, step])

参数说明：

• start: 计数从 start 开始。默认是从 0 开始。例如range（5）等价于range（0， 5）;
• stop: 计数到 stop 结束，但不包括 stop。例如：range（0， 5） 是[0, 1, 2, 3, 4]没有5
• step：步长，默认为1。例如：range（0， 5） 等价于 range(0, 5, 1），步长可以为 -1

3 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

def printListFromTailToHead(self, listNode):
        if not listNode:
            return []
        p1 = listNode
        res = []
        out = []
        while p1:
            res.append(p1.val)
            p1 = p1.next
        while res:
            out.append(res.pop())
        return out

思路：反向链表，想到用栈来解决。python中的栈很方便，用List的pop就可

补充：pop() 函数用于移除列表中的一个元素（默认最后一个元素，即-1），并且返回该元素的值。pop(0)则变成了队列

语法

pop()方法语法：

list.pop([index=-1])

参数

• index -- 可选参数，要移除列表元素的索引值，不能超过列表总长度，默认为 index=-1，删除最后一个列表值

另外，还可用递归来实现。

4 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

 def reConstructBinaryTree(self, pre, tin):
        if not pre:
            return None
        elif len(pre) ==1:
            return TreeNode(pre[0]) #要有return 
        else:
            res = TreeNode(pre[0])
            res.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
            res.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:])
        return res

思路：可以先画一棵二叉树，写出其前序与中序遍历，可以看出根据前序遍历的根得到划分条件；注意递归的停止条件，注意切片时候需要+1。注意index函数的用法。

index() 函数用于从列表中找出某个值第一个匹配项的索引位置。

index()方法语法：

list.index(obj)

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

def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self,node):
        self.stack1.append(node)
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        elif not self.stack1:
            return None
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
                

思路：将1往2中弹，之后2最上边的就是队列的pop

注意：list只有append而不是push，注意定义的方法，注意self，注意 stack1为空的情况

6 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        else:
            for i in range(len(rotateArray)-1):
                if rotateArray[i] > rotateArray[i+1]:
                    return  rotateArray[i+1]

思路：暴力法，直到下一个值小于上一个值

def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        left = 0
        mid = len( rotateArray)//2
        while mid -left > 1:
            left = 0
            mid = len( rotateArray)//2
            if rotateArray[left] < rotateArray[mid]:
                rotateArray = rotateArray[mid:]
            elif rotateArray[left] > rotateArray[mid]:
                rotateArray = rotateArray[:mid+1]
            else:
                pass
                return min(rotateArray)
        #return min(rotateArray[left],rotateArray[mid])
        return rotateArray[mid]

思路：借用了二分查找的思想，比较左边与中间的值，如果相等则只能用传统方法。若一直不等，则最后可以用二分查找得出顺序。注意最后返回的是Mid还是left的值。

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

n<=39

        if n ==0: #递归超时
            return 0          
        elif n ==1 or n ==2:
            return 1
        return self.Fibonacci(n-1)+self.Fibonacci(n-2)

思路：递归解决，注意or前后都得有 n==

问题：运行超时

res = [0,1,1]
        j = 1
        while n>j:
            res.append(res[j]+res[j+1])
            j = j+1
        return res[n]
        

思路：采用循环生成的方法，注意的是while的结束值，以及别忘了j要加1（与for循环区别开来）

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

        res = [0,1,2]
        j = 1
        while  number>j:
            res.append(res[j]+res[j+1])
            j = j+1
        return res[number]

思路：本题可以从一层台阶开始递推，会发现其实也是一个斐波那契数列，所以跟上题的解决方式相同。发现while的结束值不重要，只要大于j就行，但是最后return的值要验证下是否正确。

8 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        #return 2**(number-1)
        return 2**(number-1)

思路：借鉴评论区的一句话——每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共用2^(n-1)中情况，或者说这青蛙是个神仙（因为他的步长时没限制的），他要做的是从第0个台阶（也就是地面）到第n个，所以第n个是必须踩的，前n-1个踩不踩看心情，都有踩/不踩两种选择，所以是2^(n-1）

9 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        if not number:
            return 0
        res = [0,1,2]
        j = 1
        while j<number:
            res.append(res[j]+res[j+1])
            j = j+1
        return res[number]

思路：依旧是斐波那契数列，分析见评论区的此图。

注意：不要忘了j = j+1，否则会陷入无限循环

这类题目注意初始数组的值很重要

10 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

 count = 0
        if n<0:
            n = n & 0xffffffff
        while n:
                n = n&(n-1) #相与
                count = count+1
        return count 

思路：规律：把一个整数减去1，再和原来整数相与，会把最后边的1变成0

注意：当int大于32位的时候，用更大的数long存储从而导致不能到0，理论上python可以处理无限大的数，因此会无限循环下去，从而超时。所以（来自评论区用户@polaris95）n = n & 0xffffffff，在Python中，数的大小是可以无限扩大的，不会像Java或c++中，数超过32位会溢出，而是继续扩张，所以对于一个负数而言，进行了这个操作，实际上是提取了负数的后32位（在计算机中以补码形式存在），前面的任意位呢，则变成了0，比如说 -1，一开始是 111.....(n个1)...11111111，进行与运算之后，得到，00....(n个0)....111111111（32个1），变成了含32个1的正数，然后就不用担心负数陷入死循环

补码：负数为原码符号位不变，其余的按位取反再加一。p计算机中 CPU 内一般是以补码的形式计算数据，python 显示在终端的变量值是原码转换成的数值。python的位运算参考https://blog.csdn.net/u013061183/article/details/78525807

11 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方

if exponent>=0:
            res = 1
            for i in range(exponent):
                res = res*base
            return res
        elif exponent < 0 and base ==0:
            return None
        else:
            res = 1
            for i in range(abs(exponent)):
                res = res*base
            res = 1/res
            return res

思路：主要考察分类讨论，尤其是exponent小于0的情况，与base等于0的情况。

注意点：range(2)里的循环是两次而不是三次，因为是从0开始，1结束，而不是0，1，2  ；

              注意exponent小于零 的时候要求绝对值

              可以优化效率避免重复计算，快速幂计算：https://blog.csdn.net/hkdgjqr/article/details/5381028

12 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变

        odd = []
        even = []
        for i in array:
            if i%2 ==0:
                even.append(i)
            else:
                odd.append(i)
        res = odd+even
        return res

思路：一遍过的解法，用两个数组分别存储奇数跟偶数，最后合并得到新的数组

扩展：不考虑顺序，可用头尾双指针法；函数的解耦，可以提高代码的重用性

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

if not head or not k:
            return None
        res = []
        p1 = head
        while p1:
            res.append(p1)
            p1 = p1.next
        if k <= len(res):
            return res[-k]
        else:
            return None

思路：顺序遍历链表并存储在res中，最后判断输出

易错：存储的是结点而不是val，注意为空跟k大于长度的情况的讨论

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

思路：快慢指针法，一指针先走K步，然后再一起行进

易错：判断为空的情况。判断k是不是大于链表长度了

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

        if not pHead:
            return None
        last = None
        p1 = pHead
        while p1:
            pnext = p1.next
            p1.next = last
            last = p1
            p1 = pnext
            
        return last

思路：三个指针，分别是P，P前，P后，尤其注意要有P后来保存下一个值。

易错点：一定要注意，last一开始None，也就是链表的最后一个值指向的是空，再者要注意，四行语句的顺序。先保存p为last。再p移动到next。最后注意返回的应该是last，也就是将最后一个节点返回。跳出来的时候p1已经不存在了，所以不能返回p1。

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

        newlist = ListNode(0)
        first = newlist
        p1 = pHead1
        p2 = pHead2
        while p1 and p2:
            if p1.val<p2.val:
                newlist.next = p1
                newlist = newlist.next
                p1 = p1.next
            else:
                newlist.next = p2
                newlist = newlist.next
                p2 = p2.next
        if p1:
            newlist.next = p1
        if p2:
            newlist.next = p2
        return first.next

思路：建立一个新的节点，之后从p1p2头遍历。哪个小则哪个加到新链表，同时往后一一位。

易错点：新建节点的时候需要传入参数。最后返回的是first之后。

if not pHead1:
    return pHead2
if not pHead2:
    return pHead1
if pHead1.val<pHead2.val:
    pHead1.next = self.Merge(pHead1.next,pHead2)
    return pHead1
else:
    pHead2.next = self.Merge(pHead1,pHead2.next)
    return pHead2

思路：对于每个节点来说，都是将小的添加进去，可采用递归的方法。

易错点：要加self，递归思想的理解。

16  输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

def HasSubtree(self, p1, p2):
        if not p1 or not p2:
            return False
        res = False
        if p1.val ==p2.val:
            res = self.Son(p1,p2)
        if not res:
            res = self.HasSubtree(p1.left,p2)
        if not res:
            res = self.HasSubtree(p1.right,p2)
        return res
    def Son(self,p1,p2):
        if not p2:
            return True
        if not p1 and p2:
            return False
        if p1 and p2:
            if p1.val ==p2.val:
                return self.Son(p1.left,p2.left) and self.Son(p1.right,p2.right)
            else:
                return False
            

思路;分成两个函数，一个负责遍历A找与B的根相同的结点，找到之后，遍历两个树，判断是否相等。都采用递归可以解决。

易错点：遍历的写法，尤其是注意，什么时候结束递归(基准条件）。

17 操作给定的二叉树，将其变换为源二叉树的镜像

if not root:
    return None
temp = root.left
root.left = root.right
root.right = temp
self.Mirror(root.left)
self.Mirror(root.right)
#return root

思路：一遍通过。运用递归，不断的交换左右，记得用一个值保存作为过渡。

易错点：看清递归截止的条件，要用temp作为交换的过渡。只要变换完就可以，不用返回值。

18 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

        out = []
        if len(matrix) ==1:
            return matrix[0]
        while matrix:
            if len(matrix) ==1:
                out = out + matrix[0]
                break
            for i in range(len(matrix[0])):
                out.append(matrix[0].pop(0))
            matrix.pop(0)
            if matrix and matrix[0]:
                for i in range(len(matrix)):
                    out.append(matrix[i].pop())
            if matrix:
                for i in range(len(matrix[0])):
                    out.append(matrix[-1].pop()) 
            matrix.pop()
            if matrix and matrix[0]:
                for i in range(len(matrix)-1,0,-1):
                    out.append(matrix[i].pop(0)) 
        return out

思路：不断的弹出，缩小矩阵，加到out里

易错点：只剩一行的时候单独讨论，注意matrix[0]仍然是个list，在pop完后是个[]，需要pop走。

range的用法：100到1 的 遍历

for i in range(100,0,-1):
    print(i)

pop默认是-1，也就是最后一个值，pop(0)才是pop出第一个元素。

上边思路的代码优化：

        out = []
        while matrix:
            # 上边界即为数组的第一个子数组（而不是列！！）
            out += matrix.pop(0) #弹出第一行
            # 如果这里仅判断if matrix，那么对于测试数组例[[1],[2],[3]]，循环后变成了[[],[]]，            
            matrix不为空
            if matrix and matrix[0]:
                # 右边界即为数组每一项的最后一个元素
                for row in matrix:
                    out.append(row.pop())
            # 下边界即为数组最后一个子数组的逆序排列
            if matrix:
                out += matrix.pop()[::-1]  #逆序
            if matrix and matrix[0]:
                # 左边界即为数组从尾到头的每一项子数组的第一个元素
                for row in matrix[::-1]: #行的逆序
                    out.append(row.pop(0)) #行的第一个元素
        return out

注意：matrix为空跟matrix[0]为空并不等同。如[[]]。

思路2：链接：https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a
来源：牛客网

可以模拟魔方逆时针旋转的方法，一直做取出第一行的操作

例如 

1 2 3

4 5 6

7 8 9

输出并删除第一行后，再进行一次逆时针旋转，就变成：

6 9

5 8

4 7

继续重复上述操作即可。

Python代码如下

链接：https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a
来源：牛客网

class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        result = []
        while(matrix):
            result+=matrix.pop(0)
            if not matrix or not matrix[0]:
                break
            matrix = self.turn(matrix)
        return result
    def turn(self,matrix):
        num_r = len(matrix)
        num_c = len(matrix[0])
        newmat = []
        for i in range(num_c):
            newmat2 = []
            for j in range(num_r):
                newmat2.append(matrix[j][i])
            newmat.append(newmat2)
        newmat.reverse()
        return newmat

只考虑第一行就行了，很秀的思路，复杂度有点高。

19 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

    def __init__(self):
        self.stack = []
        self.assist = []
    def push(self,node):
        min1 = self.min()
        if not min1 or min1>node:
            self.stack.append(node)
            self.assist.append(node)
        else:
            self.stack.append(node)
            self.assist.append(min1)
    def pop(self):
        if self.stack:
            self.stack.pop()
            self.assist.pop() 
    def top(self):
        if self.stack:
            return self.stack[-1]  
    def min(self):
        if self.assist:
            return self.assist[-1]
        
    

思路：新建一个与stack等大的辅助栈，记录最小值。把每次的最小元素（之前的最小元素和新入栈的元素之间的较小值）都保存起来存入另一个辅助栈。跟下图类似，不同的是把不压入改成压入之前最小的那个。这样方便一起弹出。

易错点： init的用法；带self，不论是变量还是函数；注意pop（改变原栈）与stack[-1]（只是读取）的区别。注意在操作时先检查是否存在不为空。

20 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

        stack = []
        while popV:
            if pushV: 
                if not stack or stack[-1]!=popV[0]: 
                    stack.append(pushV.pop(0))
                    #popV.pop(0) 
                elif stack[-1] == popV[0]:
                    stack.pop()
                    popV.pop(0)
            else:
                if stack[-1] == popV[0]:
                    stack.pop()
                    popV.pop(0)
                else:
                    popV.pop(0) 
        #print(stack)
        if stack:
            return False
        else:
            return True

思路：用一个辅助栈，当栈顶与pop的开始不同，往里添加，当顶层与pop[0]相同，则一起弹出，当pushV弹出完毕，则开始小曲popV,继续抵消，之后退出看stack是否还有剩下的元素，有的话则不行。

易错点： pushV与popV是pop(0)，stack是pop() ，可以在纸上来模拟过程，

评论区同思路代码：

链接：https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
来源：牛客网

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size() == 0) return false;
        vector<int> stack;
        for(int i = 0,j = 0 ;i < pushV.size();){
            stack.push_back(pushV[i++]);
            while(j < popV.size() && stack.back() == popV[j]){
                stack.pop_back();
                j++;
            }      
        }
        return stack.empty();
    }
};