[数据结构与算法]11月14日一周总结

题目总结

线段树问题+二分查找
对一个数列进行以下操作：
查询操作，查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
插入操作，将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。

long long max(long long a,long long b)
{
    return a>b?a:b;
}
const long long inf=-(1<<62);
void add(int s,int k,int o,int l,int r)
{
    if(l==r)
    {
        data[o]=k;
        return;
    }
    int mid=(l+r)>>1;     //二分部分
    if(mid>=s) add(s,k,o<<1,l,mid);
    if(mid<s) add(s,k,o<<1|1,mid+1,r);
    data[o]=max(data[o<<1],data[o<<1|1])%p;//按题目要求对一个数取模
}

插入操作代码，要想用数组得到线段树，可以借助二分算法，原理是完全二叉树的性质，首先有一个足够大的数组，然后在线段树的叶子节点附上插入的数值，同时对他的父节点赋值，附上两个子节点的最大值，这步可以通过递归达到，这里有一个可以减小运算规模的小技巧，o<<1，o<<1|1，第一个就是单纯的二倍关系，但是比乘2要快，而按位或运算可以达到奇数不变，而偶数加一的效果，同时这步也比加1要快，可以看出位运算的运算量要小于十进制的四则运算量。

long long ask(int ll,int rr,int o,int l,int r)
{
    if(ll<=l&&rr>=r) return data[o];
    int mid=(l+r)>>1;
    long long a=inf,b=inf;
    if(mid>=ll) a=ask(ll,rr,o<<1,l,mid);
    if(mid<rr) b=ask(ll,rr,o<<1|1,mid+1,r);
    return max(a,b);
}

这里的查询函数可以看出二分的方便，非常基础的二分查找代码。(题目的难度不大，但是有很多零散的知识点，虽然是针对某一部分的练习，却含盖了不只一种算法在其中，算法学习还是需要更广范围的认识和更深的认识，达到灵活使用的目的)

图论

个人理解：点线图，但是难点在于根据要求建立合适的模型，树这一数据结构可以看做是特殊的图。图的种类很多，可以根据有无回路，权值，方向分为多种。
对于无向图：自环，即一条连接一个顶点和其自身的边，连接同一对顶点的两条边称为平行边。
图的基本操作：

//计算v的度数
public static int degree(Graph G, int v) {
    int degree = 0;
    for (int w : G.adj(v)) degree++;
    return degree;
}

//计算所有顶点的最大度数
public static int maxDegree(Graph G) {
    int max = 0;
    for (int v = 0; v < G.V(); v++) {
        if (degree(G, v) > max)
            max = degree(G, v);
    }
    return max;
}

//计算所有定点的平均度数
public static double avgDegree(Graph G) {
    return 2.0 * G.E() / G.V();
}

//计算自环的个数
public static int numberOfSelfLoops(Graph G) {
    int count = 0;
    for (int v = 0; v < G.V(); v++) {
        for (int w : G.adj(v)) {
            if (w == v) count++;
        }
    }
    //每一条边都被标记过两次
    return count / 2;
}

图的基本表示：邻接矩阵：我们可以使用一个V乘V的布尔矩阵来表示，但对于大图是不合适的。邻接表数组：以顶点为索引的链表数组，其中的每个元素都是和该顶点相邻的顶点链表。
链接表代码：

class Graph{
    private final int V;         //顶点数目
    private int E;               //边的数目
    private Set<Integer>[] adj;  //邻接表
    public Graph(int V, int[][] edges) {
        this.V = V;
        adj=(HashSet<Integer>[])new HashSet[V];
        for (int v = 0; v < V; v++) {
            adj[v]=new HashSet<Integer>();
        }
        for (int[]edge:edges) {
            int w=edge[0];   //第一个顶点
            int v=edge[1];   //第二个顶点
            addEdge(w, v);
        }
    }
    public void addEdge(int w, int v) {
        adj[w].add(v);
        adj[v].add(w);
        E++;
    }
    public int V() {
        return V;
    }
    public int E() {
        return E;
    }
    public Set<Integer> adj(int v) {
        return adj[v];
    }
}