leetcode每日一题(一)_分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2

89. 格雷编码 1.8

算法思路：

如果我们有一个二进制数序列，我们也可以将它直接转换成格雷码序列。假设n 位二进制数为b，对应的格雷码为g，转换规则如下：

g(i)=b(i+1)⊕b(i), 0≤i<n

其中⊕ 是按位异或运算，g(i)和b(i) 分别表示 g 和b 的第 i 位，且 b(n)=0。

也就是，二进制数i与i右移一位的异或结果，就为i对应的格雷编码。

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        res=[]
        for i in range(1<<n):#若n为3，则有2的3次方个数0-7依次遍历
            res.append(i^i>>1)
        return res
1
2
3
4
5
6
7
8
9
10

2.两数相加

算法思路：

两个链表从头开始遍历位，逐位相加，保存进位（求整除），新链表中保存结果（求余数）。
只要有一个链表不为空，就需计算，往后进行
两个链表都结束，进位项不为0，需把进位项添加在链表结果后面

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result=curr=ListNode()#result用于返回最后的结果，curr用于保留每位计算结果
        remainder=0#进位标志
        while l1 or l2:#1.有一个链表不为空就计算
            x=l1.val if l1 else 0
            y=l2.val if l2 else 0
            total=x+y+remainder
            curr.next=ListNode(total%10)
            remainder=total//10
            #三个指针向后移动
            #2.判断是否为空，空链表的next会报错
            if l1:
                l1=l1.next
            if l2:
                l2=l2.next
            curr=curr.next
        if remainder:#进位不为0，添加到链表后
            curr.next=ListNode(remainder)
        return result.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1629.按键持续时间最长键 1.9

算法思路：
简单题，算出每个键对应的时间，再选最大即可。注意，如果最长时间相等要选序列最小值。

class Solution(object):
    def slowestKey(self, releaseTimes, keysPressed):
        """
        :type releaseTimes: List[int]
        :type keysPressed: str
        :rtype: str
        """
        ans=keysPressed[0]
        maxtime=releaseTimes[0]
        for i in range(1,len(keysPressed)):
            key=keysPressed[i]
            time=releaseTimes[i]-releaseTimes[i-1]
            if time>maxtime or time==maxtime and key>ans:#不能写为>=
                ans=key
                maxtime=time
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.寻找两个正序数组的中位数（难）

算法思想：二分查找法
难的是边界处理
要求：1.分割线左边元素个数与右边元素个数满足关系（统一左边可多一个）
2.分割线两边元素满足交叉小于等于

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n1=len(nums1)
        n2=len(nums2)
        if n1>n2:#交换，nums1为较短的那个
            return self.findMedianSortedArrays(nums2,nums1)
        #分割线左边的所有元素需要满足的个数m+(n-m+1)/2
        k=(n1+n2+1)//2

        #在nums1的区间[0,m]里查找恰当的分割线
        #使得nums1[i-1]<=nums2[j]&&nums2[j-1]<=nums1[i]
        #满足交叉关系：第一个的分割线最左边的元素小于等于第二个的分割线右边的
        # 且 第二个的分割线最左边的小于第一个的分割线最右边的

        left=0
        right=n1

        while left<right:
            m1=left+(right-left)//2
            m2=k-m1
            if nums1[m1]<nums2[m2-1]:#nums1的右边数比nums2左边数小，分界线化小了
                left=m1+1#nums1分界线右移
            else:
                right=m1#反之，变为右边界，缩小范围
        m1=left#第一个分界线
        m2=k-m1#第二个分界线
        c1=max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )#选两个分界线左边的最大值
        if (n1+n2)%2==1:#奇数，直接输出
            return c1
        c2=min(nums1[m1] if m1<n1 else float("inf"),nums2[m2] if m2<n2 else float("inf"))#选两个分界线右边的最小值
        return (c1+c2)*1.0/2  #偶数，返回平均数
        #如果用python3返回值为float,这里就不用转变为小数型，否则要写，不然有测试通过不了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

306.累加数组 1.10

