LeetCode个人中心截图

2021.8.16
image.png
2021.9.5
image.png

前言

因为在面试的时候,发现自己的代码基础和算法基础真的不算特别牢靠,所以特地开个页面来记录一下自己的刷题,也争取督促自己不当懒狗

题目笔记

2021.7.22

数组中有无重复元素

给定一个整数数组,判断是否存在重复元素。
如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false 。

解法:

  1. 直接用python的set,判断set后的数组长度和原始长度是否相同
  2. 数组排序后判断相邻元素是否相同
  3. 将数组遍历过的元素存入哈希表,如果插入新的发现已经存在,则有重复元素

最大子序列和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
解法:

  1. 贪心算法
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = nums[0]
        sum = 0
        for i in range(len(nums)):
            sum = max(sum+nums[i],nums[i])
            ans = max(sum,ans)
        return ans
  1. 动态规划
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1,len(nums)):
            if nums[i-1] >0:
                nums[i] = nums[i] + nums[i-1]
        return max(nums)

删除排序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

解法:
双指针

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        fast = 1
        slow = 1
        while fast < length:
            if(nums[fast] != nums[fast - 1]):
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

买卖股票的最佳时机 II

给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

解法:
贪心算法,我们用后一天减去前一天,得到所有两天间的价格差
然后只要把所有正的价格差加起来,就是最大利润

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        maxmoney = 0
        new = []
        for i in range(1,len(prices)):
            new.append(prices[i]-prices[i-1])
        for j in new:
            if j > 0 :
                maxmoney += j
        return maxmoney 

旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数

解法:
旋转相当于把最后k个数移到前面,直接用python分割操作,注意考虑只有两个数的数组操作不一样就可以

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n != 2:
            nums[:] = nums[n-k:] + nums[:n-k]
        else:
            for i in range(k):
                nums[:] = nums[::-1]
        return nums

2021.7.24

两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

解法:
用哈希表存数据,只需要找target - nums中的数是否存在于哈希表中即可

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = dict()
        for i,num in enumerate(nums):
            if (target - num) in hashmap:
                return [hashmap[target-num],i]
            hashmap[num] = i
        return []

合并两个有序数组

给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。

解法:

  1. 将nums2加到nums1后面,然后将整个新数组重新排序
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2
        nums1.sort()
        return nums1
  1. 用双指针,轮流比较nums1和nums2并将结果放到临时数组sorted
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1=0
        p2=0
        sorted = []
        while p1 < m or p2 < n:
            if p1 == m:
                sorted.append(nums2[p2])
                p2 += 1
            elif p2 == n:
                sorted.append(nums1[p1])
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                sorted.append(nums1[p1])
                p1 += 1
            else:
                sorted.append(nums2[p2])
                p2 += 1
        nums1[:] = sorted
        return nums1   

两个数组的交集

给定两个数组,编写一个函数来计算它们的交集。

解法:
用哈希表存放一个数组的数和他出现的次数,然后遍历另一个数组,如果存在与哈希表并且次数大于0,则加到result,每次遍历到的数在哈希表中次数减少1

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        hashtable = collections.Counter(nums1)
        for i in nums2:
            if i in hashtable and hashtable[i] > 0:
                result.append(i)
                hashtable[i] -= 1
        return result

买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

解法:
用一个变量记录最低的价格,然后在每一天都假设我在最低点买了股票,那么我卖出能挣多少钱,找到最大的利润

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        minprice = prices[0]
        for i in prices:
            minprice = min(i,minprice)
            res = max(res,i-minprice)
        return res

2021.7.25

删除链表中的节点

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为要被删除的节点。

解法:
将要被删除的节点后面节点的值赋给被删除的节点,然后将被删除的节点连到被删除节点后面的后面那个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

删除链表的倒数第N个节点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

