33：数据结构和算法：数组与链表
1.数据结构与算法基本概念。
单列表翻转，判断平衡二叉树。
string 转int，边界判断，
大数据相乘。
海量数据筛选5个最大数据。
《算法4-红色壳子》
数据结构
数据元素之间的关系
集合结构，线性关系，树形关系，图形结构等。
存储结构：顺序存储、链式存储。
程序 = 数据结构+算法。
算法的特性：输入、输出、有穷性、确定性和可行性。
2.时间复杂度和空间复杂度
算法的优劣：从算法的执行时间和 所占用的存储空间两方面衡量。会求时间和空间的复杂度。
- 时间复杂度：定性描述了该算法的运行时间，时间复杂度常用大O符号表示。
可以理解为代码执行的步骤 - 空间复杂度：对一个算法运行过程中临时占用存储空间大小的量度。
malloc(sizeof(char) *n); // 空间O(n),字符串反转
常见的时间复杂度:
常数阶O(1),
对数阶O(log2 n),
线性阶O(n),
线性对数阶O(n *log2n)，
平方阶O(n^2),
立方阶O(n^3),
k次方阶O(n^k)，
指数阶O(2^n)
很多时候，需要拿空间复杂度 换时间复杂度
统计一篇文章字符出现的个数。
1.Map集合查询。key存字母，value存储出现的次数。时间复杂度O(n)+ Map查询
2.定义一个123长度的数组，arr['c'] = arr['c']++;
只有一步，空间换时间。
3.数组与链表源码分析
https://www.jianshu.com/p/66baa9a5f855
-
ArrayList 源码分析【底层基于数组】：构造函数默认长度10， len += len>>1; 扩容时要开辟空间对原来的数据进行拷贝。
新增时涉及到开辟新空间、数据拷贝、释放原来的old指针（析构掉），插入数据快。
但是访问数据直接通过角标访问。
移除数据remove，当到达一定阈值，会开辟一块更小的空间，然后将数据拷贝过去。
删除数据，移除当前位置，后面的所有数据往前copy。 -
LinkedList源码【双向链表】，每个Node有prev、next两个指针。
整个链表维护header、last指针
添加节点：创建新节点newNode，当前节点的prev= 原来链表的last;
void linkLast(E e){ // 添加节点
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode; // last的next 指向新的节点。
if(l == null) // 没有last节点，数据为空。 first，last都为新节点。
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
单链表实现LinkedList，有什么缺点？因为查找速度太慢了，用空间换时间。
c++的list，也是使用双向链表。
#include <iostream>
using namespace std;
/*
// 比如我们现在 求 1+2+3+4+***+n
// 任何算法在特定执行的 n 步骤下，我们都可以推演出算法的复杂度（时间，空间）
// 简单的理解为执行的步骤
int sum1(int n){// n + 2 步 O(n)
int sum = 0;// 1 步
for (int i = 0; i <= n; i++)// n 步
{
sum += i;
}
return sum;// 1步
}
int sum2(int n){ // O(1)
return (1 + n)*n / 2;// 1 步
}
// 空间复杂度 反转一个字符串 aaa222bbb -> bbb222aaa
char* reverse1(char str[], int n){ // O(n)
// 第一种写法
// 创建一个新的数组
char* res = (char*)malloc(sizeof(char)*n);// 1 空间 O(n)
// 倒序循环
for (int i = n; i >= 0; i--) // n
{
// 赋值
// res[n - i] =
}
return res;// 1
}
void reverse2(char str[], int n){// 空间的复杂度是 O(1) 时间的复杂度 O(n)
int mid = n / 2;
for (int i = 0; i < mid; i++)
{
// i 的位置和 i+mid 的位置进行交换
// 交换 1 次交换是两次赋值
}
}
void main(){
// int sum = sum2(100);
// cout << "sum = " << sum << endl;
int n = (int)'b';// a 97
// 'z' 122
cout << n << endl;
getchar();
}
// 读一篇因为文档统计字符出现的个数
void main(){
// 一个字符一个字符的读过来
char* str = "zxcvbnmsdfghjklertyuiop tyuiocvbnm";
// 开辟一块内存大小数组,用空间换时间，里面默认值都是0
int aisc[123] = {0};
// 当我读到一个字符 ， 'a' ， 'b '
int index = (int)'d';
aisc[index]++;
// 最后一个for循环输出 ，变种 2000 个数字（1，2000），统计数字出现的次数。
getchar();
}
*/
// 数组与链表源码分析
// C++基础 - 实现 Native 层的 ArrayList
网友评论