leetcode抢救_def sortedsquares(self, nums: list[int]) -> list[i

新版的编辑器真的好难用好难用

day 1

因为实在是惰性太强，付费参加了做题打卡，希望自己接下来足够自觉吧呜呜呜

704. 二分查找

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not len(nums):
            return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            middle = left + (right - left) // 2
            if nums[middle] < target:
                left = middle + 1
            elif nums[middle] > target:
                right = middle - 1
            else:
                return middle
        return -1

 写了八百遍了，很简单，不多说

27. 移除元素

写这道题的时候发现自己在大厂面试的时候的强大劣势就是，完全怎么会用最简单的方式解决问题，反而只会用一些奇奇怪怪的方法做，类似于基础都没有开始，就开始fancy了。。

暴力破解：

它要O(1)的时间复杂度，aka只能在原列表上修改，但是写的又多少有点问题：

        for i in range(len(nums) - 1):
            if nums[i] == val:
                nums[i: len(nums)] = nums[i + 1: len(nums)]
        print(nums)

麻木了，问了python老师之后发现是又越界又出错的。这个方法没办法按照示例来做，还是要用到while。说起来那天美团面试也让用空间复杂度O（1）来做，整个人傻掉了。。

i = 0
while i < len(nums):
    if nums[i] == val:
        nums[i: len(nums)] = nums[i + 1: len(nums)]
        i  -= 1
    i += 1
    
return nums

快慢指针：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow, fast = 0, 0
        while fast < len(nums):
            if nums[slow] == val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        
        return slow

 这个是错的因为压根就没有运动这个slow

while fast < len(nums):
    if nums[fast] != val:
        nums[slow] = nums[fast]
        slow += 1
    fast += 1
 
return slow

然后return这个slow是因为需要的是短的那个

day 2

目前都还比较简单属于在舒适区中，之后怎么样就不太知道了呜呜

目前的想法是重刷这波之后把代码随想录里相关的题也刷了，生活还是比较艰难呜呜

977. 有序数组的平方

上次写这个题还是在去年6月了，又学习了一段时间的代码视频，可以比较清晰的看出来一些了，这道题用双指针的话属于是变形版的merge sort，比较简单

打脸了，发现这道题要从大到小排，然后再反向输出：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums) - 1
        ans = []
        while left <= right:
            if nums[left] ** 2 <= nums[right] ** 2:
                ans.append(nums[right] ** 2)
                right -= 1
            else:
                ans.append(nums[left] ** 2)
                left += 1
        return ans[::-1]

 209. 长度最小的子数组

不知道是从哪次面试开始觉得自己写暴力破解真的写的很差，所以这次还是先试试暴力破解吧

重要！！！

for i in range(len(nums)):
    for j in range(i + 1, len(nums) + 1): # 因为下面打印的东西左闭右开所以才这样打印
        print(nums[i: j])

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        count = float("inf") # 定义无限大的or可以len(nums) + 1since里面都是正整数
        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                if sum(nums[i: j]) == target and j - i < count:
                    count = j - i
        if count != float("inf"):
            return count
        else:
            return 0

看了一下代码随想录的方法，他说是移动到target之后left_ bound可以选择右移，这个方案是对的，因为里面都是正整数，但是面试里面其实大多数时候都遇到的是里面有正有负的，然后整个人就会傻掉呜呜呜呜，这个待会儿需要去看一下！！！（但是今天就不写了，主要还是因为我的dp真的学的太太太太拉垮了呜呜）

滑动的双指针解法：

悟性太差了，认真看了一下感觉可能还是有一点动规的影子在里面，就是遍历的是右边界（使用右边界作为care about的条件往左看

这道题的重点在于：是先right_bound往右移，如果sum > target，那么left_bound往左移动，然后while的break条件是和与target的关系（这道题基本还是靠了一下答案，还得再做）

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left, right = 0, 0
        count = 0
        res = len(nums) + 1
        for right in range(len(nums)):
            count += nums[right]
            while count >= target:
                res = min(res, right - left + 1)
                count -= nums[left]
                left += 1
                        
        if res < len(nums) + 1:
            return res
        else:
            return 0

59. 螺旋矩阵 II

这又是一道没做过的呜呜呜呜，这么一看，好嘛果然又不太会，但是谁又是天生啥都会呢，看到小红书上面说200-500道就可以量变引起质变了，那就努力！！等待质变呜呜（以后要正能量，少说呜呜，从明天开始做起）

