2018年8月

两种最普遍的表示法:

  • 邻接表
  • 邻接矩阵

如果G是一个有向图，则所有邻接表的长度之和为|E|
如果G是一个无向图，则所有邻接表的长度之和为2|E|
邻接表有个很好的特性:存储空间为:(V+E)

邻接链表的一大缺点是无法快速判断一条边是否是图中的，唯一的办法是搜索结点找边。
图规模比较小时，更倾向于使用邻接矩阵表示法。

广度优先搜索:
BFS:使用循环+队列实现
DFS:使用递归实现 具有括号性质
利用DFS可以对边进行归类:

拓扑排序:图中所有顶点的沿水平线排列而成的一个序列

基本思路：对于一个图而言，采用深度优先搜索会产生一棵树或者一个森林，对于其中的一棵树而言，其中某一个节点越早结

束（第一次访问节点是开始时间，遍历完所有子节点返回该节点是结束时间，具体参见算法导论——深度优先搜索章节）意味着该节点

在该树中处于越底层的位置，所以在拓扑排序中应该排在最后边（只有等前边的节点做完了它才能做）。至于不同树之间，因为没有对应的依赖关系，所以顺序随意。

所以，依据访问节点的结束时间依次插入链表中【链表中的时间顺序：最快结束（最底层）——>较快结束（较底层）......——>较慢结束（较高层）——>最慢结束（最高层，也即是根节点）】，

最后逆序输出，求得最终的拓扑排序结果。

强连通图:

强连通分量：有向图中，尽可能多的若干顶点组成的子图中，这些顶点都是相互可到达的，则这些顶点成为一个强连通分量。

上图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。

小Q的歌单
热度指数：1624 时间限制：1秒 空间限制：32768K

小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。
输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。

输出描述:
输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对1000000007取模的结果。
示例1
输入
5
2 3 3 3
输出
9

其实就是枚举所有可能的组合数

package com.company;

import java.util.Scanner;

public class Main {
    static long c[][] = new long[105][105];
    static int mod = 1000000007;
    private static void init(){
        c[0][0] = 1;
        for(int i = 1;i<=100;i++){
            c[i][0] = 1;
            for(int j = 1;j<=100;j++){
                c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;//当前组合数数量是c[i-1][j-1]+c[i-1][j] i表示要取的数量总和 j表示总数
            }
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        init();
        int k = scanner.nextInt();
        int aLength = scanner.nextInt();
        int ANum = scanner.nextInt();
        int bLength = scanner.nextInt();
        int BNum = scanner.nextInt();
        int dp[][] = new int[k+1][ANum+BNum];
        int res = 0;
        for(int i = 0;i<ANum;i++){
            for(int j = 0;j<BNum;j++){
                if(i*aLength + j*bLength == k){
                    res += c[ANum][i] * c[BNum][j]; //ANum里面i的组合数 与 BNum里面j的组合数相乘得到结果
                }
            }
        }
        System.out.println(res % mod);
        //dfs(0,0,k);
    // write your code here
    }
}

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

解题关键:直接对一个数异或全部 你会发现剩下的那些不为0的位数是 数1和数2的异或 所以对其分别异或

class Solution {
    public int[] singleNumber(int[] nums) {
        int res = 0;
        int xo = 0;
         for(int num: nums)
             xo ^= num;
         int idx = 0;
         while(((xo >> idx) & 1) == 0) idx++;
         int res1 = 0, res2 = 0;
         for(int num: nums){
            if(((num >> idx) & 1) == 1) res1 ^= num;
             else res2 ^= num;
        }
        return new int[]{res1,res2};
    }
}

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:

输入: "23-45"
输出: [-34, -14, -10, -10, 10]
解释:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
解题关键:利用分治法 遇到运算符分左右执行 返回的是左边 与右边的所有可能 边界条件则是如果res.size() == 0则直接add input

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList();
        for(int i = 0;i<input.length();i++){
            char c = input.charAt(i);
            //只有遇到运算符的时候
            if(c == '+' || c == '-' || c == '*'){
                //运算符左边
                List<Integer> res1 = diffWaysToCompute(input.substring(0,i));
                //运算符右边
                List<Integer> res2 = diffWaysToCompute(input.substring(i+1));
                for(int r1:res1){
                    for(int r2:res2){
                        if(c == '+'){
                            res.add(r1+r2);
                        }else if(c == '-'){
                            res.add(r1-r2);
                        }else if(c == '*'){
                            res.add(r1*r2);
                        }
                    }
                }
            }
        }
        if(res.size() == 0){
            res.add(Integer.parseInt(input));
        }
        return res;
    }
}

