剑指offer刷题笔记

由于本人的主力语言为python，以下面试题都用python实现

面试题之二：实现Singleton模式

题目：实现一个单例模式

class Singleton(object):
    _instance = None
    _instance_lock = threading.Lock()

    def __init__(self, *args, **kwargs):
        pass

    def __new__(cls, *args, **kwargs):
        if cls._instance:
            return cls._instance
        with cls._instance_lock:
            cls._instance = object.__new__(cls)
        return cls._instance

面试题之三：二维数组中的查找

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

例如下面的数组，如果查找数字7，则返回True；如果查找数字5，则返回False

[
    [1,2,8,9],
    [2,4,9,12],
    [4,7,10,13],
    [6,8,11,15]
]

思路：

1.从左下角开始选取元素，将此元素与目标元素比较，有三种可能的情况

1）此元素与目标元素相等，返回True，程序结束

2）此元素小于目标元素，则在这个元素的右侧开始查找

3）此元素大于目标元素，则在这个元素的上侧开始查找

2.重复步骤1，直到结束，返回False

代码

def find_in_partially_sorted_matrix(matrix, num):
    '''
    :type matrix: List[List[int]]
    :type num: int
    :rtype: bool
    '''
    if not matrix or not matrix[0]:
        return False
    if num < matrix[0][0] or num > matrix[-1][-1]:
        return False

    i, j = len(matrix) - 1, 0
    while i >= 0 and j <= len(matrix[0]) - 1:
        if matrix[i][j] == num:
            return True
        elif matrix[i][j] < num:
            j += 1
        elif matrix[i][j] > num:
            i -= 1
    return False


if __name__ == '__main__':
    matrix = [
                [1, 2, 8, 9],
                [2, 4, 9, 12],
                [4, 7, 10, 13],
                [6, 8, 11, 15]
            ]
    #print(find_in_partially_sorted_matrix(matrix, 10))
    #print(find_in_partially_sorted_matrix(matrix, 4))
    #print(find_in_partially_sorted_matrix(matrix, 15))
    #print(find_in_partially_sorted_matrix(matrix, 9))
    #print(find_in_partially_sorted_matrix(matrix, 5))
    #print(find_in_partially_sorted_matrix(matrix, -1))
    #print(find_in_partially_sorted_matrix(matrix, 1))
    #print(find_in_partially_sorted_matrix(matrix, 18))

    matrix = [
            [-2, 1, 5, 9]
            ]
    #print(find_in_partially_sorted_matrix(matrix, -2))
    #print(find_in_partially_sorted_matrix(matrix, 5))
    #print(find_in_partially_sorted_matrix(matrix, 9))
    #print(find_in_partially_sorted_matrix(matrix, -1))
    #print(find_in_partially_sorted_matrix(matrix, -3))
    #print(find_in_partially_sorted_matrix(matrix, 10))

    matrix = [
            [-5,],
            [-2,],
            [3,],
            [6,],
            [8,]
            ]
    #print(find_in_partially_sorted_matrix(matrix, 0))
    #print(find_in_partially_sorted_matrix(matrix, -8))
    #print(find_in_partially_sorted_matrix(matrix, 6))
    #print(find_in_partially_sorted_matrix(matrix, 8))
    #print(find_in_partially_sorted_matrix(matrix, -5))
    #print(find_in_partially_sorted_matrix(matrix, 10))

    matrix = []
    #print(find_in_partially_sorted_matrix(matrix, 3))

    matrix = [
            [],
            [],
            []
            ]
    print(find_in_partially_sorted_matrix(matrix, 5)) 

持续更新中...

剑指offer刷题笔记

原文：https://www.cnblogs.com/zzliu/p/12368177.html