蓝桥杯第四天 16 20 21

川长思鸟来 2023-01-06 04:29 106阅读 0赞

# 一 力扣题目16 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]

## 1思路 ##

*  暴力算法没有任何作用，尝试过大部分暴力会超时
 *  我们尝试选取固定一个，然后使用双指针的方法
 *  要双指针的启发式算法，顺序必须有规律，所以我们先排序，使它有规律可循
 *  启发式算法是每次迭代产生的解可以帮助算法优化最佳解，在我们这道题中，求出的解如果大就让双指针向大的方向移动，反之亦然
 *  我们选取for 来进行第一个数字的遍历
 *  在循环中，我们选取左（l)右（r）指针来遍历，根据解集的和temp和target目标数的差可以让指针向左向有移动

## 代码 ##

class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            res=nums[0]+nums[1]+nums[2]
            nums.sort()
            for i in range(len(nums)):#固定一个数字，让另外两个指针根据结果迭代遍历
                l=i+1
                r=len(nums)-1
                while l<r:
                    temp=nums[i]+nums[r]+nums[l]#更新解
                    if abs(temp-target)<abs(res-target):#新解与原解比较取最优
                        res=temp 
                    if temp-target>0:#如果整体大让右侧指针减小
                        r-=1
                      #  temp=min(abs(temp-target),abs(-target+nums[i]+num[r]+nums[l]))
                    elif temp-target<0:#相反
                        l+=1
                       # temp=min(abs(temp-target),abs(-target+nums[i]+num[r]+nums[l]))
                    else:#恰好相等不须迭代
                        return temp
            return res

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]  
虽然结果不是很高，但是思路觉得很对

# 二力扣题目20 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]

## 1思路 ##

*  一看到括号，就能知道左右括号是对应的，很自然联想到**字典**
 *  一看到以正确的顺序闭合，就能联想到**栈**
 *  如果能控制用栈的顺序和字典的对应，就能正确完成判断
 *  我们在循环中只需要判断括号有没有对应在字典，栈的取出和字典的储存对应不对应即可
 *

## 2代码 ##

class Solution:
        def isValid(self, s: str) -> bool:
            dic = {
        '{': '}',  '[': ']', '(': ')'}
            stack = []
            for c in s:
                if c in dic: stack.append(c)
                elif stack:#考虑栈中只有右括号的情况
                    if dic[stack.pop()] != c:#删去这个括号并检查是否于字典对应
                        return False 
                else:#就是右侧括号数目大于左括号数目
                    return False
            return len(stack) == 0#括号相等且顺序一致的情况会为0

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 3]  
结果较为理想，此题考察比较偏重结合性

# 三 力扣题目21 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 4]

## 1 思路 ##

*  这个就是传说中的递归！递归就是不断在函数中调用，从而递归出结果
 *  暂时简单的说一下啊，这个得学代码，说不容易：

1.  *我们递归的话是要在某个链表后面递归，返回链表。即，在l.next后更换正确顺序，用self的递归来调整，返回一定是l，因为我们返回的是从头到尾，而不是最后，最后的next一定指向NULL*
2.  *我们要将小的数值MIN安排在前，然后让MIN之后的链表与另一条链表比较，从而完成一个完整的递归思路*
3.  *知道以上两点后，我们要明白我们的递归以怎样的方式结束，必须考虑一方结束或两方结束的条件*

## 2代码 ##

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            #f1,f1=l1,l2
            #如果需要更迭位置变量而不影响原链表可以用其他替换
            if l1 and l2:
                if l1.val<l2.val:#如果l1小于l2
                    l1.next=self.mergeTwoLists(l1.next,l2)#在l1小数的后面接上剩下更小的数，用递归此函数第一个链表的后面和第二个链表递归
                    return l1#不能返回next，因为上一步是帮我们厘清
                else:
                    l2.next=self.mergeTwoLists(l1,l2.next)#相反情况
                    return l2
            else:
                return l1 if l1 else l2#排除一方空链表的情况，也可以用return l1 or l2代替

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 5]  
最后，给看到本博客的大家出一个递归的问题：

class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            if l1 and l2:
                l1.next=self.mergeTwoLists(l1.next,l2) if l1.val<=l2.val else self.mergeTwoLists(l2.next,l1)
                return l1
            else:
                return l1 if l1 else l2

这个是错误的代码，我编的时候犯得，下期博客揭晓

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]: /images/20221119/2987e385d84b414eb311fd5dcddb66dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]: /images/20221119/6771104a537a456b83349bf9f24dc3d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]: /images/20221119/f9765f32349a4f5b98e4921bc43453f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 3]: /images/20221119/1aec9307dcee44dba31b80b2e0d9c173.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 4]: /images/20221119/89cea23684274c34a47d0d7082754ad0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 5]: /images/20221119/cab120bd4b8f4eef8e37a94b03450bf7.png