并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

阅读全文

前缀和可以简单理解为「数列的前 n 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

初级练习

左右元素和的差值

思路

思路简单，使用前缀和，不过需要左右两边都计算一下前缀和，然后对每个i的位置进行计算。

阅读全文

图相关的算法练习，需要掌握图的基本数据结构，图的连通性，图的遍历，最短路径，最小生成树等问题。

初级练习

找到小镇的法官

思路

思路很简单，基于图的度，由于法官不信任其他人，因此他的出度是0，这样就可以找到了。

阅读全文

贪心算法没有固定的模板，基本思路是找到问题的一个切入点，虽然证明这个解法是最优的。

初级练习

拆分数位后四位数字的最小和

思路

这题很简单，数据只有4个数，组合就3种，不过为了求最小和，贪心的思路就是组成的数值最高位都尽量小，因此把四个数排序，1和4组成一个数，2和3组成一个数，这样就能得到最小的和。

阅读全文

初级练习

下一个更大元素 I

思路

最基础的单调栈用法。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func nextGreaterElement(nums1, nums2 []int) []int {
    mp := map[int]int{}
    stack := []int{}
    for i := len(nums2) - 1; i >= 0; i-- {
        num := nums2[i]
        for len(stack) > 0 && num >= stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) > 0 {
            mp[num] = stack[len(stack)-1]
        } else {
            mp[num] = -1
        }
        stack = append(stack, num)
    }
    res := make([]int, len(nums1))
    for i, num := range nums1 {
        res[i] = mp[num]
    }
    return res
}

商品折扣后的最终价格

思路

阅读全文

滑动窗口，这个算法思路非常简单，就是维护一个窗口，不断滑动，然后更新答案。

初级练习

学生分数的最小差值

思路

因为可以任意选k名学生，因此我们排序后，使用滑动窗口，维持k大小的窗口，计算每次窗口内的最大值和最小值的差，数组遍历结束后返回最小值。这道题是最基本的滑动窗口使用方法。

阅读全文

双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

阅读全文

二分查找 (Binary Search) 也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

总结有以下特征和解题步骤：

• 寻找有序性
• 寻找判断函数，func(mid)
• 使用的二分查找模板

基础模板

阅读全文

回溯 (backtracking) 是暴力搜索的方法之一。

总结有以下特征和解题步骤：

• 问题的解在可预估的范围内
• 给出一个解能快速判断是否符合要求
• 代码有固定模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

result = []

def backtrack(路径, 选择列表): 
    if 满足结束条件:
        result.add(路径) 
        return
    for 选择 in 选择列表: 
        做选择
        backtrack(路径, 选择列表)
        撤销选择

组合问题

题目leetcode77 组合

题解

阅读全文

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程。总结有以下特征和解题步骤：

• 肯定是求最值问题，并且具备重叠子问题
• 定义问题(dp子问题的定义)
• 寻找状态转变的所有选择情况(定义状态转移方程式)
• 确定边界情况 bad case

01背包问题

描述

阅读全文