# 刷题记录-python

**Repository Path**: swaaaay/offer

## Basic Information

- **Project Name**: 刷题记录-python
- **Description**: 剑指offer&华为机试个人刷题记录
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: Offer
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-11-23
- **Last Updated**: 2022-03-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 剑指offer刷题记录-python

#### offer 03 [数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)

```
class Solution(object):
    def findRepeatNumber(self, nums):
        mark=set()
        for item in nums:
            if item not in mark:
                mark.add(item)
            else:
                return item
```

#### offer 05 [替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)

```
class Solution(object):
    def replaceSpace(self, s):
        # return s.replace(' ','%20')
        mark=[]
        for i in s:
            if i==' ': mark.append('%20')
            else: mark.append(i)
        return ''.join(mark)
```

#### offer 06 [从尾到头打印链表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)

```
class Solution(object):
    def reversePrint(self, head):
        mark,curr=[],head
        while curr:
            mark.append(curr.val)
            curr=curr.next
        return mark[::-1]
```

#### offer 07 [重建二叉树*](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)

#### offer 09 [用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)

```
class CQueue(object):

    def __init__(self):
        self.li_head,self.li_tail=[],[]

    def appendTail(self, value):
        self.li_tail.append(value)

    def deleteHead(self):
        if self.li_head: 
            return self.li_head.pop()
        elif self.li_tail:
            for _ in range(len(self.li_tail)):
                self.li_head.append(self.li_tail.pop())
            return self.li_head.pop()
        else: return -1
```
#### offer 10 [斐波那契数列](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)
```
class Solution(object):
    def fib(self, n):
        ans=[0,1,1]
        if n<=2: return ans[n]
        for _ in range(n-2):
            ans.append(ans[-1]+ans[-2])
        return ans[-1]%1000000007
```
#### offer 10 [青蛙跳台阶问题](https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)
```
class Solution(object):
    def numWays(self, n):
        ans=[1,1,2]
        if n<=2: return ans[n]
        else:
            for _ in range(n-2):
                ans.append(ans[-1]+ans[-2])
        return ans[-1]%1000000007
```
#### offer 11 [旋转数组的最小数字^](https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/)
```
class Solution(object):
    def minArray(self, rotateArray):
        if not rotateArray:return None
        left,right=0,len(rotateArray)-1
        while left<right:
            mid=(left+right)//2
            if rotateArray[mid]>rotateArray[right]:
                left=mid+1
            elif rotateArray[mid]<rotateArray[right]:
                right=mid
            else: right-=1
        return rotateArray[left]
```

#### offer 15 [二进制中1的个数*](https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)

```
class Solution(object):
    def hammingWeight(self, n):
        count = 0
        B = 32
        while B:
            key = (n >> (B-1)) & 1 # 判断第B位是否为1
            B -= 1
            if key == 1: count += 1
        return count
```

#### offer 17 [打印从1到最大的n位数](https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)

```
class Solution(object):
    def printNumbers(self, n):
        return[i for i in range(1,10**n)]
```
#### offer 18 [删除链表的节点*]( https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/ )
```
class Solution(object):
    def deleteNode(self, head, val):
        if not head: return None
        if head.val==val: return head.next
        curr=head
        while curr:
            if curr.next.val==val:
                curr.next=curr.next.next
                break           
            curr=curr.next
        return head
```
#### offer 21 [调整数组顺序使奇数位于偶数前面](https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)

```
class Solution(object):
    def exchange(self, nums):
        odd,even=[],[]
        for item in nums:
            if item%2==0:
                even.append(item)
            else:
                odd.append(item)
        return odd+even
```

#### offer 22 [链表中倒数第k个节点^](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

```
class Solution(object):
    def getKthFromEnd(self, head, k):
        left,right=head,head
        for _ in range(k):
            right=right.next
        while right:
            left=left.next
            right=right.next
        return left
```
#### offer 23 [链表中环的入口结点](https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=265&tqId=39225&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=)

