LeetCode 热题 100

未完待续…

一、哈希

1、两数之和

在这里插入图片描述

# 暴力解，时间复杂度：o(n^2)
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[j] == target - nums[i]:
                    print([i, j])
                    return [i, j]
                # print(i, j)

# 哈希优化解，时间复杂度o(n)
class Solution2(object):
    def twoSum(self, nums, target):
        dic = {}
        for i in range(len(nums)):
            tar_num = target - nums[i]

            if tar_num in dic:
                print([dic[tar_num], i])
                return [dic[tar_num], i]
            dic[nums[i]] = i
        return []


if __name__ == '__main__':
    # s = Solution()
    # # s.twoSum([2, 7, 11, 15], 9)
    # # s.twoSum([3, 2, 4], 6)
    # s.twoSum([3, 3], 6)

    s = Solution2()
    # s.twoSum([2, 7, 11, 15], 9)
    s.twoSum([3, 2, 4], 6)
    # s.twoSum([3, 3], 6)

2.字母异位词分组

在这里插入图片描述

# 自己写的
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = {}
        final_list = []
        for word in strs:
            sort_tup_word = tuple(list(sorted(word)))
            if sort_tup_word in dic:
                dic[sort_tup_word].append(word)
            else:
                dic[sort_tup_word] = [word]  # value为列表，才可以实现append

        print(dic)
        for k in dic:
            final_list.append(dic.get(k))
        print(final_list)
        return final_list


