分类 杂谈 下的文章

如何让Word公式编辑器自动使用斜体


只要不是需要特别奇怪的格式, Word自带的公式编辑器其实还挺好用的, 大部分的LaTeX公式指令也都支持, 但很烦的一点是这玩意默认样式和上下文是一样的, 而公式往往我们都希望它能够是斜体.
因此, 简单研究了一下以后, 发现可以通过VBA宏的形式来达到自动斜体公式的功能.

  1. 创建宏: 视图--录制宏, 宏名改成你喜欢的就行, 将宏指定到可以选择键盘, 然后输入你想绑定的快捷键, 这里我选择Alt+=也就是默认的插入公式快捷键
  2. 创建完以后它会自动开始录制, 点击界面下方状态栏的停止按钮即可停止录制
  3. 修改宏: 视图--查看宏, 选择你刚刚创建的宏名, 点击编辑, 然后在Sub ${宏名}()End Sub之间删除掉原有的代码然后插入如下代码:
    Selection.OMaths.Add Range:=Selection.Range 'Creates an equation
    Selection.OMaths(1).ConvertToMathText 'Converts an equation to math text

然后保存即可

  • 如果你之前设置了快捷键的话, 现在找到一处空白位置按下快捷键即可, 如果没有, 那么可以去选项中设置快捷键
  • 如果需要对代码进行调试, 可以在VBA的编辑窗口中进行单步调试

Ref: https://zhuanlan.zhihu.com/p/27072646


LeetCode刷题Wrapper


起因

LeetCode上的题目放到本地调试很麻烦, 需要在本地新建一个Main方法来运行, 多TestCase的测试也需要写很多重复代码, 所以想写一个简单Wrapper将很多重复的工作放在里面来执行.

目标

使用Wrapper之后, 只需要将Solution类放入再实现getTestCase()即可.
这里的Solution类可以直接不作任何修改的复制粘贴到LeetCode中, 不需要任何额外的代码即可直接运行这个类.

public class Problem7 extends AbstractSolution{
    /**
     * Given a 32-bit signed integer, reverse digits of an integer.
     * <p>
     * Example 1:
     * Input: 123
     * Output: 321
     * <p>
     * Example 2:
     * Input: -123
     * Output: -321
     * <p>
     * Example 3:
     * Input: 120
     * Output: 21
     * <p>
     * Note:
     * Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
     */
    class Solution{
        @Resource
        public int reverse(int x){
            // 统一调整到负数来处理
            boolean isPositive = x >= 0;
            x = isPositive ? -x : x;

            int result = 0;
            while(x < 0 && result >= Integer.MIN_VALUE / 10){
                int n = x % 10;
                if(result == 0){
                    result = result + n;
                }else{
                    if(result == Integer.MIN_VALUE / 10 && x < -8){
                        break;
                    }
                    result = result * 10 + n;
                }
                x /= 10;
            }
            result = x < 0 ? 0 : result;

            return isPositive ? -result : result;
        }
    }

    @Override
    protected Map<?, ?> getTestCase(){
        return ImmutableMap.builder()
                .put(123, 321)
                .put(-123, -321)
                .put(120, 21)
                .put(1534236469, 0)
                .put(-2147483412, -2143847412)
                .put(1463847412, 2147483641)
                .put(1234, 111)
                .build();
    }
}

由于使用Guava, 所以可能还需要引入它的依赖到工程中.
另外, Solution类的入口方法需要放上@Resource注解, 否则Wrapper无法找到运行的入口方法.
运行的结果如下所示:

TestCase 0: Passed
TestCase 1: Passed
TestCase 2: Passed
TestCase 3: Passed
TestCase 4: Passed
TestCase 5: Passed
TestCase 6: Wrong
    Input: 1234
    Output: 4321
    Expected: 111
Some TestCase Failed!

解析

首先展示一下AbstractSolution的内容:

