algorithm

排序

冒泡排序： 它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。 时间复杂度： O(n^2)，空间复杂度：O(1)，算法稳定。
选择排序： 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。时间复杂度：O(n^2)，空间复杂度：O(1)，算法不稳定。
插入排序： 把待排序的数组分成已排序和未排序两部分，初始把第一个元素认为是已排好序的。从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。时间复杂度：O(n^2)，空间复杂度：O(1)，算法稳定。
快速排序： 通过选定一个基准值，依据这个基准值分为左右两部分，也就是小于和大于基准值的两部分，然后通过递归调用再次去排序小于和大于的部分，最后得到排序后的数组。 时间复杂度：O(nlogn)，空间复杂度：O(nlogn)，算法不稳定。
归并排序： 通过递归调用，将未排序的数组进行拆分成单个元素，然后再合并的过程中保证合并前后的数组进行有序的即可。时间复杂度：O(nlogn)，空间复杂度：O(n)，算法稳定。
堆排序： 堆（树的形式存储）排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。时间复杂度：O(nlogn)，空间复杂度：O(1)，算法不稳定。

        
# 快速排序
# 时间复杂度 N * logN

# 1. 选择数组的最左侧值作为基准值，并初始化 i, j 分别表示区间的两端。
# 2. 设置循环，比较区间内的数，大于基准值放在右侧，小于基准值放在左侧，然后就基准值放在中间。
# 3. 再将基准值的位置作为分割点，再次区分左子区间和右子区间，递归处理。

def process(nums):
    s(nums, 0, len(nums)-1)

def s(nums, l, r):
    if l >= r:
        return
    # 基准值，比较区间
    p, i, j = nums[l], l, r
    # 从区间内从后往前寻找大于基准值的下标，从前往后寻找小于基准值的下标，互换二者位置，直至前后到达同一位置，该位置就是基准位置 i
    while i < j:
        while i < j and nums[j] >= p: # 先从后开始
            j -= 1
        while i < j and nums[i] <= p:
            i += 1
        nums[i], nums[j] = nums[j], nums[i]
        # print(i, j, nums)
    print(l, r, i, j, nums)
    # 将基准值交换到基准位置 i，并继续递归子区间
    nums[l], nums[i] = nums[i], nums[l]
    s(nums, l, i-1)
    s(nums, i+1, r)

# 变种题目，取前k位或后k位。仅需在区间判断中，增加k的位置判断即可。[l>=r && l>k 前k位排序] [l>=r &&r$lt;k 后k位排序]
        
        

        
# 归并排序
# 归并排序主要分为两部分，拆分和合并。

# 拆分：计算数组的中点作为分割点，持续进行分割，直至区间内剩余一位数。
# 合并：定义临时数组保存排序后的数，比较当前左侧区间和右侧区间内数，较小的数放入临时工数组，直至一方全部放入，然后再将没有放入的区间放入临时数组，最后将临时数组复制回原始数组中。
def process(nums):
    n = len(nums)
    merge(nums, 0, n-1)

def merge_sort(nums, left, mid, right):
    # 左侧区间 [left, mid]， 右侧区间 [mid+1, right]
    # 临时数组
    tmp = []
    i, j = left, mid+1
    while i <= mid and j <= right:
        if nums[i] < nums[j]:
            tmp.append(nums[i])
            i += 1
        else:
            tmp.append(nums[j])
            j += 1
    # print('tmp1', tmp)
    while i <= mid:
        tmp.append(nums[i])
        i += 1
    while j <= right:
        tmp.append(nums[j])
        j += 1
    # 排序后的临时数组数据复制回原始数组中
    for t in range(len(tmp)):
        # print(t, tmp[t])
        nums[left + t] = tmp[t]