# 看了大佬之后的优化方法，思路倒是一样的，只是对代码没那么熟悉
class Solution2(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = {}
        final_list = []
        for word in strs:
            sort_word = "".join(sorted(word))
            if sort_word in dic:
                dic[sort_word].append(word)
            else:
                dic[sort_word] = [word]
        print(list(dic.values()))
        return list(dic.values())


if __name__ == '__main__':
    # strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    # # strs = [""]
    # # strs = ["a"]
    # # for i in strs:
    # #     print(list(sorted(i)))
    # s = Solution()
    # s.groupAnagrams(strs)

    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    # strs = [""]
    # strs = ["a"]
    # for i in strs:
    #     print(list(sorted(i)))
    s = Solution2()
    s.groupAnagrams(strs)

3.最长连续序列

在这里插入图片描述

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sort_num = sorted(set(nums)) # 题目没有明说，当出现两个数字相同时，要去重！
        cnt = 0 if len(nums) == 0 else 1 # 避免输入一个空列表的情况
        cnt_list = []
        for i in range(len(sort_num)):
            if i+1 < len(sort_num):
                if sort_num[i] + 1 == sort_num[i+1]:
                    cnt += 1
                else:
                    cnt_list.append(cnt)
                    cnt = 1
        cnt_list.append(cnt)
        print(max(cnt_list))
        return max(cnt_list)


if __name__ == '__main__':
    # nums = [100, 4, 200, 1, 3, 2]
    # nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
    # nums = [9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6]
    nums = [1, 2, 0, 1]
    s = Solution()
    s.longestConsecutive(nums)

二：双指针

4、移动零

在这里插入图片描述

# 实际开发写法，类似快排的实现
class Solution1(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        zero_index = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                tmp = nums[zero_index]
                nums[zero_index] = nums[i]
                nums[i] = tmp
                zero_index += 1  # 一定要index所在值非0了，再往后移动，否则会导致数据0排在非0前面

        return nums


# 缩写写法
class Solution2(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        zero_index = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[zero_index], nums[i] = nums[i], nums[zero_index]
                zero_index += 1

        return nums



if __name__ == '__main__':
    nums = [0, 1, 0, 3, 12]
    # nums = [0]
    # nums = [0, 0, 1]

    s = Solution2()
    print(s.moveZeroes(nums))

5、盛水最多的容器

在这里插入图片描述

class Solution(object):
    def maxArea(self, height):  # 这个会超出时间限制
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        for i in range(len(height) - 1):
            for j in range(i+1, len(height)):
                length = j - i
                width = min(height[i], height[j])
                if max_area < length*width:
                    max_area = length*width
        print(max_area)
        return max_area

    # 双指针，从两头开始内卷，先卷了挫的那头
    def maxArea_2(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0
        r = len(height) - 1
        max_area = 0
        while l < r:
            tmp = min(height[l], height[r]) * (r-l)
            max_area = max(max_area, tmp)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        print(max_area)
        return max_area


if __name__ == '__main__':
    # test_list = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    test_list = [1, 1]
    s = Solution()
    # s.maxArea(test_list)
    s.maxArea_2(test_list)

6、三数之和

在这里插入图片描述

本题的暴力题解可以仿照二数之和，直接三层遍历，取和为 0 的三元组，并记录下来，最后再去重。但是作为一个有智慧的人，我们不能这么去做。
因为我们的目标是找数，当然使用指针的方式最简单。假若我们的数组为：

[-1, 0, 1, 2, -1, -4]
求解过程如下：首先我们先把数组排个序（原因一会儿说），排完序长这样：
在这里插入图片描述
因为我们要同时找三个数，所以采取固定一个数，同时用双指针来查找另外两个数的方式。所以初始化时，我们选择固定第一个元素（当然，这一轮走完了，这个蓝框框我们就要也往前移动），同时将下一个元素和末尾元素分别设上 left 和 right 指针。画出图来就是下面这个样子：
在这里插入图片描述
现在已经找到了三个数，当然是计算其三值是否满足三元组。但是这里因为我们已经排好了序，如果**固定下来的数（上面蓝色框框）本身就大于 0，那三数之和必然无法等于 0 **。比如下面这种：
在这里插入图片描述

然后自然用脚指头也能想到，我们需要移动指针。现在我们的排序就发挥出用处了，如果和大于 0，那就说明 right 的值太大，需要左移。如果和小于 0，那就说明 left 的值太小，需要右移。(上面这个思考过程是本题的核心) 整个过程如下图所示：
在这里插入图片描述
其中：在第 6 行时，因为三数之和大于 0，所以 right 进行了左移。最后一行，跳过了重复的 -1。

然后啰嗦一句，因为我们需要处理重复值的情况。除了固定下来的i值（蓝框框），left 和 right 当然也是需要处理重复的情况，所以对于 left 和 left+1，以及 right 和 right-1，我们都单独做一下重复值的处理。（其实没啥处理，就是简单的跳过）

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: 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是大于0的值，那么就没必要进行循环了
                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  # 盲猜为了得到L>R,结束循环
                    R = R - 1  # 盲盲猜为了得到L>R,结束循环
                elif nums[i] + nums[L] + nums[R] > 0:
                    R = R - 1
                else:
                    L = L + 1
        return res


if __name__ == '__main__':
    nums = [-1, 0, 1, 2, -1, -4]
    s = Solution()
    print(s.threeSum(nums))

7、接雨水

在这里插入图片描述
暴力解：很明显每个柱子顶部可以储水的高度为，该柱子的左右两侧最大高度的较小者减去此柱子的高度。因此我们只需要遍历每个柱子，累加每个柱子可以储水的高度即可。
双指针：
在这里插入图片描述


class Solution(object):    # 暴力解，时间会超时  o(n^2)

    def trap(self, height):
        # 很明显每个柱子顶部可以储水的高度为：该柱子的左右两侧最大高度的较小者减去此柱子的高度。
        # 因此我们只需要遍历每个柱子，累加每个柱子可以储水的高度即可。
        """
        :type height: List[int]
        :rtype: int
        """
        nums = 0

        for i in range(1, len(height) - 1):
            max_l = 0
            max_r = 0
            for j in range(0, i):
                max_l = max(height[j], max_l)
            for j in range(i + 1, len(height)):
                max_r = max(height[j], max_r)

            tmp = min(max_r, max_l) - height[i]
            if tmp < 0:
                tmp = 0
            nums += tmp

        return nums

    def trap_2(self, height):  # 双指针解，有点无法解释...
        # 1、初始左右指针在数组的第一个位置和最后一个位置
        # 2、如果左指针所指柱子的高度小于右指针所指柱子的高度，那么左右指针之间柱子的接雨水量取决于左指针所指柱子的高度，从左向右移动左指针，
        # 并记录柱子高度的最大值，如果当前柱子高度小于最大值，则当前柱子可以接雨水为柱子高度的最大值减去当前柱子高度
        # 3、否则，如果右指针所指柱子的高度小于左指针所指柱子的高度，那么左右指针之间柱子的接雨水量取决于右指针所指柱子的高度
        # 从右向左移动右指针，并记录柱子高度的最大值
        # 如果当前柱子高度小于最大值，则当前柱子可以接雨水为柱子高度的最大值减去当前柱子高度
        # 4.重复步骤2, 3
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1

        return ans


if __name__ == '__main__':
    height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    s = Solution()
    # print(s.trap(height))
    print(s.trap_2(height))

三、滑动窗口

8、无重复字符的最长子串

在这里插入图片描述
在这里插入图片描述

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        if len(s) == 1:
            return 1
        data_list = list(s)
        result = []
        for i in range(len(data_list) - 1):
            tmp = data_list[i]
            for dst in range(i, len(data_list) - 1):
                if data_list[dst + 1] in tmp:
                    result.append(set(tmp))
                    break
                else:
                    tmp += data_list[dst+1]
                    if dst + 1 == len(data_list) - 1:
                        result.append(set(tmp))

        return len(max(result, key=len))



if __name__ == '__main__':
    data = "abcabcbb"
    # data = "bbbbb"
    # data = "pwwkew"
    # data = " "
    # data = "au"
    # data = "cdd"
    # data = "abcabcbb"
    s = Solution()
    print(s.lengthOfLongestSubstring(data))

9、找出字符串中所有字母异位词

在这里插入图片描述
逻辑：遍历s字符串中，当窗口大小与P_len一样时，比较两个窗口的字母出现的次数，相同即保留相应的下标；
假设示例：
在这里插入图片描述
循环遍历s字符串，i经过两轮循环，窗口往右走，窗口扩大一次，相应schar的字母次数值就要+1，当窗口长度扩大至2（i=1），此时scharpchar，保留i - p_len + 1 (+1是因为i是从0开始) = 0的下标；
在这里插入图片描述
继续遍历，i=2,此时i>=p_len，超出p的长度了，要减去第一个进入窗口的字母次数值，schar={‘a’:1,‘b’:1}，此时scharpchar，保留i - p_len + 1 (+1是因为i是从0开始) = 1的下标；
在这里插入图片描述
继续遍历，i=3，重复第三张图操作，b值减1，b变为0，要从计数中删除；
此时schar==pchar，保留i - p_len + 1 (+1是因为i是从0开始) = 2的下标；
在这里插入图片描述

继续遍历，i=4，重复第三张图操作，a值减1，a变为0，要从计数中删除；
此时schar != pchar，不保留下标，遍历结束；
在这里插入图片描述
最终结果：[0, 1, 2]

class Solution(object):  --排序暴力检索，会超时
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        len_tar = len(p)
        target = sorted(p)
        result = []
        for i in range(len(s) - len_tar + 1):
            if target == sorted(s[i:i + len_tar]):
                result.append(i)

        return result
    
class Solution:
    def findAnagrams(self, s, p):  -- 统计窗口出现次数实现方案，可实现
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        from collections import Counter
        s_len, p_len = len(s), len(p)
        pChar, sChar = Counter(p), Counter()

        result = []
        for i in range(s_len):
            sChar[s[i]] += 1
            if i >= p_len:
                sChar[s[i - p_len]] -= 1
                if sChar[s[i - p_len]] == 0:
                    del sChar[s[i - p_len]]

            if pChar == sChar:
                result.append(i - p_len + 1)
        return result

if __name__ == '__main__':
    # s = "cbaebabacd"
    # p = "abc"

    s = "abab"
    p = "ab"

    # s = "abacbabc"
    # p = "abc"

    so = Solution()
    print(so.findAnagrams(s, p))

四、子串

太难了，不会做

五、普通数组

1、最大子数组和（中等，人生哲理题）

在这里插入图片描述

# 该题双循环不用看了，必超时
# 核心是从前往后遍历，例如-2和1的sum，与1相比，1比-1大，pre就取1，依次与后一位数字比较
# 人生哲理是这行：pre = max(data, pre + data)：后面的人与前一个max的人在一起，如果能变优秀，那么我就和它在一起过余生，否则还不如后面的人自己过日子；
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pre = 0
        max_sum = nums[0]
        for data in nums:
            pre = max(data, pre + data)
            max_sum = max(pre, max_sum)

        return max_sum


if __name__ == '__main__':
    so = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    # nums = [-2, 1]
    print(so.maxSubArray(nums))

2、合并区间（中等）

在这里插入图片描述

class Solution:
    def merge(self, intervals):
        if len(intervals) == 0:
            return []
        res = []
        intervals.sort(key=lambda x: x[0])  # 先按区间左边界值由小到大排序
        for inter in intervals:
            if len(res) == 0 or res[-1][1] < inter[0]:  # 如果结果集最后一个元素的右边界比新加入区间的左边界小，直接加入结果集
                res.append(inter)
            else:  # 否则，说明新加入的和结果集最后一个区间有重合，更新区间右边界即可
                res[-1][1] = max(res[-1][1], inter[1])
        return res


if __name__ == '__main__':
    so = Solution()
    intervals = [[6, 20], [1, 3], [2, 6], [5, 10], [15, 18]]
    print(so.merge(intervals))

3、轮转数组

在这里插入图片描述

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # 对k求余是因为k可能会大于数组的长度，直接旋转会导致数组元素重叠。通过取模运算可以确保k不会超过数组的长度，从而避免数组元素重叠的问题。
        k = k % len(nums)
        # 为什么不从k开始取，因为nums下标是从0开始的，k的值余下标实际是差1的，不利于定位
        # 而用负下标，-1代表就是最后一个元素，符合k的数值定义
        # 以后尽量都用负下表定位会简单很多
        nums[:] = nums[-k:] + nums[:-k]
        return nums

if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5, 6, 7]
    k = 6

    # nums = [-1, -100, 3, 99]
    # k = 2

    # nums = [1, 2]
    # k = 1
    # k = 2
    # k = 3
    so = Solution()
    print(so.rotate(nums, k))

除自身以外数组的乘积

在这里插入图片描述
分别使用pre和last两个列表存储每个位置对应的前缀乘积和后缀乘积；
之后相乘即可，直接两个for循环会超时；

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        answer = []

        # 前缀乘积
        pre = [1]
        tmp_pre = 1
        for i in range(len(nums) - 1):
            tmp_pre = tmp_pre * nums[i]
            pre.append(tmp_pre)

        # 后缀乘积
        last = [1]
        tmp_last = 1
        for i in range(len(nums) - 1):
            tmp_last = tmp_last * nums[len(nums) - i - 1]
            last.append(tmp_last)

        # 相乘
        for i in range(len(nums)):
            answer.append(pre[i] * last[len(nums) - i - 1])

        return answer


if __name__ == '__main__':
    so = Solution()

    # nums = [1, 2, 3, 4]
    nums = [-1,1,0,-3,3]
    print(so.productExceptSelf(nums))

六、二叉树

1、中序遍历：

在这里插入图片描述

class Solution(object):
    def inorderTraversal(self, root):
        """
		:type root: TreeNode
		:rtype: List[int]
		"""
        res = []

        def dfs(root):
            if not root:
                return
            # 按照 左-打印-右的方式遍历
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)

        dfs(root)
        return res

class Solution(object):
    def inorderTraversal(self, root):
        """
		莫里斯遍历
		"""
        res = []
        pre = None
        while root:
            # 如果左节点不为空，就将当前节点连带右子树全部挂到
            # 左节点的最右子树下面
            if root.left:
                pre = root.left
                while pre.right:
                    pre = pre.right
                pre.right = root
                # 将root指向root的left
                tmp = root
                root = root.left
                tmp.left = None
            # 左子树为空，则打印这个节点，并向右边遍历
            else:
                res.append(root.val)
                root = root.right
        return res

2、二叉树最大深度

在这里插入图片描述

class Solution:
    def maxDepth(self, root):
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

3、翻转二叉树

在这里插入图片描述

class Solution(object):
    def invertTree(self, root):
        # 递归函数的终止条件，节点为空时返回
        if not root:
            return None
        # 将当前节点的左右子树交换
        root.left, root.right = root.right, root.left
        # 递归交换当前节点的 左子树和右子树
        self.invertTree(root.left)
        self.invertTree(root.right)
        # 函数返回时就表示当前这个节点，以及它的左右子树
        # 都已经交换完了
        return root


class Solution2(object):
    def invertTree(self, root):
        # 迭代方式
        if not root:
            return None
        # 将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
        queue = [root]
        while queue:
            # 每次都从队列中拿一个节点，并交换这个节点的左右子树
            tmp = queue.pop(0)
            tmp.left, tmp.right = tmp.right, tmp.left
            # 如果当前节点的左子树不为空，则放入队列等待后续处理
            if tmp.left:
                queue.append(tmp.left)
            # 如果当前节点的右子树不为空，则放入队列等待后续处理
            if tmp.right:
                queue.append(tmp.right)
        # 返回处理完的根节点
        return root

4、对称二叉树

在这里插入图片描述

class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True

        def dfs(left, right):
            # 递归的终止条件是两个节点都为空
            # 或者两个节点中有一个为空
            # 或者两个节点的值不相等
            if not (left or right):
                return True
            if not (left and right):
                return False
            if left.val != right.val:
                return False
            # 分别比较左子节点的左子节点与右子节点的右子节点、左子节点的右子节点与右子节点的左子节点，如果两对节点都对称，则返回True，否则返回False。
            return dfs(left.left, right.right) and dfs(left.right, right.left)

        # 用递归函数，比较左节点，右节点
        return dfs(root.left, root.right)

5、二叉树的直径

在这里插入图片描述
在这里插入图片描述

# 返回二元 tuple (depth, diameter)
# 二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,经过根结点的最长路径}
# 经过根结点的最长路径 = 左子树的深度+右子树的深度
# 所以二叉树的最长路径=max{左子树的最长路径,右子树的最长路径,左子树的深度+右子树的深度}
# depth 表示子树的最大深度，diameter 表示子树的最长路径（直径）
class Solution(object):
    def diameterOfBinaryTree(self, root):
        def traverse(root):
            if root is None:
                return (0, 0)

            left_depth, left_diam = traverse(root.left)
            right_depth, right_diam = traverse(root.right)
            # 求二叉树深度的常规方法
            depth = 1 + max(left_depth, right_depth)
            # 套用上面推导出的最长路径公式
            diam = max(left_diam, right_diam, left_depth + right_depth)
            return depth, diam

        depth, diam = traverse(root)
        return diam

6、二叉树层序遍历

在这里插入图片描述
在这里插入图片描述

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        res = []
        queue = [root]
        while queue:
            # 获取当前队列的长度，这个长度相当于 当前这一层的节点个数
            size = len(queue)
            tmp = []
            # 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
            # 如果节点的左/右子树不为空，也放入队列中
            for _ in range(size):
                r = queue.pop(0)
                tmp.append(r.val)
                if r.left:
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)
            # 将临时list加入最终返回结果中
            res.append(tmp)
        return res

# 首先，定义一个用于构建二叉树的简单类
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 构建一棵二叉树
def build_binary_tree():
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    return root

# 测试代码
solution = Solution()

# 创建测试用的二叉树
test_tree = build_binary_tree()

# 调用levelOrder方法并打印结果
result = solution.levelOrder(test_tree)
print("层序遍历的结果：", result)

# 预期结果是每一层节点值组成的列表
expected_result = [[1], [2, 3], [4, 5, 6]]
assert result == expected_result, "测试失败，实际结果与预期结果不符"

7、将有序数组转为二叉搜索树

在这里插入图片描述

# 二叉搜索树满足两个条件：
# 1）根比左子树大比右子树小；
# 2）高度平衡。因此直接获取有序数组中值作为根就可以，递归生成左子树和右子树即可

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums)==0: return
        elif len(nums)==1: return TreeNode(nums[0])  #  这个TreeNode会报错，但是不影响在leetcode的判断

        mid = len(nums)//2
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid+1:])
        return node

