leetcode 学习笔记

2. 两数相加

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = cur = ListNode(0)
        carry = 0
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            carry, mod = divmod(carry + x + y, 10)
            cur.next = ListNode(mod)
            cur = cur.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        if carry: cur.next = ListNode(1)
        return result.next

3. 无重复字符的最长子串

暴力法： $O(n^3)$
滑动窗口: 时间复杂度 $O(n)$ ，通过使用 HashSet 作为滑动窗口，我们可以用O(1)的时间来完成对字符是否在当前的子字符串中的检查。滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i,j)向右滑动 11 个元素，则它将变为 [i+1,j+1)（左闭，右开）。回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i,j)最初（j=i）中。然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        st = {}
        i, ans = 0, 0 # i 是开始位置
        for j in range(len(s)):
            if s[j] in st:
                i = max(st[s[j]], i) # 原来开始的位置和s[j]重复的位置，取大的那个
            ans = max(ans, j - i + 1)
            st[s[j]] = j + 1 # 更新当前字符在 hashset 中存储的位置，hashset 存储了一个窗口中字符的位置
        return ans;

5. 最长回文子串

可以用动态规划但更优的是中心扩展算法，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s: return ""
        start = end = 0
        for i in range(len(s)):
            len1 = self.expand_around_center(s, i, i)
            len2 = self.expand_around_center(s, i, i + 1)
            m_len = max(len1, len2)
            if m_len > end - start:
                start = i - (m_len - 1) // 2
                end = i + m_len // 2
        return s[start:end + 1]
    
    def expand_around_center(self, s, left, right):
        L, R = left, right
        while L >= 0 and R < len(s) and s[L] == s[R]:
            L -= 1
            R += 1
        return R - L -1

6. Z 字形变换

用一个二维矩阵来表示完整Z 型字符串，然后按行遍历二维矩阵，输出字符串

模拟 Z 字形过程，先垂直向下走再斜向上走

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if not s:
            return ""
        if numRows == 1:
            return s
        # s_Rows[j]代表每一行的字符串，最后再 join
        s_Rows = [""] * numRows
        i  = 0
        n = len(s)
        while i < n:
            # 垂直向下走
            for j in range(numRows):
                if i < n:
                    s_Rows[j] += s[i]
                    i += 1
            # 斜向上走
            for j in range(numRows-2,0,-1):
                if i < n:
                    s_Rows[j] += s[i]
                    i += 1
        return "".join(s_Rows)

8. 字符串转换整数 (atoi)

使用正则表达式

class Solution:
    def myAtoi(self, s: str) -> int:
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

^：匹配字符串开头
[\+\-]：代表一个+字符或-字符
?：前面一个字符可有可无
\d：一个数字
+：前面一个字符的一个或多个

max(min(数字, 2**31 - 1), -2**31) 用来防止结果越界

题目中描述：假设我们的环境只能存储 32 位大小的有符号整数

首先，这个假设对于python不成立，python不存在32位的int类型。其次，即使搜索到的字符串转32位整数可能导致溢出，我们也可以直接通过字符串判断是否存在溢出的情况（比如 try函数或判断字符串长度+字符串比较）

11. 盛最多水的容器

暴力法，考虑每对可能出现的线段组合并找出这些情况之下的最大面积，时间复杂度 $O(n^2)$
双指针法！很妙

这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。此外，我们会使用变量 maxarea来持续存储到目前为止所获得的最大面积。在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxarea，并将指向较短线段的指针向较长线段那端移动一步。

最初我们考虑由最外围两条线段构成的区域。现在，为了使面积最大化，我们需要考虑更长的两条线段之间的区域。

如果我们试图将指向较长线段的指针向内侧移动，矩形区域的面积将受限于较短的线段而不会获得任何增加。

但是，在同样的条件下，移动指向较短线段的指针尽管造成了矩形宽度的减小，但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段，这可以克服由宽度减小而引起的面积减小。
```
class Solution:
    def maxArea(self, height: List[int]) -> int:
        res, l, r = 0, 0, len(height) - 1
        while l < r: 
            if height[l] < height[r]:
                res = max(res,  height[l] * (r - l))
                l = l + 1
            else:
                res = max(res,  height[r] * (r - l))
                r = r - 1
        return res
```

12. 整数转罗马数字

比较简单，用哈希查表的方法

class Solution:
    def intToRoman(self, num: int) -> str:
        lookup = {1:'I', 4:'IV', 5:'V', 9:'IX', 10:'X', 40:'XL', 50:'L', 90:'XC',
            100:'C', 400:'CD', 500:'D', 900:'CM', 1000:'M'}
        res = ""
        for key in sorted(lookup.keys())[::-1]:
            a, num = divmod(num, key)
            if a == 0:
                continue
            res += (lookup[key] * a)
            if num == 0:
                break
        return res