```
class Solution:
    def EntryNodeOfLoop(self, pHead):
        if not pHead: return None
        mark,curr=set(),pHead
        while curr:
            if curr in mark: return curr
            else: mark.add(curr)
            curr=curr.next
        return None
```

#### offer 24 [反转链表^^^](https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/)

```
class Solution(object):
    def reverseList(self, head):
        prev,curr=None,head
        while curr:
            next_node=curr.next # 暂存下一节点
            curr.next=prev # 修改next引用指向
            prev=curr # prev暂存curr
            curr=next_node # curr访问下一节点
        return prev
```

#### offer 25 [合并两个排序的链表^^](https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)

```
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        cur1,cur2=l1, l2
        if not cur1: return cur2
        elif not cur2: return cur1
        new_cur=ans=ListNode(0)
        while cur1 and cur2:
            if cur1.val<=cur2.val:
                new_cur.next=cur1
                cur1=cur1.next
            else:
                new_cur.next=cur2
                cur2=cur2.next
            new_cur=new_cur.next
        new_cur.next = cur1 if cur1 else cur2
        return ans.next
```

#### offer 27 [二叉树的镜像*](https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/)

```
class Solution(object):
    def mirrorTree(self, root):
        if not root: return None
        #先分别找到源二叉树的左子树和右子树，然后开始翻转二叉树
        left = self.mirrorTree(root.left)
        right = self.mirrorTree(root.right)
        #左子树 == 右子树,右子树 == 左子树
        root.left = right
        root.right = left
        return root
```
#### offer 30 [包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)

```
class MinStack(object):
    def __init__(self):
        self.stack=[]
        self.stack_min=[]
    def push(self, node):
        self.stack.append(node)
        if not self.stack_min:
            self.stack_min.append(node)
        elif node < self.stack_min[-1]:
            self.stack_min.append(node)
        else:
            self.stack_min.append(self.stack_min[-1])
    def pop(self):
        self.stack.pop()
        self.stack_min.pop()
    def top(self):
        return self.stack[-1]
    def min(self):
        return self.stack_min[-1]
```

#### offer 32 [从上到下打印二叉树 II](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)

#### offer 35 [复杂链表的复制*](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/)

#### offer 39 [数组中出现次数超过一半的数字](https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/)

```
class Solution(object):
    def majorityElement(self, nums):
        mark={}
        for item in nums:
            mark[item]=mark.get(item,0)+1
        for k,v in mark.items():
            if v>len(nums)//2:
                return k
```
#### offer 40 [最小的k个数](https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/)

```
class Solution(object):
    def getLeastNumbers(self, li, k):
        def __recursive(begin, end):
            if begin > end: return None
            # 从数列中挑出一个元素，称为"基准"
            left, right = begin, end
            pivot = li[begin]
            # 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
            while left < right:
                while left < right and li[right] > pivot:
                    right = right - 1
                while left < right and li[left] <= pivot:
                    left = left + 1
                li[left], li[right] = li[right], li[left]
            # 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
            li[left], li[begin] = li[begin], li[left]
            __recursive(begin, left - 1)
            __recursive(right + 1, end)

        __recursive(0, len(li) - 1)
        return li[:k]

```
#### offer 43 [整数中1出现的次数（从1到n整数中1出现的次数）](https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=265&tqId=39245&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=)

```
class Solution:
    def NumberOf1Between1AndN_Solution(self , n: int) -> int:
        mark=''
        for i in range(1,n+1):
            mark+=str(i)
        return mark.count('1')
```
#### offer 45 [把数组排成最小的数](https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=265&tqId=39246&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=)

```
import functools
class Solution:
    def PrintMinNumber(self , numbers: List[int]) -> str:
        # write code here
        if not numbers: return ''
        length=len(numbers)
        if length==1: return str(numbers[0])
        
        def __mysort(x,y):
            if (x + y) > (y + x):return 1
            else: return -1
        
        li=[str(i) for i in numbers]
        li.sort(key=functools.cmp_to_key(__mysort))
        return ''.join(li)
```


#### offer 47 [礼物的最大价值*](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/)

