图的基本结构以及BFS和DFS(递归和非递归)
图的基本结构以及BFS和DFS(递归和非递归) 完整的图结构 有向图建图以及BFS和DFS 无向图建图以及BFS和DFS DFS和BFS常见应用 完整的图结构 图的每个顶点包括顶点的值、入度、出度、和它相邻的点(或者在有向图中就是下一个可以到达的点)的集合、以及以它为起点出发的边的集合； 图的每条边包括边的权值、边的起点、边的终点； 一个图包括点的集合和边的集合； 综上可以得到如下的图结构: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 //点 (默认我是from的情况下) static class Node{ public int value; public int in; //入度 public int out; //出度 public ArrayList<Node>nexts;// 从我出发能到达的下一级结点，...
最长公共子序列LCS 和 最长公众子串
最长公共子序列LCS 和 最长公众子串 51Nod-1006-最长公共子序列LCS 最长公众子串 51Nod-1006-最长公共子序列LCS题目链接 http://www.51nod.com/Challenge/Problem.html#!#problemId=1006 题目就是输入两个字符串str1、str2，输出任意一个最长公共子序列。 解析dp[i][j]代表的是 : 必须以str1[i]、str2[j]结尾的最长公共子序列，dp[i][j]来源: 可能是dp[i-1][j]，代表str1[0~i-1]与str2[0~j]的最长公共子序列。 可能是dp[i][j-1]，代表str1[0~i]与str2[0~j-1]的最长公共子序列。 如果str1[i] == str2[j]，还可能是dp[i-1][j-1] + 1。 这三种情况中取最大值。 构造结果的过程(利用dp数组即可) 从矩阵的右下角开始，有三种移动方式: 向上、向左、向左上。 如果dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1]，...
各种排序算法总结(全面)
各种排序算法总结(全面) 概括 冒泡排序 改进的冒泡排序-鸡尾酒排序 选择排序 插入排序 二分插入排序 希尔排序 快速排序 归并排序 堆排序 计数排序 基数排序 桶排序 测试代码 附C++部分代码 概括排序算法大体可分为两种： 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。 另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。 下面给出常见比较算法的排序性能 排序方法 平均情况 最好情况 最坏情况 空间 稳定性 冒泡 O(n2) O(n) O(n2) O(1) 稳定 简单选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 直接插入排序 O(n2) O(n) O(n2) O(1) 稳定 希尔排序 O(nlogn) ~ O(n2) O(n1.3) O(n2) O(1) 不稳定 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 归并排序 O(nlogn) O(nlogn) O(nlogn)...
二分查找的总结(6种变形)
二分查找的总结 普通的二分查找 普通二分查找的另一种写法 第一个=key的，不存在返回-1 第一个>=key的 第一个>key的 第一个...的总结 最后一个=key的，不存在返回-1 最后一个<=key的 最后一个<key 的 最后一个...的总结 完整测试代码 普通的二分查找最普通的写法: 范围在[L,R]闭区间中，L = 0、R = arr.length - 1； 注意循环条件为 L <= R ，而不是L < R； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 static int bs1(int[] arr,int key){ int L = 0,R = arr.length - 1; //在[L,R]范围内寻找key int mid; while( L <= R){ mid = L + (R - L) / 2; if(arr[mid] == key) return mid; if(arr[...
计算机网络知识总结一计算机网络和协议(一)
计算机网络知识总结一计算机网络和协议(一) 互联网概述 互联网组成 计算机网络的性能指标 OSI参考模型以及TCP/IP四层模型、五层协议 通信过程、数据传输、网络设备 小结 互联网概述 计算机网络: 由若干节点和连接这些节点的链路组成，网络中的节点可以是计算机、集线器、交换机、或路由器等； 网络之间可以通过路由器相互连接，这就构成了一个更大范围的计算机网路，这样的网路称为互连网，因此互连网是网路的网路； 因特网(互联网): 全球最大的特定互连网； 注意以下两个意思相差很大的名词 internet 和 Internet [RFC 1208]: 以小写字母 i 开始的 internet (互连网) 是一个通用名词，它泛指由多个计算机网络互连而成的计算机网络。在这些网络之间的通信协议〈即通信规则) 可以任意选择，不一定非要使用TCP/IP 协议； 以大写字母 I 开始的 Internet 〈互联网或因特网) 则是一个专用名词，它指当前全球最大的、开放的、由众多网络相互连接而成的特定互连网，它采用 TCP/IP 协议族作为通信的规则，且其前身是美国的 ARPANET；...
Http协议
Http协议 一、Web和网络基础 一、Web和网络基础1、使用HTTP协议访问Web 客户端: 通过发送请求获取服务器资源的 Web 浏览器等，都可称为客户端（ client ）。 Web 使用一种名为 HTTP （ HyperText Transfer Protocol ，超文本传输协议）的协议作为规范，完成从客户端到服务器端等一系列运作流程。而协议是指规则的约定。Web是建立在Http协议上通信的； 2、TCP/IPTCP/IP 协议族按层次分别分为以下 4 层：应用层、传输层、网络层和数据链路层； 应用层: TCP/IP 协议族内预存了各类通用的应用服务。比如， FTP （ File Transfer Protocol ，文件传输协议）和 DNS （ Domain Name System ，域名系统）服务就是其中两类。HTTP 协议也处于该层。 传输层: 传输层对上层应用层，提供处于网络连接中的两台计算机之间的数据传输。在传输层有两个性质不同的协议： TCP （ Transmission Control Protocol ，传输控制协...
C语言基础知识总结(一)
C++基础知识总结(一) C++对C语言的提高 命令空间简单使用 const关键字的加强 引用-重点 指针引用 没有引用指针 const引用 默认参数函数重载作用域运算符 new、delete的使用 C++面向对象基础 一个简单案例 构造函数和析构函数 深拷贝和浅拷贝 指向对象成员函数的指针 常对象 常对象成员-常数据成员&常成员函数 指向对象的常指针 指向常变量、对象的指针 静态成员 友元 C++重载运算符 重载基本运算符 重载=号操作符 重载流插入运算符和流提取运算符 综合案例-矩阵加法以及输入输出 函数模板、类模板 案例-简单实现的Vector类模板中的push_back 文件操作 输入输出流 文件读写 C++对C语言的提高命令空间简单使用引用命令空间的三种方式: 直接指定标识符。例如std::cout<<"hello"<<std::endl;； 使用using关键字。例如using std::cout; ； 导入整个命令空间。例如using namespace std; 导入std命名空间； ...
C语言基础知识总结(一)
C语言基础知识总结(一) 编译、运行 编译格式 C语言编译过程 CPU、寄存器 关于VS的C4996错误 进制，原、反、补码 进制相关 原码、反码、补码 原码和补码互换 有符号和无符号的区别 数据类型取值分析 越界问题 数据类型、运算符等基础 C语言数据类型 sizeof关键字 char数据类型-char的本质就是一个1字节大小的整型 浮点数不准确、类型限定符 字符的输入问题 运算符以及优先级 类型转换 数组、字符串、函数 数组初始化的几种方式 字符数组与字符串 字符串输出乱码问题以及一系列字符串要注意的问题 随机数生成 字符串相关函数 函数 编译、运行编译格式gcc -o main main.cpp生成main可执行文件，可以有两种运行方式: 当前目录运行./main； 绝对路径运行，例如/home/zxzxin/C/main，要注意的是绝对路 径没有.，因为.代表的是当前路径，也就是说我们只需要写上完整路径即可； 编译命令格式 1 2 gcc [-option] ... <filename> //c语言编译 g++ [-...
JVM总结(二)
JVM总结(二) - 垃圾收集器与内存分配策略 一、垃圾回收概述 二、如何判定对象为垃圾对象 1、引用计数法 2、可达性分析算法 3、引用分类 4、生存还是死亡-finalize()方法 5、回收方法区 三、垃圾回收算法 1、标记清除算法 2、复制算法 3、标记整理算法 4、分代收集算法 四、垃圾收集器 1、各个垃圾收集器的联系 2、Serial收集器 3、ParNew收集器 4、Parallel Scavenge收集器 5、Serial Old收集器 6、Paralell Old收集器 7、CMS收集器 8、G1收集器 9、各种垃圾收集算法的对比 五、内存分配与回收策略 1、对象优先在Eden分配 2、大对象直接进入老年代 3、长期存活对象将进入老年代 4、空间分配担保 5、动态对象年龄判定 6、关于逃逸分析以及栈上分配 一、垃圾回收概述关于垃圾回收，主要探讨下面四个问题。 1、回收区域 程序计数器、虚拟机栈和本地方法栈这三个区域属于线程私有的，只存在于线程的生命周期内，线程结束之后也会消失，因此不需要对这三个区域进行垃圾回收； 垃圾回收主要是针对 Ja...
JVM总结(一)
JVM总结(一) - 内存区域与内存管理 一、JVM启动以及JVM体系概述 1、JVM启动流程 2、JVM体系结构 二、运行时数据区总体概括 1、程序计数器 2、Java虚拟机栈 3、本地方法栈 4、Java堆 5、方法区 6、运行时常量池 7、直接内存-不是运行时数据区域的一部分 三、对象相关 1、对象的创建过程 2、对象的内存布局 3、对象的访问定位 一、JVM启动以及JVM体系概述概括: Java有Java编译器和Java虚拟机，编译器将Java源代码转换为.class文件，虚拟机加载并运行.class文件。 Java 的开发遵循“一次编写到处乱跑”理念，它运行在 VM（虚拟机）上。 1、JVM启动流程JVM工作原理和特点主要是指操作系统装入JVM，是通过jdk中java.exe来完成,通过下面4步来完成JVM环境: 创建JVM装载环境和配置； 装载JVM.dll； 初始化JVM.dll并挂界到JNIENV(JNI调用接口)实例； 调用JNIEnv实例装载并处理class类。 2、JVM体系结构JVM体系主要是两个JVM的内部体系结构，分为三个子系...