Leetcode刷题第三天-贪心-双指针

738:单调递增

链接：738. 单调递增的数字 - 力扣（LeetCode）

嘶~介个介个恶心心，从后往前遍历，前一个数比当前数大，前一个数-1，当前数变为9

需要注意的是，保证每个9后面全是9

100，第一轮遍历完时90T_T

 1 class Solution:
 2     def monotoneIncreasingDigits(self, n: int) -> int:
 3         if(n<10):   return n
 4         nums=[]
 5         tmp=n
 6         while tmp:
 7             nums.insert(0,tmp%10)
 8             tmp=tmp//10
 9         lens=len(nums)
10         i=lens-1
11         flage=False
12         while i>0:
13             if(nums[i-1]>nums[i]):
14                 nums[i-1]-=1
15                 nums[i]=9
16                 flage=True
17             i-=1
18         n=0
19         start=False
20         for i in range(lens):
21             if(flage and nums[i]==9):
22                 start=True
23             if(start):
24                 n=n*10+9
25             else:
26                 n=n*10+nums[i]
27         return n

968:监控二叉树

链接：968. 监控二叉树 - 力扣（LeetCode）

吐了，真的吐了，从未见过如次厚颜无耻之题

先是统计了每层节点个数，想按层安装，但是会出现子层节点少于父层节点，若在子层节点安装，还需要计算父-父层，跳不出来了T_T

然后迭代，后序遍历T_T左在前，左空的时候直接安到根上，右丢了，右在前，左空了，又跑根上了

最后递归，俩孩子有一个没有被覆盖，父就要安，俩孩子都被覆盖到了，父歇着就好，等待后续判断要不要安，其他情况父被覆盖，最后返回根的左右俩孩子状态，俩孩子都是0，根安T_T我真的已经哭死了

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self, val=0, left=None, right=None):
 4 #         self.val = val
 5 #         self.left = left
 6 #         self.right = right
 7 class Solution:
 8     def minCameraCover(self, root: Optional[TreeNode]) -> int:
 9         re=[0]
10         if(self.help(root,re)==0):  re[0]+=1
11         return re[0]
12 
13     def help(self,root,re):
14         if(not root):   return 2
15         left=self.help(root.left,re)
16         right=self.help(root.right,re)
17         #左右都有覆盖，当前什么都不做
18         if(left==2 and right==2):
19             return 0
20         #左右有一个没覆盖，自己有摄像头
21         elif(left==0 or right==0):
22             re[0]+=1
23             return 1
24         else:
25             #左右有一个摄像头，自己被覆盖
26             return 2

不行了，需要换个脑子了，开始双指针之旅

167:两个数之和

链接：167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

(⊙﹏⊙)就两头开始加

 1 class Solution:
 2     def twoSum(self, numbers: List[int], target: int) -> List[int]:
 3         if(not numbers):    return numbers
 4         left,right=0,len(numbers)-1
 5         while True:
 6             if(left==right):    break
 7             if(numbers[left]+numbers[right]==target):   return [left+1,right+1]
 8             elif(numbers[left]+numbers[right]>target):  right-=1
 9             else:   left+=1
10         return []
11 
12             

142:环形链表

链接：142. 环形链表 II - 力扣（LeetCode）

俩个指针，快的每次走两步，慢的每次走一步，链表有环，快的会再比慢的多走n个环的距离时相遇（跑步套圈）

找环的入口：从头再来一个指针3，也是每次都走一步，指针3和慢指针相遇的时候，比慢指针少走了一个环，相遇位置就是环口

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
 9         if(not head):   return None
10         start,link=head,head
11         while link and link.next:
12             link=link.next.next
13             start=start.next
14             if(link==start):
15                 start=head
16                 while start!=link:
17                     start=start.next
18                     link=link.next
19                 return link
20         return None
21 
22     

76：最小覆盖字串

链接：76. 最小覆盖子串 - 力扣（LeetCode）

待优化，一坨什么玩意

 1 class Solution(object):
 2     def minWindow(self,s,t):
 3         if(not s):  return ""
 4         lent=len(t)
 5         lens=len(s)
 6         if(lens<lent):  return ""
 7         flage={x:t.count(x) for x in t}
 8         left,right,minleft,minright=0,0,-1,lens
 9         while left<lens:
10             if(lent!=0):
11                 strl=s[left]
12                 if(strl not in t):  
13                     left+=1
14                     continue
15                 if(right<lens):
16                     strs=s[right]
17                     right+=1
18                     if(strs in t):
19                         flage[strs]-=1
20                         if(flage[strs]>=0): lent-=1
21                 else:
22                     if(lent>0):   left+=1
23             else:
24                 strl=s[left]
25                 if(strl not in t):  
26                     left+=1
27                     continue
28                 if(right-left<minright-minleft):
29                     minleft=left
30                     minright=right
31                 while left<lens:
32                     strs=s[left]
33                     left+=1
34                     if(strs in t):
35                         flage[strs]+=1
36                         if(flage[strs]>0):  lent+=1
37                         break
38         if(minleft==-1):    return ""
39         return s[minleft:minright]