解法:

  1. 长度法
    遍历计算出整个链表的长度,第倒数第n个的前一个就是length-n+1,只要让她指向要删除的节点的下一个节点即可
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        length = 0
        dummpy = ListNode(0,head)
        while head:
            length += 1
            head = head.next
        pos = length - n + 1
        cur = dummpy
        for i in range(1,pos):
            cur = cur.next
        cur.next = cur.next.next
        return dummpy.next
  1. 双指针法
    利用快慢双指针,当快指针先走n+1步,然后快慢指针同步移动,当快指针走到结尾时,慢指针刚好在要删除的节点前一个节点
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        left = right = head
        for i in range(n):
            right = right.next
        if right == None:
            return head.next
        while right.next:
            left = left.next
            right = right.next
        if left.next:
            left.next = left.next.next
        return head

反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

解法:
利用三个指针,pre,cur,next来完成,pre一开始指向None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解法:
递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

回文链表

请判断一个链表是否为回文链表。

解法:
将链表存入一个列表,然后分别从前后开始判断是否相等

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        tmplist = []
        while head:
            tmplist.append(head.val)
            head = head.next
        left = 0
        right = len(tmplist)-1
        while left < right:
            if(tmplist[left] != tmplist[right]):
                return False
                break
            left += 1
            right -= 1
        return True

环形链表

给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。

解法:
快慢指针,只要两个指针不一样快,那么如果存在环,他们必定会相遇

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while(fast is not None and fast.next is not None):
            slow = slow.next
            fast = fast.next.next
            if(slow == fast):
                return True
        return False

反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

解法:
双指针,从头尾分别开始,然后交换

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1
        tmp = ""
        while left < right:
            tmp = s[left]
            s[left] = s[right]
            s[right] = tmp
            left += 1
            right -= 1

整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)。

解法:
先将int转为string,然后反转后再转回来

class Solution:
    def reverse(self, x: int) -> int:
        if x == 0:
            return 0
        elif x <0:
            str1 = str(-x)
            str2 = str1[::-1]
            if(-int(str2) < -(2**31)):
                return 0
            else:
                return -int(str2)
        else:
            str1 = str(x)
            str2 = str1[::-1]
            if(int(str2) > (2**31)):
                return 0
            else:
                return int(str2)

2021.8.16

只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

解法:

  1. 用hashmap来存放元素和出现的次数,最后找到值为1的键
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hashmap = dict()
        for i in range(len(nums)):
            if nums[i] in hashmap:
                hashmap[nums[i]] += 1
            else:
                hashmap[nums[i]] = 1
        for key,value in hashmap.items():
            if value == 1:
                return key
                break
  1. 用位运算,相同的元素异或为0,0与非零元素异或为非零元素本身,因为该题目其余元素均为两次,所以所有非一次的数异或完就是0,再与一次的数异或,就是一次的数本身
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for i in nums:
            result = result^i
        return result

两个数组的交集 II

给定两个数组,编写一个函数来计算它们的交集。

解法:

  1. 双指针,先将两个数组进行排序,然后设置两个指针同时从两个数组开始,如果两个指针的值相同,则判定是交集的数,如果不同,则让较小的值的指针向后走,最后直到某个指针走完
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1 = sorted(nums1)
        nums2 = sorted(nums2)
        len1 = len(nums1)
        len2 = len(nums2)
        p1 = 0
        p2 = 0
        result = []
        while(p1<len1 and p2<len2):
            if(nums1[p1] == nums2[p2]):
                result.append(nums1[p1])
                p1 += 1
                p2 += 1
            elif(nums1[p1] < nums2[p2]):
                p1 += 1
            else:
                p2 += 1
        return result
  1. 使用哈希表,将一个数组的元素存入哈希表中,然后遍历另一个数组,如果发现存在并且值大于等于1就加入结果并让值-1
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hashmap = dict()
        res = []
        for i in range(len(nums1)):
            if(hashmap.get(nums1[i])):
                hashmap[nums1[i]] += 1
            else:
                hashmap[nums1[i]] = 1
        for i in range(len(nums2)):
            if(hashmap.get(nums2[i]) and hashmap[nums2[i]] >=1):
                res.append(nums2[i])
                hashmap[nums2[i]] -= 1
        return res