```
class Solution(object):
    def maxValue(self, grid):
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0: continue
                if i == 0: grid[i][j] += grid[i][j - 1]
                elif j == 0: grid[i][j] += grid[i - 1][j]
                else: grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
        return grid[-1][-1]
```
#### offer 50 [第一个只出现一次的字符](https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/)

```
class Solution(object):
    def firstUniqChar(self, s):
        mark={}
        for item in s:
            mark[item]=mark.get(item,0)+1
        for item in s:
            if mark[item]==1: return item
        return ' '
```
#### offer 52 [两个链表的第一个公共结点](https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=265&tqId=39250&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=)

```
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        mark1,mark2=pHead1,pHead2
        while mark1!=mark2:
            mark1=mark1.next if mark1 else pHead2
            mark2=mark2.next if mark2 else pHead1
        else:
            return mark1
        return None
```

#### offer 53 [数字在升序数组中出现的次数](https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=265&tqId=39266&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13%26type%3D265&difficulty=undefined&judgeStatus=undefined&tags=&title=)

```
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if len(data)==1:
            if data[0]==k:return 1
            else:return 0
        l=self.getleft(data, k)
        r=self.getleft(data, k+1)
        return r-l
    def getleft(self,data,k):
        left,right=0,len(data)
        while left<right:
            mid=(left+right)//2
            if data[mid]<k:left=mid+1
            elif data[mid]>=k:right=mid
        return left

```

#### offer 54 [二叉搜索树的第k大节点***](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/)

```
class Solution(object):
    def __init__(self):
        self.nodes = []
         
    def kthLargest(self, root, k):
        """二叉搜索树中序遍历是升序数组"""
        if not root or k == 0: return None
        self.inOrder(root)
        return self.nodes[-k]
         
    def inOrder(self, root):
        if not root: return None
        self.inOrder(root.left)
        self.nodes.append(root.val)
        self.inOrder(root.right)
```

#### offer 55 [二叉树的深度*](https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/)

```
class Solution(object):
    def maxDepth(self, root):
        if not root: return 0
        l = self.maxDepth(root.left) + 1
        r = self.maxDepth(root.right) + 1
        if l > r:return l
        else :return r
```

#### offer 56 [数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)

```
class Solution(object):
    def singleNumbers(self, nums):
        mark=set()
        for item in nums:
            if item not in mark:
                mark.add(item)
            else:
                mark.remove(item)
        return list(mark)
```

#### offer 56 [数组中数字出现的次数 II^](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)

```
class Solution(object):
    def singleNumber(self, nums):
        mark={}
        for item in nums:
            mark[item]=mark.get(item,0)+1
        for k,v in mark.items():
            if v==1: return k
```

#### offer 57 [和为s的连续正数序列*](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)

```
class Solution(object):
    def findContinuousSequence(self, target):
        left,right,sum,res=1,2,3,[]
        while left < right:
            if sum == target:
                res.append(list(range(left,right + 1)))
                sum-=left
                left+=1
            if sum>target:
                sum-=left
                left+=1
            else:
                right += 1
                sum+=right
        return res
```

#### offer 57 [和为s的两个数字*](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/)

```
class Solution(object):
    def twoSum(self, nums, target):
        left,right=0,len(nums)-1
        while left<right:
            while left<right and nums[left]+nums[right]==target:
                return [nums[left],nums[right]]
            while left<right and nums[left]+nums[right]>target:
                right-=1
            while left<right and nums[left]+nums[right]<target:
                 left+=1
        return[]
```

#### offer 58 [左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)

```
class Solution(object):
    def reverseLeftWords(self, s, n):
        return s[n:]+s[:n]
```

#### offer 62 [圆圈中最后剩下的数字](https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)

#### offer 64 [求1+2+...+n](https://leetcode-cn.com/problems/qiu-12n-lcof/)

```
class Solution(object):
    def sumNums(self, n):
        return (1+n)*n/2
```

#### offer 68 [二叉树的最近公共祖先*](https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/)