淘先锋技术网

首页 1 2 3 4 5 6 7

剑指offer刷题记录 python

1. 数组中重复的数字

长度n，数字0-n-1

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def duplicate(self , numbers: List[int]) -> int:
        n = len(numbers)
        for i in range(n):
            num = numbers[i]
            while num != i:
                if num < 0 or num > n-1:
                    return -1
                elif numbers[num] == num:
                    return num
                numbers[i],numbers[num] = numbers[num],numbers[i]
                num = numbers[i]
        return -1

引申：不修改数组，找出重复的数字

长度n+1的数组里，所有数字都在1-n范围内注意这里与上面的数字范围其实不同，只有数字区间比长度小1的时候可以这么做，上一题数字区间与长度是一样长的

方法1：用o(n)辅助空间，时间复杂度o(n)

方法2：不用辅助空间，用二分法count数字数量，时间复杂度o(nlog(n))

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @return int整型
#
class Solution:
    def duplicate(self, numbers: list[int]) -> int:
        n = len(numbers)
        if n < 2:
            return -1
        l,r = 0,n-1
        while l < r-1:
            mid = (l + r) // 2
            numCnt = 0
            for num in numbers:
                if num <= mid:
                    numCnt += 1
            if numCnt > mid-l+1:
                r = mid
            else:
                l = mid+1
        lNumCnt,rNumCnt = 0,0
        for num in numbers:
            if num == numbers[l]:
                lNumCnt += 1
            elif num == numbers[r]:
                rNumCnt += 1
            if lNumCnt > 1:
                return numbers[l]
            if rNumCnt > 1:
                return numbers[r]
        return -1

2. 二维数组中的查找

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        if len(array) == 0 or len(array[0]) == 0:
            return False
        m,n = len(array),len(array[0])
        # select the number on right up corner
        i,j = 0,n-1
        while array[i][j] != target:
            if array[i][j] < target:
                i += 1
            else:
                j -= 1
            if i < 0 or i > m-1 or j < 0 or j > n-1:
                return False
        return True

3. 替换空格

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return string字符串
#
class Solution:
    def replaceSpace(self , s: str) -> str:
        # step1: 统计空格数量
        n = len(s)
        spaceCnt = 0
        for i in range(n):
            if s[i] == " ":
                spaceCnt += 1
        # 注意这里增加的数量的2倍空格，空格本身就有位置
        s = s + " " * spaceCnt * 2
        # python字符串无法修改，改成list修改
        s = list(s)
        j = len(s) - 1
        for i in range(n-1,-1,-1):
            if s[i] == " ":
                s[j],s[j-1],s[j-2] = "0","2","%"
                j -= 3
            else:
                s[j] = s[i]
                j -= 1
            print("".join(s))
        return "".join(s)

4. 从尾到头打印链表

用递归 or 栈

栈

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param listNode ListNode类 
# @return int整型一维数组
#
class Solution:
    def printListFromTailToHead(self, listNode: ListNode) -> list[int]:
        printList = []
        if not listNode:
            return printList
        stack = []
        l = listNode
        while l:
            stack.append(l.val)
            l = l.next
        while stack:
            val = stack.pop(-1)
            printList.append(val)
        return printList

递归

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param listNode ListNode类 
# @return int整型一维数组
#
class Solution:
    def printListFromTailToHead(self, listNode: ListNode) -> list[int]:
        if not listNode:
            return []
        if not listNode.next:
            return [listNode.val]
        printList = self.printListFromTailToHead(listNode.next)
        printList.append(listNode.val)
        return printList

5.重建二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pre int整型一维数组 
# @param vin int整型一维数组 
# @return TreeNode类
#
class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        if len(pre) == 0:
            return None
        root = TreeNode(pre[0])
        if len(pre) == 1:
            return root

        rootIdx = 0
        for i in range(len(vin)):
            if vin[i] == pre[0]:
                rootIdx = i
                break
        
        vinLeft,vinRight = vin[0:rootIdx],vin[rootIdx+1:len(vin)]
        preLeft,preRight = pre[1:len(vinLeft)+1],pre[len(vinLeft)+1:len(pre)]
        root.left = self.reConstructBinaryTree(preLeft,vinLeft)
        root.right = self.reConstructBinaryTree(preRight,vinRight)
        return root

6.二叉树的下一个结点

# -*- coding:utf-8 -*-
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None
class Solution:
    def GetNext(self, pNode):
        if not pNode:
            return None
        # 有右子树,右子树最左节点就是下个节点
        if pNode.right:
            p = pNode.right
            while p.left:
                p = p.left
            return p
        # 没有右子树,
        else:
            # 如果是父节点的左子树，则返回父节点,否则不断往上，直到满足这个条件
            p = pNode
            father = p.next
            while father and father.left != p:
                p = father
                father = p.next
            return father

7.用两个栈实现队列

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if len(self.stack2) == 0:
            while len(self.stack1):
                self.stack2.append(self.stack1.pop(-1))
        if len(self.stack2):
            return self.stack2.pop(-1)
        return None

8.斐波那契数列

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def Fibonacci(self , n: int) -> int:
        if n == 1 or n ==2:
            return 1
        f1,f2 = 1,1
        cur = 2
        while cur < n:
            curSum = f1+f2
            f1 = max(f1,f2)
            f2 = curSum
            cur += 1
        return f2

