《剑指offer》 python实现(持续更新中)

面试题3. 不修改数组找出重复的数字

在一个长度为 n+1 的数组里，所有数字都在 1～n 范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组 {2,3,5,4,3,2,6,7}, 那么对应的输出是重复的2 或者3.

def getDuplication(n, s):
    if not n:
        return 0
    l = 1
    r = n       
    while l < r:
        num = 0
        mid = (l + r) // 2
        for i in range(len(s)):
            if s[i] <= mid and s[i] >= l:
                num += 1
        if num > (mid - l + 1):
            r = mid
        else:
            l = mid + 1
    return l

总的时间复杂度为O(nlogn), 空间复杂度为O(1)

面试题4. 二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：从右上角开始查找，若该值小于需要寻找的值，删除该列，大于的话，删除该行。

def Find(s, num):
    row = len(s)
    column = len(s[0])
    if row > 0 and column > 0:
        r = 0
        c = column - 1
        while r != row - 1 and c != 0:
            if s[r][c] == num:
                return True
            elif s[r][c] > num:
                c -= 1
            else:
                r += 1
        if s[row - 1][0] != num:
            return False
        else:
            return True
    return False

面试题5.替换空格

请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
思路：首先遍历一遍确定替换后的总长度，之后设置双指针从后往前进行替换。时间复杂度为O(n)

def ReplaceBlank(st):
    res = list(st)
    num = res.count(' ')
    res += [0] * 2 * num
    p = len(st) - 1
    q = len(res) - 1
    while p != q:
        if res[p] != ' ':
            res[q] = res[p]
            q -= 1
        else:
            res[q] = '0'
            res[q - 1] = '2'
            res[q - 2] = '%'
            q -= 3
        p -= 1
    return ''.join(res)