加一

给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。

解法:

  1. 先转字符,再转数字,再加一,再转字符,再转数组
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        str1 = ""
        for i in range(len(digits)):
            str1 += str(digits[i])
        nums = int(str1)
        nums += 1
        str2 = str(nums)
        res = []
        for i in str2:
            res.append(int(i))
        return res
  1. 正常操作数组,只要数组不是全为9,那么从后往前,非九的那一位+1即可,全为9,那就开头1,然后数组原长度个0
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        length = len(digits)
        for i in range(length-1,-1,-1):
            if(digits[i] == 9):
                digits[i] = 0
            else:
                digits[i] += 1
                return digits
        new = [1]
        for i in range(length):
            new.append(0)
        return new

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

解法:

  1. 将0和第一个非0元素换位,以此类推
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        tmp = 0
        for i in range(len(nums)):
            if(nums[i] == 0):
                for j in range(i,len(nums)):
                    if(nums[j] != 0):
                        nums[i] = nums[j]
                        nums[j] = 0
                        break

2021.8.17

有效的数独

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.' 表示。

解法:
利用hashmap,分别判断行,列和3x3的九宫格是否有重复

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        hashmapRow = dict()
        hashmapCol = dict()
        hashmapTable = dict()
        for i in range(9):
            for j in range(9):
                if(board[i][j] != '.' and hashmapRow.get(board[i][j])):
                    return False
                else:
                    hashmapRow[board[i][j]] = 1
            hashmapRow.clear()
        for i in range(9):
            for j in range(9):
                if(board[j][i] != '.' and hashmapCol.get(board[j][i])):
                    return False
                else:
                    hashmapCol[board[j][i]] = 1
            hashmapCol.clear()
        for i in range(0,9,3):
            for m in range(i,i+3):
                for n in range(0,3):
                    if(board[m][n] != '.' and hashmapTable.get(board[m][n])):
                        return False
                    else:
                        hashmapTable[board[m][n]] = 1
            hashmapTable.clear()
            for m in range(i,i+3):
                for n in range(3,6):
                    if(board[m][n] != '.' and hashmapTable.get(board[m][n])):
                        return False
                    else:
                        hashmapTable[board[m][n]] = 1
            hashmapTable.clear()
            for m in range(i,i+3):
                for n in range(6,9):
                    if(board[m][n] != '.' and hashmapTable.get(board[m][n])):
                        return False
                    else:
                        hashmapTable[board[m][n]] = 1
            hashmapTable.clear()
        return True

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

解法:
利用python的zip来先对列进行解包,然后逆序,最后排列成行即可

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        for i,vec in enumerate(zip(*matrix)):
            matrix[i] = list(vec)
            matrix[i].reverse()

2021.8.18

字符串中的第一个唯一字符

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

解法:
直接用hashmap按顺序存字符和出现的次数,然后遍历hashmap的值找到等于1的,然后返回它在字符串的index即可

class Solution:
    def firstUniqChar(self, s: str) -> int:
        hashmap = dict()
        for i in range(len(s)):
            if(hashmap.get(s[i])):
                hashmap[s[i]] += 1
            else:
                hashmap[s[i]] = 1
        for word,i in hashmap.items():
            if(i == 1):
                return s.index(word)
        return -1

有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

解法:
利用hashmap,我们可以用python的collections的Counter来创建关于s和t的字符出现次数的哈希表,然后只需要比较hashmap是否相同即可

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        hashmaps = collections.Counter(s)
        hashmapt = collections.Counter(t)
        if(hashmaps == hashmapt):
            return True
        else:
            return False

验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。

解法:
利用双指针,一个从前往后,一个从后往前,如果遇到特殊字符就跳过,然后判断是否相同