七、链表

1、合并两个有序链表

在这里插入图片描述

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2


#  执行不了
# if __name__ == '__main__':
#     l1 = [1, 2, 4]
#     l2 = [1, 3, 4]
#     so = Solution
#     so.mergeTwoLists(l1, l2)

2、相交链表

在这里插入图片描述
在这里插入图片描述

# 暴力解：o(n^2)
# class Solution(object):
#     def getIntersectionNode(self, headA, headB):
#         p = headA
#         while p:
#             q = headB
#             while q:
#                 if p == q:
#                     return p
#                 q = q.next
#             p = p.next
#         return p

# 哈希表：先将其中一个链表存到哈希表中，此时再遍历另外一个链表查找重复结点只需 O(1) 时间
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        s = set()
        p, q = headA, headB
        while p:
            s.add(p)
            p = p.next

        while q:
            if q in s:
                return q
            q = q.next
        return None

3、反转链表

在这里插入图片描述

# 双指针迭代
class Solution(object):
    def reverseList(self, head):
        """
		:type head: ListNode
		:rtype: ListNode
		"""
        # 申请两个节点，pre和 cur，pre指向None
        pre = None
        cur = head

        while cur:
            # 记录当前节点的下一个节点
            tmp = cur.next
            # 然后将当前节点指向pre
            cur.next = pre
            # pre和cur节点都前进一位
            pre = cur
            cur = tmp
        return pre

