剑指offer（一）

雨点打透心脏的1/2处 2022-02-18 11:27 224阅读 0赞

这几天开始刷牛客网上[剑指offer][offer]的编程题，下面一系列博客将用python实现里面的编程题，很多参考了大神的思路（C实现），然后用python实现的。

### 二维数组查找 ###

**题目描述**  
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，  
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。  
6 14 22 26  
8 16 24 30  
10 20 30 40  
输入10 ，返回True

**思路**  
观察数组规律，从左下角元素开始找，如果目标值比它大，就查找下一列，比它小，就查找上一行。

**代码实现**

class Solution:
        # array 二维列表
        def Find(self, target, array):
            rows=len(array)-1
            cols=len(array[0])-1
            i=rows
            j=0
            while (j<=cols and i>=0):     #从左下角元素开始寻找
                if(target<array[i][j]):   #比左下角元素小，查找上一行
                    i=i-1
                elif(target>array[i][j]): #比左下角元素大，查找下一列
                    j=j+1
                else:
                    return True
            return False

### 替换空格 ###

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

**思路**  
这题很简单，一个循环遍历加替换就行了，需要注意的最后需要把列表中的值转换为字符串输出。

**代码实现**

class Solution:
        # s 源字符串
        def replaceSpace(self, s):
            s1=list(s)                  #转换成列表处理
            for i in range(len(s1)):
                if(s1[i]==' '):
                    s1[i]='%20'
            return ''.join(s1)        #将列表元素以字符串形式输出

### 从尾到头打印链表 ###

**题目描述**  
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

**思路**  
利用一个列表，不断的取链表结点，通过insert方法将元素**前插**到列表。

**代码实现**

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        # 返回从尾部到头部的列表值序列，例如[1,2,3]
        def printListFromTailToHead(self, listNode):
            result=[]                       #存储从尾到头输出的元素
            head = listNode                 #链表头结点
            while (head is not None):
                result.insert(0,head.val)   #将从头部取出的结点前插到列表中
                head=head.next              #指向下一个结点
            return result

### 重建二叉树 ###

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

**思路**  
因为先序遍历中，根节点是第一个被访问的，所以先序序列中的第一个结点就是根节点，然后根据该结点值在中序遍历中的位置，可以将中序遍历划分为左子树、根节点、右子树。最后结合先序遍历和中序遍历序列中左右子树下标递归即可。

**代码实现**

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, preorder, inorder):
            if not preorder or not inorder:
                return
            root = TreeNode(preorder[0])   #前序序列中的第一个元素为根节点
            i=inorder.index(preorder[0])   #根节点元素在中序序列中的位置，从而划分得到左子树和右子树中的元素
            root.left=self.reConstructBinaryTree(preorder[1:i+1],inorder[:i])    #递归重建左子树
            root.right=self.reConstructBinaryTree(preorder[i+1:],inorder[i+1:])  #递归重建右子树
            return root

### 两个栈实现队列 ###

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

**思路**  
队列符合**先进先出规则**。栈符合**先进后出**规则。  
入队时：直接将元素压入stack1  
出队时：若stack2为空，先将stack1中的元素出栈压入栈2，栈2在出栈

![1.jpg][]

**代码实现**

class Solution:
        def __init__(self):
            self.stack1=[]
            self.stack2=[]
        def push(self, node):
            self.stack1.append(node)        #入队时，直接将元素压入栈1
        def pop(self):
            if self.stack2==[]:             #出队时，若栈2为空，先将栈1中的元素出栈压入栈2，栈2再出栈
                while self.stack1:
                    self.stack2.append(self.stack1.pop())
                return self.stack2.pop()
            return self.stack2.pop()

### 用2个队列实现一个栈呢？ ###

**思路**  
所有元素进入q1，因为我们的目的是栈，也就是最先出c,儿队是从队头开始出，所有先把ab出q1并入q2,此时目标c跑到了队头，出q1。此时q1已经为空，下一个要出的是b,把a从q2出队并进q1,此时目标b在q2队头,出队………  
即：**把非空队列的n-1个压人空对列，剩的第n个出队…即总有一个队列为空**。

![2.jpg][]

**代码实现**

class StackWithTwoQueues(object):
        #定义两个空队列
        def __init__(self):
            self.queue1 = []
            self.queue2 = []
        #入栈
        def push(self, item):
            self.queue1.append(item)
        #出栈
        def pop(self):
            if len(self.queue1) == 0:
                return(None)
            while(len(self.queue1) != 1):
                self.queue2.append(self.queue1.pop(0))
            self.queue1, self.queue2 = self.queue2, self.queue1
            return (self.queue2.pop())

[offer]: https://www.nowcoder.com/ta/coding-interviews
[1.jpg]: /images/20220218/ca783ad30a854f7f94b392d80d20b475.png
[2.jpg]: /images/20220218/cab0ec92a34b4f9cba337ab6b540fc39.png