class Solution:
    def isPalindrome(self, s: str) -> bool:
        ptr1 = 0
        ptr2 = len(s) - 1
        dicts = "abcdefghijklnmopqrstuvwxyz0123456789"
        while(ptr1<=ptr2):
            if(s[ptr1].lower() not in dicts):
                ptr1 += 1
            elif(s[ptr2].lower() not in dicts):
                ptr2 -= 1
            elif(s[ptr1].lower() == s[ptr2].lower()):
                ptr1 += 1
                ptr2 -= 1
            else:
                return False
        return True

2021.8.19

字符串转换整数(atoi)

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。
函数 myAtoi(string s) 的算法如下:
读入字符串并丢弃无用的前导空格
检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。

解法,慢慢写if。。把各种可能的情况尽量考虑进去,仍然待优化

class Solution:
    def myAtoi(self, s: str) -> int:
        length1 = len(s)
        if not s:
            return 0
        flag = 1
        n = 0
        while(s[n] == " " and n < length1-1):
            n += 1
        s = s[n:]
        if s[0] == "-":
            flag = -1
            s = s[1:]
        elif s[0] == "+":
            s = s[1:]
        elif not s[0].isdigit:
            return 0
        length = len(s)
        num = ""
        word = "abcdefghijklmnopqrstuvwxyz-+ "
        for i in range(length):
            if ((s[i] in word) and num == ""):
                return 0
            elif ((s[i] in word) and num != ""):
                break
            elif (s[i] == "." and num != ""):
                break
            elif (s[i] == "." and num == ""):
                return 0
            else:
                num += s[i]
        if not num:
            return 0
        num = int(num)
        if(flag == -1):
            return max(-num,-(2**31))
        else:
            return min(num,2**31-1)

实现strStr()

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回-1 。

解法:
1.直接进行循环判断

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        length = len(needle)
        if needle == "":
            return 0
        firstS = needle[0]
        for i in range(len(haystack)):
            if(haystack[i] == firstS):
                if(haystack[i:i+length] == needle):
                    return i
        return -1                
  1. 滑动窗口
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        left = 0
        right = len(needle)
        length = len(haystack)
        if right == 0:
            return 0
        while right <= length:
            if(haystack[left:right] == needle):
                return left
            left += 1
            right += 1
        return -1

2021.8.20

外观数列

给定一个正整数 n ,输出外观数列的第 n 项。
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列:
countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。
前五项如下:
1
11
21
1211
111221
第一项是数字 1
描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"
描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"
描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"
要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。

解法:
利用递归+双指针完成

class Solution:
    def countAndSay(self, n: int) -> str:
        def generate(s):
            res = ""
            slow = 0
            fast = 0
            while(fast < len(s)):
                if (s[slow] == s[fast]):
                    fast += 1
                else:
                    res += str(fast-slow)
                    res += s[slow]
                    slow = fast
            res += str(fast-slow)
            res += s[slow]
            return res
        if n == 1:
            return "1"
        result = "1"
        i = 1
        while(i<n):
            result = generate(result)
            i += 1
        return result

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。