4、回文链表

在这里插入图片描述

# 先将链表数据存入到数组arr， 双指针i,j分别从第一个和最后一个从前往后和从后往前遍历
# 相等就继续遍历，直至i > j，如果i和j指向的值不相等，就判断不是回文
class Solution(object):
    def isPalindrome(self, head):
        """
		:type head: ListNode
		:rtype: bool
		"""
        if not (head and head.next):
            return True
        arr, i = [], 0
        # 申请一个数组，然后把元素都放到数组中
        while head:
            _, head = arr.append(head.val), head.next
        j = len(arr) - 1
        # 用i和j两个指针，一个往后，一个往前，不断迭代
        # 如果i的值不等于j说明不是回文，反之是回文
        while i < j:
            if arr[i] != arr[j]:
                return False
            i, j = i + 1, j - 1
        return True

5、环形链表

在这里插入图片描述

# # 哈希：我们可以利用set这个数据结构来解决这道题，首先定义一个Set。
# # 之后遍历链表的节点，每遍历一个节点，就将这个节点的元素放入set中，如果这个链表没有环，那么最终遍历就结束了。
# # 如果链表有环的话，那么肯定有一个元素会被访问两次，当第二次访问这个元素的时候，set中就有记录了，这样就可以判断出链表是否有环了。
# class Solution(object):
#     def hasCycle(self, head):
#         # 定义一个set，然后不断遍历链表
#         s = set()
#         while head:
#             # 如果某个节点在set中，说明遍历到重复元素了，也就是有环
#             if head in s:
#                 return True
#             s.add(head)
#             head = head.next
#         return False

