剑指offer小结第一波
2019-01-10 本文已影响0人
mying_三丘
最近在做剑指offer，平时事比较多，疏于及时总结，故抽点时间对近来所做题目做个大致回顾。
面试题3：数组中重复的数字
这道题的特殊之处在于长度为n,所有数字在n-1这个范围。
解法一：将输入的数组排序：
先排序，排好序的数组中找第一个重复的数很容易，排序的时间复杂度为O(nlogn)
解法二：利用哈希表解决:
O(1)的查询时间复杂度背后需要O(n)的哈希表空间复杂度做支撑
解法三：空间复杂度也为O(1)的解法
充分应用本题的特殊之处，若无重复数字，则排序后，数字i 出现在下标为i的位置
注意，这种方法修改了原来数组中的元素位置，如果不允许修改，则考虑开辟辅助空间。书中还提到了一种避免开辟额外空间的二分查找方法，个人感觉意义不大，不能保证找出所有重复的数字。
Ying的解法：
充分利用python中列表结构提供的便利，遍历数组，找到第一个出现次数不为1的元素。
def duplicate(self, numbers, duplication):
# write code here
ll = len(numbers)
for i in numbers:
if numbers.count(i)>1:
duplication[0]=i
return True
return False
面试题四： 二维数组中的查找
技巧：
选择右上角或左下角元素作为比较标定点，可以缩小查找范围
面试题五：空格替换
题目来源于URL参数中含有特殊字符时需要转换为服务器可识别字符的应用场景。
先遍历一遍，看有多少个空格，计算转换之后的总长度，然后从后往前走，遇到空格做修改，空间复杂度为O(1)
面试题六：从尾到头打印链表
技巧：本质上将是先进后出，考虑用栈，遍历链表，将链表元素入栈，然后再让栈中元素出栈，作为新的链表元素，进而也可以考虑 用递归，访问每个链表节点时，递归地先输出下一个节点元素，然后再输出当前节点。
Ying的解法：
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
li = []
while True:
if listNode is None:
break
else:
li.append(listNode.val)
listNode = listNode.next
li.reverse()
return li
面试题七：重建二叉树
根据先序中序或中序后序构建二叉树。先序遍历第一个位置是根节点，中序遍历根节点左右分别是左右子树，根据这个做递归
Ying的解法：
finding函数是在先序遍历和中序遍历发你别找到根节点的做右子树序列
reConstructBinaryTree则是递归建树的过程
class Solution:
# 返回构造的TreeNode根节点
def finding(self,pre,tin):
p=tin.index(pre[0])
left1=pre[1:p+1]
left2=tin[:p]
right1=pre[p+1:]
right2=tin[p+1:]
return left1,left2,right1,right2
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre)==0:
return None
tn = TreeNode(pre[0])
if len(pre)==1:
return tn
left1,left2,right1,right2 = self.finding(pre,tin)
if len(left1)>=1:
tn.left = self.reConstructBinaryTree(left1,left2)
if len(right1)>=1:
tn.right = self.reConstructBinaryTree(right1,right2)
return tn
面试题八：二叉树的下一个节点
中序遍历的下一个节点的确定需要考虑以下几种情况：
- 若当前节点有右子树，则下一个节点是它右子树中的最左子节点；
- 若没有右子树，若当前节点是其父节点的左孩子，则下一个节点是其父节点；若当前节点是其父节点的右孩子，则下一个节点是其一直往上遍历且是其父节点的左孩子。
Ying的解法：
class Solution:
def GetNext(self, pNode):
# write code here
#普通情况，有右子节点
if pNode.right is not None:
pNode = pNode.right
while pNode.left is not None:
pNode = pNode.left
# 没有右子树的情况
else:
if pNode.next is None: # 根节点
pNode = None
elif pNode == pNode.next.left: # 是父节点的左孩子
pNode = pNode.next
elif pNode == pNode.next.right: # 是父节点的右孩子
pNode = pNode.next
while pNode.next is not None and pNode.next.right == pNode:
pNode = pNode.next
if pNode.next is None:
pNode = None
else:
pNode = pNode.next
return pNode
碎碎念
- C/C++中每个字符串都以字符'\0'作为结尾，常量字符串在内存中只有一个拷贝，指向同一常量字符串的变量具有同一个地址。
- 链表：创建、插入节点、删除节点等操作都只需要20行左右的代码就能实现，链表是一种动态的数据结构，需要对指针进行操作，注意，题目所给的pHead是只想指针的指针。同二叉树一样，都是考察的重点。
- 二叉树三种遍历方式的实现都可以基于递归和循环做实现。
- 二叉搜索树中找到一个节点的时间复杂度是O(logn).
- 堆分为最大堆和最小堆，堆排序应用。
- 红黑树是把树中节点定义为红黑两种颜色，通过规则确保从根节点到叶节点的最长路径不超过最短路径的两倍。很多数据结构是基于红黑树实现的，例如C++的STL中，set,multiset,map,multimap等。
作者原创，欢迎交流，如需转载请先联系作者。
