广州市官网网站建设怎么样js弹出网站

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

广州市官网网站建设怎么样,js弹出网站,js 曲线 网站,宁波seo网络推广软件系统队列 队列#xff08;Queue#xff09;#xff0c;它是一种受限的线性表#xff0c;先进先出#xff08;FIFO First In First Out#xff09; 受限之处在于它只允许在队列的前端#xff08;front#xff09;进行删除操作而在队列的后端#xff08;rear#xff09;进…队列 队列Queue它是一种受限的线性表先进先出FIFO First In First Out 受限之处在于它只允许在队列的前端front进行删除操作而在队列的后端rear进行插入操作 队列 有五份文档需要打印这些文档会按照次序放入到打印队列中打印机会依次从队列中取出文档优先放入的文档优先被取出并且对该文档进行打印以此类推直到队列中不再有新的文档 线程队列: 在开发中为了让任务可以并行处理通常会开启多个线程但是我们不能让大量的线程同时运行处理任务。占用过多的资源这个时候如果有需要开启线程处理任务的情况我们就会使用线程队列线程队列会依照次序来启动线程并且处理对应的任务 当然队列还有很多其他应用我们后续的很多算法中也会用到队列比如二叉树的层序遍历 队列操作 enqueue(element)向队列尾部添加一个或多个新的项dequeue()移除队列的第一即排在队列最前面的项并返回被移除的元素front/peek()返回队列中第一个元素————最先被添加也将是最先被移除的元素。队列不做任何变动 不移除元素只返回元素信息一一与 Stack 类的 peek 方法非常类似isEmpty()如果队列中不包含任何元素返回 true否则返回 falsesize()返回队列包含的元素个数与数组的 length 属性类似 实现队列 队列的实现和栈一样有两种方案 基于 数组 实现基于 链表 实现 import IQueue from ./IQueueclass ArrayQueueT implements IQueueT {// 内部是通过数组保存private data: T[] []enqueue(element: T): void {this.data.push(element)}dequeue(): T | undefined {return this.data.shift()}peek(): T | undefined {return this.data[0]}isEmpty(): boolean {return this.data.length 0}size(): number {return this.data.length} }export default ArrayQueue泛型 interface IListT {peek(): T | undefinedisEmpty(): booleansize(): number } interface IQueueT extends IListT {enqueue(element: T): voiddequeue(): T | undefined }击鼓传花 原游戏规则 班级中玩一个游戏所有学生围成一圈从某位同学手里开始向旁边的同学传一束花这个时候某个人比如班长在击鼓鼓声停下的一颗花落在谁手里谁就出来表演节目 修改游戏规则 我们来修改一下这个游戏规则几个朋友一起玩一个游戏围成一圈开始数数数到某个数字的人自动淘汰最后剩下的这个人会获得胜利请问最后剩下的是原来在哪一个位置上的人 封装一个基于队列的函数 参数所有参与人的姓名基于的数字口结果最终剩下的一人的姓名 function hotPotato(names: string[], num: number) {if (names.length 0) return -1// 1.创建队列结构const queue new ArrayQueuestring()// 2.将所有的name入队操作for (const name of names) {queue.enqueue(name)}// 3.淘汰规则while (queue.size() 1) {for (let i 1; i num; i) {const name queue.dequeue()if (name) queue.enqueue(name)}queue.dequeue()}return queue.dequeue() }约瑟夫环问题 阿桥问题有时也称为约瑟夫斯置换是一个出现在计算机科学和数学中的问题。在计算机编程的算法中类似问题又称为约瑟夫环 人们站在一个等待被处决的圈子里计数从圆圈中的指定点开始并沿指定方向围绕圆圈进行在跳过指定数量的人之后处刑下一个人对剩下的人重复该过程从下一个人开始朝同一方向跳过相同数量的人直到只剩下一个人并被释放在给定数量的情况下站在第几个位置可以避免被处决? 这个问题是以弗拉维奥·约瑟夫命名的他是1世纪的一名犹太历史学家口 他在自己的日记中写道他和他的40个战友被罗马军队包围在洞中他们讨论是自杀还是被俘最终决定自杀并以抽签的方式决定谁杀掉谁 剑指 Offer 62. 圆圈中最后剩下的数字 0,1,···,n-1 这 n 个数字排成一个圆圈从数字 0 开始每次从这个圆圈里删除第 m 个数字删除后从下一个数字开始计数。求出这个圆圈里剩下的最后一个数字 例如0、1、2、3、4 这 5 个数字组成一个圆圈从数字 0 开始每次删除第 3 个数字则删除的前 4 个数字依次是 2、0、4、1因此最后剩下的数字是 3 import ArrayQueue from ./queuefunction lastRemaining(n: number, m: number) {// 1.创建队列const queue new ArrayQueuenumber()// 2.将所有的数字加入队列中for (let i 0; i n; i) {queue.enqueue(i)}// 3.判断队列中是否还有数字while (queue.size() 1) {for (let i 1; i m; i) {queue.enqueue(queue.dequeue()!)}queue.dequeue()}return queue.dequeue() }console.log(lastRemaining(5, 3)) // 3 console.log(lastRemaining(10, 17)) // 2动态规划 function lastRemaining(n: number, m: number) {let position 0for (let i 2; i n; i) {position (position m) % i}return position }链表 链表与数组 链表和数组一样可以用于存储一系列的元素但是链表和数组的实现机制完全不同 数组有很多缺点: 数组的创建通常需要申请一段 连续的内存空间一整块的内存并且大小是固定的大多数编程语言数组都是固定的所以当当前数组 不能满足容量需求 时需要 扩容。(一般情况下是申请一个更大的数组比如 2 倍。然后将原数组中的元素复制过去)而且在 数组开头或中间位置插入数据的成本很高需要 进行大量元素的位移尽管 JavaScript 的 Array 底层可以帮我们做这些事但背后的原理依然是这样 要存储多个元素另外一个选择就是链表 但不同于数组链表中的元素在内存中不必是连续的空间链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用有些语言称为指针或者链接组成 相对于数组链表有一些优点: 内存空间不是必须连续的 可以充分利用计算机的内存实现灵活的内存动态管理口 链表不必在创建时就 确定大小并且大小可以 无限的延伸 下去口链表在 插入和删除 数据时时间复杂度 可以达到 O(1) 相对数组效率高很多
相对于数组链表有一些缺点: 链表访问任何一个位置的元素时都需要 从头开始访问。(无法跳过第一个元素访问任何一个元素)无法通过下标直接访问元素需要从头一个个访问直到找到对应的元素 链表 什么是链表呢? 其实上面我们已经简单的提过了链表的结构我们这里更加详细的分析一下链表类似于火车有一个火车头火车头会连接一个节点节点上有乘客类似于数据并且这个节点会连接下一个节点以此类推 实现链表 封装一个 Node 类用于封装每一个节点上的信息 (包括值和指向下一个节点的引用)它是一个泛型类封装一个 LinkedList 类用于表示我们的链表结构。(和 Java 中的链表同名不同 Java 中的这个类是一个双向链表)链表中我们保存两个属性一个是链表的长度一个是链表中第一个节点 class NodeT {value: Tnext: NodeT | null nullconstructor(value: T) {this.value value} }class LinkedListT {private head: NodeT | null nullprivate size: number 0get length() {return this.size} }链表操作 append(element)向链表尾部添加一个新的项insert(positionelement)向链表的特定位置插入一个新的项get(position)获取对应位置的元素indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回 -1update(positionelement)修改某个位置的元素removeAt(position)从链表的特定位置移除一项remove(element)从链表中移除一项isEmpty()如果链表中不包含任何元素返回 true如果链表长度大于 0 则返回 falsesize()返回链表包含的元素个数。与数组的 length 属性类似 向链表尾部追加数据可能有两种情况 链表本身为空新添加的数据时唯一的节点链表不为空需要向其他节点后面追加节点 class NodeT {value: Tnext: NodeT | null nullconstructor(value: T) {this.value value} }class LinkedListT {private head: NodeT | null nullprivate size: number 0get length() {return this.size}// 根据position获取到当前的节点不是节点的value而是获取节点private getNode(position: number): NodeT | null {let index 0let current this.headwhile (index position current) {current current.next}return current}append(value: T) {// 1.根据value创建一个新及诶单const newNode new Node(value)// 2.判断this.heade是否为nullif (!this.head) {this.head newNode} else {let current this.headwhile (current.next) {current current.next}current.next newNode}this.size}traverse() {const values: T[] []let current this.headwhile (current) {values.push(current.value)current current.next}console.log(values.join(-))}insert(value: T, position: number): boolean {// 1.越界的判断if (position 0 || position this.size) return false// 2.根据value创建新的节点const newNode new Node(value)// 3.判断是否需要插入头部if (position 0) {// 新节点next指向头部节点、头部newNode.next this.headthis.head newNode} else {const previous this.getNode(position - 1)newNode.next previous?.next ?? nullprevious!.next newNode}this.sizereturn true}removeAt(position: number): T | null {// 1.越界的判断if (position 0 || position this.size) return null// 2.判断是否是删除第一个节点let current this.headif (position 0) {this.head current?.next ?? null} else {const previous this.getNode(position - 1)previous!.next previous?.next?.next ?? null}this.size–return current?.value ?? null}get(position: number): T | null {// 1.越界的判断if (position 0 || position this.size) return null// 2.查找元素并且返回元素return this.getNode(position)?.value ?? null}update(value: T, position: number): boolean {if (position 0 || position this.size) return falseconst currentNode this.getNode(position)// 获取对应位置的节点直接更新即可currentNode!.value valuereturn true}indexOf(value: T): number {let current this.headlet index 0while (current) {if (current.value value) {return index}current current.nextindex}return -1}remove(value: T): T | null {const index this.indexOf(value)return this.removeAt(index)}isEmpty() {return this.size 0} }设计链表 707. 设计链表 你可以选择使用单链表或者双链表设计并实现自己的链表 单链表中的节点应该具备两个属性val 和 next 。val 是当前节点的值next 是指向下一个节点的指针/引用 如果是双向链表则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始 实现 MyLinkedList 类 MyLinkedList() 初始化 MyLinkedList 对象int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效则返回 -1void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度那么该节点会被追加到链表的末尾。如果 index 比长度更大该节点将 不会插入 到链表中void deleteAtIndex(int index) 如果下标有效则删除链表中下标为 index 的节点 抽离接口方法 interface IListT {peek(): T | undefinedisEmpty(): booleansize(): number }interface ILinkedListT extends IListT {append(value: T): voidtraverse(): voidinsert(value: T, position: number): booleanget(position: number): T | nullupdate(value: T, position: number): booleanindexOf(value: T): numberremove(value: T): T | null }删除链表中的节点 237. 删除链表中的节点 有一个单链表的 head我们想删除它其中的一个节点 node 给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head 链表的所有值都是 唯一的并且保证给定的节点 node 不是链表中的最后一个节点 删除给定的节点。注意删除节点并不是指从内存中删除它。这里的意思是 给定节点的值不应该存在于链表中链表中的节点数应该减少 1node 前面的所有值顺序相同node 后面的所有值顺序相同 class ListNode {val: numbernext: ListNode | nullconstructor(val?: number, next?: ListNode | null) {this.val val undefined ? 0 : valthis.next next undefined ? null : next} }function deleteNode(node: ListNode | null): void {node!.val node!.next!.valnode!.next node!.next!.next }反转链表 206. 反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表 利用栈结构解决 function reverseList(head: ListNode | null): ListNode | null {if (head null) return nullif (head.next null) return headconst stack: ListNode[] []let current: ListNode | null headwhile (current) {stack.push(current)current current.next}let newHead: ListNode stack.pop()!let newHeadCurrent newHeadwhile (stack.length) {const node stack.pop()!newHeadCurrent.next nodenewHeadCurrent newHeadCurrent.next}// 注意获取到最后一个节点时一定要将节点的 next 置为 nullnewHeadCurrent.next nullreturn newHead }const node1 new ListNode(1) node1.next new ListNode(2) node1.next.next new ListNode(3) const newHead reverseList(node1) let current newHead while (current) {console.log(current.val)current current.next }非递归方式 让 current 指向下一个节点 目的保留着下一个节点的引用可以拿到并且不会销毁 改变 head 当前指向的节点指向 newHead 对于第一个节点来说指向 newHead 就是指向 null 让 newHead 指向 head 节点 目的是下一次遍历时第二步操作可以让下一个节点指向第一个节点 让 head 移向下一个节点指向 current
function reverseList(head: ListNode | null): ListNode | null {if (head null || head.next null) return headlet newHead: ListNode | null nullwhile (head) {let current: ListNode | null head.nexthead.next newHeadnewHead headhead current}return newHead }递归方式 第一次进入 const newHead 下面的代码是倒数第二个节点因为倒数第一个节点的 next 为 null function reverseList(head: ListNode | null): ListNode | null {if (head null || head.next null) return headconst newHead reverseList(head.next)head.next.next headhead.next nullreturn newHead }