# 快慢指针解法
# 按照这个思路，我们可以假设有a和b两个指针，一个慢一个快，如果链表是有环状的，那么走的快的那个指针迟早会跟慢指针重合的
class Solution(object):
    def hasCycle(self, head):
        """
		:type head: ListNode
		:rtype: bool
		"""
        if not (head and head.next):
            return False
        # 定义两个指针i和j，i为慢指针，j为快指针
        i, j = head, head.next
        while j and j.next:
            if i == j:
                return True
            # i每次走一步，j每次走两步
            i, j = i.next, j.next.next
        return False

6、两数相加

在这里插入图片描述
在这里插入图片描述

# 我们不断的遍历两个链表，每次遍历都将链表a和链表b的值相加，再赋给链表a。如果有进位我们还需要记录一个进位标志。
# 循环的条件是链表a不为空或者链表b不为空，这样当整个循环结束时，链表就被串起来了。
# 当循环结束时，如果进位标志>0还需要处理下边界条件。
# 我们不用生成一个新的节点，直接将两个节点相加的值赋给节点a就可以了，这样只用改变节点的内容，速度会更快一些。

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        # 定义一个进位标志
        a, b, p, carry = l1, l2, None, 0
        while a or b:
            # a和b节点的值相加，如果有进位还要加上进位的值
            val = (a.val if a else 0) + (b.val if b else 0) + carry
            # 根据val判断是否有进位,不管有没有进位，val都应该小于10
            carry, val = val / 10 if val >= 10 else 0, val % 10
            p, p.val = a if a else b, val
            # a和b指针都前进一位
            a, b = a.next if a else None, b.next if b else None
            # 根据a和b是否为空，p指针也前进一位
            p.next = a if a else b
        # 不要忘记最后的边界条件，如果循环结束carry>0说明有进位需要处理这个条件
        if carry:
            p.next = ListNode(carry)
        # 每次迭代实际上都是将val赋给a指针的，所以最后返回的是l1
        return l1

