leetcode

算法代码阅读

sort

两数之和 -1

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """ #这里应该是判断用的
        # 遍历列表
        for i in range(len(nums)):
            # 计算需要找到的下一个目标数字
            res = target-nums[i]
                # i个数字的对应的大小放在 i的空间上
            if res in nums[i+1:]:


                # 若存在，返回答案。这里由于是两数之和，可采用.index()方法
                # 获得目标元素在nums[i+1:]这个子数组中的索引后，还需加上i+1才是该元素在nums中的索引
                return [i, nums[i+1:].index(res)+i+1] #index(值用的是直接索引出标签、)

# 时间复杂读为 n^2
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}  # 创建一个空哈希表（字典）
        for j, x in enumerate(nums):  # x=nums[j]
            if target - x in idx:  # 在左边找 nums[i]，满足 nums[i]+x=target
                return [idx[target - x], j]  # 返回两个数的下标
            idx[x] = j  # 保存 nums[j] 和 j

#hash表的映射关系, a[i] = x 令 b[x] = i 对于target - x 只要检测后表是不是有这个值即可

两数相加 -2

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution:
    # l1 和 l2 为当前遍历的节点，carry 为进位
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:#Optional表示可以是ListNode类型也可以是None类型
        #递归的结束标志
        if l1 is None and l2 is None:  # 递归边界：l1 和 l2 都是空节点
            return ListNode(carry) if carry else None  # 创建一个节点值为carry的结点
            #进位的标志
        if l1 is None:  # 令l1一直是长的节点
            l1, l2 = l2, l1  

        carry += l1.val + (l2.val if l2 else 0)  # 这个语句不需要修正是否为零的长度
        l1.val = carry % 10  # 每个节点保存一个数位
        l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, carry // 10)  # 进位 已经正确的决定l2的长度
        #carry
        return l1

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 哨兵节点
        carry = 0  # 进位
        while l1 or l2 or carry:  # 有一个不是空节点，或者还有进位，就继续迭代
            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)  # 节点值和进位加在一起
            cur.next = ListNode(carry % 10)  # 每个节点保存一个数位
            carry //= 10  # 新的进位
            cur = cur.next  # 下一个节点
            if l1: l1 = l1.next  # 下一个节点
            if l2: l2 = l2.next  # 下一个节点
        return dummy.next  # 哨兵节点的下一个节点就是头节点

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

#滑动窗口以及 哈希表
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int: #这个应该是定义了内部变量的以及函数的返回类型
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic: #如果在表的位置上查到了这个的值也就是重复了
            # 识别出每一个重复的左指标,以及这个采取缩减的方式,完成了一起更新,还有比较的模式
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 在表的s[j]放入 在字符串s中的位置 也就是可以一一映射的
            res = max(res, j - i) # 更新结果
        return res

#动态规划加hash 鉴定为脑瘫东西
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        res = tmp = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1) # 获取索引 i
            dic[s[j]] = j # 更新哈希表
            
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            res = max(res, tmp) # max(dp[j - 1], dp[j])
        return res

寻找两个正序数组的中位数 -4gg

时间复杂度为 \[ \log(m+n) \]

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def get_k_min(nums1, start1, end1, nums2, start2, end2, k):
            remain1 = end1 - start1 + 1
            remain2 = end2 - start2 + 1
            if remain1 == 0:
                return nums2[start2 + k - 1]
            if remain2 == 0:
                return nums1[start1 + k - 1]
            if k == 1:
                return min(nums1[start1], nums2[start2])
            i = start1 + min(remain1, k // 2) - 1
            j = start2 + min(remain2, k // 2) - 1
            if nums1[i] <= nums2[j]:
                return get_k_min(nums1, i+1, end1, nums2, start2, end2, k - (i - start1 + 1))
            else:
                return get_k_min(nums1, start1, end1, nums2, j+1, end2, k - (j - start2 + 1))

        m, n = len(nums1), len(nums2)
        mid1 = (m + n + 1) // 2
        mid2 = (m + n + 2) // 2
        a = get_k_min(nums1, 0, m-1, nums2, 0, n-1, mid1)
        b = get_k_min(nums1, 0, m-1, nums2, 0, n-1, mid2)
        return (a + b) / 2


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        #都是可以通过替换两个数组的名称来保证一定的顺序 num2的长度始终是最长的

        infinty = 2**40  # 代表正无穷
        m, n = len(nums1), len(nums2)
        left, right = 0, m
        # median1：前一部分的最大值
        # median2：后一部分的最小值
        median1, median2 = 0, 0


        while left <= right: # 一直循环找到一个最大的i满足A[i−1]≤B[j]
            # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i


            # nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            # 当一个数组不出现在前一部分时,对应的值为负无穷,就不会对前一部分的最大值产生影响
            nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 注意写法与java不同
            # 当一个数组不出现在后一部分时,对应的值为正无穷,就不会对后一部分的最小值产生影响
            nums_i = (infinty if i == m else nums1[i])
            nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
            nums_j = (infinty if j == n else nums2[j])


            if nums_im1 <= nums_j:
                median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
                left = i + 1
            else:
                right = i - 1


        return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1

最长回文串

识别出最长的回文串

# 这个程序复杂度有点高()
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)] #[False]*n 为一个列表中的False的拼接的展示
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                #i,j 分别为左边界与有边界 在这个循环中,i,j覆盖了所有的值
                if j >= n:
                    break
                #检测的顺序为 按照长度来进行检索
                #对于i开始的,有多少相同的字符串,同时一开始的时候默认是对于任意一个字符,都可以视为回文串,同时对于任何一个串来说,如果首位相同的话,只需要检测里面两个的字符串是否是相同的.
                # 以下开始递归
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

#这是一个从中心向旁边扩散的算法,只要有就可以向外检测
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
# 这里表示当前的东西判断完成了
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):# 从字符串的长度出发?
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

n字形扩散 - 6 (1)

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]# 含有numrow个空字符串的结构 同时相当于做了一个初始化
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag # 通过设置一个flag来控制数字的加入方式
        return "".join(res)

## 排序

插入区间排序 57 - (2)

对于这个数据,只有重合下面的交集, 以及可以直接放入的数组集, 所以一旦有交集 ,可以更新新的left 与 right 放入新的循环中进行更新

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        left, right = newInterval
        placed = False
        ans = list() #相当于创建了一个新的列表
        for li, ri in intervals:
            if li > right:
                # 在插入区间的右侧且无交集
                if not placed:
                    ans.append([left, right])
                    placed = True #完成了放置
                ans.append([li, ri])

            elif ri < left:
                # 在插入区间的左侧且无交集
                ans.append([li, ri])
            
            else:
                # 与插入区间有交集，计算它们的并集
                left = min(left, li)
                right = max(right, ri)
        
        if not placed:
            ans.append([left, right])
        return ans

三数之和 - (3)

给你一个整数数组 nums ，判断是否存在三元组 [ nums[i], nums[j], nums[k] ] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。

#低空间复杂度的算法
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort() #相当于直接完成升序排列
        res=[]
        for i in range(n):
            if(nums[i]>0): #?只能保证 i指标是一个用负数的形式取出来的值
                return res
            if(i>0 and nums[i]==nums[i-1]):#已经检测过了不需要运行
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]): #相同不需要执行
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res
# 说实话, 有点像遍历的直接求出所有情况的算法但实际上采用了一种类似于一层遍历的方法,对于一个数来说,只要排序过后才用一种类似于双指针遍历的方法即可


# 主打一个利用字典排序
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = [] # 结果列表
        counts = {} # 使用字典存储nums中的元素及其出现次数
        for i in nums:
            counts[i] = counts.get(i, 0) + 1 # get是得到 i对应的字典的值, 时间复杂度甚至接近1 
        
        nums = sorted(counts) # sorted 是保留副本的排序方法,sort是直接在原来的字典上面排序
        for i, num in enumerate(nums):
            if counts[num] > 1: # 如果当前元素的出现次数大于1
                if num == 0: # 处理特殊情况0
                    if counts[num] > 2:  
                        ans.append([0, 0, 0]) # 如果0出现三次及以上,添加[0, 0, 0]到结果
                        continue
                else:
                    if -num * 2 in counts: # 如果当前元素的相反数的两倍也在counts中
                        ans.append([num, num, -2 * num]) # 添加[num, num, -2*num]到结果

            
            if num < 0: # 只需要考虑负数的情况
                two_sum = -num # two_sum表示除num外另外两个元素的和
                left = bisect.bisect_left(nums, (two_sum - nums[-1]), i + 1) 
                # 使用二分查找找到合适的左边界下标
                for j in nums[left: bisect.bisect_right(nums, (two_sum // 2), left)]:
                    # 在合适范围内遍历
                    k = two_sum - j  
                    if k in counts and k != j: # 如果找到符合的k
                        ans.append([num, j, k]) # 添加到结果

        return ans

三数之和接近target

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        min_diff = inf
        for i in range(n - 2):
            x = nums[i]
            if i and x == nums[i - 1]:
                continue  # 优化三 排序后的常见的优化方法, 如果排序后,有两个数相互临近则必不可能输出正确的值

            # 优化一 如果执行到了这个值,同时后三个数之和比target大 那么这里是最接近的值
            s = x + nums[i + 1] + nums[i + 2]
            if s > target:  # 后面无论怎么选，选出的三个数的和不会比 s 还小
                if s - target < min_diff:
                    ans = s  # 由于下一行直接 break，这里无需更新 min_diff
                break

            # 优化二
            s = x + nums[-2] + nums[-1]
            if s < target:  # x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
                if target - s < min_diff:
                    min_diff = target - s
                    ans = s
                continue

            # 双指针 典中典之双指针
            j, k = i + 1, n - 1
            while j < k:
                s = x + nums[j] + nums[k]
                if s == target:
                    return s
                if s > target:
                    if s - target < min_diff:  # s 与 target 更近
                        min_diff = s - target
                        ans = s
                    k -= 1
                else:  # s < target
                    if target - s < min_diff:  # s 与 target 更近
                        min_diff = target - s
                        ans = s
                    j += 1
        return ans

四数之和

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        quadruplets = list()
        if not nums or len(nums) < 4:
            return quadruplets
        
        nums.sort()
        length = len(nums)
        for i in range(length - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            if nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target:
                continue
            
            #简单的优化 

            for j in range(i + 1, length - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target:
                    continue
                left, right = j + 1, length - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        
        return quadruplets

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        a={}
        for i in strs:
            i_=''.join(sorted(i))#内部的字符串排序??? 有点抽象了
            if i_ not in a:
                a[i_]=[i]
            else:
                a[i_].append(i) #存入i 合理的, 但是抽象
        return list(a.values())

合并相关的区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0]) #排序的关键函数 这里也就是把left进行排列

        merged = []
        for interval in intervals:
            # 如果列表为空，或者当前区间与上一区间不重合，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则的话，我们就可以与上一区间进行合并
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged