一、算法详解

1、心历路程

今年暑假，研一下册结束了，这学期肝了一篇论文出来。准备再在此论文基础上改一下，丰富一下实验，拿来作为毕业设计的底子。其实论文做的还可以，可以拆成两篇小论文，拿去做毕业设计问题不大吧（骄傲了，罚站）。
先上图，为找工作准备数据结构知识。想给自己数据结构开个头。第一次刷算法题，点了第一个通过率较高的算法题，感觉很挫折。
志斌师兄几分钟就做完了，他给我讲了他的想法，我感觉挺好的，思路很快很清晰。上面的论文能出来，也靠志斌师兄给我搞了好久的环境，谈论了一下论文思路，不然我可能已经放弃了（真心感谢）。但是不知道为什么我就是喜欢转牛角尖，不想有太高的空间复杂度。结果搞了2个小时，还好终于完成了。

2、源代码

class Solution {
    boolean flag = true;
    public boolean fn(int[][] ranges, int left, int right)
    {
        if(left == right + 1)
            return true;
        boolean b = false;
        for (int i = 0; i < ranges.length; i++) {
            if(left<ranges[i][0] && ranges[i][0]<=right && right <= ranges[i][1])
                right = ranges[i][0] -1;
            else if(left >= ranges[i][0] && right <= ranges[i][1])
                left = right + 1;
            else if(left >= ranges[i][0] && left <= ranges[i][1] && right > ranges[i][1])
                left = ranges[i][1] + 1;
            else if(left < ranges[i][0] && right > ranges[i][1]){
                flag = flag && fn(ranges,left,ranges[i][0]-1);
                return flag && fn(ranges,ranges[i][1]+1,right);
            }
            b = b || left == right + 1;
        }
        return b;
    }
    public boolean isCovered(int[][] ranges, int left, int right) {
        return fn(ranges, left, right);
    }
}

3、思路详解

原题内容在这就不写了，错了好几次，就是没理解透里面的细节。

A) 理论思想

常见数学分析法
有序表快速匹配
多递归思想
其他细节

B) 应用思想

1.常见数学分析法
这个问题可以看成是两个数组的匹配问题，所以可以分为6种情况。

细节1：数组的列只有两列，即start，end列，这也是减少运算时间的关键。
a)right < ranges[i][1]
b)left < ranges[i][0] && right >= ranges[i][0] && right <= ranges[i][1]
c)left >= ranges[i][0] && right <= ranges[i][1]
注：left <= right这是给定条件
d)left >= ranges[i][0] && left <= ranges[i][1] && right > ranges[i][1]
e)left > ranges[i][1]
f)left < ranges[i][0] && right >ranges[i][1]
注：除了f情况，其他的都可以分割成未匹配数组，而f情况会分割出两个数组，此时就需要就必须用到多递归思想了。

有序表快速匹配
因为数组里面的元素都是有序的，所以每一次匹配都根据start、end对应left、right，然后快速分割出来未能匹配上的“数组”，这也是快速匹配的原因所在。
在a、e情况中，数组都未能部分匹配成功，所以不用做任何处理。
b：部分匹配成功，将right=ranges[i][0]-1，分割出未能匹配部分，进入下一次匹配。
c：全部匹配成功，将left=right+1，达到匹配成功条件left==right+1，然后return true。
d：部分匹配成功，将left = ranges[i][1]+1。
多递归思想
在f情况中，分割出了两个数组，此时无法在进入for循环，所有需要分别递归进入匹配。
※※※特别注意
A)这里还可以加快速度，将fn()再传入一个point变量，这个point指向已经匹配了的行，第一次进入的时候设为0。这样可以更快。我就不改了，写博客还是可以，整理整理新思路就来了。
B)可以使用三目运算符来代替if、else。为什么三目运算符比if、else的效率更高？这里更if、else的处理方式和CPU的处理模式有关。
CPU将一系列的指令存入一个队列中，CPU通过顺序执行这个队列中的所有指令来做到快速计算。对于if、else，CPU根据判断条件将一种指令序列排序，但是如果世界不满足条件，那就得把排好的指令队列清空，重新把其他指令排在后面，此时就需要把刚才排好的队列清空，这种预测错误的惩罚将导致CPU处理时间变得更长。
对于三目运算符，CPU会把判断true和false下的指令都进行排队计算，然后再通过判断来选择那个结果，虽然计算量变大，但是对于CPU来说，计算就是最擅长的事。虽然if、else通过判断后只计算一种判断方向的指令，但是得到的惩罚时间反而大于全部指令执行的时间。
4.其他细节
这里的其他细节就不详记录了，都是一些基础，可以通过阅读代码自行体会，如递a)归结出口b)递归返回等等。

4、总结

谈到算法，还是得看看它的评估标准时间、空间复杂度。
1、时间复杂度：这个与输入的二维数组ranges有关，如果二维数组有n行，那么最坏时间复杂度为O(n)。
2、空间复杂度：显而易见，该空间复杂度为O(1)
3、做算法的感受：感觉算法就是一道数学题，分析拆解问题，转化问题，再结合CPU的处理方式，用高效的代码实现。