解法:
利用hashmap来判断每一位(代码有点乱

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        length = []
        hashmap = dict()
        for i in strs:
            length.append(len(i))
        res = ""
        miniumstr = strs[length.index(min(length))]
        for i in range(len(miniumstr)):
            for j in range(len(strs)):
                if(hashmap.get(strs[j][i])):
                    hashmap[strs[j][i]] += 1
                else:
                    hashmap[strs[j][i]] = 1
            if(max(hashmap.values()) == len(strs)):
                res += strs[j][i]
            else:
                return res
            hashmap.clear()
        return res

二叉树的最大深度

给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

解法:递归法,直到为叶子节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return max(left,right) + 1

2021.8.23

第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

解法
简单的二分法

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left = 1
        right = n
        res = 1
        while(left <= right):
            half = (left + right) // 2
            if(isBadVersion(half)):
                res = half
                right = half - 1
            else:
                left = half + 1
        return res

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

解法:

  1. 利用排列组合的知识,将n拆分成i个2个j个1,然后C(i/n)即可
class Solution:
    def climbStairs(self, n: int) -> int:
        if n % 2 == 1:
            max2 = n // 2
            nums = 0
            for i in range(1,max2+1):
                nums += comb(i+n-i*2,i)
            nums += 1
            return nums
        else:
            max2 = n // 2
            nums = 0
            for i in range(1,max2):
                nums += comb(i+n-i*2,i)
            nums += 2
            return nums
  1. 动态规划,当是一阶台阶时,只有1种方法,是两阶台阶时,有两种方法
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

买卖股票的最佳时机

见上

2021.8.24

最大子序和

见上

2021.8.26

Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。
如果 n 是3的倍数,输出“Fizz”;
如果 n 是5的倍数,输出“Buzz”;
如果 n 同时是3和5的倍数,输出 “FizzBuzz”。

解法:分情况判断即可

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        res = []
        for i in range(1,n+1):
            if i % 3 == 0 and i % 5 == 0:
                res.append("FizzBuzz")
            elif i % 3 == 0 and i % 5 != 0:
                res.append("Fizz")
            elif i % 3 != 0 and i % 5 == 0:
                res.append("Buzz")
            else:
                res.append(str(i))
        return res

计数质数

统计所有小于非负整数 n 的质数的数量。

解法:
用质数筛,先把所有数设为True,进行循环,如果这个数为True,那么就把这个数后面是这个数的倍数的数全部设为False

class Solution:
    def countPrimes(self, n: int) -> int:
        count = 0
        isPrimenums = [True]*n
        for i in range(2,n):
            if isPrimenums[i]:
                count += 1
                for j in range(i*i,n,i):
                    isPrimenums[j] = False
        return count

2021.8.27

3的幂

给定一个整数,写一个函数来判断它是否是 3 的幂次方。如果是,返回 true ;否则,返回 false 。
整数 n 是 3 的幂次方需满足:存在整数 x 使得 n == 3x

解法:
循环解决

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        while(n>1):
            if n % 3 == 0:
                n = n // 3
            else:
                return False
        return True

罗马数字转整数

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

解法:
将特殊情况列出,其他正常判断

class Solution:
    def romanToInt(self, s: str) -> int:
        sums = 0
        hashmap = dict()
        hashmap = {
            "I" : 1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000
        }
        i = 0
        while(i<len(s)):
            if s[i:i+2] == "CM":
                sums += 900
                i += 2
            elif s[i:i+2] == "CD":
                sums += 400
                i += 2
            elif s[i:i+2] == "XC":
                sums += 90
                i += 2
            elif s[i:i+2] == "XL":
                sums += 40
                i += 2
            elif s[i:i+2] == "IX":
                sums += 9
                i += 2
            elif s[i:i+2] == "IV":
                sums += 4
                i += 2
            else:
                sums += hashmap[s[i]]
                i += 1
        return sums

位1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)。

解法:
先用format转二进制,然后count

class Solution:
    def hammingWeight(self, n: int) -> int:
        return format(n,"0b").count("1")

汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

解法:
辗转相除,每一位比较

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        count = 0
        i = 0
        if x > y:
            while(x > 0):
                if(x % 2 != y % 2):
                    count += 1
                x = x // 2
                y = y // 2
            return count
        else:
            while(y > 0):
                if(x % 2 != y % 2):
                    count += 1
                x = x // 2
                y = y // 2
            return count

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

解法:
将n的最后一位取出给res并右移

class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for i in range(32):
            res <<= 1
            res += n & 1
            n >>= 1
        return res

2021.8.30

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

解法:
因为这里只要求实现尾部插入和头部删除,直接写

class CQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value: int) -> None:
        self.stack1.append(value)

    def deleteHead(self) -> int:
        if self.stack2:
            return self.stack2.pop()
        if not self.stack1:
            return -1
        while(self.stack1):
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

