leetcode 15. 三数之和

发表于 2021-05-09 分类于 leetcode 阅读次数：

解题思路

利用双指针将时间复杂度从O(N^3)降为O(N^2)

时间复杂度

O(N^2)

空间复杂度

O(N)

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []

        nums_len = len(nums)
        if nums_len < 3:
            return ret
            
        nums.sort()
        for i, num in enumerate(nums):
            if num > 0:
                break
            if i > 0 and num == nums[i-1]:
                continue
            left = i + 1
            right = nums_len - 1
            while left < right:
                total = num + nums[left] + nums[right]
                if total == 0:
                    ret.append([num, nums[left], nums[right]])
                    while left < right and nums[left+1] == nums[left]:
                        left += 1
                    while right > left and nums[right-1] == nums[right]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total > 0:
                    right -= 1
                else:
                    left += 1
        
        return ret

leetcode 49. 字母异位词分组

发表于 2021-04-23 更新于 2021-04-24 分类于 leetcode 阅读次数：

解题思路

排序后相等的字符串，划归为一组

时间复杂度

O(n*mlogm) （n：字符串个数；m：字符串长度）

空间复杂度

O(n*m) （n：字符串个数；m：字符串长度）

代码

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        flag_to_list = defaultdict(list)
        for s in strs:
            flag_to_list[''.join(sorted(s))].append(s)
        return list(flag_to_list.values())

leetcode 54. 螺旋矩阵

发表于 2021-04-22 分类于 leetcode 阅读次数：

解题思路

模拟

时间复杂度

O(mn)

空间复杂度

O(mn)

代码

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ret = []
        col = len(matrix[0])
        row = len(matrix)
        visited = [[False]*col for i in range(row)]
        x = 0
        y = 0
        direct = 'right'

        while True:
            if x >= row or y >= col or visited[x][y]:
                break
            
            ret.append(matrix[x][y])
            visited[x][y] = True

            if direct == 'right':
                if y == col - 1 or visited[x][y+1]:
                    direct = 'down'
                    x += 1
                else:
                    y += 1
                continue

            if direct == 'down':
                if x == row - 1 or visited[x+1][y]:
                    direct = 'left'
                    y -= 1
                else:
                    x += 1
                continue
            
            if direct == 'left':
                if y == 0 or visited[x][y-1]:
                    direct = 'up'
                    x -= 1
                else:
                    y -= 1
                continue

            if direct == 'up':
                if x == 0 or visited[x-1][y]:
                    direct = 'right'
                    y += 1
                else:
                    x -= 1
                continue

        return ret

leetcode 41. 缺失的第一个正数

发表于 2021-04-17 更新于 2021-04-18 分类于 leetcode 阅读次数：

解题思路

对于一个长度为N的数组，缺失的第一个正数在[1, N+1]中（若[1,N]在数组都出现了，那么答案是N+1），否则答案是[1,N]中没有出现的最小正数

代码

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums_len = len(nums)

        for i, num in enumerate(nums):
            if num <= 0:
                nums[i] = nums_len + 1
            
        for num in nums:
            num = abs(num)
            if num <= nums_len:
                nums[num-1] = -abs(nums[num-1])

        for i, num in enumerate(nums):
            if num > 0:
                return i + 1

        return nums_len + 1

leetcode 121. 买卖股票的最佳时机

发表于 2021-04-15 更新于 2021-06-05 分类于 leetcode 阅读次数：

解题思路

遍历一次数组即可

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ret = 0
        min_val = float('INF')
        for price in prices:
            min_val = min(min_val, price)
            profit = price - min_val
            if profit > ret:
                ret = profit
        return ret

leetcode 1650. 二叉树的最近公共祖先 III

发表于 2021-04-15 分类于 leetcode 阅读次数：

解题思路

同 leetcode 236. 二叉树的最近公共祖先方法1

代码

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""

class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        p_parent_set = set()
        while p:
            p_parent_set.add(p.val)
            p = p.parent

        while q:
            if q.val in p_parent_set:
                return q
            q = q.parent

leetcode 325. 和等于 k 的最长子数组长度