内存管理的目标:

  • 内存管理
  • 提高内存利用率、内存访问速度

存储器的层次结构:

  • 不同容量
  • 不同成本
  • 不同访问时间

从高层到底层(L0~L5) 较低层的存储设备速度更慢、容量更大、价格更便宜。

  • L0:是少量的快速CPU寄存器 CPU可以在一个时钟周期内访问它们。
  • L1:多个小型或中型的基于SRAM的高速缓存存储器 CPU可以在几个CPU时钟周期内访问他们
  • L3:一个大的基于DRAM的主存，可以在几十或几百个时钟周期内访问它们。
  • L4:慢速但容量大的本地磁盘
  • L5:远程磁盘等……

CPU寄存器保存最常用的数据。 靠近CPU的容量小、速度快的高速缓存存储器作为速度相对较慢、容量较大的主存数据和指令子集的缓冲区。

总的来说，局部性原理表现为时间和空间的局部性。

静态链接:

  • 对逻辑地址进行修改
  • 变换外部调用符号
    优点:运行速度快 缺点:占用空间大

动态链接(调用时才进行链接):
优点:节省内存和外存空间
缺点: 速度慢

源程序要变为一个可在内存中执行的程序要经过编译、链接、装入三个阶段。
通常，可执行程序以二进制可执行文件的形式存储在磁盘上，
程序的装入方式分为绝对装入方式、可重定位装入方式和动态运行时装入方式。

  • 绝对装入方式
    事先已知程序在内存中的驻留位置，编译时产生物理地址的目标代码，绝对装入程序按照装入模块的物理地址将程序和数据装入内存。因此装入模块被装入内存后，无需对程序和数据的地址进行修改。
  • 可重定位装入方式

在程序装入时对目标程序中的指令和数据地址的修改过程称为重定位。
可重定位方式的两个特定如下:

  • 编译程序使目标模块的起始地址从0开始
  • 程序装入时根据内存使用情况将模块装入到内存的某个位置 并对模块进行重定位

物理地址=有效逻辑地址+程序在内存中的起始地址

  • 动态运行时装入
    进程在装入内存后，还可能从内存的一个区域移动到另一个区域，这种情况可能发生在支持虚拟存储的系统中。

连续分配存储管理方式:

单一连续区分配方式

  • 固定分区分配方式
    分区方式:分配的用户分区数量是固定的，每个分区的大小也是固定的。但是每个分区的大小可以相等，也可以不相等。

动态分区分配方式

1.动态分区分配原理:当进程请求空间时，由于系统根据进程需要的空间大小划分出一片空闲区分配给进程。
系统初始只有一个大空闲区，

2.动态分区分配数据结构

- 空闲分区表
- 空闲分区链

3.动态分区的分配算法

  • 首次适应算法(First Fit)
    优点:结构简单 缺点:搜索空闲分区链需要的时间开销比较大
  • 循环首次适应算法(Next Fit)
    优点:空闲区分布均匀、查找开销较小 缺点:容易缺乏大空闲分区
  • 最佳适应算法(Best Fit)
    按分区大小递增组成一个空闲链

优点:避免大材小用 提高内存利用 缺点:留下难以利用的小空闲区。

