401. 二进制手表

二进制手表

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间
超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 "13:00", "0:61" 等时间。

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        if turnedOn>10:
            return []
        ans=[]
        #extra_len=0 if turnedOn<=7 else turnedOn-7
        #hours和minutes的数字顺序是机关重要的

        #在10个灯里面选择，必须保证hour[i]和minute[i]不能同时选择
        hours=[8,4,2,1,0,0,0,0,0,0]
        minutes=[0,0,0,0,32,16,8,4,2,1]
        def dfs(num,index,hour,minute):
            if hour>11 or minute>59:
                return#剪枝
            if num==0:
                ans.append("{}:{:0>2}".format(hour,minute))
                return 
            for i in range(index,10):
                dfs(num-1,i+1,hour+hours[i],minute+minutes[i])
        dfs(turnedOn,0,0,0)
        return ans

• 从所有序列中挑选序列，可以使用该种办法。

处理方式是，既可以遍历10种不同的灯，又将小时和分钟的数据区分开；同时为了防止选择num个灯的相同顺序不同，统一安排好一个顺序，即选择了该灯，后面的选择，该灯前面的都不应该选。

递归函数：
  for 遍历情况：
    递归函数

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

注意的问题，边界条件，列表越界问题

必须熟练计算复杂度，以降低运行时间

    def findKthPositive(self, arr: List[int], k: int) -> int:
        #设置一个变量count从1开始递增
        #设置一个miss的量，作为结束标志
        #设置一个arr的index
##低内存，低运行时间方案
        count,miscount,index,current=1,0,0,1
        length=len(arr)-1
        while miscount<k:
            if count==arr[index]:
                if index<length:
                    index+=1
            else:
                miscount+=1
                current=count
            count+=1
        return current
        
        '''
        max_=max(arr)
        #遍历一遍
        list_all=list(range(1,max_+k+1))#O(n)
        cnt=0
        for i in list_all:#O(n)
            if i not in arr:#O(n)
                cnt+=1
                if cnt==k:
                    return i
       
        '''

你的初始 能量 为 P，初始 分数 为 0，只有一包令牌 tokens 。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
令牌可能的两种使用方法如下：
如果你至少有 token[i] 点 能量 ，可以将令牌 i 置为正面朝上，失去 token[i] 点 能量 ，并得到 1 分 。
如果我们至少有 1 分 ，可以将令牌 i 置为反面朝上，获得 token[i] 点 能量 ，并失去 1 分 。
每个令牌 最多 只能使用一次，使用 顺序不限 ，不需 使用所有令牌。
在使用任意数量的令牌后，返回我们可以得到的最大 分数 。

• ans表示为该策略中出现的最大数量情况。current是目前的分数（关系到能不能换取大能量的token，换取大能量的策略是一次换一个也可以，这样组合更多，遍历了每一种情况）
• 使用collections的deque用来删除元素，可以进行记忆，这种数据结构挺强大的

为什么使用贪心？使用贪心能否达到全局最优的数学证明：

数学证明

class Solution(object):
    def bagOfTokensScore(self, tokens, P):
    #只能使用贪心，不存在使用正面中间来替换大的能量来收获更多小的能量
        ans=0
        tokens=sorted(tokens)
        #使用队列作为数据结构，分别用来弹出
        deque=collections.deque(tokens)
        current=0
        while deque and(P>=deque[0] or current):
            while deque and P>=deque[0]:
                P-=deque.popleft()
                current+=1
            ans=max(ans,current)
            if deque and current:
                P+=deque.pop()
                current-=1
        return ans

给你一个整数 num 。

你可以对它进行如下步骤恰好 两次 ：
选择一个数字 x (0 <= x <= 9).
选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
将 num 中所有出现 x 的数位都用 y 替换。
得到的新的整数 不能 有前导 0 ，得到的新整数也 不能 是 0 。
令两次对 num 的操作得到的结果分别为 a 和 b 。
请你返回 a 和 b 的 最大差值 。

• 建立初始思路，通过调试改善思路直至正确，思考量小但不严谨

class Solution:
    def maxDiff(self, num: int) -> int:
        #大：找到第一个非9数改为9
        #小：从1开始找到第一个非0数改为0
        str_num=str(num)
        min_flag=False
        min_index,max_index=0,0#该max_index在计算中后移一位
        for i in range(len(str_num)):
            if not min_index:
                if  str_num[i]!=str_num[0] and i>0 and str_num[i]>'0' :
                    min_flag=True
                    min_index=i
            if not max_index:
                if str_num[i]<'9':
                    max_index=i+1
        #print("str_num is",str_num)
        str_num1=str_num
        if not min_flag or str_num[0]>'1':
            str_num1=str_num.replace(str_num[0],'1')
        else:
            str_num1=str_num.replace(str_num[min_index],'0')
        #print("str_num is",str_num)
        str_num2=str_num
        str_num2=str_num.replace(str_num[max_index-1],'9')
        
        return int(str_num2)-int(str_num1)

list可以通过extend可迭代序列增加步长

zip(*)可以序列解包，在大的函数与程序中可能经常使用

a=[[1,2,3],[4,5,6],[7,8,9]]
b,c,d=zip(*a)
print(b,c,d)
'''
(1, 4, 7) (2, 5, 8) (3, 6, 9)
'''

unsqueeze（index）在index列上加一个维度
squeeze（index）在index上减一个列，如果本来就是1维就不再减