八、二分查找

1、搜索插入位置

在这里插入图片描述

class Solution:
    def searchInsert(self, nums, target):
        left, right = 0, len(nums)  # 采用左闭右开区间[left,right)
        while left < right:         # 右开所以不能有=,区间不存在
            mid = left + (right - left) // 2  # 防止溢出, //表示整除
            if nums[mid] < target:  # 中点小于目标值,在右侧,可以得到相等位置
                left = mid + 1  # 左闭,所以要+1
            else:
                right = mid  # 右开,真正右端点为mid-1
        return left  # 此算法结束时保证left = right,返回谁都一样


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5, 6, 8]
    target = 5
    so= Solution()
    print(so.searchInsert(nums, target))

2、搜索二维矩阵

在这里插入图片描述

# # 暴力解：直接遍历
# class Solution(object):
#     def searchMatrix(self, matrix, target):
#         """
#         :type matrix: List[List[int]]
#         :type target: int
#         :rtype: bool
#         """
#         M, N = len(matrix), len(matrix[0])
#         for i in range(M):
#             for j in range(N):
#                 if matrix[i][j] == target:
#                     return True
#         return False

# 如果 target 大于这一行的末尾元素，那么target 一定不在这一行中，只能出现在矩阵的下面的行中。
# 那么，假如 target < matrix[i][N - 1]时，说明 target 可能在本行中出现，而且由于下面各行的元素都大于 matrix[i][N - 1] ，
# 所以，不可能在下面的行中出现。此时，可以在本行中使用顺序查找，或者二分查找。
class Solution(object):
    def searchMatrix(self, matrix, target):
        M, N = len(matrix), len(matrix[0])
        for i in range(M):
            if target > matrix[i][N - 1]:
                continue
            if target in matrix[i]:
                return True
        return False



if __name__ == '__main__':
    matrix  = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
    so = Solution()
    print(so.searchMatrix(matrix, 3))

3、在排序数组中找到元素的第一个位置和最后一个位置

在这里插入图片描述

# 找到相同的元素即为起始索引，向后一直找到终止索引
class Solution:
    def searchRange(self, nums, target):
        for i in range(len(nums)):
            if nums[i] == target:
                j = i + 1
                while j < len(nums) and nums[j] == target:
                    j += 1
                return [i, j-1]
        return [-1, -1]


if __name__ == '__main__':
    nums = [5, 7, 7, 8, 8, 10]
    target = 8

    so = Solution()
    print(so.searchRange(nums, target))

九、矩阵

1、矩阵置0

在这里插入图片描述

# 遍历一次矩阵，记录一下每行、列是否出现了 0，分别记录行值和列值；
# 第二次遍历，如果行值或者列值出现在去重集合中，则将矩阵所在点的值置0
class Solution:
    def setZeroes(self, matrix):
        if not matrix or not matrix[0]:
            return
        M, N = len(matrix), len(matrix[0])
        row, col = set(), set()
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == 0:
                    row.add(i)
                    col.add(j)
        for i in range(M):
            for j in range(N):
                if i in row or j in col:
                    matrix[i][j] = 0


if __name__ == '__main__':
    matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
    so =Solution()
    print(so.setZeroes(matrix))

10、栈

1、有效括号

在这里插入图片描述

# 通过栈，使用右括号匹配左括号
class Solution:
    def isValid(self, s):
        dic = {')': '(', ']': '[', '}': '{'}
        stack = []
        for i in s:
            if stack and i in dic:
                if stack[-1] == dic[i]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(i)
        # 使用not stack 代替 True可以减少计算S只有一位的值的测试数据
        return not stack


if __name__ == '__main__':
    so = Solution()
    # s = "()[]{}"
    s = "{()[()]}"
    print(so.isValid(s))

11、贪心算法

1、股票买卖的最佳时期

在这里插入图片描述

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minprice = float('inf')
        maxprofit = 0
        for price in prices:
            minprice = min(minprice, price)
            maxprofit = max(maxprofit, price - minprice)
        return maxprofit

12、动态规划

1、杨辉三角

在这里插入图片描述

class Solution:
    def generate(self, numRows: int):
        triangle = []

        for i in range(numRows):
            row = [1] * (i + 1)
            if i >= 2:
                for j in range(1, i):
                    row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            triangle.append(row)

        return triangle


if __name__ == '__main__':
    numRows = 5
    so = Solution()
    print(so.generate(numRows))

13、技巧

1、只出现一次的数字

在这里插入图片描述

