单链表-数组模拟版
数组模拟单链表由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。
单链表的特点:
单链表不要求逻辑上相邻的两个元素在物理位置上也相邻,因此不需要连续的存储空间。
单链表是非随机的存储结构,即不能直接找到表中某个特定的结点。查找某个特定的结点时,需要从表头开始遍历,依次查找。 对于每个链表结点,除了存放元素自身的信息外,还需要存放一个指向其后继的指针。
单链表中结点类型的描述:
1234typedef struct LNode{ //定义单链表结点类型 int data; //数据域,可以是别的各种数据类型,本文统一用int类型 struct LNode *next; //指针域}LNode, *LinkList;
但采用上述方法申请新结点,需要用到new Node()函数,这样会浪费大量时间,特别是在曹祖数特别大的情况下,这样,用数组模拟链表可以省去大量时间,且可以完成链表存在的 ...
快速排序quick_sort
快速排序快速排序是一种原地排序,只需要一个很小的栈作为辅助空间,空间复杂度为O(logN),所以适合在数据集比较大且无序的时候使用。实现方法有经典快排和双指针快排,本文介绍的是双指针快排的实现。
快排算法复杂度
空间复杂度
时间复杂度(最好)
时间复杂度(最差)
时间复杂度(平均)
O(logN)
O(N)
O(N^2)
O(NlogN)
基本思想随机找出一个数,可以随机取,也可以取固定位置,一般是取第一个或最后一个称为基准,然后就是比基准小的放在左边,比基准大的放到右边。
实现方法一种是在每次递归时利用两个数组存取基准pivot前后的数据,这种空间复杂度较高。
另外一种是利用双指针的思想:利用left和right指针,首先left从前向后遍历,碰到大于pivot的数则停止;right从后向前遍历,碰到小于pivot的数则停止,随后交换left和right处的数据,直到left>=right。代码如下:
12345678910111213141516171819202122232425262728#include<iostream>using names ...
决策树DT
决策树思想:分而治之,即在每个节点寻找最优的划分属性
表1 下午3点通知家长名单
学生姓名
性别
语文作业是否完成
周记是否完成
张三
M
Yes
No
李四
F
No
Yes
王五
M
No
No
石子合并
石子合并石子合并是一类动态规划问题,其中石子合并代价的解释为两堆石子的数量和。分为如下典型的三类:
不加限制的合并即为每次任意合并两堆,输出为最小花费。贪心策略每次找出最小的两个元素即可(n-1轮):
1234567n=int(input())w=list(map(int, input().split()))for i in range(n-1): label_min=min(w) w.remove(label_min) w[w.index(min(w))]+=label_minprint(w[0])
线性(相邻)合并即为每次合并相邻两堆,输出为最小花费。动态规划,具体思路为:
确定状态:设dp[i][j]表示合并第i到j个石子的最小代价。
确定状态转移方程:对于第i到第j个石子的合并,可以选择在任意一个位置k断开,将问题分成合并i到k之间的石子和合并k+1到j之间的石子两个子问题。因此,可以得到状态转移方程:dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j]-sum[i-1]) (i<& ...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick StartCreate a new post1$ hexo new "My New Post"
More info: Writing
Run server1$ hexo server
More info: Server
Generate static files1$ hexo generate
More info: Generating
Deploy to remote sites1$ hexo deploy
More info: Deployment