内存分配流程:
1.检索空闲分区链 m.size >= u.size
2.如果m.size(当前结点对应的空闲分区大小) - u.size (用户申请的空间)<= size (系统阈值) 则直接分配 否则从m.size 中划出大小为u.size的空间分配给进程，把剩余的大小为m.size-u.size的空闲空间作为新的空闲分区。
3.将分配给进程的分区起始地址返回给内存分配程序的调用者
4.修改空闲分区链表

内存回收流程

  • 释放一块连续的内存区域
  • 如果被释放区域与其他空闲区间相邻，则合并空闲区
  • 修改空闲分区链

基本分页存储管理方式
把进程离散地存储在内存中物理地址不连续的区域中，这种内存管理方式称为离散内存管理方式。
原理:
页:将一个进程的逻辑地址空间分为若干个大小相等的片
页框:将物理内存空间分成与页大小相同的若干个存储块，称为页框或页帧
分页存储:以页框为单位将进程中的若干页分别装入多个可以不相邻接的页框中。
页内碎片:进程的最后一页一般装不满一个页框。
页表:页表是系统为进程建立的数据结构，作用是实现从页号到页框号的映射。

地址结构:
基本分页的逻辑地址结构分为两部分:页号P和页内偏移W 低n位表示页内偏移量W 用高m-n位表示页号P
以32位为例子:当0~12位表示页偏移时 则可以容纳2的12次方字 大概:4KB 12~31位(20位)可以有2的20次方个页 则有1M个页 则总共可表示4G的逻辑地址空间。
计算公式:A为逻辑地址 L为页大小 W为页内偏移量 计算关系:
P=INT(A/L)
W=MOD(A/L)

分页地址变换过程

  • 进程执行，PCB中页表起始地址和页表长度送CPU的页表寄存器
  • CPU访问逻辑单元A
  • 由分页地址变换硬件自动将A分为页号和页内偏移两部分
  • 由硬件检索页表，得到A所在的页对应的页框号
    页号对应的页表起始地址 = 页表起始地址 + 页表项长度 × 页号
  • 页框号和页内偏移地址送物理地址寄存器，计算物理地址。物理地址 = 页框大小×页框号 + 页内偏移量

页大小的选择:
选择较小 会使进程的页数较多、换出频繁
选择较大 会使进程缺页率高，页表过长占用大量内存空间

影响大小的设计因素:

  • 管理内存的开销
  • 内存的利用率

一般选择2的次幂 4KB一般

快表也称为后援缓冲(Translation Look-aside Buffer):
页表的硬件实现方法之一,用来存放最近被访问过的页表项
相当于是一个键值缓存 通过键(页号)映射到值(页框号)

有效访存时间:
假设CPU访问内存的速度为:120ns,访问TLB的速度为20ns,比较有TLB和无TLB系统的平均访存时间,假定命中率为:90%。
则有TLB:(未命中)(120+120+20)×10% + (命中)(120+20)x90% = 152ns
无TLB:120+120 = 240ns
(240-152)/152 = 57.9%;

反置页表:
现代系统可能存在大量进程，每个进程都允许有很大的逻辑地址空间，因而进程可能拥有一个很大的页表。可以使用反置页表，为每一个页框设一个表项、表项中存放进程号和页号，系统只维护一张反置页表即可。

空闲页框管理:
使用位图管理空闲页框:
用二进制的位数对应物理内存的页框数 0 代表当前位数的页框未占用 1 代表占用

基于分页的虚拟存储系统

虚拟存储技术实现的基本思想:按需载入 如果当前CPU访问的内容不在内存上面则通过抛出异常让外存载入指定内容到内存上。
置换:当内存满的时候把一部分不相关的换出到外存上。

优点:

  • 提高内存利用率
  • 提高多道程序度
  • 把逻辑地址空间和物理地址空间分开

虚拟存储系统具有以下几个主要特征:

  • 离散性
  • 多次性
  • 对换性
  • 虚拟性