算法思路：将很长的整数转为字符串，就可以解决溢出。
穷举累加序列第一个数字和第二个数字的所有可能性，对每个可能性，进行一次合法性的判断。当出现一次合法的累加序列后，即可返回 true。当所有可能性都遍历完仍无法找到一个合法的累加序列时，返回 false。

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        def dfs(num,firstnum,secondnum):
            if not num:
                return True
            total=firstnum+secondnum
            length=len(str(total))
            if str(total)==num[:length]:#字符串，防止溢出
                return dfs(num[length:],secondnum,total)#若满足，则继续判断
            return False

        for i in range(1,len(num)-1):#i遍历第二个数
            if num[0]=='0' and i>1:#除0外，以0开头的数字不存在
                break
            for j in range(i+1,len(num)):#j遍历第三个数
                if j-i>1 and num[i]=='0':#第三个数的位数已经大于第二个数的并且第i位数为0，不满足则退出
                    break
                if dfs(num[j:],int(num[:i]),int(num[i:j])):#判断三个数，是否满足累加条件
                    return True
        return False    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1036.逃离大迷宫（难） 1.11

算法思想：BFS + 给定障碍物所能围成的最大面积
MAX为最大访问点数量，从起点开始跑一边dfs，并从终点开始跑一边dfs。若他们已访问点数都超过了最大的访问点数，则不必继续遍历，返回true，因为一定能走通。
数量为n的障碍，最多能包围像下图所示的这么多个面积，MAX=1+2+3+…+n-1=n*(n-1)/2。若从起点终点开始，已经超过障碍所围的最大面积，则说明必能走通。反之继续遍历没走过的点，统计个数。若全部都走完还未走出则false。

BOUND=int(1e6)#1x10的6次方
class Solution(object):
    def isEscapePossible(self, blocked, source, target):
        """
        :type blocked: List[List[int]]
        :type source: List[int]
        :type target: List[int]
        :rtype: bool
        """
        blocked,MAX={tuple(p) for p in blocked},len(blocked)*(len(blocked)-1)//2
        def bfs(start,end):
            points,idx,explored=[start],0,{tuple(start)}#points保存已经过的点，idx从0位置开始遍历points队列里的点；explored保存已探索过的
            while idx<len(points):
                for dx,dy in (0,1),(1,0),(-1,0),(0,-1):#四个方向
                    nx,ny=points[idx][0]+dx,points[idx][1]+dy#这个点的x,y加上对应的方向
                    if 0<=nx<BOUND and 0<=ny<BOUND and (nx,ny) not in blocked and (nx,ny) not in explored:#这个点移动后的位置在边界内，不是封锁的，没有探索过
                        if [nx,ny]==end:#已经到终点
                            return True
                        explored.add((nx,ny))#还不是终点，标记探索过
                        points.append((nx,ny))#还不是终点，标记有遍历，将从这个点出发
                if len(points)>MAX:#如果遍历的点，超过最大面积，则肯定能走出
                    return True
                idx+=1#遍历下一个点
            return False
        return bfs(source,target) and bfs(target,source)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

334.递增的三元子序列 1.12

算法思想：双向遍历，遍历nums每个数，若有大于左边的最小值，小于右边的最大值，则是递增的三元序列。找最大最小值，只需保存在i-1,i+1这种位置，然后它们再和i对比，就不用重新遍历整个数组。时间复杂度：O（n）nums要遍历三遍,空间复杂度O（n）要创建两个长度为n的数组

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums)<3:
            return False
        n=len(nums)
        leftMin=[0]*n
        leftMin[0]=nums[0]
        for i in range(1,n-1):#第一次遍历
            leftMin[i]=min(leftMin[i-1],nums[i])
        rightMax=[0]*n
        rightMax[n-1]=nums[n-1]
        for i in range(n-2,-1,-1):#第二次遍历
            rightMax[i]=max(rightMax[i+1],nums[i])
        for i in range(1,n-1):#判断有没有符合的
            if leftMin[i-1]<nums[i]<rightMax[i+1]:
                return True
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果需要O（1）的空间复杂度，也就是不能申请另外的数组空间。可使用贪心，设两个变量first,second，可找first<second<num，first和second要尽可能小，这样最容易找到递增三元,且只要找到就返回，不一定全部遍历完，速度快。
时间复杂度O（n）只需遍历一遍。

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        first, second = nums[0], float('inf')
        for i in range(1, n):
            num = nums[i]
            if num > second:#只要找到一个，就说明有返回true
                return True
            if num > first:#second是第二小的
                second = num
            else:#first是最小的
                first = num
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

747.至少是其他数字两倍的最大数(简) 1.13