public abstract class AbstractSolution{
    /**
     * 1. 实例化SolutionWrapper类
     * 2. 找到目标的Solution类并获得实例
     * 3. 找到目标方法(用@Resource注解)
     * 4. 检查参数类型和TestCase是否匹配
     * 5. 使用TestCase运行目标方法
     */
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for(Class<?> c : classes){
            if(c.getName().endsWith("$Solution")){
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if(targetClass != null && targetClass.getDeclaredConstructors().length > 0){
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if(targetClass != null){
            Method[] methods = targetClass.getDeclaredMethods();
            for(Method m : methods){
                if(m.isAnnotationPresent(Resource.class)){
                    targetMethod = m;
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if(targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0){
            Class<?> parameterTypes = targetMethod.getParameterTypes()[0];
            Class<?> testCaseType = testCase.keySet().toArray()[0].getClass();
            if(ReflectionUtils.isAssignableFrom(testCaseType, parameterTypes)){
                runCases(targetInstance, targetMethod, testCase);
            }
        }
    }

    private static boolean runCases(Object targetInstance, Method targetMethod, Map<?, ?> testCase) throws InvocationTargetException, IllegalAccessException{
        int index = 0;
        boolean allPassed = true;
        for(Object input : testCase.keySet()){
            Object result = targetMethod.invoke(targetInstance, input);
            Object expectedResult = testCase.get(input);
            boolean passed = result.toString().equals(expectedResult.toString());
            allPassed = passed && allPassed;

            if(passed){
                System.out.printf("TestCase %d: Passed\n", index++);
            }else{
                System.out.printf("TestCase %d: Wrong\n"
                                + "\tInput: %s\n"
                                + "\tOutput: %s\n"
                                + "\tExpected: %s\n",
                        index++, input, result, expectedResult);
            }
        }
        System.out.println(allPassed ? "All TestCase Passed!" : "Some TestCase Failed!");
        return allPassed;
    }

    protected abstract Map<?, ?> getTestCase();
}

我们在Problem7类中运行的main()方法放在了AbstractSolution里, 首先我们需要获得实际子类的实例, 即Problem7类的实例.
AbstractSolution类里, 我们是没办法知道到底具体是哪一个子类调用的main()方法的, 如果想要知道有两种方法:

  1. 运行的命令行参数里, 会带上实际执行的子类.
    例如在这个例子中, 命令行参数是java algorithm.leetcode.Problem7. 这样从命令行参数就可以知道实际调用main()的类是Problem7了.
  2. 在加载子类之前, 父类一定会被加载. 因此, 我们遍历当前一遍所有加载的类, 看当前类的哪一个子类被加载了, 就可以知道实际调用的类.

在这里, 我使用的是第二种方法, 通过ReflectionUtils.getLoadedSubClass(AbstractSolution.class)来获取, 具体实现如下:

    @SuppressWarnings("unchecked")
    public static <T> Class<? extends T> getLoadedSubClass(Class<T> superClass){
        // Read Loaded Classes
        Collection<Class<?>> classes = getLoadedClass(Thread.currentThread().getContextClassLoader());

        // Find the SubClass of CurrentClass
        for(Class c : classes){
            if(c.getSuperclass() != null && superClass.equals(c.getSuperclass())){
                return c;
            }
        }
        throw new IllegalStateException("No Valid SubClass.");
    }

    /**
     * 获取指定类加载器已加载的类
     */
    @SuppressWarnings("unchecked")
    public static Collection<Class<?>> getLoadedClass(ClassLoader cl){
        try{
            Field f = ClassLoader.class.getDeclaredField("classes");
            f.setAccessible(true);
            return (Collection<Class<?>>)f.get(cl);
        }catch(NoSuchFieldException | IllegalAccessException e){
            e.printStackTrace();
        }
        throw new IllegalStateException("Unexpected Error.");
    }

ClassLoader本身是没有提供方法让你获得当前已加载的类, 但是存在一个private的classes属性包含所有已加载的类, 因此可以通过读取该属性来获得指定类加载已加载的类.

在获得Problem7的实例solutionWrapper后, 我们再从Problem7类中找到其内部类$Solution并实例化它.
需要注意的是, 这里不能直接用newInstance(), 因为内部类没有public的构造器, 只有包含外部类引用的private构造器, 所以需要首先获得这个构造器, 然后使用构造器实例化内部类.

在获得内部类targetClass以后, 再遍历所有的方法找到标记有注解的方法作为入口方法targetMethod.
这里用@Resouce注解的原因只是...我觉得用JDK自带注解就够了...

最后, 检查一下testCase的类型和targetMethod的参数类型是否匹配, 就可以调用targetMethod来实际执行Solution类里的实际方法了.
这里考虑到存在primitive类型和其包装类混用的情况, 所以首先将其都unwrap, 如果都为primitive类型那么一定是可以转型成功的(当然可能损失精度).
如果没有primitive类型, 那么使用isAssignableFrom()方法来判断; 如果一个primitive一个正常对象, 那么必然转型失败.

    /**
     * 检查是否可从target转型到source
     * 考虑两个primitive类型一定可以互转(可能损失精度)
     */
    public static boolean isAssignableFrom(Class<?> source, Class<?> target){
        source = Primitives.unwrap(source);
        target = Primitives.unwrap(target);

        // All Object
        if(source.isPrimitive() && target.isPrimitive()){
            return true;
        }else if(!source.isPrimitive() && !target.isPrimitive()){
            return source.isAssignableFrom(target);
        }else{
            return false;
        }
    }

总的来说, 大体上的思路就是这样了, 我觉得还是很有意思的.

总结

这么一番操作下来, 感觉对框架内部实现的很多东西了解得更深了呢233
之前简单的看过Spring-Core的内部实现, 也是大量类似的检查代码, 以及一吨设计模式→_→
实话说, 感觉设计得有点太过复杂了...不过有可能是我看的源码版本比较老吧233(Spring 3.1.1)

懒果然是人类进步的阶梯(并不

Update 2019-05-10:
我把AbstractSolution又改了改, 在方法上做标注还是有一些略麻烦...
我把它改成了标注在内部类上, 然后用lookup属性来指定待执行的方法, 或者选取第一个找到的Public方法

public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for(Class<?> c : classes){
            if(c.isAnnotationPresent(Resource.class)){
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if(targetClass != null && targetClass.getDeclaredConstructors().length > 0){
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if(targetClass != null){
            Method[] methods = targetClass.getDeclaredMethods();
            Resource annotation = (Resource)targetClass.getAnnotation(Resource.class);
            for(Method m : methods){
                if(!annotation.lookup().isEmpty()){
                    // specify by lookup
                    if(m.getName().equals(annotation.lookup())){
                        targetMethod = m;
                    }
                }else{
                    // first public method
                    if(Modifier.isPublic(m.getModifiers())){
                        targetMethod = m;
                    }
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if(targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0){
            Class<?> parameterTypes = targetMethod.getParameterTypes()[0];
            Class<?> testCaseType = testCase.keySet().toArray()[0].getClass();
            if(ReflectionUtils.isAssignableFrom(testCaseType, parameterTypes)){
                runCases(targetInstance, targetMethod, testCase);
            }
        }
    }

Update 2019-09-04:

以前做的居然不支持多参数输入, 醉了醉了...
验证参数类型其实挺麻烦的, 感觉在我这个场景下也不是特别重要就删掉了...只检查参数数目是否一致
然后输出的检测考虑到可能会有比较复杂的类型输出出来干脆就用gson全部转换到字符串然后比较字符串好了...

public abstract class AbstractSolution{
    private final static Gson gson = new GsonBuilder().create();

    /**
     * 1. 实例化SolutionWrapper类
     * 2. 找到目标的Solution类并获得实例
     * 3. 找到目标方法(用@Resource注解)
     * 4. 检查参数类型和TestCase是否匹配
     * 5. 使用TestCase运行目标方法
     */
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, InvocationTargetException{
        // fetch solution wrapper
        AbstractSolution solutionWrapper = ReflectionUtils.getLoadedSubClass(AbstractSolution.class).newInstance();

        // find targetClass
        Class targetClass = null;
        Class<?>[] classes = solutionWrapper.getClass().getDeclaredClasses();
        for (Class<?> c : classes) {
            if (c.isAnnotationPresent(Resource.class)) {
                targetClass = c;
            }
        }

        // get targetClass instance
        Object targetInstance = null;
        if (targetClass != null && targetClass.getDeclaredConstructors().length > 0) {
            Constructor<?> targetConstructor = targetClass.getDeclaredConstructors()[0];
            targetInstance = targetConstructor.newInstance(solutionWrapper);
        }

        // find targetMethod
        Method targetMethod = null;
        if (targetClass != null) {
            Method[] methods = targetClass.getDeclaredMethods();
            Resource annotation = (Resource)targetClass.getAnnotation(Resource.class);
            for (Method m : methods) {
                if (!annotation.lookup().isEmpty()) {
                    // specify by lookup
                    if (m.getName().equals(annotation.lookup())) {
                        targetMethod = m;
                    }
                } else {
                    // first public method
                    if (Modifier.isPublic(m.getModifiers())) {
                        targetMethod = m;
                    }
                }
            }
        }

        // check parameter and run
        Map<?, ?> testCase = solutionWrapper.getTestCase();
        if (targetMethod != null && targetMethod.getParameterTypes().length > 0 && testCase.size() > 0) {
            runCases(targetInstance, targetMethod, testCase);
        }
    }

    private static boolean runCases(Object targetInstance, Method targetMethod, Map<?, ?> testCase) throws InvocationTargetException, IllegalAccessException{
        int index = 0;
        boolean allPassed = true;
        for (Object input : testCase.keySet()) {
            // read params
            Object[] params;
            if (targetMethod.getParameterCount() > 1) {
                params = new Object[Array.getLength(input)];
                for (int i = 0; i < params.length; i++) {
                    params[i] = Array.get(input, i);
                }
            } else {
                params = new Object[]{input};
            }

            // check parameter length
            if (params.length != targetMethod.getParameterCount()) {
                throw new IllegalArgumentException("Incompatible Parameters.");
            }

            // actual invoke
            Object result = targetMethod.invoke(targetInstance, params);
            Object expectedResult = testCase.get(input);

            // compare string
            String inputStr = gson.toJson(input);
            String resultStr = gson.toJson(result);
            String expectedStr = gson.toJson(expectedResult);
            boolean passed = resultStr.equals(expectedStr);
            allPassed = passed && allPassed;

            if (passed) {
                System.out.printf("TestCase %d: Passed\n", index++);
            } else {
                System.out.printf("TestCase %d: Wrong\n"
                                + "\tInput: %s\n"
                                + "\tOutput: %s\n"
                                + "\tExpected: %s\n",
                        index++, inputStr, resultStr, expectedStr);
            }
        }
        System.out.println(allPassed ? "All TestCase Passed!" : "Some TestCase Failed!");
        return allPassed;
    }

    protected abstract Map<?, ?> getTestCase();
}

关于技术学习的一些思考


我觉得任何技术都可以从这么几个角度去考虑:

技术选型

  • 这个框架它解决了什么旧的问题? 又带来了什么新的问题?
  • 它与其他同类技术相比有什么特点? 其侧重点在什么地方?
  • 基于以上问题, 该框架适用于什么场合?

软件工程的一个基本原则就是没有银弹, 任何技术都有其适用的场合, 在学习一个技术之前先想清楚为什么要学它.

比如说, 微服务的两大主要优点是 分布式部署 和 代码解耦, 但问题是如果你的项目量级根本没有大到需要分布式部署, 而且业务的复杂程度也没有大到耦合度很高, 那么到底是为什么需要它呢? 不要忘记了, 一项技术会有优点的同时那么必然也会有缺点以及其带来的问题.

优点没有享受到, 反倒是被缺点坑到吐血, 那就是本末倒置了.

当然你说是做技术储备, 从长远考虑, 那当我没说.

技术学习

一般来说, 技术文档可以分为三类: Tutorial, User Guide和Reference

  • 首先应该看的是Tutorial, 一般是step-by-step的教你做一个基本的demo出来.
  • 然后应该看的是User Guide, 一般是介绍整体功能结构以及常见场景的解决方案.
  • 最后是Reference, 基本上就是事无巨细的罗列所有功能了.

一般来说, Tutorial用来快速上手, 深入学习需要User Guide看一遍, Reference那就纯粹是查漏补缺了, 需要的时候翻一翻就行.

我个人的学习路线基本上是:

  • 首先通过step-by-step的Tutorial快速构建出一个demo, 了解其基本写法
  • 然后根据User Guide, 在demo上进行魔改以完成我所想的功能
  • 如果遇到一些奇葩问题, 可以去stackoverflow上看看有没有解答
  • 如果没有, 可能就需要去怼源码了→_→

学习Tutorial的时候可能很重要的一点是, 不仅仅是照着做, 更要想清楚为什么要这么做, 每一行都有什么用, 我能不能不这么写, 有没有别的写法.

技术总结

纸上得来终觉浅,绝知此事要躬行

在使用技术的过程中, 更要去思考和总结, 还是上面提到的几个问题:

  • 横向比较: 它与其他同类框架相比有什么特点?
  • 纵向比较: 这个框架它解决了什么问题? 又带来了什么问题?
  • 最后: 基于以上问题, 该框架适用于什么场合?

这是软件工程层面的, 从纯技术层面上, 在使用过程中会逐渐对其机制逐渐了解, 那么能不能从机制反推出框架内部的实现原理?

  • 如果实现一个功能类似的框架, 会怎么设计?
  • 框架现有的一些坑, 如果重新设计的话, 会怎么去设计?

带着以上问题再去学习源码, 必然是事半功倍, 你会了解到:

  • 框架的设计和你的设计有什么不同, 侧重点分别在什么地方?
  • 为什么框架会有这些坑? 也许是没想到, 那么你可以提交PR, 也许只是一种折衷和妥协, 那么为什么要这么妥协?
  • 如果你发现你的理念和现有框架的理念完全不同, 在某一方面又有突出优势, 那么说不定你就可以开个新的框架了呢233

技术本身不是重点, 重点是技术背后的思想和设计理念.

就好比挖沙子, 到底用铁铲挖还是挖掘机挖其实取决于你到底要挖多少沙子(不同场景). 挖基坑可以用挖土机, 那挖古墓还用挖土机? 而且会用铁铲挖了再去学怎么用挖掘机挖很难吗? 毕竟造挖掘机的人也是从用铲子挖开始的.
更重要的是, 怎么从挖掘机联想到推土机, 甚至是如何去自动化整个造房子的过程.


数据库范式简明解释


总的来说, 数据库范式就是逐渐消除数据冗余的过程.

1NF: 字段不可分

  • 属性的原子性约束
  • 一个数据库中字段不能包含多个可分的字段

    • 比如说不能把手机和邮箱记录在同一个字段中
    • 同理, 把多个手机记录在同一个字段中也是不合适的

2NF: 非主键字段完全依赖于主键 (消除部分子函数依赖)

  • 记录的惟一性约束
  • 消除了主键组合字段之间的依赖
  • 反例: 两个独立的组合主键 (K1, K2) -> (V1, V2) | (K1) -> (V1), (K2) -> (V2), (K1) -> (K2)

    • 修改为: (K1) -> (V1), (K2) -> (V2), (K1) -> (K2)

3NF: 非主键字段不依赖于其它非主键字段 (消除传递依赖)

  • 字段冗余性的约束
  • 消除了非主键字段之间的依赖
  • 不存在非主键字段对任一候选主键的传递函数依赖
  • 数据冗余: V1依赖于V2, 导致多个重复V1时, V2也发生重复 (K1) -> (V1, V2) | (V1) -> (V2)

    • 修改为: (K1) -> (V1), (V1) -> (V2)

BCNF: 任何字段不依赖于其他字段 (消除传递依赖)

  • 字段冗余性的约束
  • 消除了所有字段之间的依赖(
  • 不存在任何字段对任一候选主键的传递函数依赖
  • 主键依赖主键: (K1, K2) -> (V1) | (K1) -> (K2)

    • 修改为: (K1) -> (V1), (K1) -> (K2)
  • 与3NF的主要区别是: 3NF只考虑了非主键字段之间的依赖, 而没有考虑主键组合字段之间的依赖, BCNF是一种更严格的3NF

算法和数据结构总结大纲


时间复杂度

基本原则

一些容易混淆的时间复杂度分析

常数优化

  1. IO优化(快速读写)
  2. 避免浮点数, 尽量只处理整数
  3. 快速乘法, 通过对乘数拆解做移位
  4. 避免除法, 2的整数次幂除法可以用移位代替
  5. 避免取模, 快速取模方法

基本思想

递归

主要可以分为如下三种:

  • 尾部递归, 就是循环, 不支持循环的语言会有尾递归优化
  • 中间递归, 可以用一个栈模拟栈帧来将其转为循环, 比如阶乘的递归实现
  • 树状递归, 这个就比较复杂了, 最好是从需求上将其转为循环, 比如斐波拉契数列的递归实现

分治

前提: 如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解, 并可利用这些子问题的解求出原问题的解

流程:

  • 分解: 将一个问题分成多个类似的子问题(中间递归或者树状递归都可以)
  • 解决: 简单子问题可以直接求解
  • 合并: 将子问题的解合并成原问题的解

状态和状态转移方程:

  • 状态: 你要求解的子问题
  • 状态转移方程: 如何将子问题合并

例子:

  • 二分查找
  • 快速排序
  • 归并排序
  • MapReduce

贪心

前提:

  • 局部最优解可以合成为全局最优解
  • 某个状态以前的过程不会影响以后的状态, 只与当前状态有关(无后效性)

流程:

  • 分解: 将一个问题分解成线性的多个子问题(中间递归)
  • 解决: 对每一个线性子问题求局部最优解
  • 合并: 将子问题的局部最优解合并成全局最优解
可以视作为分治的一种特殊情况, 问题可以被分解链式的单个问题, 最后合并的时候是线性合并

动态规划

前提: 将原问题分解成为子问题后, 存在重叠子问题

可以视作为分治的一种特殊情况, 同样要求问题可以被分解为链式的单个问题, 只不过由于分解之后的子问题可能重复, 所以保存每一个子问题的最优解, 这个最优解可能在不同的状态下会被更新.
通常容易用递推实现

离散化

只考虑需要的值, 而不用考虑整个值域

基本数据结构

  • 逻辑结构: 集合/线性结构/树形结构/图形结构
  • 存储结构: 顺序存储/链式存储/索引存储/Hash存储

线性表

  • 数组/链表
  • 队列/栈

图论

存储方式

  • 邻接表
  • 邻接矩阵

基础算法

搜索和遍历
  • BFS
  • DFS
最短路算法

松弛操作: 更新两点距离

Dijkstra
  • 单源最短路
  • 要求: 非负权边
  • 适合稠密图, 邻接表
  • 思路: 贪心 O(N^2)

    • 分为已处理集合P和未处理集合Q
    • 每一步从Q中选择距离源点s最近的点u, 更新源点s到点u所有近邻的距离
SPFA(Bellman-Ford)
  • 稀疏图/负权边
  • 思路: 基于BFS O(kN)

    • 源点s入队列
    • 出队列节点u, 如果可以松弛, 节点u的所有近邻入队列
Floyd
  • 多源最短路
  • 思路: 动态规划

    • 假设>$D_k(i, j)$<表示从i到j的最短路径, 且只经过>$[1, k]$<的节点

      • 若经过k点, 那么>$D_k(i, j) = D_{k-1}(i, k) + D_{k-1}(k, j)$<
      • 若不经过k点, 那么>$D_k(i, j) = D_{k-1}(i, j)$<
      • 因此: >$D_k(i, j) = \min{D_{k-1}(i, j), D_{k-1}(i, k) + D_{k-1}(k, j)}$<
for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            d[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
最小生成树
Prim
  • 思路: 贪心 O(N^2)

    • 往集合V加入起始点s
    • 找到一端在V中另一端不在V中且权值最小的边
    • 记录这条边, 并把节点添加到V中
    • 直到所有节点都加入V
Kruskal
  • 思路: 并查集 O(NlogN)

    • 对所有边排序
    • 考虑每一条边的两个端点是否在同一并查集中
    • 如果不联通则合并两个并查集
    • 直到所有边都被检查, 或者所有节点都在同一个集合中(记录所有节点数做一次合并就减去一)
拓扑排序

并查集

  • 集合存在代表元素, 但不关心具体是哪一个元素
  • 常用操作

    • 快速找到代表元素/合并两个集合
  • 实现

    • 树和路径压缩

前缀和

  • 定义: 数组前N项的和: >$S[N]=a[1]+a[2]+\cdots+a[N]$<
  • 用途:

    • 快速得到区间和: >$S[M, N] = S[N] - S[M-1]$<
    • 区间快速运算: 对>$[M, N]$<加上k

      • 构造辅助数组aux[i], 表示>$[i, len(a)]$<区别的变化值

        • 拆分成: >$[M, len(a)]$<加上k, >$[N+1, len(a)]$<减去k
        • aux[M] = k, aux[N+1] = -k
        • 求aux的前缀和即可知道每个位置的变化量