剑指offer--day01

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

1.2思路：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

1.3代码：

 # -*- coding:utf-8 -*-

 class Solution:

     # array 二维列表

     def Find(self, target, array):

         # write code here

         rows = len(array)

         cols = len(array[0])

         if rows > 0 and cols > 0:

             row = 0

             col = cols - 1

             while row < rows and col >= 0:

                 if target == array[row][col]:

                     return True

                 elif target < array[row][col]:

                     col -= 1

                 else:

                     row += 1

         return False

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

2.2思路：建立一个新的空字符串tempstr，然后遍历输入的字符串，判断字符串中当前字符是否为空，若否，添加字符到空字符串tempstr中，若是，添加%20到空字符串tempstr中，最后返回tempstr。

2.3 代码：

 # -*- coding:utf-8 -*-

 class Solution:

     # s 源字符串

     def replaceSpace(self, s):

         # write code here

         tempstr = ''

         for c in s:

             if c == ' ':

                 tempstr += "%20"

             else:

                 tempstr += c

         return tempstr

3.1题目：从尾到头打印链表：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

3.2解题思路：创建一个栈，循环遍历节点并将节点的data存放到栈中，最后返回这个栈。（栈的特性：先进后出）

3.3代码：

 # -*- coding:utf-8 -*-

 # class ListNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.next = None

 class Solution:

     # 返回从尾部到头部的列表值序列，例如[1,2,3]

     def printListFromTailToHead(self, listNode):

         # write code here

         result = []

         while listNode:

             result.insert(0, listNode.val)

             listNode = listNode.next

         return result

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

4.2解题思路：

　　通常树有如下几种遍历方式：

前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。

　　本题为前序遍历和中序遍历，最少需要两种遍历方式，才能重建二叉树。

　　前序遍历序列中，第一个数字总是树的根结点的值。在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。剩下的我们可以递归来实现，具体如图：

4.3代码：

 # -*- coding:utf-8 -*-

 # class TreeNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution:

     # 返回构造的TreeNode根节点

     def reConstructBinaryTree(self, pre, tin):

         # write code here

         if len(pre) == 0:

             return None

         elif len(pre) == 1:

             return TreeNode(pre[0])

         else:

             root = TreeNode(pre[0])

             pos = tin.index(pre[0])

             root.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])

             root.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])

         return root

牛客网刷题平台：https://www.nowcoder.com/ta/coding-interviews

参考：https://cuijiahua.com/（这位大牛的个人网站非常给力，强烈建议大家过去看看！）

巴特西

剑指offer--day01

最新文章

热门文章