算了很晚了明天继续吧

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = []
        for i in range(n):
            matrix.append([0] * n)
        # 用列表生成式感觉简单很多 nums = [[0] * n for i in range(n)]
        if n % 2 != 0:
            matrix[n // 2][n // 2] = n ** 2 # 这个得写在最前面因为之后n的值改变
        m, n = 0, n - 1
        input_num = 0
        extra_count = 0
        
        while n - m >= 1:
            for i in range(m, n):
                input_num += 1
                matrix[m][i] = input_num
            for i in range(m, n):
                input_num += 1
                matrix[i][n] = input_num
            for i in range(m - extra_count , n - extra_count):
                input_num += 1
                matrix[n][n - i] = input_num
            for i in range(m - extra_count, n - extra_count):
                input_num += 1
                matrix[n - i][m] = input_num
            m += 1
            n -= 1
            extra_count += 1
 
        return matrix

倒是写完了但是还是得，加个思考分析图

day 3

终于day 3了呜呜呜！现在的状态是丝毫没有尽吾志也，所以还是要努力努力再努力，感觉做出来一道题又好有成就感呀！！！

链表，哈哈哈哈不出意外的话就大概又要反转链表了 

但恕我直言我是真的很讨厌链表题....突然发现现在比刚回来好了太多，那个时候做代码随想录，每天在省图里面哭，无语了真的，永远不要放弃勇敢啊啊啊啊

然后关于listnode的定义函数

class ListNode:
    def __init__(self, val, next):
        self.val = val
        self.next = next

203. 移除链表元素

这道题好像跟剑指18题一毛一样

用一个cur来做指针走完这个链表，同时为了避免第一个结点就是要删除的结点带来的麻烦所以要做了个dummyhead当head

写着写着发现还有一个坑在如果在cur在最后一位（写写改改之后发现忧虑不存在）

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummyhead = ListNode(next = head)
        cur = dummyhead
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next # 因为如果cur.next存在，最差最差cur.next.next也是个null，也就是他依然可以写出来不需要判定cur.next.next是否存在
            else:
                cur = cur.next
        return dummyhead.next

707.设计链表

大晚上的好想吃麦当劳啊...做完就去吃吧呜呜呜呜

206. 反转链表

每一次反转链表的时候都会忘记那三个东西谁先谁后的顺序，然后就抓起了ipad（真是代码拯救者，画画图用ipad还挺方便的

朴素好理解的用一个temp来装载cur.next法：

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, pre = head, None
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        return pre

比较fancy的一行法：（至今记不清楚该什么顺序）

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, pre = head, None
        while cur:
            cur.next, pre, cur =  pre, cur, cur.next
            # pre, cur, cur.next = cur, cur.next, pre
            # cur, cur.next, pre = cur.next, pre, cur
        
        return pre

算了，放弃挣扎了，这个方法靠背吧，cur.next, pre, cur 

day 4

24. 两两交换链表中的节点

# 错误解法
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 怎么写感觉都还是要做一个dummyhead
        dummyhead = ListNode(val = 0, next = head)
        cur = dummyhead
        while cur.next.next and cur.next:
            temp = cur.next
            cur.next = cur.next.next
            cur.next.next.next = temp
            temp.next = cur.next.next.next
            cur = cur.next.next
        return dummyhead.next

 就，也不太懂错在哪儿了，但是感觉看了一下答案还是挺简单的...他那边是做了三个变量在完成这个东西，思路就会比较清晰

这道题最大难点可能在正常情况应该是处理1. pre.next, 2. cur_next.next, 3. cur.next，但是实际在代码完成中应该是321的方式

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 怎么写感觉都还是要做一个dummyhead
        dummyhead = ListNode(val = 0, next = head)
        pre = dummyhead
        
        while pre.next and pre.next.next:
            cur, cur_next = pre.next, pre.next.next # 这段需要放在while里面，暂时不知原因
            # pre.next, cur_next.next, = cur_next, cur, # 如果这样写最后就找不到pre.next.next那个值了所以得先赋
            cur.next, cur_next.next, pre.next = cur_next.next, cur, cur_next
            pre = pre.next.next
 
        return dummyhead.next

这部分先等量变引起质变再说吧

19. 删除链表的倒数第 N 个结点

这道题跟剑指22题基本一致，不过太久了忘记了呜呜呜呜

暂时想到的方法是双指针法，第一个先走n or n - 1 or whatever，就可以找到倒数第n个了再做一个cur.next = cur.next.next大功告成

一直报AttributeError: 'NoneType' object has no attribute 'next'，问了群里是空指针异常报错，aka当前指针指向的位置已经是null了，就没有cur.next了

而且万一要删的是第一位，那就没有办法写了，为了简单起见还是要做个dummyhead（目前发现的是如果做删除操作可能都需要一波dummyhead）

下面本来写的cur和pre，为了防止我自己老年痴呆以后不记得了，所以还是用代码随想录的fast，slow好了

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

做出来了！！！（感激大佬呜呜呜

160. 相交链表

和面试2.7一毛一样，之前做过一次就用以前的链接了，果然每做出一道题都对自信心极大的提升，我好棒！！！！！有点想笑就是本来想的周末提前把明天的做了，卷死大家，后来发现原来我周末还在赶之前的

记得是分别把两个链表的尾巴叠上两个链表的头，然后看后面是不是有一样的，但是我的问题是，不知道之后还for不for完，看了一下之前写了很多很精妙的写法，感觉那个时候还是菜菜的主要靠答案大佬，自己写终究还是要回归菜鸟本质哈哈哈哈哈，认真的想了想不管是先计数还是怎么样，时间复杂度都是O（m + n） 

        cur_a, cur_b = headA, headB
        count_a, count_b = 0, 0
        while cur_a.next:
            cur_a = cur_a.next
            count_a += 1
        cur_a = headB
        while cur_b.next:
            cur_b = cur_b.next
            count_b += 1
        cur_b = headA
        if count_a > count_b:
            for i in range(count_a - count_b):
                cur_b = cur_b.next
        elif count_a < count_b:
            for i in range(count_b - count_a):
                cur_a = cur_a.next
        while cur_a:
            if cur_a == cur_b:
                return cur_a
            cur_a, cur_b = cur_a.next, cur_b.next

想了一下还是太懒了不想记一遍数再运行一遍了，可以直接拿个count来收数，然后对比一下运行啥的

142. 环形链表 II

这道题类似于之前环形链表的进阶，因为是要找环的入口，不知道为什么写着写着觉得还是要远离很多有毒的关系比如...我是一个很容易接受到情绪然后放大的人，这样不太好而且吧他们也没有带给我任何东西...so就 

我记得当时做这个环形是做了快慢指针来着，但是如果找入口的话还可以用快慢指针吗，看了一下答案，还是快慢指针，但是公式也太太太太太复杂了....我已经不是小学那个奥数双一的我了