目录
字符串
,是一个种特殊的线性表,由n(n>=0)个字符组成的有序序列。
public interface IString{
public void clear(); //串的清空
public boolean isEmpty(); //是否为空
public int length(); //串的长度,串中字符的个数
public char charAt(index); //返回第index个字符值
public IString substring(begin,end); //*获得子串[begin,end)
public IString insert(offset, str); //在第offset个字符之前插入str串
public IString delete(begin, end); //删除子串[begin,end)
public IString concat(IString str); //*把str串连接到当前串的后面
public int compareTo(IString str); //串的比较,相同返回0,否则返回正/负
public int indexOf(str, begin); //从start开始,返回str在串中位置,不存在返回-1
}
串的存储结构包括:顺序存储 和 链式存储。
public class SeqString implements IString{
private char[] strvalue; // 字符数组,用于存放字符串信息
private int curlen; // 串的长度 current length
}
链式存储:使用链表存储。
块链表:每个结点可以有多个字符。
public class SeqString implements IString{
private char[] strvalue; // 字符数组,用于存放字符串信息
private int curlen; // 串的长度 current length
public void clear() { //清空
this.curlen = 0;
}
public boolean isEmpty() { //是否有空
return this.curlen == 0;
}
public int length() { //串的长度
return this.curlen;
}
public char charAt(int index) {
if(index < 0 || index >= curlen) {
throw new 字符串索引越界异常(); //String Index OutOfBounds Exception
}
return strvalue[index];
}
}
/**
* @param newCapacity 新容器大小
*/
public void allocate(int newCapacity) {
char[] temp = strvalue; // 存放原来的数据 ab数组
strvalue = new char[newCapacity]; // 给strValue重新赋一个更大数组的值
for(int i = 0; i < temp.length; i++) { // 拷贝数据
strvalue[i] = temp[i];
}
}
需求:"abcd".substring(1,3) --> "bc"
public IString substring(int begin , int end) {
// 1 两个参数校验
if(begin < 0) { // 1.1 begin 不能小于0
throw new StringIndexOutOfBoundsException("begin不能小于0");
}
if(end > curlen) { // 1.2 end 不能大于当前长度
throw new StringIndexOutOfBoundsException("end不能大于当前长度");
}
if(begin > end) { // 1.3
throw new StringIndexOutOfBoundsException("begin不能大于end");
}
// 2 优化:当前串直接返回
if(begin == 0 && end == curlen) {
return this;
}
// 3 核心算法
char[] buffer = new char[end - begin]; // 构建新数组
for(int i = 0 ; i < buffer.length ; i ++) { // 依次循环遍历新数组,一个一个赋值
buffer[i] = strvalue[i + begin];
}
return new SeqString(buffer); // 使用字符数组构建一个新字符串
}
/** "abcdef".insert(2,"123").insert(...)
* @param offset 偏移量,插入的位置
* @param str 插入数据
*/
public IString insert (int offset, IString str) {
//1 校验
if(offset < 0 || offset > curlen) {
throw new StringIndexOutOfBoundsException("插入位置不合法");
}
//2 兼容:如果容器不够,需要扩容 当前长度 + 新字符串 > 容器长度
int newCount = curlen + str.length();
if( newCount > strvalue.length ) {
allocate(newCount); //扩容结果就是刚刚好,没有额外空间
}
// 3 核心
//3.1 核心1:从offset开始向后移动 str长度 个字符
for(int i = curlen-1 ; i >= offset ; i --) {
strvalue[i + str.length() ] = strvalue[i];
}
//3.2 核心2:依次插入
for(int i = 0; i < str.length() ; i ++) {
strvalue[i + offset] = str.charAt(i);
}
//3.3 设置数组长度
this.curlen = newCount;
return this;
}
/**
* @param begin 删除开始位置(含)
* @param end 删除结果位置(不含)
*/
public IString delete(int begin , int end) {
// 1 校验
// 1.1 begin 范围
if(begin < 0) {
throw new StringIndexOutOfBoundsException("begin不能小于0");
}
// 1.2 end 范围
if(end > curlen) {
throw new StringIndexOutOfBoundsException("end不能大于串长");
}
// 1.3 关系
if(begin > end) {
throw new StringIndexOutOfBoundsException("begin不能大于end");
}
// 2 核心:将后面内容移动到签名
// 2.1 移动
for(int i = 0 ; i < curlen - end ; i ++) {
strvalue[i + begin] = strvalue[i + end];
}
// 2.2 重新统计长度 (end-begin 需要删除串的长度)
curlen = curlen - (end-begin)
return this;
}
/**
* @param str 需要比较的串
* return
* >0 : 前面串值的值大于后面串
* =0 : 前面串值的值等于后面串
* <0 : 前面串值的值小于后面串
*/
public int compareTo(SeqString str) {
int n = Math.min(curlen, str.curnlen) ; // 获得最短串的长度
int k = 0 ; // 循环遍历k
char[] s1 = strvalue;
char[] s2 = str.strvalue;
while(k < n) {
if(s1[k] != s2[k]) { // 处理前缀不一致
return s1[k] - s2[k];
}
k++;
}
return curlen - str.curlen; // 两个串的前缀相等
}
/** this 主串
* @param t 模式串
* @param start 在主串中开始位置,例如:indexOf_BF("abcabc", 0)
*/
public int indexOf_BF(IString t, int start) {
// 0.1 非空校验
if(this == null || t == null) { //0.1 主串或模式串为空
return -1;
}
// 0.2 范围校验
if(t.length() == 0 || this.length() < t.length()) { //0.2模式串为空或比主串长
return -1;
}
int i = start , j = 0; // 1 声明变量
while( i<this.length() && j<t.length() ) { // 2 循环比较,主串和模式串都不能超过长度
if(this.charAt(i) == t.charAt(j)) { // 2.1 主串和模式串依次比较每一个字符
i++;
j++;
} else { // 2.2 当前趟过渡到下一趟
i = i - j + 1; // 2.3 核心算法:主串中下一字符
j = 0; // 2.4 模式串归零
}
}
// 3 处理结果
if(j >= t.length()) { //3.1 模式串已经循环完毕
return i - t.length(); //3.2 匹配成功,第一个字母的索引号
} else {
return -1; //3.3 匹配失败
}
}
滑动
模式串进行匹配。
实例1:模式串:"abcabc"
第三位的数值
第四位的数值
第五位的数值
第六位的数值
处理完成
实例2:"ababaaa"
第三位的值: k == 0
第四位的值:字符相等
第五位的值: 字符相等
第六位的值:字符相等
第七位的值:字符不相等,且k!=0
字符不相等,k!=0,再移动k
字符相等
处理完成
/** 获得next数组
* @param T 模式串
* return 返回next数组
*/
public int[] getNext(IString T) {
//1. 创建数组,与模式串字符个数一致
int[] next = new int[T.length()];
int j = 1; // 串的指针
int k = 0; // 模式串的指针(相同字符计数器)
// 2 默认情况
next[0] = -1;
next[1] = 0;
// 3 准备比较
while( j < T.length() -1 ) { // 比较倒数第二个字符
if(T.charAt(j) == T.charAt(k)) { // 连续有字符相等
next[j+1] = k+1;
j++;
k++;
} else if (k == 0) {
next[j+1] = 0;
j++;
} else { //k不是零
k = next[k]; //p119 数学推导
}
}
// 4 处理完成,返回数组
return next;
}
/** this 当前串,也就是主串 (this.length() 主串长度)
* @param T 模式串 (T.length() 模式串长度)
* @param start 从主串中开始位置,例如:"abaababaaa".index_KMP("ababaaa",0);
*/
public int index_KMP(IString T, int start) {
//1 准备工作:next数组、指针
int[] next = getNext(T); //1.1 获得模式的next数组
int i = start; //1.2 主串指针
int j = 0; //1.3 模式串的指针
//2 字符比较移动
while(i<this.length() && j<T.length()) { //2.1 串小于长度
if(j == -1 || //2.2.1 第一个字符不匹配,直接跳过
this.charAt(i) == T.charAt(j)) {//2.2.2 字符匹配
i++;
j++;
} else {
j = next[j]; //2.3 移动模式串
}
}
//3 处理结果
if(j < T.length()) { //3.1 移动位置没有模式串长,不匹配
return -1;
} else {
return i - T.length(); //3.2 匹配,目前在串后面,需要移动首字符
}
}
/** this 当前串,也就是主串 (this.length() 主串长度)
* @param T 模式串 (T.length() 模式串长度)
* @param start 从主串中开始位置,例如:"abaababaaa".index_KMP("ababaaa",0);
*/
public int index_KMP(IString T, int start) {
//1 准备工作:next数组、指针
int[] next = getNext(T); //1.1 获得模式的next数组
int i = start; //1.2 主串指针
int j = 0; //1.3 模式串的指针
//2 字符比较移动
while(i<this.length() && j<T.length()) { //2.1 串小于长度
if(j == -1 || //2.2.1 第一个字符不匹配,直接跳过
this.charAt(i) == T.charAt(j)) {//2.2.2 字符匹配
i++;
j++;
} else {
j = next[j]; //2.3 移动模式串
}
}
//3 处理结果
if(j < T.length()) { //3.1 移动位置没有模式串长,不匹配
return -1;
} else {
return i - T.length(); //3.2 匹配,目前在串后面,需要移动首字符
}
}
行序:使用内存中一维空间(一片连续的存储空间),以行的方式存放二维数组。先存放第一行,在存放第二行,依次类推存放所有行。
注意:
归零
,再使用公式。
列序:使用内存中一维空间(一片连续的存储空间),以列的方式存放二维数组。先存放第一列,再存放第二列,依次类推,存放所有列。
A[1..8,1..10] --> A[8×10] //先行后列
设有数组A[0..8,1..10],数组的每个元素占5字节,数组从内存首地址BA开始以==列序==为主顺序存放,则数组元素A[7,8]的存储首地址为( BA + 350 )。
A[0..8,1..10] --> A[9×10]
什么是对称矩阵:a(i,j) = a(j,i)
对称矩阵的压缩方式:共4种
下三角部分以行序为主序存储的压缩【学习,掌握】
下三角部分以列序为主序存储的压缩
上三角部分以行序为主序存储的压缩
上三角部分以列序为主序存储的压缩
n×n对称矩阵压缩 n (n+1) / 2 个元素,求 1+2+3+...+n的和,只需要计算三角中的数据即可
压缩后存放到一维空间(连续的存放空间中)
对称矩形 A(i,j) 对应 一维数组 s[k] , k与i和j 公式:
练习1:
a(8,5) -->索引库1,1表示方式 需要将1,1转化成0,0方式,从而可以使用公式,i和j同时-1 a(7,4) -->索引库0,0表示方式 因为:i >= j k= i(i+1)/2 +j = 7 * 8 / 2 + 4 = 32 32为索引为0的一维数组的下标 数据b下标是从1开始,对应的下标 32+1=33
练习2:
b[13] 下标从1开始,归零 b[12] 下标从0开始,k=12 i*(i+1)/2 , 如果i=4,结果为10 12-10 = j 下标0,0时,a(4,2) 下标1,1时,a(5,3)
三角矩阵分为:上三角矩阵、下三角矩阵
上三角矩阵:主对角线(不含主对角线)下方的元素值均为0。只在上三角的位置进行数据存储
下三角矩阵:主对角线(不含主对角线)上方的元素值均为0。只在下三角的位置进行数据存储
存储方式:三角矩阵的存放方式,与对称矩阵的存放方式相同。
上三角矩阵实例
上三角矩阵对应一维数组存放下标,计算公式
下三角矩阵实例
下三角矩阵对应一维数组存放下标,计算公式
对角矩阵:矩阵的所有非零元素都集中在以主对角线为中心的带状区域中,即除主对角线上和直接在主对角线上、下方若干条对角线上的元素之外,其余元素皆为零。
名词:
一维数组存储个数:n(2d+1) ,若某行没有2d+1个元素,则0补足。
2d+1
,所以需要补零。
稀疏矩阵:具有较多的零元素,且非零元素的分布无规律的矩阵。
稀疏因子:用于确定稀疏矩阵个数指标
常见的2种存放方式:三元组表存储、十字链表存储
三元组结点类
public class TripleNode { //三结点
public int row; //行号
public int column; //列号
public int value; //元素值
}
三元组顺序表类
public class SparseMatrix { //稀疏矩阵
public TripleNode[] data; //三元组表
public int rows; //行数n
public int cols; //列数m
public int nums; //非零元素的个数
}
三元组表初始化操作
行列
序号互换。
/** this转置前的对象,每一个对象中都有一个data数据
* tm 转置后的对象,每一个对象中都有一个data数据
* return 转置后的稀疏矩阵对象
*/
public SparseMatrix transpose() { //转置
// 1 根据元素个数,创建稀疏矩阵
SparseMatrix tm = new SparseMatrix(nums);
// 2 设置基本信息
tm.cols = rows; //2.1 行列交换
tm.rows = cols; //2.2 列行交换
tm.nums = nums; //2.3 元素个数
// 3 进行转置
int q = 0; //3.1 转置后数据的索引
for(int col = 0 ; col < cols; col ++) { //3.2 转置之前数据数组的每一个列号
for(int p = 0; p < nums; p ++) { //3.3 依次获得转置前数据数组的每一个数据
if (data[p].column == col) { //3.4 获得指定列的数据
tm.data[q].row = data[p].column; //3.5 行列交换,值不变
tm.data[q].column = data[p].row;
tm.data[q].value = data[p].value;
q++; //3.6 转置后的指针后移
}
}
}
// 4 返回转置后的稀疏矩阵
return tm;
}
矩阵转置时间复杂度:O(n×t) ,n列数,t非零个数
原稀疏矩阵的数据
,得到与转置后数据
关系
public SparseMatrix fasttranspose() {
// 1 根据元素个数,创建稀疏矩阵
SparseMatrix tm = new SparseMatrix(nums);
// 2 设置基本信息
tm.cols = rows; //2.1 行列交换
tm.rows = cols; //2.2 列行交换
tm.nums = nums; //2.3 元素个数
// 3 校验
if(num <= 0) {
return tm;
}
// 4 每一列的非零个数
int num = new int[cols]; //4.1 根据列数创建num数组
for(int i = 0; i<cols; i ++) { //4.2 初始数据(可省略)
num[i] = 0;
}
for(int i = 0; i< nums; i ++) { //4.3 遍历转置的数据
int j = data[i].column;
num[j]++;
}
// 5 转置后每一列第一个元素的位置数组
int cpot = new int[cols]; // 5.1 位置的数组
cpot[0] = 0; // 5.2 第一列第一个元素为0
for(int i = 1; i < cols ; i ++) {
cpot[i] = cpot[i-1] + num[i-1]; // 5.3 当前列第一个元素位置 = 上一列位置+个数
}
// 6 转置处理
for(int i = 0 ; i < nums ; i ++) {
int j = data[i].column; //6.1 转置前,每一个元素的列数
int k = cpot[j]; //6.2 转置后的位置
tm.data[k].row = data[i].column; //6.3 原数据 转置后 数据
tm.data[k].column = data[i].row;
tm.data[k].value = data[i].value;
cpot[j]++; //6.4 下一个元素的位置
}
}
时间复杂度:O(n+t) ,n列数,t非零个数
结点类:
class OLNode {
public int row, col; //行号、列号
public int value; //元素值
public OLNode right; //行链表指针
public OLNode down; //列链表指针
}
十字链表类:
class CrossList {
public int mu, nu, tu; //行数、列数、非零元素个数
public OLNode[] rhead, chead; //行、列指针数组
}