发表于 2021-04-14 更新于 2021-04-15 分类于 leetcode 阅读次数：

解题思路

方法同 leetcode 560. 和为K的子数组

代码

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        ret = 0
        pre_sum_to_index = {0: -1}
        pre_sum = 0

        for i, num in enumerate(nums):
            pre_sum += num
            expected_val = pre_sum - k
            if expected_val in pre_sum_to_index:
                ret = max(ret, i - pre_sum_to_index[expected_val])
            if pre_sum not in pre_sum_to_index:
                pre_sum_to_index[pre_sum] = i

        return ret

leetcode 236. 二叉树的最近公共祖先

发表于 2021-04-14 分类于 leetcode 阅读次数：

方法1

思路

获取每个节点的父节点
记录p所有的祖先节点
q节点不断向祖先移动，若有祖先在p的祖先节点中，则该祖先为p、q的最近公共祖先

时间复杂度

O(n)

空间复杂度

O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.node_to_father = dict()

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.node_to_father = dict()
        self.traverse_tree(root)

        visited_node_set = set()
        while p:
            visited_node_set.add(p.val)
            p = self.node_to_father.get(p.val)

        while q:
            if q.val in visited_node_set:
                return q
            q = self.node_to_father.get(q.val)
        
    def traverse_tree(self, root):
        if root.left:
            self.node_to_father[root.left.val] = root
            self.traverse_tree(root.left)
        
        if root.right:
            self.node_to_father[root.right.val] = root
            self.traverse_tree(root.right)

方法2

思路

两种情况：
1、p不是q的祖先节点（反之亦然）
从root结点开始遍历节点，若存在节点，p（或q）在其左子树找到且 q（或p）在其右子树找到，则该节点就是p、q的最近公共祖先
2、p是q的祖先节点（反之亦然）
从root结点开始遍历节点，若存在节点等于p（或q），则该节点就是p、q的最近公共祖先

时间复杂度

O(n)

空间复杂度

O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return 

        if p.val == root.val or q.val == root.val:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        if left and right:
            return root
        if left:
            return left
        if right:
            return right

leetcode 523. 连续的子数组和

发表于 2021-04-13 分类于 leetcode 阅读次数：

解题思路

定义pre[i]

下标[0, i]的子数组和

求解方法

下标[j, i]的子数组和为k的倍数 (j<i)
<=>
pre[i]-pre[j-1] == n*k
<==>
pre[i] == n1*k + rem1
pre[j] == n2*k + rem2
rem1 == rem2
<==>
通过计算第i个元素前，是否有pre%k等于pre[i]%k，即说明存在以i结尾的子数组和为k的倍数

时间复杂度

O(n)

空间复杂度

O(min(n,k))

代码

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        rem_to_index = {0: -1}  # 确保[0, i]子数组和是k的倍数时，返回true（i>=2）
        pre_sum = 0

        for i, num in enumerate(nums):
            pre_sum += num
            rem = pre_sum%k
            equal_rem_pos = rem_to_index.get(rem)

            if equal_rem_pos is None:
                rem_to_index[rem] = i
                continue

            if i - equal_rem_pos >= 2:
                return True
        
        return False

leetcode 560. 和为K的子数组

发表于 2021-04-11 分类于 leetcode 阅读次数：

解题思路

定义pre[i]

下标[0, i]的子数组和

求解方法

下标[j, i]的子数组和为k <=> pre[i]-pre[j-1] == k <==> pre[j-1] == pre[i]-k (注意：j <= i）
通过计算第i个元素前，有多少个pre等于pre[i]-k，可得到以第i个元素结尾的和为k的子数组个数
遍历n个元素，累加和为k的子数组个数，即可得到答案

时间复杂度

O(n)

空间复杂度

O(n)

代码

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ret = 0
        pre_sum = 0
        pre_val_to_cnt = defaultdict(int)
        pre_val_to_cnt[0] = 1

        for i, num in enumerate(nums):
            pre_sum += num
            ret += pre_val_to_cnt.get(pre_sum - k) or 0
            pre_val_to_cnt[pre_sum] += 1

        return ret