15. 三数之和

超出时间限制，┑(￣Д ￣)┍

排序 + 对撞指针 + 剪枝策略，时间复杂度 $O(n^2)$

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums = sorted(nums)
        for i, num in enumerate(nums):
            if num in [r[0] for r in res]:
                continue
            tmp = nums[i+1:]
            n1, n2 = 0, len(tmp) - 1
            while n1 < n2:
                _sum = tmp[n1] + tmp[n2] + num
                if _sum > 0:
                    while n2 > n1 and tmp[n2] == tmp[n2 - 1]:
                        n2 -= 1
                    n2 -= 1
                elif _sum < 0:
                    while n2 > n1 and tmp[n1] == tmp[n1 + 1]:
                        n1 += 1
                    n1 += 1
                else:
                    res.append([num, tmp[n1], tmp[n2]])
                    while n2 > n1 and tmp[n2] == tmp[n2 - 1]:
                        n2 -= 1
                    n2 -= 1
                    while n2 > n1 and tmp[n1] == tmp[n1 + 1]:
                        n1 += 1
                    n1 += 1
        return res

16. 最接近的三数之和

和上题差不多的思路

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        res = float("inf")
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i + 1, n - 1
            while left < right :
                cur = nums[i] + nums[left] + nums[right]
                if cur == target:
                    return target
                if abs(res - target) > abs(cur - target):
                    res = cur
                if cur > target:
                    right -= 1
                elif cur < target:
                    left += 1
        return res

17. 电话号码的字母组合

使用回溯算法(递归迭代)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits or digits == "": return []
        self.letters = {'2':"abc", '3':"def", '4':"ghi", '5':"jkl", '6':"mno", '7':"pqrs", '8':"tuv", '9':"wxyz"}
        return self.inner(digits)
        
    def inner(self, digits):
        if digits == "":
            return [""]
        new_res = []
        res = self.inner(digits[1:]) # 得到除头部数字后面字符串得到的所有结果
        for j in self.letters[digits[0]]:
            for i in res:
                new_res.append(j + i) # 加上当前的数字对应的所有字母
        return new_res

18. 四数之和

仿照三数之和，使用双循环固定两个数，用双指针找另外两个数，通过比较与target 的大小，移动指针。

时间复杂度是 $O(n^3)$

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if n < 4: return []
        nums.sort()
        res = []
        for i in range(n-3):
            if i > 0 and nums[i] == nums[i-1]: continue # 防止重复 数组进入 res
            # 当数组最小值和都大于 target 跳出
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target: break
            # 当数组最大值和都小于target,说明i这个数还是太小,遍历下一个
            if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target: continue
            for j in range(i+1,n-2):
                if j - i > 1 and nums[j] == nums[j-1]: continue # 防止重复 数组进入 res
                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target: break # 同理
                if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target: continue # 同理
                left, right = j + 1, n - 1 # 双指针
                while left < right:
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    if tmp == target:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < right and nums[left] == nums[left+1]: left += 1
                        while left < right and nums[right] == nums[right-1]: right -= 1
                        left += 1
                        right -= 1
                    elif tmp > target:
                        right -= 1
                    else:
                        left += 1
        return res

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

用双指针，间隔为 n，并且创建一个新的 head 节点来避免临界的情况判断

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        new_head = ListNode(-1)
        new_head.next = head
        ptr1, ptr2 = new_head, head
        for i in range(n):
            ptr2 = ptr2.next
        while ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        ptr1.next = ptr1.next.next
        return new_head.next

22. 括号生成

使用回溯算法，时间复杂度 $\frac{1}{n+1}\dbinom{2n}{n}$

class Solution(object):
    def generateParenthesis(self, N):
        ans = []
        def backtrack(S = '', left = 0, right = 0):
            if len(S) == 2 * N:
                ans.append(S)
                return
            if left < N: backtrack(S+'(', left+1, right)
            if right < left: backtrack(S+')', left, right+1)
        backtrack()
        return ans

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

两种思路：1. 迭代 2. 递归

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        tmp = head.next
        head.next = self.swapPairs(head.next.next)
        tmp.next = head
        return tmp

26. 删除排序数组中的重复项

这题用双指针很妙

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i + 1

27. 移除元素

和上题思路相同，使用双指针

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not len(nums): return 0
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1                
        return i

29. 两数相除

使用位运算（代替乘除法）+二分查找

leetcode 学习笔记

Post Directory