《剑指Offer》第二章（一）题 9 -12
_Ennio 人气:1第二章
面试题9：用两个栈实现队列
题目：如面试题，给你两个栈， 实现队列的先进先出，即在队列头删除一个元素以及在队列的尾部添加一个元素
思路：这个题的分析感觉很巧妙，从一个具体的例子入手，找出其中的规律，进而得到一种解决方法。解决方法几句话就能说完，但是这种思维很重要，放个图留着自己以后体会吧。
图好大。。
代码如下：
stack1 = []
stack2 = []
# 尾部添加一个节点
def appendTail(val):
stack1.append(val)
# 头部删除一个元素
def deleteHead():
if stack2.__len__() == 0 and stack1.__len__() == 0:
return "error"
if stack2.__len__() == 0:
while stack1.__len__() != 0:
stack2.append(stack1.pop())
return stack2.pop()
测试代码：
appendTail(1) appendTail(2) appendTail(3) print(deleteHead()) print(deleteHead())
代码用Python写还是比较简洁的,java要多写挺多的，python牛逼
类似题目：两个队列实现一个栈。
自己画一下就知道了，加的时候往有元素的队列加，当然一开始直接往1队列加。出的时候，把有元素的队列其中的n-1个元素都取出来，放到另一个队列之中，剩下最后一个元素，即为目标元素，其它同理。
面试题10：斐波那切数列
做过很多次了。记住一点，对于这类问题，先假设n很小的时候，求出n==1,2....或者其它一般情况之下的值，然后规模为的问题进行分解，想办法分解为n-1和规模的问题，最终就可以缩小成1,2.....的问题，进而求解出N问题。难点还是在分解问题上，看自己能不能想到。
非递归的写法：
def solution(n):
result = [0,1]
if n < 2:
return result[n]
x = 1
y = 0
target = None
for i in range(1,n):
target = x + y
y = x
x = target
return target
代码不多说了，一看就会。
面试题11：求旋转数组之中的最小值
题目：旋转数组是指将一个有序的数组前面的x个数移动到最后面，类似于，原数组【1,2,3,4,5】，旋转过后的数组：【3,4,5,1,2】，当然这个x也可以是0，就是不移动，但是它本身也是一个旋转数组。如题，求该数组之中的最小值。
思路分析：首先能想到的肯定是O(N)的方法，遍历数组然后找出最小值，但是这肯定是不行的，需要找到一个O(logn)复杂度的方法，一般来讲，这种查找数字的，而且是部分有序，都可以用二分查找的思想进行。可以看到了这个旋转数组，它仍然可以划分为两个有序的子数组，一个是【3,4,5】，一个是【1,2】，前面数组的值都大于等于后面数组之中的值， 我们需要找的数字是1，二分查找，自然是需要两个边界指针，和一个中间指针，比较中间和两边的值，进而一步步缩小目标值的范围，从而达到O(logn)复杂度的查找方法。对于【3,4,5,1,2】，设有指针left，right，middle，初始时，分别指向3,2,5，比较5>3，说明left到middle之间的数字，都是处于第一个数组之中的，所以最小值肯定是在midlle~right之间，同理，如果旋转数组为【4,5,1,2,3】，1<3,说明midlle~right之间都是后面那个子数组的元素，所以最小值肯定是位于middle~left之间的，之后的都同理。总体上说，就是通过比较middle和两边的值，不断缩小最小值的区间，当最小值区间大小为2时，nums[right]的值就是最小值。
但是需要注意两个特殊情况：
一，就是刚开始说得，旋转了0个或者n个数字的情况，此时第一个数字就是最小数字，没有必要再进行查找了，所以，如果第一个数小于最后一个数字，说明旋转了n个或者0个数字，直接返回第一个数字就可以了。
二，如果midlle,left,right这三个数字都相等的话，那么就无法继续缩小区间，比如这个数组【0,1,1,1,1】，旋转之后可以是【1,0,1,1,1】，【1,1,1,0,1】，可以看到，按照之前的规则是有可能得出错误的结果的，所以如果这种情况，那么就只能采用顺序查找的方法了。
个人认为这题需要考虑的很多，现阶段我肯定是考虑不到这么周全的，继续加油。
代码如下：
def min(nums):
if len(nums) == 0 or nums == None:
return False
left = 0
right = len(nums)-1
# 旋转了0或者n
if nums[left] < nums[right]:
return nums[0]
# 正常旋转
while nums[left] >= nums[right]:
# 查找到了最小值
if right - left == 1:
return nums[right]
middle = int((right+left)/2)
if nums[middle] == nums[left] == nums[right]:
# 顺序查找
return orderSearch(nums, left, end)
# 正常缩小区间
if nums[middle] >= nums[left]:
left = middle
elif nums[middle] <= nums[right]:
right = middle
# 顺序查找
def orderSearch(nums, start, end):
result = nums[start]
for i in range(start, end+1):
if nums[i] < result:
result = nums[i]
return result
面试题12：矩阵之中的路径
题目：给定一个字符矩阵以及一个字符串，寻找在该字符矩阵之中是否有一条路径，连起来的顺序刚好是给定的字符串，只能上下左右相连，不能斜着相连，并且一个字符格走过之后就不能再走这个了，相当于不能重复走过同一个矩阵之中的格子。
思路：这个问题相当于从一个点开始，下一步可以有好几种走法，每次判断一下是否达到了目标，以及能够达到目标，达到目标了直接结束，没有达到的话说明当前步骤行不通，回溯到上一步，尝试其他路径是否可行。这种问题一般都是用回溯法来解决。
具体到这个问题：以矩阵之中任何一个字符格为起点进行考察，判断当前字符是否等于字符串第一个字符，等于了进行下步，以该字符的上下左右四个字符作为下一个考察点(有的话)，看看是否等于字符串的第二个字符，等于的话，重复上一次的步骤，不等于则停止以当前字符为基准的判断，回溯到上一个格子，尝试其它可行的路径，以此类推。
思路还是比较容易理解的，代码虽然很长，但是其中的思路很明了。
代码如下：
def hasPath(matrix, rows, cols, word):
if matrix == None or rows < 1 or cols <1 or word == None:
return False
visited = []
for i in range(rows):
visited.append([])
for j in range(cols):
visited[i].append(False)
pathLength = 0
for i in range(rows):
for j in range(cols):
# 以每一个矩阵格子为起点进行考察
if hasPathCore(matrix, rows, cols, i, j, word, pathLength, visited):
return True
return False
def hasPathCore(matrix, rows, cols, row, col, word, pathLength, visited):
# 判断是否到了字符串结尾
if word[pathLength] == '#':
return True
hasPath = False
# 判断当前字符是否在矩阵之中并且需要等于第pathLength个字符
# 而且不能已经访问过了
if row < rows and row >= 0 and col < cols and col >= 0 and \
word[pathLength] == matrix[row][col] and visited[row][col] == False:
# 进行下一个字符的查找
pathLength += 1
visited[row][col] = True
# 对上下左右四条路径进行查找
hasPath = hasPathCore(matrix, rows, cols, row+1, col, word, pathLength, visited) or \
hasPathCore(matrix, rows, cols, row-1, col, word, pathLength, visited) or \
hasPathCore(matrix, rows, cols, row, col+1, word, pathLength, visited) or \
hasPathCore(matrix, rows, cols, row, col-1, word, pathLength, visited)
if hasPath: # 没有找到，回溯到上一个字符
visited[row][col] = False
pathLength -= 1
return hasPath
测试代码如下：
nums = [
['a', 'b', 't', 'g'],
['c', 'f', 'c', 's'],
['j', 'd', 'e', 'h'],
]
print(hasPath(nums, 3, 4, 'cehsg#'))
加载全部内容