剑指offer6

发表于 | 分类于 ，

面试题11: 旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路：使用二分查找法，一般情况下，这个最小值将数组分成两个部分。二分法有三个很重要的指针，左指针，右指针和中间的指针。这里可以分成三种情况，数组没有真正旋转、数值的左指针和右指针以及中间的指针指向的数字相等、正常二分法情况。数组没有真正旋转的话，直接返回第一个；相等的话就只能一个个找；二分法就二分法地找。二分法的核心是缩小寻找的范围，而缩小寻找的范围的条件又是数组不能有重复的数字。所以这里才会主要分成两种情况，一种就是可以使用二分法的，另一种就是不能分成二分法的。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        left = 0
        right = len(rotateArray)-1
        mid = 0
        while(rotateArray[left] >= rotateArray[right]):
            if right-left == 1:
                mid = right
                break
            mid = (left+right)//2
            if rotateArray[right] == rotateArray[left] and rotateArray[right] == rotateArray[mid]:
                return self.MinOrder(rotateArray,left,right)
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            else:
                right =mid
        return rotateArray[mid]
    def MinOrder(self, num, left, right):
        result = num[left]
        for i in num[left+1:right]:
            if i<result:
                result =i
        return result

算法思路：让mid等于0是让算法简洁，输出逻辑和二分法保持一致。while循环保证是满足二分法的（或者相等的情况）。二分法就是逼近的思想，让两个指针一直在两边，然后往最小值靠。

面试题12:矩阵中的路径

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路：回溯法体现在递归中，回溯就是一个探索路径的过程，探索的顺序是自定的，就像触手一样伸出去，就像深度遍历一样，知道找到一条可行的路径或者根本就不存在符合的条件的路径为止。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        # write code here
        # 将矩阵转成二维数组表示
        x = [list(matrix[i*cols:(i+1)*cols]) for i in range(rows)]
        for i in range(rows):
            for j in range(cols):
                self._dict = {}
                if self.dfs(x, i, j, path):
                    return True
        return False
    def dfs(self, matrix, i, j, p):#四个if语句中i,j边界判断保证了不越界，return保证了去掉不匹配的结果
        if matrix[i][j] == p[0]:
            if not p[1:]:#出口，路径中所有字母都找到
                return True
            matrix[i][j] = ''#先置为空，递归后再改回来，保证了不发生重复
            if i > 0 and self.dfs(matrix, i-1, j, p[1:]):#向上寻找，回溯体现在递归中
                return True
            if i < len(matrix)-1 and self.dfs(matrix, i+1, j ,p[1:]):#向下寻找
                return True
            if j > 0 and self.dfs(matrix, i, j-1, p[1:]):#向左寻找
                return True
            if j < len(matrix[0])-1 and self.dfs(matrix, i, j+1, p[1:]):#向右寻找
                return True
            matrix[i][j] = p[0]
            return False
        else:
            return False

代码思路：首先将矩阵转成二维数组表示，方便后续的遍历。在遍历的过程中要避免数组越界的情况，回溯体现在递归中。

这里有一个小细节：就是not p[1:],这里不能用p[1:] == None ,因为这样会报string下标溢出的错，因为这个情况下，p只剩下最后一位了，p[1:]是不存在的， 后者的写法就溢出了。

请作者喝杯咖啡吧！