1. 概念#
数据结构与算法是计算机科学的重要基础知识。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它涉及数据的存储、组织和管理。常见的数据结构包括数组、链表、栈、队列、树、图等。
算法是完成特定任务的步骤或指令的序列。它本质上是对数据操作的一种描述。算法主要包含输入、输出以及转换输入为输出的步骤。
数据结构与算法之间有着密不可分的关系。算法的设计取决于所选的数据结构，不同的数据结构适用于不同的算法。而数据结构的组织方式直接影响算法的效率。
掌握数据结构与算法对开发高质量程序非常重要。它们是评估开发人员技术能力的重要标准。数据结构与算法知识也是面试中的常见考点。许多编程语言都需要实现和使用各种数据结构与算法。
所以数据结构与算法是每个程序员必备的基础知识，需要通过大量的学习、练习和使用才能真正掌握。它们是开发人员必须重点提高的核心竞争力之一。
数据结构构成#
1. 栈结构
2. 队列
3. 数组
4. 链表
5. 树
6. 图
7. 堆结构
1.1 栈结构的实现#
实现方法：基于数组和基于链表，由于 ts/js 中不存在链表，需要重新实现。
interface IStack<T>{
push():void;
pop():void;
size():number
peek():T
isEmpty():bollean
}
class Stack<T=any> immplements IStack{
private arr:T[]=[]
push(element:T):void{
this.arr.push(element)
}
pop():void{
this.arr.pop()
}
size():number{
return this.arr.length();
}
peek():T|undefined{
return this.arr.pop()
}
isEmpty():bollean{
return this.arr.length===0?true:false
}
}
面试题 1. 实现一个十进制转二进制的函数#
function toBinary(count:number):string{
let stack =new Stack()
let binary=""
while(count>0){
stack.push(count%2)
count= Math.floor((count/2))
}
while(!stack.isEmpty()){
binary+=stack.pop()
}
return binary;
}
面试题 2. 实现字符 “（”，“{”，“[” 与 "}","]",#
")" 对称
例如： valid ("(){}[]") true
valid("({[]})") true
valid("{()]}") false
function valid(str:string):boolean{
const stack=new Stack()
for(let i=0;i<str.length;i++){
switch(str[i]){
case "(":
stack.push(")")
break;
case "{":
stack.push("}")
break;
case "[";
stack.push("]")
break;
default:
if(str[i]!==stack.pop()) return false
}
}
return stack.isEmpty()
}
击鼓传花#
1. 一群人围着圈，开始数，当停止时，数数该人被淘汰，并得出最后一个胜利者的初始位置。
思路：根据队列依次出栈，若不为叫到人，则再进栈。#
function findLast(arr:string[],loop:number){
if (arr.length === 0) return -1;
const queue=new Queue()
for(let i=0;i<arr.length;i++){
queue.enqueue(arr[i])
}
while(queue.size()>1){
for(let i=1;i<loop;i++){
const name=queue.dequeue()
queue.enqueue(name)
}
queue.dequeue()
}
return queue.dequeue()
}
链表结构#
概念：和数组一样是线性结构可用于存储一系列元素，但列表和数组的实现机制完全不同，在什么场景下用到数组或链表，取决于应用场景的操作。
数组：在空间内分配一块固定大小的连续空间用于存贮数据，但当在数组前、中插入元素时，所有的之后的元素都要向后移动响应的内存地址，如果数组元素特别多的情况下，开销会很大。
链表：链表不需要在创建时就确定大小，根据 head 指针指向链表中 next 的元素，head=>next=>next2=>next3=>next4
当设计到大量删除、插入操作时，只需要改变 next 的指针指向即可，时间复杂度为 O (1) ，但他的缺点很明显，数组通过索引即可寻址，但链表需要走头开始。
链表的实现#
class Node<T=any>{
value:T;
next:Node<T>|null
constructor(value:T){
this.value=value
}
}
class LinkList<T>{
head:T|null=null;
size:number=0;
get length():number{
return this.size
}
add(element):void{
const newNode=new Node<T>(element)
if(!this.head){
this.head=newNode
}else{
let current=this.head
while(current.next){
current=current.next
}
current.next=newNode
}
this.size++
}
traverse(){
let values:T[]=[]
let current=this.head
while(current){
values.push(current.value)
current=current.next
}
console.log(values.join("->"))
}
insert(elememt:T,position:number):boolean{
if(position<0||position>this.size) return false
const value=new Node(element)
if(position===0){
value.next=this.head
this.head=value
}else{
let prev:Node<T>|null=null
let current=this.head
let index=0
while(index++<position){
prev= current;
current=current.next
}
prev.next=value
value.next=current
}
this.size++
return true
}
//删除某个位置节点
removeAt(position:number):T|null{
if(position<0||position>=this.size)
return null
if(position===0){
this.head=this.head.next
}else{
let prev:Node<T>|null=null
let current =this.head
let index=0
while(index++<position){
prev=current
current=current.next
}
prev.next=current?.next ?? null
}
this.size--;
return null;
}
//获取某个位置的节点
get(position:number):T|null{
if(position>size||position<0) return null
let current=this.head
let index=0
while(index++<position){
current=current.next ?? null
}
return current.value??null
}
//更新某个节点的元素
update(element:T,position:number):boolean{
if(position>=size||position<0) return false
let current=this.head
let index=0
while(index++<position&¤t){
current=current.next
}
current.value=element
return true;
}
//根据元素寻找下标
indexOf(element:T){
let current=this.head
let index=0;
while(current){
if(current.value===element){
return index;
}
current=current.next
index++
}
return -1;
}
remove(element: T): T | null {
const first = this.indexOf(element);
//方法一：
// if (first > 0) {
// let prev: Node<T> | null = null;
// let current = this.head;
// let index = 0;
// while (index++ < first && current) {
// prev = current;
// current = current.next;
// }
// prev!.next = current!.next ?? null;
// return true;
// } else {
// return false;
// }
return this.removeAt(first);
}
isEmpty(): boolean {
return this.size === 0 ? true : false;
}
}
面试题反转链表 （栈结构实现）#
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
function reverseList(head: ListNode | null): ListNode | null {
if (head === null) return null;
//只有一个节点
if (!head.next) return head;
//使用栈结构
let stack: ListNode[] = [];
while (head) {
stack.push(head);
head = head.next;
}
const newhead: ListNode = stack.pop()!;
let newheadCurrent = newhead;
while (stack.length) {
const node = stack.pop();
newheadCurrent.next = node!;
newheadCurrent = newheadCurrent!.next;
}
newheadCurrent.next = null; //因为最后一个元素指向null，而不是前一个，否则会循环引用
return newhead;
}
export {};
反转链表（非递归实现）#
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
function reverseList(head: ListNode | null): ListNode | null {
if(head===null ||!head.next) return head
let newHead:ListNode|null=null
while(head){
let current:ListNode |null=head.next
//让第一个节点指向null，
head.next=newHead
//向后推进，依次类推
newHead=head
head=current
}
return newHead;
}
反转链表（递归）#
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}
function reverseList(head: ListNode | null): ListNode | null {
if(head===null || head.next===null) return head
const newhead=reverseList(head.next??null)
head.next.next=head
head.next=null
return newhead
}
哈希表#
哈希表是基于数组实现的，但是区别于数组有许多优势：
优点#
1. 提供非常快速的查找、删除、插入操作
2. 无论多少数据，插入、删除的时间都接近常量 O (1)，实际上只需要几行机械指令即可。
3. 哈希表的速度比树还要快，基本可以瞬间查到目标元素。
4. 哈希表比树结构更容易编写。
缺点#
1. 哈希表的数据结构是无序的，所以没有一种固定的方式来遍历元素。
2. 通常情况下，哈希表的 key 不能重复，不能放置相同的 key, 用于保存不同的元素。
本质#
它的结构就是数组结构，但是它的神奇之处在于数组下标值的变换，这种变换我们可以使用哈希函数，通过哈希函数获取 hashCode。
比如存贮 50000 本图书信息，数组：复杂度 o (n)，顺序查找下标值索引，当然，可以利用二分将复杂度降到 O (logn)，但是利用哈希函数，可以提前将每一项图书的每一项获取到对应的下标即索引值，这个函数规则可以由我们自己来制定，
比如 每本书对应存贮字符串 "abc"，按照 ascii 编码得到一个规则 下标 = 97+98+99,=== 该数组的下标值。
显而易见，这种存储方式的重复率极高，因此方案 b 可以解决这个问题 幂的连乘
比如 “abc"=271^3+272^3......
但是这样做，还有弊端，虽然保持了唯一性，但是极其浪费数组空间，比如 “zzzzzzzzzzzzzzzzzzz”, 需要分配天文数字的存贮空间，这是不科学的。
因此 链地址法和 开放地址法
- 对关键字 key 计算哈希函数，获得散列地址。
- 查看该散列地址，如果为空，则直接插入。
- 如果不为空，则检查该地址上的链表中是否存在相同 key 的元素。
- 如果存在，则修改内容。如果不存在，则在该链表头部插入一个新的元素。
- 插入新元素时，需要创建结点，并将新结点插入链表头部。
- 查找元素时，需要遍历链表，逐一比对关键字。
链地址法解决了冲突，但查找效率较低，需要遍历链表。平均查找长度约为 O (1+α),α 是链表长度。