解法:
因为需要最小值,所以在栈的结构中定义两个数组,一个当作栈的操作,一个存放最小值

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minest = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minest or self.minest[-1] >= x:
            self.minest.append(x)

    def pop(self) -> None:
        if self.minest[-1] == self.stack.pop():
            self.minest.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.minest[-1]

字符串解码

给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

解法:
需要注意判断类似10,100这样的数

class Solution:
    def decodeString(self, s: str) -> str:
        stack,nums,res = [],0,""
        for i in s:
            if i == "[":
                stack.append([nums,res])
                nums,res = 0,""
            elif i == "]":
                num,cur_res = stack.pop()
                res = cur_res + num*res
            elif "0" <= i <="9":
                nums = nums*10+int(i)
            else:
                res += i
        return res

2021.9.1

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

解法:
当看见所有组合类型的题目,考虑回溯

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        hashmap = dict()
        hashmap["2"] = "abc"
        hashmap["3"] = "def"
        hashmap["4"] = "ghi"
        hashmap["5"] = "jkl"
        hashmap["6"] = "mno"
        hashmap["7"] = "pqrs"
        hashmap["8"] = "tuv"
        hashmap["9"] = "wxyz"
        if digits == "":
            return []
        def back(conbain,remain):
            if(len(remain) == 0):
                return res.append(conbain)
            else:
                for i in hashmap[remain[0]]:
                    back(conbain+i,remain[1:])
        res = []
        back("",digits)
        return res

反转链表

本题在之前做过,但是感觉自己不是很熟练

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None
        while(cur is not None):
            next1 = cur.next
            cur.next = pre
            pre = cur
            cur = next1
        return pre

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

解法:
利用字典存储原链表的节点

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if head is None:
            return 
        cur = head
        hashmap = dict()
        while(cur):
            hashmap[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while(cur):
            hashmap[cur].next = hashmap.get(cur.next)
            hashmap[cur].random = hashmap.get(cur.random)
            cur = cur.next
        return hashmap[head]

2021.9.2

剑指 Offer 05. 替换空格

请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

解法:
直接遍历替换即可

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = ""
        for i in s:
            if i == " ":
                res += "%20"
            else:
                res += i
        return res

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。

解法:
利用python的字符串切割,将前n位移到后面即可

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        res = ""
        left = s[0:n]
        right = s[n:]
        res += right
        res += left
        return res

2021.9.3

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数

解法:
哈希表解决

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        hashmap = dict()
        hashmap = collections.Counter(nums)
        for i,num in hashmap.items():
            if num > 1:
                return i
                break

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

解法:

  1. 哈希表
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        hashmap = dict()
        hashmap = collections.Counter(nums)
        if(hashmap[target] is None):
            return 0
        else:
            return hashmap[target]
  1. 二分查找,利用到了排序好的数组
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i = 0
        j = len(nums)-1
        while(i <= j):
            mid = (i+j) // 2
            if nums[mid] > target:
                j = mid - 1
            else:
                i = mid + 1
        right = i
        i = 0
        while(i <= j):
            mid = (i+j) // 2
            if nums[mid] < target:
                i = mid + 1
            else:
                j = mid - 1
        left = j
        return (right-left-1)

剑指 Offer 53 - II. 0~n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

解法:
有几个特殊情况就是首尾缺失需要特殊考虑,其他就考虑两个相邻的差不为1即可

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        if nums[-1] != n:
            return n
        elif nums[0] != 0:
            return 0
        else:
            for i in range(0,n-1):
                if nums[i+1] - nums[i] != 1:
                    return nums[i] + 1

2021.9.4

剑指 Offer 04. 二维数组中的查找

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

解法:
从左下角开始判断,如果大于,则往右查找,小于,则往下查找

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0:
            return False
        i = len(matrix) - 1
        j = 0
        while(i >= 0  and j <= len(matrix[0]) - 1):
            if(matrix[i][j] == target):
                return True
            elif matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        return False

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。 

解法:
遍历,如果发现突然后面比前面小,则是后面那个数

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        mini = numbers[0]
        for i in range(len(numbers)-1):
            if numbers[i+1] < numbers[i]:
                mini = numbers[i+1]
        return mini

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

解法:
哈希表解决

class Solution:
    def firstUniqChar(self, s: str) -> str:
        hashmap = dict()
        hashmap = collections.Counter(s)
        for i in s:
            if hashmap[i] == 1:
                return i
        return " "

2021.9.5

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

解法:
利用队列存放要遍历的节点

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        res = []
        if root is None:
            return res
        quene = collections.deque()
        quene.append(root)
        while quene:
            node = quene.popleft()
            res.append(node.val)
            if(node.left):
                quene.append(node.left)
            if(node.right):
                quene.append(node.right)
        return res

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行

解法:
相比于上一题,增加了一个每一层打印到一行的要求,稍微改下代码

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        quene = collections.deque()
        quene.append(root)
        while quene:
            tmp = []
            for i in range(len(quene)):
                node = quene.popleft()
                tmp.append(node.val)
                if node.left:
                    quene.append(node.left)
                if node.right:
                    quene.append(node.right)
            res.append(tmp)
        return res

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

解法:
此题增加了一个奇偶数判断并倒序输出的功能,我们可以利用python的两端队列,偶数就从左边加入队列

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if root is None:
            return res
        quene = collections.deque([root])
        flag = 1
        while quene:
            tmp = collections.deque()
            for i in range(len(quene)):
                node = quene.popleft()
                if flag > 0:
                    tmp.append(node.val)
                else:
                    tmp.appendleft(node.val)
                if node.left:
                    quene.append(node.left)
                if node.right:
                    quene.append(node.right)
            res.append(list(tmp))
            flag *= -1
        return res

2021.9.6

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。

解法:
简单的遍历

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: return True
            if not A or A.val != B.val: return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

剑指 Offer 27. 二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

解法:
直接遍历,使用python交换左右

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left,root.right = self.mirrorTree(root.right),self.mirrorTree(root.left)
        return root

剑指 Offer 28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

解法:
判断左右是否相等和左左和右右是否相等

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def subtree(L,R):
            if not L and not R:
                return True
            if not L or not R or L.val != R.val:
                return False
            return subtree(L.left,R.right) and subtree(L.right,R.left)
        if root:
            return subtree(root.left,root.right)
        return True

剑指 Offer 10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))