# 异或解法：异或运算满足交换律，a^b^a=a^a^b=b,因此ans相当于nums[0]^nums[1]^nums[2]^nums[3]^nums[4].....
# 然后再根据交换律把相等的合并到一块儿进行异或（结果为0），然后再与只出现过一次的元素进行异或，这样最后的结果就是，只出现过一次的元素（0^任意值=任意值）
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = nums[0]
        if len(nums) > 1:
            for i in range(1, len(nums)):
                ans = ans ^ nums[i]
        return ans


if __name__ == '__main__':
    # nums = [2, 2, 1]
    # nums = [2, 2, 1, 1, 5]
    nums = [2, 3, 4, 3, 4]
    so = Solution()
    print(so.singleNumber(nums))

2、多数元素

在这里插入图片描述

# 时间复杂度O(nlogn)
# class Solution(object):
#     def majorityElement(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: int
#         """
#         nums.sort()
#         return nums[len(nums)//2]

# 时间复杂度：O(n),空间复杂度：O(M)
class Solution(object):
    def majorityElement(self, nums):
        dict = {}
        for i in nums:
            if i in dict:
                dict[i] = dict[i] + 1
            else:
                dict[i] = 1
        maxval = max(dict.values())
        # print(maxval)
        for key, val in dict.items():
            if dict[key] == maxval:
                return key

if __name__ == '__main__':
    # nums = [2, 2, 1, 1, 1, 2, 2]
    nums = [3, 3, 4]
    so = Solution()
    print(so.majorityElement(nums))

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/467807.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

检查约束

检查约束

Oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 检查约束 检查约束指的是在数据列上设置一些过滤条件&#xff0c;当过滤条件满足的时候才可以进行保存&#xff0c;如果不满足则出现错误。例如&#xff0c;设置年龄的信息…
阅读更多...
【C语言】猜数字游戏

【C语言】猜数字游戏

代码如下&#xff1a; #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <time.h> void game() {int r rand() % 100 1;int guess 0;while (1){printf("请猜数字>:");scanf("%d", &guess…
阅读更多...
【vscode】vscode重命名变量后多了很多空白行

【vscode】vscode重命名变量后多了很多空白行

这种情况&#xff0c;一般出现在重新安装 vscode 后出现。 原因大概率是语言服务器没设置好或设置对。 以 Python 为例&#xff0c;到设置里搜索 "python.languageServer"&#xff0c;将 Python 的语言服务器设置为 Pylance 即可。
阅读更多...
Vue3学习日记 Day4 —— pnpm，Eslint

Vue3学习日记 Day4 —— pnpm，Eslint

注&#xff1a;此课程需要有Git的基础才能学习 一、pnpm包管理工具 1、使用原因 1.1、速度快&#xff0c;远胜过yarn和npm 1.2、节省磁盘空间 2、使用方式 2.1、安装方式 npm install -g pnpm 2.2、创建项目 pnpm create vue 二、Eslint配置代码风格 1、环境同步 1、禁用Pret…
阅读更多...
OpenCV Steger算法提取条纹中心线

OpenCV Steger算法提取条纹中心线

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 Steger 算法是一种常用的图像边缘检测算法，可以用于提取图像中的中心线或边缘信息。它的理论假设是：条纹的亮度是按照高斯分布呈现的，即中心亮两侧渐暗。 其计算过程如下所述： 1、首先，我们需要计算每个点Hess…
阅读更多...
Apache Doris 2.1 核心特性 Variant 数据类型技术深度解析

Apache Doris 2.1 核心特性 Variant 数据类型技术深度解析

在最新发布的 Apache Doris 2.1 新版本中&#xff0c;我们引入了全新的数据类型 Variant&#xff0c;对半结构化数据分析能力进行了全面增强。无需提前在表结构中定义具体的列&#xff0c;彻底改变了 Doris 过去基于 String、JSONB 等行存类型的存储和查询方式。为了让大家快速…
阅读更多...
Spring Boot 实现程序的优雅退出

Spring Boot 实现程序的优雅退出

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 前言 优雅停机是什么 SpringBoot如何实现优雅停机 合理杀死进程 法一&…
阅读更多...
【nfs报错】rpc mount export: RPC: Unable to receive； errno = No route to host

【nfs报错】rpc mount export: RPC: Unable to receive； errno = No route to host

NFS错误 问题现象解决方法 写在前面 这两天搭建几台服务器&#xff0c;需要使用nfs服务&#xff0c;于是六台选其一做服务端&#xff0c;其余做客户端&#xff0c;搭建过程写在centos7离线搭建NFS共享文件&#xff0c;但是访问共享时出现报错&#xff1a;rpc mount export: RPC…
阅读更多...
基于单片机的家庭烟雾报警系统

基于单片机的家庭烟雾报警系统

摘要：本文主要针对家庭等小型应用场所， 提出基于以单片机CC2530 作为控制器的智能烟雾报警系统，通过MQ-2 气体传感器来检测烟雾浓度，在单片机的A/D模块转化后，并配合蜂鸣元器件实现声音报警功能。 【关键词】烟雾报警 单片机 烟雾传感器 由于科技的发展以及各类家电走入…
阅读更多...
sentinel系统负载自适应流控

