剑指offer
http://blog.csdn.net/DERRANTCM/article/details/46887821
目录
第01-10题
【剑指Offer学习】【面试题02：实现Singleton 模式——七种实现方式】
【剑指Offer学习】【面试题03：二维数组中的查找】
每行递增，每列递增（注意是每列，不是第一列）：先指针指向右上角元素，如果>target: 列 = 列-1 （j = j-1)
如果< target ，行(i = i-1)
【剑指Offer学习】【面试题04：替换空格】
先遍历一遍看有多少个空格需要替换，后面增加相应的空格，然后从后往前双指针填补空白
【剑指Offer学习】【面试题05：从尾到头打印链表】
用栈，再出栈
【剑指Offer学习】【面试题06：重建二叉树】
参考leetcode，二叉树里面
【剑指Offer学习】【面试题07：用两个栈实现队列】
【剑指Offer学习】【面试题08：旋转数组的最小数字】
二分查找 O(logN)
【剑指Offer学习】【面试题09：斐波那契数列】
dp ，标准递推，dp[0]=0,dp[1]=1, dp[i] = dp[i-1] + dp[i-2]
【剑指Offer学习】【面试题10：二进制中1 的个数】
第11-20题
【剑指Offer学习】【面试题11：数值的整数次方】
【剑指Offer学习】【面试题12：打印1 到最大的n 位数】
【剑指Offer学习】【面试题13：在O（1）时间删除链表结点】
【剑指Offer学习】【面试题14：调整数组顺序使奇数位于偶数前面】
简化版的快排，两层while，相当于快排里的每次迭代，双指针，碰到符合要求的pair进行交换
【剑指Offer学习】【面试题15：链表中倒数第k个结点】
快慢指针
【剑指Offer学习】【面试题16：反转链表】
非递归 tail = None
while head:
new = head.next
head.next = tail
tail = head
head = new
return tail
【剑指Offer学习】【面试题17：合并两个排序的链表】
和归并差不多
【剑指Offer学习】【面试题18：树的子结构】
写一个方法判断两个树是否match(递归，判断当前节点与左右节点）
另一个方法遍历树A，对于树A的每个节点，如果值和B的根节点值一样，去调用match方法，当match为True，则返回
【剑指Offer学习】【面试题19：二叉树的镜像】
和leetcode226. Invert Binary Tree 一样，node不为空，则交换左右，然后对左右调用同样的方法
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return
root.left,root.right = root.right,root.left
if root.left:
self.invertTree(root.left)
if root.right:
self.invertTree(root.right)
return root
【剑指Offer学习】【面试题20：顺时针打印矩阵】
第21-30题
【剑指Offer学习】【面试题21：包含min函数的钱】
【剑指Offer学习】【面试题22：栈的压入、弹出序列】
【剑指Offer学习】【面试题23：从上往下打印二叉树】
层次遍历
使用队列
【剑指Offer学习】【面试题24：二叉搜索树的后序遍历序列】
【剑指Offer学习】【面试题25：二叉树中和为某一值的路径】
DFS，保存所有和为target的path
返回条件为到叶子节点（左右都NULL）
class Solution(object):
def pathSum(self, root, sum):
if root is None or sum is None:
return []
path = [root.val]
res = []
self.dfs(root,path,sum - root.val,res)
return res
def dfs(self,root,path,target,res):
if not root.left and not root.right:
if target == 0:
res.append(path)
if root.left is not None:
self.dfs(root.left,path+[root.left.val],target - root.left.val,res)
if root.right is not None:
self.dfs(root.right,path + [root.right.val],target - root.right.val,res)
【剑指Offer学习】【面试题26：复杂链表的复制】
【剑指Offer学习】【面试题27：二叉搜索树与双向链表】
【剑指Offer学习】【面试题28：字符串的排列】
全排列，个人感觉DFS最简洁
【剑指Offer学习】【面试题29：数组中出现次数超过一半的数字】
一个元素保存当前str，一个保存当前次数c
如果碰到一样的元素 c+1，否则c -1，如果c<0则str替换成当前的数字，最终的str肯定是超过一半的哪一个
【剑指Offer学习】【面试题30：最小的k个数】
堆排序，前k个数先整成最大堆，之后nums[k+1:]每个数和最大堆堆顶进行比较，
如果 <堆顶 则替换掉堆顶的元素，再整堆 复杂度k*log(k) + (N-k)*log(k) = N*log(k)
第31-40题
【剑指Offer学习】【面试题31：连续子数组的最大和】
基础DP
cur_max = max(nums[i],cur_max+nums[i])
tmp_max = max(cur_max,tmp_max)
【剑指Offer学习】【面试题32：求从1到n的整数中1出现的次数】
【剑指Offer学习】【面试题33：把数组排成最小的数】
【剑指Offer学习】【面试题34：丑数】
【剑指Offer学习】【面试题35：第一个只出现一次的字符】
字典遍历一遍，value存count,再遍历一遍，碰到第一个value == 1的字符，时间o(N),空间o(N)
【剑指Offer学习】【面试题36：数组中的逆序对】
归并排序，完全一样的代码，归并过程中判断left 和right有没有逆序对，逆序对count + (len(left) - i) if right[j] < left[i]
【剑指Offer学习】【面试题37：两个链表的第一个公共结点】
一个函数计算长度，长度差为diff
标记两个链表为long和short，long先走diff步
long和short一起往前走，直到long == short
【剑指Offer学习】【面试题38：数字在排序数组中出现的次数】
二分查找，找到后双指针前后扫，平均O(logN)，最坏O(N)
或者二分查找，找到后继续查找开头和结尾位置,平均O(logN)
【剑指Offer学习】【面试题39：二叉树的深度】
return max(depth(left) + depth(right)) + 1
【剑指Offer学习】【面试题40：数组中只出现一次的数字】
第41-50题
【剑指Offer学习】【面试题41：和为s 的两个数字vs 和为s 的连续正数序列】
第一题: 2 SUMS
第二题: 相当于双指针，起始[1,2]，分别为开头left和结尾right，如果和小于s则结尾right+1，如果和大于s则开头left + 1
一种实现：直接while True，当最后path出现两个均大于 target一半 target //2的元素时break
def foo(target):
path = [1,2]
while True:
if len(path) == 2 and path[0] > target // 2 and path[1] > target//2:
break
s = sum(path)
# print(path)
if s == target:
res.append(path[:]) # 注意这里添加path[:] 避免浅拷贝
path.append(path[-1]+1)
elif s < target:
path.append(path[-1]+1)
else:
path.pop(0)
print(res)
foo(15)
【剑指Offer学习】【面试题42：翻转单词顺序vs左旋转字符串】
【剑指Offer学习】【面试题43 : n 个锻子的点数】
【剑指Offer学习】【面试题44：扑克牌的顺子】
【剑指Offer学习】【面试题45：圆圈中最后剩下的数字(约瑟夫环问题)】
【剑指Offer学习】【面试题47：不用加减乘除做加法】
【剑指Offer学习】【面试题49：把字符串转换成整数】
【剑指Offer学习】【面试题50：树中两个结点的最低公共祖先】
第51-60题
【剑指Offer学习】【面试题51：数组中重复的数字】
【剑指Offer学习】【面试题52：构建乘积数组】
【剑指Offer学习】【面试题53：正则表达式匹配】
【剑指Offer学习】【面试题54：表示数值的字符串】
【剑指Offer学习】【面试题55：字符流中第一个不重复的字符】
【剑指Offer学习】【面试题56：链表中环的入口结点】
【剑指Offer学习】【面试题57：删除链表中重复的结点】
【剑指Offer学习】【面试题58：二叉树的下一个结点】
【剑指Offer学习】【面试题59：对称的二叉树】
【剑指Offer学习】【面试题60：把二叉树打印出多行】
第61-67题
【剑指Offer学习】【面试题61：按之字形顺序打印二叉树】
【剑指Offer学习】【面试题62：序列化二叉树】
【剑指Offer学习】【面试题63：二叉搜索树的第k个结点】
【剑指Offer学习】【面试题64：数据流中的中位数】
【剑指Offer学习】【面试题65：滑动窗口的最大值】
【剑指Offer学习】【面试题66：矩阵中的路径】
【剑指Offer学习】【面试题67：机器人的运动范围】
特别声明