8.旋转数组的最小数字

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param rotateArray int整型一维数组
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return None
        l,r = 0,len(rotateArray)-1

        while l+1 < r:
            mid = (l+r)//2
            if rotateArray[l] < rotateArray[mid]:
                l = mid
            elif rotateArray[l] > rotateArray[mid]:
                r = mid
            # 2,2,2,1,2
            # 2,1,2,2,2
            else:
                if rotateArray[r] < rotateArray[mid]:
                    l = mid
                    # 这里只能r走，否则出现顺序情况会无法判断
                while rotateArray[l] == rotateArray[r] and l < r:
                    r -= 1
        # 数组完全是顺序的情况
        return min(min(rotateArray[l],rotateArray[r]),rotateArray[0])

反向写，相对来说不容易卡边界，但是我会有点想不清楚

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param rotateArray int整型一维数组
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if len(rotateArray) == 0:
            return None
        l,r = 0,len(rotateArray)-1

        while l+1 < r:
            mid = (l+r)//2
            if rotateArray[r] < rotateArray[mid]:
                l = mid
            elif rotateArray[r] > rotateArray[mid]:
                r = mid
            # 2,2,2,1,2
            # 2,1,2,2,2
            else:
                if rotateArray[l] < rotateArray[mid]:
                    return rotateArray[l]
                elif rotateArray[l] > rotateArray[mid]:
                    r = mid
                while rotateArray[l] == rotateArray[r] and l < r:
                    l += 1
                    r -= 1
        # 数组完全是顺序的情况
        return min(rotateArray[l],rotateArray[r])

9.矩阵中的路径

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix char字符型二维数组
# @param word string字符串
# @return bool布尔型
#
class Solution:
    def __init__(self):
        self.direction = [[-1,0],[1,0],[0,1],[0,-1]]

    def hasPath(self , matrix: list[list[str]], word: str) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        self.lenX = len(matrix)
        self.lenY = len(matrix[0])
        self.matrix = matrix
        self.word = word
        self.visited = [[0 for j in range(self.lenY)] for i in range(self.lenX)]

        for i in range(self.lenX):
            for j in range(self.lenY):
                if self.dfs(i,j,0):
                    return True
        return False

    def dfs(self,x,y,n):
        if n == len(self.word):
            return True
        # 注意不要漏掉x < 0 or y < 0的判断
        if x < 0 or y < 0 or x >= self.lenX or y >= self.lenY or self.matrix[x][y] != self.word[n] or self.visited[x][y]:
            return False

        self.visited[x][y] = 1
        for i,j in self.direction:
            if self.dfs(x+i,y+j,n+1):
                return True

        self.visited[x][y] = 0
        return False

10.机器人的运动范围

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param threshold int整型
# @param rows int整型
# @param cols int整型
# @return int整型
#
class Solution:
    def __init__(self):
        self.direction = [[-1,0],[1,0],[0,1],[0,-1]]

    def movingCount(self , threshold: int, rows: int, cols: int) -> int:
        if not rows or not cols or threshold < 0:
            return 0
        self.rows = rows
        self.cols = cols
        self.visited = [[0 for i in range(cols)] for j in range(rows)]
        self.squireCnt = 0
        self.dfs(0,0,threshold)
        return self.squireCnt

    def dfs(self,x,y,threshold):
        if x >= self.rows or y >= self.cols or x < 0 or y < 0 or self.visited[x][y] == 1 or not self.checkNum(x,y,threshold):
            return
        self.visited[x][y] = 1
        self.squireCnt += 1
        for i,j in self.direction:
            self.dfs(x+i,y+j,threshold)

    def checkNum(self,x,y,threshold):
        xysum = 0
        while x:
            xysum += x%10
            x //= 10
        while y:
            xysum += y%10
            y //= 10
        if xysum > threshold:
            return False
        else:
            return True

11.剪绳子

注意不要漏余数为0的判断

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param number int整型
# @return int整型
#
class Solution:
    def cutRope(self , number: int) -> int:
        # 8:2,3,3
        # 10:1,3,3,3/2,3,3,2
        cnt3 = number//3
        remain = number%3
        # 注意不要漏余数为0的判断
        if remain == 0:
            return pow(3,cnt3)
        elif remain == 1:
            return 4 * pow(3,cnt3-1)
        else:
            return 2 * pow(3,cnt3)

12.二进制中1的个数

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return int整型
#
class Solution:
    def NumberOf1(self , n: int) -> int:
        flag = 1
        cnt = 0
        for i in range(32):
            if flag & n:
                cnt += 1
            flag <<= 1
        return cnt

13.数值的整数次方

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param base double浮点型
# @param exponent int整型
# @return double浮点型
#
class Solution:
    def Power(self , base: float, exponent: int) -> float:
        if base == 0:
            return 0
        if exponent == 0 or base == 1:
            return 1
        isNeg = False
        if exponent < 0:
            isNeg = True
        result = 1
        exp = abs(exponent)
        for i in range(exp):
            result *= base
        if isNeg:
            return 1.0/result
        return result

快速幂，具体解法参考之前文章

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param base double浮点型
# @param exponent int整型
# @return double浮点型
#
class Solution:
    def Power(self , base: float, exponent: int) -> float:
        if base == 0:
            return 0
        if exponent == 0 or base == 1:
            return 1
        isNeg = False
        if exponent < 0:
            isNeg = True
        result = 1
        exp = abs(exponent)
        while exp:
            if exp & 1:
                result *= base
            base *= base
            exp = exp >> 1
        if isNeg:
            return 1.0/result
        return result

 14.删除链表的节点

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param val int整型 
# @return ListNode类
#
class Solution:
    def deleteNode(self , head: ListNode, val: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        p = dummy
        while p.next:
            if p.next.val == val:
                p.next = p.next.next
            p = p.next
        return dummy.next

15.正则表达式匹配