首页 > > 网络编程 > 其它 >

剑指offer--day01

2019-07-24 09:13:28来源：博客园阅读 ()

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

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

1.3代码：

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     # array 二维列表
 4     def Find(self, target, array):
 5         # write code here
 6         rows = len(array)
 7         cols = len(array[0])
 8         
 9         if rows > 0 and cols > 0:
10             row = 0
11             col = cols - 1
12             while row < rows and col >= 0:
13                 if target == array[row][col]:
14                     return True
15                 elif target < array[row][col]:
16                     col -= 1
17                 else:
18                     row += 1
19         return False

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

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

2.3 代码：

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     # s 源字符串
 4     def replaceSpace(self, s):
 5         # write code here
 6         tempstr = ''
 7         for c in s:
 8             if c == ' ':
 9                 tempstr += "%20"
10             else:
11                 tempstr += c
12         return tempstr

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

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

3.3代码：

 1 # -*- coding:utf-8 -*-
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     # 返回从尾部到头部的列表值序列，例如[1,2,3]
 9     def printListFromTailToHead(self, listNode):
10         # write code here
11         result = []
12         while listNode:
13             result.insert(0, listNode.val)
14             listNode = listNode.next
15         return result

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

4.2解题思路：

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

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

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

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

4.3代码：

 1 # -*- coding:utf-8 -*-
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 class Solution:
 8     # 返回构造的TreeNode根节点
 9     def reConstructBinaryTree(self, pre, tin):
10         # write code here
11         if len(pre) == 0:
12             return None
13         elif len(pre) == 1:
14             return TreeNode(pre[0])
15         else:
16             root = TreeNode(pre[0])
17             pos = tin.index(pre[0])
18             root.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])
19             root.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])
20         return root