算法day35|860，406，452

目录

860.柠檬水找零

406.根据身高重建队列

452. 用最少数量的箭引爆气球

860.柠檬水找零

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five,ten,twenty = 0,0,0
        for bill in bills:
            #情况一：如果bills是5元，不需要找零
            if bill == 5:
                five += 1
            #情况二:如果bills是10元，找5元
            elif bill == 10:
                if five >= 1:
                    five -= 1
                    ten += 1
                else:
                    return False
            #情况三，如果bills是20元,找10元，找5元，贪心算法，先花大的，再画小的
            else:
                if ten >0 and five >0:
                    twenty += 1
                    ten -= 1
                    five -= 1
                elif five >2:
                        five -=3
                else:
                    return False
        return True

看起来还挺难的，只需要知道三个逻辑。

1.如果是5块，不需要找

2.如果是10块，找5

3.如果是20块，找5和10.

本题看上好像挺难，其实挺简单的，大家先尝试自己做一做。

代码随想录

二刷：（未ac）

var lemonadeChange = function(bills) {
    // 统计一下都有多少张纸币
    let five = 0
    let ten = 0
    let twenty = 0
    for(let i = 0;i<bills.length;i++){
        if(bills[i] === 5){
            five ++
        }
        if(bills[i] === 10){
            if(five >0){
                five --
                ten ++
            }else{
                return false
            }
            
        }
        if(bills[i] === 20){
            if(ten >= 1 && five >=1){
                five --
                ten --
                twenty ++
            }else if (five >=3){
                five = five -3
                twenty ++
                
            }else{
                return false
            }
            
        }
    }
    return true
    
};

406.根据身高重建队列

大概逻辑，就是分为两个维度，第一个维度是根据height排序，第二个维度是根据k（前面有几个人）排序。

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        #根据height排序
        people.sort(key=lambda x: (-x[0], x[1]))
        result = []
        #二个维度来判断，第一个为height，第二个为k
        #遍历people数组，看第二位，如果下标是什么，就插入什么
        for p in people:
            result.insert(p[1], p)
        return result

那么这个lamba key到底是怎么排序的呢？

sort是从小到大排序。

insert这个库函数需要记得 

该insert()方法在指定位置插入指定值。

代码随想录

二刷（未ac）

需要使用两个维度。

控制第一个维度先，先将数组根据身高从大到小排序。身高相同的话根据k值从小到大排序

再控制第二个维度，根据k值进行插入

var reconstructQueue = function(people) {
    let result = []
    people.sort((a,b)=>{
        if(b[0]!=a[0]){
            return b[0]-a[0]
        }else{
            return a[1]-b[1]
        }
    })
    for(let i = 0;i<people.length;i++){
        result.splice(people[i][1],0,people[i])
    }
 
    return result
    
};

452. 用最少数量的箭引爆气球

题目好长，有点难理解。

大概就是说，假设弓箭为8，区间为[1,10]，这才能射穿这个气球。如果是11，就不行，问，那么多区间，最少需要多少个箭射穿它。

所以说，我们需要找重复区间，像找个样子

重叠的最小边界，需要一个箭。气球三的边界因为大于最小边界，所以需要一个新的箭

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if len(points) == 0:return 0
        result = 1
        #排序，根据第一个排，一样的话根据第二个排
        points.sort(key=lambda x:x[0])
        #遍历每一个区间，如果区间的数相邻，那么就可以不算一个结果。如果不相邻，那么算一个结果
        for i in range(1,len(points)):
            if points[i-1][1]0]:
                result +=1
            else:
                points[i][1] = min(points[i-1][1],points[i][1])
                print(points[i][1])
        return result

代码随想录

二刷：（未ac）

我开始想题的时候，确实也先将区间从小到大排序了。

然后也知道重叠的部分需要使用一个弓箭。但是这个想法就直接，所以错了。

反过来想，如果不重叠那必须需要一个弓箭给它啊。

如果重叠了，更新一下最小边界。如果下一个不在最小边界的范围内，说明需要新的一个弓箭

var findMinArrowShots = function(points) {
    let result = 1
    // 根据最小区间进行排序从小到大,相同就根据第二个区间
    points.sort((a,b)=>{
        if(a[0]!==b[0]){
            return a[0]-b[0]
        }else{
            return a[1]-b[1]
        }
    })
    for(let i = 1;i<points.length;i++){
        if(points[i-1][1] < points[i][0]){
            result++;
        }else{
            points[i][1] = Math.min(points[i-1][1],points[i][1])
        }
    }
    return result
    
};

复习

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy
        while cur.next is not None and cur.next.next is not None:
            temp = cur.next
            temp1 = cur.next.next.next
            cur.next = cur.next.next
            #因为断掉了
            cur.next.next = temp
            temp.next = temp1
            cur = cur.next.next
        return dummy.next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        slow = dummy
        fast = dummy
        for i in range(n):
            fast = fast.next
        while fast.next is not None:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        lenA,lenB = 0,0
        curA = headA
        curB = headB
        while curA:
            curA = curA.next
            lenA += 1
        while curB:
            curB = curB.next
            lenB += 1
        curA = headA
        curB = headB
        #寻找
        def find(headA,headB):
            while headA != headB:
                headA = headA.next
                headB = headB.next
            if headA is not None:
                return headA
            else:
                return 
            
        if lenA > lenB:
            diff = lenA-lenB
            for i in range(diff):
                curA = curA.next
            return find(curA,curB)
        elif lenB > lenA:
            diff = lenB -lenA
            for i in range(diff):
                curB = curB.next
            return find(curA,curB)
        else:
            return find(curA,curB)