排名：519 / 1832

第一题：拥有最多糖果的孩子

思路：

很简单的一个题 直接求出最多的糖果多少，然后判断每个孩子的糖果加上多余的是否可以大于等于最多的。

class Solution(object):
    def kidsWithCandies(self, candies, extraCandies):
        """
        :type candies: List[int]
        :type extraCandies: int
        :rtype: List[bool]
        """
        max_candies = max(candies)

        ans = []
        for x in candies:
            if x+extraCandies>=max_candies:
                ans.append(True)
            else:
                ans.append(False)

        return ans

第二题：改变一个整数能得到的最大差值

思路：

又是一道细节题，我真的不会细节题。这个题思路秒想到，就是先往大了变，找到最高位的不为9的数字，变为9。然后往低了变，但是往低了变可能会把首位数字变为0，所以要特殊对待下.

如果首位数字为1，则寻找除了首位数字以外的最高位且不等于1且不等于0的数字，替换为0.

如果首位数字不是1，则将等于首位数字的数字替换为1

class Solution(object):
    def maxDiff(self, num):
        """
        :type num: int
        :rtype: int
        """
        maxs = 0

        num_str = str(num)

        # 变大
        index = 0
        while index<len(num_str) and num_str[index]=='9':
            index+=1

        if index!=len(num_str):
            big = num_str.replace(num_str[index],'9')
        else:
            big = num_str

        # 变小
        num_str = str(num)

        if num_str[0] == '1':
            i = 1
            while i<len(num_str)-1 and (num_str[i]=='0' or  num_str[i]=='1'):
                i+=1

            if i!=len(num_str):
                small = num_str.replace(num_str[i],'0')
            else:
                small = num_str
        else:
            small = num_str.replace(num_str[0],'1')

        return int(big) - int(small)

第三题：#### 检查一个字符串是否可以打破另一个字符串

思路：

这个题其实很简单，只要排序然后比较即可。

class Solution(object):
    def checkIfCanBreak(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        def helper(s1,s2):
            s1 = sorted(s1)
            s2 = sorted(s2)

            for ch1, ch2 in zip(s1, s2):
                if ch2 < ch1:
                    return False
            return True

        if helper(s1,s2) or helper(s2,s1):
            return True

        return False

187周赛

第一题：5400. 旅行终点站

看原问题的输入规模只有100，且每个输入长度不超过10，很显然即使暴力也可以轻松通过。

每次查找要到的位置，并且更新下一次要查找的位置，如果找不到了，就说明他是终点。

class Solution(object):
    def destCity(self, paths):
        """
        :type paths: List[List[str]]
        :rtype: str
        """
        tos = paths[0][1]
        find = False
        while True:
            for index,path in enumerate(paths):
                if path[0] == tos:
                    tos = path[1]
                    find = True
                    break
                else:
                    find = False

            if not find:
                return tos

考虑每个点的出入度：假如有一条路径从当前节点出去，出度+1，反正入度+1。

则假如图没有环，那么起点的入度为0，终点的出度为0.

所以我们只要记录每个节点的出入度即可，但是这个题目还要更简单一点，因为这个图是一条线，所以我们设置一个变量，如果从当前节点出去则加1，到这个节点则减1，最后找出值为-1的即可。

class Solution(object):
    def destCity(self, paths):
        """
        :type paths: List[List[str]]
        :rtype: str
        """
        d = {}

        for froms,tos in paths:
            if froms not in d:
                d[froms] = 1
            else:
                d[froms]+=1

            if tos not in d:
                d[tos] = -1
            else:
                d[tos] -= 1

        for x in d:
            if d[x]==-1:
                return x

第二题：#### 是否所有 1 都至少相隔 k 个元素

这个题的思路非常清晰，找出所有1的下标然后依次判断即可，难度应该搞错了，属于简单题。

class Solution(object):
    def kLengthApart(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if 1 not in nums:
            return True

        one_index = []

        for index,num in enumerate(nums):
            if num==1:
                one_index.append(index)

        for i in range(1,len(one_index)):
            if one_index[i]-one_index[i-1]<(k+1):
                return False

        return True

第三题：#### 5402. 绝对差不超过限制的最长连续子数组

这一题的思路大概是这样，记录当前最大连续子数组的最大最小值（这个当前数组必须包含当前的这个元素），如果当前元素满足条件，即和最大最小值的绝对值差都小于等于limit则将当前元素加到数组里面，但是假如不满足条件，就比较难办了，因为我们不能直接就让当前子数组等于当前元素，前边的数组的一部分也可能可以满足要求。
例如：
nums = [*8，7，2*，5 ],limt = 5

例如当遍历到2的时候，发现2-8=-6不满足条件，则我们应该让数组变为【7，2】而不是[2]

这里想到了用单调队列q。

单调队列就是一个列表，里面的元素是单调的。用它来记录当前子数组的有序排列。
left,right用来记录当前子数组的边界。
如果不符合条件，则缩小当前数组的范围，则从当前子数组中重复删除左边的元素，直到当前他可以和当前元素满足条件。这里的单调列表，就可以起到 快速判断当前缩小的数组是否符合条件 因为它里面保存的是一个有序的列表，而限制条件只需要和最大最小值比较。

二分查找

对于有序的列表来说，当然要用二分来提高效率。

python标准库自带了一个二分查找的模块 bisert

这里用到的操作：

bisect.insort(A, x) # 将x插入到A中并且保持有序。
bisect.bisect(A, x) # 找到x要插入的位置 eg:bisect.bisect([1,2,4,5], 3) 的值为2
bisect.bisect(A, x)-1 # 找打x的位置

代码如下：

`

import bisect
from typing import List
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        l, r, A, n, ret = 0, 0, [], len(nums), 0
        while r < n:
            bisect.insort(A, nums[r]) # 插入到单调队列里
            while A[-1] - A[0] > limit: # 不满足条件则删除左边的，同时更新单调队列
                del A[bisect.bisect(A, nums[l])-1] # 更新单调队列
                l+=1 # 删除左边的
            ret = max(ret, r -l +1)
            r+=1
        return ret

`