解法:
直接a,b双值即可解决

class Solution:
    def fib(self, n: int) -> int:
        a = 0
        b = 1
        for i in range(n):
            a,b = b,a+b
        return a % 1000000007

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

解法:
同样可以用类似斐波那契数列理解

class Solution:
    def numWays(self, n: int) -> int:
        if n == 0:
            return 1
        a = 1
        b = 1
        for i in range(n):
            a,b = b,a+b
        return a % 1000000007

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

解法:
动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        mini = float("+inf")
        profit = 0
        for price in prices:
            mini = min(mini,price)
            profit = max(profit,price-mini)
        return profit

2021.9.8

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

解法:
动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        sums = 0
        for i in range(len(nums)):
            sums = max(nums[i],nums[i]+sums)
            res = max(res,sums)
        return res

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

解法:
动态规划,一个点的最大值只能来自左方或上方

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0:
                    continue
                elif 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 46. 把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

解法:
动态规划判断两个能否翻译成字母即可,然后累加之前的可能数

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2,len(s)+1):
            if "10" <= s[i-2:i] <= "25":
                a,b = a+b,a
            else:
                a,b = a,a
        return a

739. 每日温度

请根据每日 气温 列表 temperatures ,请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高,请在该位置用 0 来代替。

解法:
使用单调栈处理

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stack = []
        res = [0]*n
        for i in range(n):
            if i == 0:
                stack.append((temperatures[i],0))
            else:
                while(stack and stack[-1][0] < temperatures[i]):
                    item = stack.pop()
                    res[item[1]] = i - item[1]
                stack.append((temperatures[i],i))
        return res