def merge(nums, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    print('mid', mid)
    merge(nums, left, mid)
    merge(nums, mid+1, right)
    merge_sort(nums, left, mid, right)
        
        

        
# 堆排序
# 堆排序是基于【堆】这种数据结构进行排序，利用 建堆操作 和 元素出堆操作 来实现。

# 1. 输入数组并建立【大顶堆】，完成后其中的最大元素在堆顶。
# 2. 将堆顶元素与堆底（最后一个元素）进行交换。
# 3. 修复大顶堆，修复完成后，该堆的堆顶依旧是最大值，然后重复执行【2，3】步骤。

# 堆使用数组进行保存数据，同时根据堆的性质进行存储数据。
# 堆的性质：
# 1. 当前 i 节点的父节点的下标为 (i - 1) / 2
# 2. 当前 i 节点的左子节点的下标为 i * 2 + 1
# 3. 当前 i 节点的右子节点的下标为 i * 2 + 2

# 时间复杂度 O(NlogN)

# 大顶堆
# nums 堆，n 堆的大小，i 当前节点下标
def heapify(nums, n, i):
    # 当前堆顶节点下标和其子节点下标
    root_i = i
    left_i = i * 2 + 1
    right_i = i * 2 + 2
    # 调整当前堆，获得最大元素的下标
    if left_i < n and nums[left_i] > nums[root_i]:
        root_i = left_i
    if right_i < n and nums[right_i] > nums[root_i]:
        root_i = right_i
    # 堆被调整时，则递归调整影响的堆
    if root_i != i:
        # 调整当前堆，使得堆顶元素最大
        nums[root_i], nums[i] = nums[i], nums[root_i]
        # 递归调整影响的堆
        heapify(nums, n, root_i)

# 小顶堆
def heapify_min(nums, n, i):
    root_i = i
    left_i = i * 2 + 1
    right_i = i * 2 + 2
    if left_i < n and nums[left_i] < nums[root_i]:
        root_i = left_i
    if right_i < n and nums[right_i] < nums[root_i]:
        root_i = right_i
    if root_i != i:
        nums[root_i], nums[i] = nums[i], nums[root_i]
        heapify_min(nums, n, root_i)

# 堆排序
def process(nums):
    n = len(nums)
    # 建堆
    for i in range(n//2-1, -1, -1):
        heapify(nums, n, i)

    print('init heap', nums)
    # 出堆排序
    for i in range(n-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        print(nums)
        heapify(nums, i, 0)

# 获得 nums 中前 k 个最大的数
def process2(nums, k):
    n = len(nums)
    # 建堆
    for i in range(n//2-1, -1, -1):
        heapify(nums, n, i)

    print('init heap', nums)
    # 出堆排序
    for i in range(n-1, k-1, -1):
        nums[i], nums[0] = nums[0], nums[i]
        print(nums)
        heapify(nums, i, 0)
    print(nums[k:])

def process3(nums):
    n = len(nums)
    # 建堆
    for i in range(n//2-1, -1, -1):
        heapify_min(nums, n, i)

    print('init min heap', nums)
    # 出堆排序
    for i in range(n-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        print(nums)
        heapify_min(nums, i, 0)
        
        

数组、列表

        
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
# 理解示例含义
def process(nums):
    k = 0 # 最远可以跳到的地方
    for i in range(len(nums)):
        if i > k: # 当前下标超过最远可到达位置
            return False
        k = max(k, i+nums[i])
    return True
        
        

        
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
# 排序，再合并区间
def process(intervals):
    intervals.sort()
    # print(intervals)
    ans = []
    for i in intervals:
        if ans and i[0] <= ans[-1][1]:
            # 合并，更新区间
            ans[-1][1] = max(ans[-1][1], i[1])
        else:
            ans.append(i)
    return ans
        
        

        
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
# 模拟
# 链表中个位在前
def process(l1, l2):
    head, tail = None, None
    carry = 0 # 前一位进位的数
    while l1 or l2:
        # l1 l2 同位数
        val1, val2 = 0, 0
        if l1:
            val1 = l1.val
        if l2:
            val2 = l2.val
        a = val1 + val2 + carry # 相同位数相加
        if tail is None:
            tail = ListNode(val=a%10)
            head = tail
        else:
            tail.next = ListNode(val=a%10)
            tail = tail.next
        carry = a // 10
        # l1 l2 非空进到下一位
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    # l1 l2 计算完成后，检查是否有进位
    if carry > 0:
        tail.next = ListNode(val=carry)
    return head

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

        
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
# 滑动窗口
# i 起始位置，j 结束位置
def process(s):
    n = len(s)
    ans, i = 0, -1
    m = {}
    for j in range(n):
        if s[j] in m:
            i = max(i, m[s[j]]) # 更新已存在字符的起始位置
        m[s[j]] = j
        ans = max(ans, j-i)
    return ans
        
        

        
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
# 确定该索引位置上的值的最终位置
# k 可能大于 nums 的长度
def process(nums, k):
    n = len(nums)
    num = [None] * n
    for i in range(n):
        num[(i+k)%n] = nums[i]
    nums[:] = num[:]

# 翻转解法
def process3(nums, k):
    n = len(nums)
    k %= n
    reverse(nums, 0, n-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, n-1)

def reverse(nums, i, j):
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1
        
        

        
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
def process(nums):
    m = {}
    for n in nums:
        if n not in m:
            m[n] = 1
    # print(m)
    ans = 0
    for n in nums:
        if n-1 not in m: # 重点，当前值的上一个值不在 m 中，即该值为序列的起始值
            cur = n
            while cur in m:
                cur += 1
            ans = max(ans, cur-n)
    return ans
        
        

        
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
# 理解示例含义
def process(nums):
    k = 0 # 最远可以跳到的地方
    for i in range(len(nums)):
        if i > k: # 当前下标超过最远可到达位置
            return False
        k = max(k, i+nums[i])
    return True
        
        

        
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i] i + j < n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
# 贪心法
# 反向寻找，从最后往前递推找出最早可到达末尾的位置，然后更新末尾位置再从头开始依次寻找即可
# 第一次，从前往后寻找可到达末尾的最小位置。
# 下一次，再次从前往后寻找可达到的上一次位置的最小位置。
def process(nums):
    n = len(nums)
    p = n-1
    step = 0
    while p > 0:
        for i in range(n):
            if i + nums[i] >= p:
                p = i
                step += 1
                break
    return step
        
        

        
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
# 前缀和
def process(height):
    n = len(height)
    prev = [0 for _ in range(n)]
    after = [0 for _ in range(n)]
    for i in range(n):
        if i == 0 or i == n-1:
            continue
        else:
            prev[i] = max(prev[i-1], height[i-1])
            after[n-1-i] = max(after[n-i], height[n-i])
    print(prev, after)
    r = 0
    for i in range(n):
        m = min(prev[i], after[i])
        if m < height[i]:
            continue
        r += m - height[i]
    return r
        
        

动态规划

        
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
# 动态规划
def process(nums):
    n = len(nums)
    pre, ans = 0, nums[0]
    for i in range(n):
        pre = max(pre + nums[i], nums[i]) # 连续数组之前的和再加上最新的值与当前值比较
        ans = max(ans, pre)
    return ans
        
        

        
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
# 动态规划
# dp[i] 表示前 i 个数字的最长递增长度，必须包含 i
# dp[i] = max(dp[i], dp[j]+1) & nums[i] > nums[j]
# 最终取 dp 中的最大值即可

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = [1] * n # 默认最长递增长度即他自己，长度为1
        for i in range(n):
            for j in range(i): # 之前的最大长度
                if nums[i] > nums[j]: # nums[i] > nums[j]，之前的值必须要小于当前值
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
        
        

        
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
# 动态规划
# dp[n] = max(dp[n-2]+nums[n], dp[n-1])
def process(nums):
    n = len(nums)
    dp = [0] * n
    if n == 1:
        dp[0] = nums[0]
    elif n == 2:
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
    else:
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])
    return dp[n-1]
        
        

        
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
# 动态规划
# 房子首尾相连，情况需要特殊考虑
def process(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    elif n == 2:
        return max(nums[0], nums[1])
    else:
        return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1))

def robRange(nums, l, r):
    start = nums[l]
    end = max(nums[l], nums[l+1])
    for i in range(l+2, r+1):
        print(i)
        start, end = end, max(start+nums[i], end)
    return end
        
        

        
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):

    def __init__(self):
        self.moneyMap = {}

    def rob(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root:
            return 0

        # 查看之前是否重复计算
        if root in self.moneyMap:
            return self.moneyMap[root]

        # 第一种情况，父节点加上左右孙子节点
        robMoney1 = root.val
        if root.left:
            robMoney1 += self.rob(root.left.left) + self.rob(root.left.right)
        if root.right:
            robMoney1 += self.rob(root.right.left) + self.rob(root.right.right)

        # 第二种情况，父节点的左右子节点
        robMoney2 = self.rob(root.left) + self.rob(root.right) 

        # 保存节点计算
        self.moneyMap[root] = max(robMoney1, robMoney2)
        return self.moneyMap[root]
        
        

        
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
# 遍历数组取得最小值，然后根据当前值与最小值的最大差就是最大利润
def process(nums):
    min_n = nums[0]
    r = 0
    for x in nums:
        r = max(r, x - min_n)
        min_n = min(min_n, x)
    return r
    
        
        

        
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
# 动态规划
# 第i天持有或没有股票的最大收益
# dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) 今天没有 = 昨天没有 ｜ 昨天有加上今天卖出
# dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) 今天有   = 昨天也有 ｜ 昨天没有今天买了
def process(prices):
    n = len(prices)
    dp = [[0,0] for i in range(n)]
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    return dp[n-1][0]
    
        
        

        
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
# 从头开始遍历即可
# 从 i 出发最远可到达 j 处，即 [i, j] 中间的区域均可达到
def process(gas, cost):
    n = len(gas)
    i = 0
    while i < n:
        g = 0
        for j in range(n):
            g += gas[(i+j)%n]
            g -= cost[(i+j)%n]
            if g < 0:
                break
        if g >= 0:
            return i
        i = i + j + 1
    return -1
        
        

        
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
# 岛屿问题 - 深度优先搜索
def process(grid):
    m = len(grid)
    n = len(grid[0])
    ans = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                ans += 1
                dfs(grid, i, j)
    return ans

def dfs(grid, r, c):
    # 结束条件
    if not inArea(grid, r, c):
        return
    # 检查节点
    if grid[r][c] != '1': # 标记过或‘0’
        return
    grid[r][c] = '2' # 遍历过的节点进行标记
    # 周边节点
    dfs(grid, r, c-1)
    dfs(grid, r-1, c)
    dfs(grid, r, c+1)
    dfs(grid, r+1, c)

def inArea(grid, r, c):
    return 0 <= r and r < len(grid) and 0 <= c and c < len(grid[0])


        
        

二叉树

        
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
# 递归处理，确定每层的编号即可，使用全局数组保存
import collections

def process(root):
    a = []
    pr(root, 0, a)
    return a

def pr(root, level, a):
    if root is None:
        return
    if len(a) == level:
        a.append([root.val])
    else:
        a[level].append(root.val)
    pr(root.left, level+1, a)
    pr(root.right, level+1, a)

# 非递归，逐层加入队列中，先进先出原则
def process2(root):
    a = []
    deque = collections.deque()
    deque.append(root)
    while deque:
        t = []
        n = len(deque)
        for _ in range(n):
            node = deque.popleft()
            t.append(node.val)
            if node.left:
                deque.append(node.left)
            if node.right:
                deque.append(node.right)
        a.append(t)
    return a

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