如何在家里做网站广州牌手表网站

当前位置： 首页 > news >正文

如何在家里做网站,广州牌手表网站,开发一个app需要多长时间,wordpress 主题域名授权一、数据结构 1、线性结构 数组#xff1a; 访问#xff1a;O(1)访问特定位置的元素#xff1b;插入#xff1a;O(n)最坏的情况发生在插入发生在数组的首部并需要移动所有元素时#xff1b;删除#xff1a;O(n)最坏的情况发生在删除数组的开头发生并需要移动第一元素后…一、数据结构 1、线性结构 数组 访问O(1)访问特定位置的元素插入O(n)最坏的情况发生在插入发生在数组的首部并需要移动所有元素时删除O(n)最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时链表使用的不是连续的内存空间来存储数据。 链表的插入和删除操作的复杂度为 O(1) 只需要知道目标位置元素的上一个元素即可。但是在查找一个节点或者访问特定位置的节点的时候复杂度为 O(n) 。数组链表比较 数组支持随机访问而链表不支持。数组使用的是连续内存空间对 CPU 的缓存机制友好链表则相反。数组的大小固定而链表则天然支持动态扩容。如果声明的数组过小需要另外申请一个更大的内存空间存放数组元素然后将原数组拷贝进去这个操作是比较耗时的栈 允许在有序的线性数据集合的一端称为栈顶 top进行加入数据push和移除数据pop后进先出LIFO, Last In First Outpush 和 pop 的操作都发生在栈顶。队列 先进先出 (FIFOFirst In, First Out) 的线性表。通常用链表或者数组来实现用数组实现的队列叫作 顺序队列 用链表实现的队列叫作 链式队列 。队列只允许在后端rear进行插入操作也就是入队 enqueue在前端front进行删除操作也就是出队 dequeue 2、图 概念 顶点图中的数据元素图至少有一个顶点非空有穷集合边顶点之间的关系用边表示度表示一个顶点包含多少条边在有向图中还分为出度和入度出度表示从该顶点出去的边的条数入度表示进入该顶点的边的条数。无向图、有向图边表示的是顶点之间的关系有的关系是双向的有的是单向的无权图、带权图边是否具有权重图的存储 邻接矩阵存储邻接矩阵将图用二维矩阵存储是一种较为直观的表示方式。如果第 i 个顶点和第 j 个顶点之间有关系且关系权值为 n则 A[i][j]n 。在无向图中当顶点 i 和顶点 j 有关系时A[i][j]1无关系时A[i][j]0。比较浪费空间 无向图的邻接矩阵是一个对称矩阵因为在无向图中顶点 i 和顶点 j 有关系则顶点 j 和顶点 i 必有关系。邻接表存储使用一个链表来存储某个顶点的所有后继相邻顶点。对于图中每个顶点 Vi把所有邻接于 Vi 的顶点 Vj 链成一个单链表这个单链表称为顶点 Vi 的 邻接表。 在无向图中邻接表元素个数等于边的条数的两倍在有向图中邻接表元素个数等于边的条数图的搜索BFS、DFS 3、堆 定义堆是一种满足以下条件的树堆中的每一个节点值都大于等于或小于等于子树中所有节点的值。或者说任意一个节点的值都大于等于或小于等于所有子节点的值。可以看成是近似的完全二叉树用途当我们只关心所有数据中的最大值或者最小值存在多次获取最大值或者最小值多次插入或删除数据时就可以使用堆。时间复杂度插入和删除操作O(lgn)堆初始化时间复杂度O(n)分类大根堆、小根堆存储由于完全二叉树的性质利用数组存储二叉树即节省空间又方便索引若根结点的序号为0那么对于树中任意节点 i其左子节点序号为 2*i 1右子节点序号为 2*i2堆的操作大根堆 插入先将元素放至数组末尾再自底向上堆化将末尾元素上浮 删除堆顶删除堆顶元素将末尾元素放至堆顶再自顶向下堆化将堆顶元素下沉 堆排序 第一步是建堆将一个无序的数组建立为一个堆 最后一个节点的父结点及它之前的元素都是非叶节点。即节点个数为 n只需对 (n - 1) / 2 到 0 的节点进行自顶向下沉底堆化顺序是从后往前堆化 第二步是排序将堆顶元素与最后位置元素交换然后对剩下元素进行堆化反复迭代 堆以及堆排序 class Solution {public int[] sortArray(int[] nums) { //若根结点的序号为0那么对于树中任意节点 i其左子节点序号为 2*i 1右子节点序号为 2*i2 //初始堆化从(n - 1)/2 到0自顶向下堆化heapify(nums); //将堆顶元素与最后位置元素交换然后对0位置进行堆化反复迭代for (int j nums.length - 1; j 0; j–) {swap(j, 0, nums);siftDown(0, j, nums);}return nums;}private void heapify(int[] nums) {for (int i (nums.length 1) - 1; i 0; i–) {siftDown(i, nums.length, nums);}}//大根堆private void siftDown(int index, int len, int[] nums) {int half len 1;while (index half) {int child (index 1) 1;//左移运算符优先级低于加号int right 1 child;//获取左右节点中较大的子节点if (right len nums[child] nums[right]) {child right;}if (nums[index] nums[child]) {break;}//跟较大的子节点交换swap(index, child, nums);index child;}}private void siftUp(int index, int[] nums) {while (index 0) {int father (index - 1) 1;if (nums[father] nums[index]) {break;}swap(father, index, nums);index father;}}private void swap(int a, int b, int[] nums) {nums[a] ^ nums[b];nums[b] ^ nums[a];nums[a] ^ nums[b];}}
4、树 定义二叉树分类 满二叉树每一个层的结点数都达到最大值。或者如果一个二叉树的层数为 K且结点总数是(2^k) -1 则它就是 满二叉树 完全二叉树最后一层外若其余层都是满的并且最后一层是满的或者是在右边缺少连续若干节点。当根节点的值为 1 的情况下若父结点的序号是 i那么左子节点的序号就是 2i右子节点的序号是 2i1。 平衡二叉树可以是一棵空树如果不是空树它的左右两个子树的高度差的绝对值不超过 1并且左右两个子树都是一棵平衡二叉树。红黑树、AVL数存储 链式存储 数组存储顺序存储就是利用数组进行存储数组中的每一个位置仅存储节点的 data不存储左右子节点的指针子节点的索引通过数组下标完成。根结点的序号为 0对于每个节点 Node假设它存储在数组中下标为 i 的位置那么它的左子节点就存储在 2i 1 的位置它的右子节点存储在下标为 2i2 的位置。 如果存储的二叉树不是完全二叉树在数组中就会出现空隙导致内存利用率降低遍历 层序遍历bfs先序遍历 中序遍历 后序遍历 morris遍历 5、红黑树 二、算法 1、算法思想 贪心局部最优–全局最优动态规划动态规划中每一个状态一定是由上一个状态推导出来 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序回溯-穷举 回溯函数返回值以及参数回溯函数终止条件回溯函数终止条件分治 将一个规模为 N 的问题分解为 K 个规模较小的子问题这些子问题相互独立且与原问题性质相同。求出子问题的解就可得到原问题的解。 2、常见数据结构算法题目 3、字符串算法 4、常见链表算法 5、十大经典排序 6、经典剑指offer题目