请求分页中的硬件支持

  • 页表
    具有以下基本字段:

    • 页框号
    • 状态位p :页是否在内存
    • 访问字段A: 最近访问信息
    • 修改位M :最近修改信息
    • 保护位 :0为只读 1为可读可写
  • 缺页异常机构
    1.通过检查当前页表的状态位p判断是否在内存中不在则产生缺页异常信号

2.找空闲页框然后调用外存读入数据
3.修改页表 存在位、页框号、访问位、保护位等
4.重新开始执行因缺页而被中断的指令

添加请求分页系统的地址变换过程如下:

  • 由分页地址变换机构从逻辑地址中分离出页号和页内偏移地址
  • 以页号为索引查找快表 如快表中没有则转到内存页表中查找
  • 若该页不在内存则产生缺页异常，请求操作系统从外存中把该页调入内存。

页分配策略

1.最少页框数
保证进程正常运行所需要的最少页框数与进程的大小没有关系，它与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。要计算每个内存单元所涉及的内存地址页数来确认进程运行最少所需分配页框数。
2.页分配和置换策略

  • 固定分配局部置换
  • 可变分配全局置换
  • 可变分配局部置换

3.分配算法

  • 平均分配算法 n个进程 m个内存页框 则为每个进程分配INT[m/n]个页框,其余MOD[m/n]放入空闲框缓冲池中
  • 按比例分配算法
    进程分配的页框数 = 进程页数/所有进程页数的总和×页框数
  • 考虑优先权分配算法
    优先权高页框数多 优先权低页框数少

页调入策略

  • 何时调入页
    1.用到的时候再调入

2.预先调入

  • 何处调入页
    1.从对换区调入 进程运行前从文件区复制到对换区。

2.UNIX方式 没有访问过的页都直接从文件区调入，换出页都存放在对换区。

页置换算法

1.最佳置换算法和先进先出置换算法(难以实现)
选择未来最长时间不会用到的内存页进行置换
2.先进先出页置换
选择进入内存时间最早的页
3.最近最久未使用LRU置换算法
选择最近最久未使用的页换出
实现办法

  • 设置一个寄存器到页中 每隔一段时间寄存向右移一位 并且最高位置一 则最小值的为最久未使用的页
  • 栈
  • 计数器

其他置换算法:
计算机系统要提供足够的硬件来支持LRU算法比较困难 所以实现时都采用LRU的近似算法 如附加位算法、简单Clock算法和改进型Clock算法
改进型Clock步骤:
从当前位置开始扫描循环队列寻找A=0,M=0(未访问页未修改) 如果找到底仍未找到则寻找A=0,M=1 第二轮扫描期间将所有经过的页的访问位A置0
如果第二步也失败则再次寻找A = 0,M = 0的第一类页,如仍失败 再寻找A = 0,M = 1的页

  • 最少使用置换算法
  • 页缓冲算法

P为缺页率 ma为存储器访问时间
有效访问时间 = (1-P)x ma + P x 缺页异常时间
缺页异常时间 = 缺页异常服务时间 + 缺页读入时间 + 进程重新执行时间

例:4-12:要使有效访问时间延长不超过10%,缺页率P为多少？
因为P = 0时,有效访问时间 = 0.1μs
P不为0时，有效访问时间为:(0.1+24999.9P)μs
P不为0时比P为0延长时间:(0.1+24999.9P) - 0.1 = 24999.9P
要使24999.9P / 0.1 < 10% 必须使 P < 0.000.0004

工作集:
引入工作集机制是为了能有效降低缺页率
提前将需要的页面调入内存
工作集就是在某段时间间隔t里,进程实际要访问的页数集合

抖动产生的原因和预防方法
1.抖动 (多道程序下大部分时间都在进行页换入、换出)
2.预防
1.采取局部置换策略,当进程发生缺页后,仅在进程自己的内存空间范围内置换页
2.在CPU调入程序中引入工作集算法,只有当每个进程在内存中都有足够大的驻留集时,才能再从外存中调入新的作业。
3.挂起若干进程,腾出进程占用的空间。

  1. 1
  2. 2
  3. 3
  4. 4
  5. ...
  6. 21