提示：
1 <= nums.length <= 50
0 <= nums[i] <= 100
nums 中的最大元素是唯一的
算法思路：题目要求找出至少是其他数两倍的最大值，只需判断数组中的最大值>=次最大值*2，遍历过程中，维护好下标。
备注：自己刚开始想着用排序，再一个个去判断是不是大于2倍。有更好的方法，不需要排序，也不需要一个个去判断。只需维护最大值和次最大值的坐标，并判断他们符不符合关系即可。时间复杂度O(n)需遍历数组一遍,空间复杂度O(1)

class Solution(object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        if n==1:#依题意得，只有一个数，返回的是0
            return 0
        maxest,max=0,-1#最大值，次最大值下标维护
        for i in range(1,n):
            if nums[i]>nums[maxest]:#找到最大值
                max=maxest#最大值变为次最大值
                maxest=i#这个值变为最大值
            elif max==-1 or nums[i]>nums[max]:#找到次最大值
                max=i#次最大值变为这个
        return maxest if nums[maxest]>=nums[max]*2 else -1#依题意得，不满足返回的是-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

373.查找和最小的K对数 1.14

算法思想：暴力，1.分别取nums1和nums2中的前k个遍历
2.使用python的小根堆 heap存储，堆顶元素是最小的。(由于题目是两数之和的最小值，我们可将两数之和的结果取反，放入堆中。由于heappop出队是将堆顶（最小值）的元素移除，所以当堆满时，可以将原数的最大值移除)
时间复杂度：O(k^2logk)
空间复杂度：O(k)

class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[List[int]]
        """
        heap=[]#pyhhon为小根堆
        for a in nums1[:k]:
            for b in nums2[:k]:
                #结果取反，堆顶为最小值，也就是原来两数的最大值
                heappush(heap,(-a-b,a,b))
                if len(heap)>k:#堆满
                    heappop(heap)#堆顶元素去掉，也就是去掉原来的最大值
        return [[a,b] for _,a,b in heap]#最终堆保存的是原来的k个最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1716.计算力扣银行的钱(简) 1.15

算法思路：非常简单的数学题，可暴力遍历，可直接用等差公式

class Solution(object):
    def totalMoney(self, n):
        """
        :type n: int
        :rtype: int
        """
        S7=28#一周7天总和
        x=n//7#有几周
        y=n%7#最后一周有几天
        return x*S7+(x-1)*x*7/2+(1+y)*y/2+y*x
1
2
3
4
5
6
7
8
9
10

382.链表随机节点 1.16

算法思想：先在列表中记录链表中的每个值，用random.choice(seq)随机选择链表中的一个节点，就变成在数组中随机选择一个元素。另外一种新解法是蓄水池抽样算法，没了解。

class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.arr = []
        while head:
            self.arr.append(head.val)#节点的值添加到列表
            head = head.next

    def getRandom(self) -> int:
        return choice(self.arr)#choice() 方法返回一个列表，元组或字符串的随机项。

1
2
3
4
5
6
7
8
9
10

1220.统计元音字母序列的数目（难） 1.17

提示：1 <= n <= 2 * 10^4
算法思想：写出动态规划的转移方程。还有其他算法：矩阵快速幂。
时间复杂度：令 C 为字符集大小，本题 C 固定为 5。整体复杂度为 O(n * C)
空间复杂度：O(n * C)

class Solution(object):
    def countVowelPermutation(self, n):
        """
        :type n: int
        :rtype: int
        """
        f=[[0 for i in range(5)] for _ in range(n) ]
        for i in range(5):#初始化数组
            f[0][i]=1
        MOD=1e9+7
        ans=0
        for i in range(n-1):
            f[i+1][1]+=f[i][0]

            f[i+1][0]+=f[i][1]
            f[i+1][2]+=f[i][1]

            f[i+1][0]+=f[i][2]
            f[i+1][1]+=f[i][2]
            f[i+1][3]+=f[i][2]
            f[i+1][4]+=f[i][2]

            f[i+1][2]+=f[i][3]
            f[i+1][4]+=f[i][3]

            f[i+1][0]+=f[i][4]
            for j in range(5):
                f[i+1][j]%=MOD
        for j in range(5):
            ans+=f[n-1][j]
        return int(ans%MOD)
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

539.最小时间差 1.18

算法思路：排序，先将timePoints排序，最小时间差必然出现在两个相邻时间差或两个首位时间差中。排序后，遍历，计算出时间差即可得到最小时间差。

• 表示无穷大 ans=float(‘inf’)
• ord(c）函数是返回字符c的ASCLL值。
• str t="12:59"时间值为(ord(t[0])-ord(‘0’))*10+ord(t[1])-ord(‘0’))*60为小时部分，转为分钟；(ord(t[4])-ord(‘0’))*10+ord(t[4])-ord(‘0’)为分钟部分

def getMinutes(t):
    return int(((ord(t[0])-ord('0'))*10+ord(t[1])-ord('0'))*60+(ord(t[3])-ord('0'))*10+ord(t[4])-ord('0'))

class Solution(object):
    def findMinDifference(self, timePoints):
        """
        :type timePoints: List[str]
        :rtype: int
        """
        timePoints.sort()
        t0=getMinutes(timePoints[0])
        pretime=t0
        ans=float("inf")
        for i in range(1,len(timePoints)):
            nowtime=getMinutes(timePoints[i])
            time=nowtime-pretime#相邻时间的时间差
            pretime=nowtime
            ans=min(time,ans)
        return min(ans,t0+1440-pretime)#首尾时间的时间差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

219.存在重复元素II(简) 1.19

算法思路：维护一个哈希表set，里面始终最多包含k个元素，当出现重复值则说明在k距离内存在重复元素；每次遍历一个元素将其加入哈希表中，如果哈希表的大小大于k，则移除最前面的数字。

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        n=len(nums)
        s=set()
        for i in range(n):
            if nums[i] in s:#如果在表中，则说明存在
                return True
            s.add(nums[i])
            if len(s)>k:#维持长度k，超过，移除第一个加入的
                s.remove(nums[i-k])
        return False     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2029.石子游戏IX 1.20

示例 1：

输入：stones = [2,1]
输出：true
解释：游戏进行如下：

• 回合 1：Alice 可以移除任意一个石子。
• 回合 2：Bob 移除剩下的石子。 已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。

示例 2：

输入：stones = [2]
输出：false
解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。
由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。

示例 3：

输入：stones = [5,1,2,4,3]
输出：false
解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：

• 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。
• 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。
• 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。
• 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.
• 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15. Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。

算法思想：博弈论
借用力扣Benhao大佬的题解。

1. 石子按模3区分，原来的大小在同一个余数堆里没有区别
2. 模3余0的石子成对出现等于没出现，因为对方被迫选了模3余0，我们再选模3余0还会让他面对刚刚的局面
3. 先手拿1，整体的选择只能为 1 1 2 1 2 1 2 …
4. 先手拿2，整体的选择只能为 2 2 1 2 1 2 1 …
5. 如果没有模3余0的石子（成对出现了），Alice先手取更少的那边的石子是必胜态，会逼对方必须从更少的石子中拿石子，他会先拿光
6. 如果没有模3余0的石子（成对出现了），且有一堆余1或余2的石子没有，那么Alice要么在第三回合输，要么拿光也没有出现模3余0，Bob必胜
7. 如果有模3余0的石子（奇数个），由于出现了一个反制的选择，如果拿更少的石子，对方拿模3余0的石子会导致自己永远要选更少的石子而先输掉游戏，
   所以必须拿更多的那一边，只多一个或两个还不行，因为那样Bob总有拿光也没有出现模3余0的策略，Bob必胜。
   只有当有一堆石子更多且多至少3个时候，Alice才有逼对方在这堆石子取到模3余0的策略（先拿更多的那边，后面对方拿0我们取这堆，对方拿这堆里的我们取0）

总结：
偶数个整除3的石子下，Alice的策略为拿1或2更少的那边，如果1或2里有一堆没有，Alice无法获胜。
奇数个整除3的石子下，Alice的策略为拿1或2更多的那边，如果更多的那边不比另一堆多至少3个，Alice无法获胜

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        # 1 1 2 1 2 1 2 1 2 ...
        # 2 2 1 2 1 2 1 2 1 ...
        cnts = [0] * 3
        for num in stones:
            if not (m := num % 3):#:=是3.8里的海象运算符
                cnts[m] ^= 1#异或
            else:
                cnts[m] += 1
        if not cnts[0]:
            # Alice获胜的策略必然是先取1或2中更少的那个，如果有一个没得可取，
            # 那么Alice必然是拿到第一个模3余0（第三次为Alice取），要么石子全拿光也不会是0（比如两个1）
            return min(cnts[1], cnts[2]) > 0
        else:
            # 拥有了一个先手反制的选择（再非第一回合选择模3余0的数，会导致本来该自己必须选某堆石子变为对方必须先选）
            # 那么Alice第一回合必须拿更多的那边的石子（更少会导致对方拿模3余0，我们面对上面分析的必输态）
            # 如果拿走一个以后，更多的石子和另一堆一样多 或者 只多一个，那么Bob总有永远和不为3且取光所有石子的选择。
            return abs(cnts[1] - cnts[2]) > 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1345.跳跃游戏IV(难) 1.21

算法思路：广度优先搜索BFS,但不能是普通的BFS,需要剪枝，否则超时。
现在没看太懂，先把代码放这。

#官方
class Solution(object):
    def minJumps(self, arr):
        idxSameValue = defaultdict(list)
        for i,a in enumerate(arr):
            idxSameValue[a].append(i)
        visitedIndex=set()
        q=deque()
        q.append([0,0])
        visitedIndex.add(0)
        while q:
            idx,step=q.popleft()
            if idx==len(arr)-1:
                return step
            v=arr[idx]
            step+=1
            for i in idxSameValue[v]:
                if i not in visitedIndex:
                    visitedIndex.add(i)
                    q.append([i,step])
            del idxSameValue[v]
            if idx+1<len(arr) and (idx+1) not in visitedIndex:
                visitedIndex.add(idx+1)
                q.append([idx+1,step])
            if idx-1>=0 and (idx-1) not in visitedIndex:
                visitedIndex.add(idx-1)
                q.append([idx-1,step])



            if i not in visitedIndex:
                visitedIndex.add(i)
                q.append([i,step])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#网友题解
class Solution:
    def minJumps(self, arr):
        """
        对于目前状态，会有三种下一步的情况
        1）+1
        2）-1
        3）和相同数字的其他坐标，需要通过数组来预先构建
        记录一个visited来避免循环遍历
        遍历的层数就是对应的操作次数
        """
        n=len(arr)
        num2idxs={}
        for i in range(n):
            #连续出现相同值的区间只保留左右两个端点，起到搜索剪枝的作用
            if i in (0,n-1):
                num2idxs[arr[i]]=num2idxs.get(arr[i],[])+[i]
            elif arr[i]!=arr[i-1] or arr[i]!=arr[i+1]:
                num2idxs[arr[i]]=num2idxs.get(arr[i],[])+[i]
        visited=[True]+[False]*(n-1)
        queue=[(0,0)]
        while queue:
            i,step=queue.pop(0)
            for j in (num2idxs.get(arr[i],[])+[i-1,i+1]):#j为下一步的index
                if 0<=j<n and not visited[j]:
                    if j==n-1:    #下一步为终点，剪枝
                        return step+1
                    visited[j]=True
                    queue.append((j,step+1))
            num2idxs[arr[i]]=[]   #这个高度已经visited,防止TLE超时
        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

1332.删除回文字序列(简)1.22

算法思路:脑筋急转弯，字符串里只有a,b两种；若是回文字符串，则只需要删除一次，若不是回文字符串则只需要删除两次（第一次全a,第二次全b）。所以最多删除两次。

class Solution(object):
    def removePalindromeSub(self, s):
        """
        :type s: str
        :rtype: int
        """
        return 1 if s==s[::-1] else 2
1
2
3
4
5
6
7

2034.股票价格波动1.23

算法思路：维护一个最大的时间戳，维护一个价格的有序列表（在相同时间戳更新价格时删掉原来错误的时间戳）
题目有点看不懂，偏，还没看。

from sortedcontainers import SortedList
class StockPrice:
    def __init__(self):
        self.sl = SortedList()
        self.time_map = {}
        self.max_time = -inf

    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.time_map:
            self.sl.discard(self.time_map[timestamp])
        self.sl.add(price)
        self.time_map[timestamp] = price
        self.max_time = max(self.max_time, timestamp)

    def current(self) -> int:
        return self.time_map[self.max_time]

    def maximum(self) -> int:
        return self.sl[-1]

    def minimum(self) -> int:
        return self.sl[0]


# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2045.到达目的地的第二短时间(难)1.24

算法思路：难，跳过了

class Solution(object):
    def secondMinimum(self, n, edges, time, change):
        """
        :type n: int
        :type edges: List[List[int]]
        :type time: int
        :type change: int
        :rtype: int
        """
        graph=[[] for _ in range(n+1)]
        for e in edges:
            x,y=e[0],e[1]
            graph[x].append(y)
            graph[y].append(x)
        #dist[i][0]表示从1到i的最短路径长度，dist[i][1]表示从1到i的严格次路径长度
        dist=[[float('inf')]*2 for _ in range(n+1)]
        dist[1][0]=0
        q=deque([(1,0)])
        while dist[n][1]==float('inf'):
            p=q.popleft()
            for y in graph[p[0]]:
                d=p[1]+1
                if d<dist[y][0]:
                    dist[y][0]=d
                    q.append((y,d))
                elif dist[y][0]<d<dist[y][1]:
                    dist[y][1]=d
                    q.append((y,d))
        ans=0
        for _ in range(dist[n][1]):
            if ans%(change*2)>=change:
                ans+=change*2-ans%(change*2)
            ans+=time
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

1688.比赛中的配对次数(简)1.25

算法思想：数学，模拟。简单题

class Solution(object):
    def numberOfMatches(self, n):
        """
        :type n: int
        :rtype: int
        """
        sum=0
        while n!=1:
            sum+=n//2
            if n%2==1:
                jingji=n//2+1
            else:
                jingji=n//2
            n=jingji
        return sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2013.检测正方形1.26

算法思路：
先考虑如何实现int count(int[] point),记输入的point的横坐标分别为x和y。则形成的正方形的上下两边中，其中一条边的纵坐标为y,我们枚举另一条边的纵坐标为col，则正方形的边长d为|y-col|且大于0。有了其中一个点的坐标(x,y)和一条横边的纵坐标col,我们可以得到正方形的四个点的坐标分别为(x,y),(x,col),(x+d,y),(x+d,col)或(x,y),(x,col),(x-d,y),(x-d,col)。
据此，我们可以用一个哈希表来存储void add(int[] point)函数中加入的点。先把点按照行来划分，键为行的纵坐标，值为另一个哈希表，其中键为该行中点的横坐标，值为这样的点的个数。因为点会重复出现，所以计算正方形的个数时需要把另外三个坐标出现的次数相乘。

class DetectSquares(object):

    def __init__(self):
        self.map=defaultdict(Counter)


    def add(self, point):
        """
        :type point: List[int]
        :rtype: None
        """
        x,y=point
        self.map[y][x]+=1


    def count(self, point):
        """
        :type point: List[int]
        :rtype: int
        """
        res=0
        x,y=point
        

        if not y in self.map:
            return 0
        yCnt=self.map[y]

        for col,colCnt in self.map.items():
            if col!=y:
                #根据对称性，这里可以不用取绝对值
                d=col-y
                res+=colCnt[x]*yCnt[x+d]*colCnt[x+d]
                res+=colCnt[x]*yCnt[x-d]*colCnt[x-d]
        return res



# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2047.句子中的有效单词数(简)1.27

算法思路：遍历
首先将句子按空格分割成单词，然后判断单词是否有效。不有效的条件为以下其中之一：

• 单词中包含数字
• 单词中包含两个以上连字符
• 连字符在单词头部或者单词末尾
• 连字符的左/右边不是小写字母
• 单词的标点符号不在单词的末尾

记录有效的单词个数，即为答案

class Solution(object):
    def countValidWords(self, sentence):
        """
        :type sentence: str
        :rtype: int
        """
        def valid(s):
            hasHyphens=False  #标记之前是否遇到过‘-’
            for i ,ch in enumerate(s):
                if ch.isdigit() or ch in "!.," and i<len(s)-1:
                    return False
                if ch=='-':
                    if hasHyphens or i==0 or i==len(s)-1 or not s[i-1].islower() or not s[i+1].islower():  #如果之前有遇到过，或这个连字符在头尾两位置，或这个连字符左右两边不是小写
                        return False
                    hasHyphens=True
            return True
        return sum(valid(s) for s in sentence.split())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1996.游戏中弱角色的数量1.28

算法思想：按攻击从小到大、防御从大到小排序后，我们得到一个比较满意的顺序，遍历到当前的指针时，之前的怪的攻击都是大于等于自己的，我们只需要知道他们之中大于自己攻击力的最高防御力，来确认自己是不是弱角色。
统计弱角色的个数。

class Solution(object):
    def numberOfWeakCharacters(self, properties):
        """
        :type properties: List[List[int]]
        :rtype: int
        """
        properties.sort(key=lambda x:(-x[0],x[1]))#.sort()是默认升序  攻击有个负号从大到小排序  防御从小到大排序  
        ans=0
        maxDef=0#最大防御
        for _, def_ in properties:
            if maxDef>def_:#当前的防御小于最大防御
                ans+=1#说明是弱角色
            else:
                maxDef=max(maxDef,def_)#否则，更新最大防御值
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15