sentinel系统负载自适应流控

系统负载自适应流控 规则配置 规则创建 public class SystemRule extends AbstractRule {private double highestSystemLoad -1;private double highestCpuUsage -1;private double qps -1;private long avgRt -1;private long maxThread -1; }SystemRule类包含了以下几…
阅读更多...
unity发布安卓获取读取权限

unity发布安卓获取读取权限

一、Player Settings 设置 Player Settings>Player>Other Settings> Android > Write Permission > External (SDCard). 二、代码 using System.Collections; using System.Collections.Generic; using System.IO; using UnityEngine; using UnityEngine.Andr…
阅读更多...
配置LVS NAT模式

配置LVS NAT模式

配置LVS NAT模式 环境准备 client1&#xff1a;eth0->192.168.88.10&#xff0c;网关192.168.88.5lvs1: eth0 -> 192.168.88.5&#xff1b;eth1->192.168.99.5web1&#xff1a;eth1->192.168.99.100&#xff1b;网关192.168.99.5web2&#xff1a;eth1->192.168…
阅读更多...
【深度学习实践】面部表情识别，深度学习分类模型，mmpretrain用于分类的实用教程，多任务网络头

【深度学习实践】面部表情识别，深度学习分类模型，mmpretrain用于分类的实用教程，多任务网络头

文章目录 数据集数据集的进一步处理转换training.csv转换validation.csv 剔除无法使用的图片数据选择mmpretrain框架来训练配置四个文件改写base model改写base datasetsschedulesdefault_runtime 总配置开始训练训练分析考虑在网络上增加facial_landmarks回归head考虑是否可以…
阅读更多...
力扣-1351 统计有序矩阵中的负数

力扣-1351 统计有序矩阵中的负数

给你一个 m * n 的矩阵 grid&#xff0c;矩阵中的元素无论是按行还是按列&#xff0c;都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。 示例 1&#xff1a; 输入&#xff1a;grid [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] 输出&#xff1a;8 解释&…
阅读更多...
基于stable diffusion的IP海报生成

基于stable diffusion的IP海报生成

【AIGC】只要10秒&#xff0c;AI生成IP海报&#xff0c;解放双手&#xff01;&#xff01;&#xff01;在AIGC市场发展的趋势下&#xff0c;如何帮助设计工作者解放双手。本文将从图像生成方向切入&#xff0c;帮助大家体系化的学习Stable diffusion的使用&#xff0c;完成自有…
阅读更多...
游戏发行商的重要意义：武汉灰京文化的角色和任务

游戏发行商的重要意义：武汉灰京文化的角色和任务

游戏发行商在游戏产业中扮演着重要的角色&#xff0c;他们不仅是游戏内容的传播者&#xff0c;还肩负着众多重要任务。武汉灰京文化作为一家游戏发行商&#xff0c;具有重要意义&#xff0c;他们在测试、本地化、版本移植、分销平台关系、品牌战略制定、法务支持等方面承担着多…
阅读更多...
【异质集成】高k复杂氧化物栅介质在GaN HEMTs上的异质集成

【异质集成】高k复杂氧化物栅介质在GaN HEMTs上的异质集成

COMMUNICATIONS ENGINEERING | (2024) 3:15论文阅读。 文章讨论了高k复杂氧化物栅介质在宽带隙高电子迁移率晶体管&#xff08;HEMTs&#xff09;上的异质集成。 其核心内容的总结如下&#xff1a; 研究背景&#xff1a; 异质集成不同晶体材料因其在高性能多功能电子和光子…
阅读更多...
mybatis-plus 的saveBatch性能分析

mybatis-plus 的saveBatch性能分析

Mybatis-Plus 的批量保存saveBatch 性能分析 目录 Mybatis-Plus 的批量保存saveBatch 性能分析背景批量保存的使用方案循环插入使用PreparedStatement 预编译优点&#xff1a;缺点&#xff1a; Mybatis-Plus 的saveBatchMybatis-Plus实现真正的批量插入自定义sql注入器定义通用…
阅读更多...
B002-springcloud alibaba 微服务环境搭建

B002-springcloud alibaba 微服务环境搭建

目录 创建父工程创建基础模块创建用户微服务创建商品微服务创建订单微服务微服务调用 创建父工程 新建项目springcloud-alibaba&#xff0c;本工程不需要写代码&#xff0c;删除src 导包 <parent><groupId>org.springframework.boot</groupId><artifact…
阅读更多...
语音识别：whisper部署服务器（远程访问，语音实时识别文字）

语音识别：whisper部署服务器（远程访问，语音实时识别文字）

Whisper是OpenAI于2022年发布的一个开源深度学习模型&#xff0c;专门用于语音识别任务。它能够将音频转换成文字&#xff0c;支持多种语言的识别&#xff0c;包括但不限于英语、中文、西班牙语等。Whisper模型的特点是它在多种不同的音频条件下&#xff08;如不同的背景噪声水…
阅读更多...
最新文章

Copyright @ 2022~2023