分类 杂谈 下的文章

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的前缀和即可知道每个位置的变化量

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


前言

时间复杂度分析简单来说大概分为这么几种情况:

  • 一层循环就是一层O(N), 循环套循环需要相乘
  • 如果是树状结构, 比如说有分治(二叉搜索, 快排)的时候, 那么就是O(logN)
  • 如果有递归:

    • 如果是尾递归, 那么其实是和循环等价的
    • 如果是树状递归, 比如说斐波拉契数列, 那么就是O(2^N), 确切的说是O(branches^depth)

Example1

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

Let's define new terms-and use names that are logical.

  • Let s be the length of the longest string.
  • Let a be the length of the array.

Now we can work through this in parts:

  • Sorting each string is O(s log s).
  • We have to do this for every string (and there are a strings), so that's O(a*s log s).
  • Now we have to sort all the strings. There are a strings, so you'll may be inclined to say that this takes O(a log a) time. This is what most candidates would say. You should also take into account that you need to compare the strings. Each string comparison takes O(s) time. There are O(a log a) comparisons, therefore this will take O(a*s log a) time.

If you add up these two parts, you get 0(a*s (log a + log s)).

这个很容易误认为是O(N^2 logN), 一方面是string的长度和array的长度并不一样, 另外一方面是在array排序的时候很容易忽略字符串比较还需要花费时间.

Example2

The following code prints all Fibonacci numbers from 0 to n. What is its time complexity?
void allFib(int n) {
    for (int i= 0; i < n; i++) {
        System.out.println(i + ": "+ fib(i));
    }
}

int fib(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
} 

Instead, let's walk through each call.

  • fib(!) -> 2^1 steps
  • fib(2) -> 2^2 steps
  • fib(3) -> 2^3 steps
  • fib(4) -> 2^4 steps
  • fib(n) -> 2^n steps

Therefore, the total amount of work is: 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^N = 2^(N+1)

这个很容易误认为是O(N*2^N), 主要是fib(n)这里的n每次循环都是变化的...很容易被误导

总结

时间复杂度的求法并不是很难, 基本就那么几种情况, 需要注意的是处理字符串时不能忽略掉字符串的长度.

Reference

Cracking the Coding Interview 6th Edition