第一章: 邂逅数据结构与算法

第一章: 邂逅数据结构与算法

编程的真相 – 数据的处理

数据结构与算法的本质

学习数据结构与算法到底有什么实际应用？

源码中的数据结构

如何学习数据结构与算法？

TypeScript常见数据结构与算法

到底什么是数据结构

什么是数据结构（Data Structure）

如何摆放图书？

常见的数据结构

什么是算法？

生活中的数据结构与算法

第一章：线性结构 – 数组

MDN

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

线性结构（Linear List）

数组（Array）结构

第一章：栈结构（Stack）

画图解决问题：合法出栈顺序–入栈随意，只要满足后进先出（先进后出）的规则即可

认识栈结构

栈结构面试题

栈结构的实现

创建栈的类

栈的操作

ts代码的运行环境

1.浏览器–需要通过webpack等环境才能运行

2.node–需要同个ts-node库 运行代码

安装库 npm install ts-node

pm install ts-node

ts-node -v

ts-node 文件名

注意点
默认ts代码在同一个作用域下，所以如果定义的类名重复的话，可以通过export {} ，将我们每个ts文件变成单独的模块
export {}

01_实现栈结构Stack.ts

// 封装一个栈
class ArrayStack {
  // 定义一个数组/链表, 用于存储元素
  // private私有变量
  private data: any[] = []

  // 实现栈中相关的操作方法
  // push方法: 将一个元素压入到栈中
  push(element: any): void {
    this.data.push(element)
  }

  // pop方法: 将栈顶的元素弹出栈(返回出去, 并且从栈顶移除掉)
  pop(): any {
    return this.data.pop()
  }

  // peek方法: 看一眼--查看栈顶元素, 但是不进行任何的操作
  peek(): any {
    return this.data[this.data.length - 1]
  }

  // isEmpty: 判断栈是否为空
  isEmpty(): boolean {
    return this.data.length === 0
  }

  // 返回栈的数据个数
  size(): number {
    return this.data.length
  }
}


// 创建Stack的实例
const stack1 = new ArrayStack()
stack1.push("aaa")
stack1.push("bbb")
stack1.push("ccc")

console.log(stack1.peek())
console.log(stack1.pop())
console.log(stack1.pop())
console.log(stack1.pop())

console.log(stack1.isEmpty())
console.log(stack1.size())

export {}

02_实现栈结构Stack(重构)

import IStack from "./IStack";

// 封装一个栈: TypeScript => AnyScript  ArrayStack< T=any > 泛型默认值
//  ArrayStack<T> 泛型 调用的时候传入泛型类型 例如 const stack1 = new ArrayStack<string>()
class ArrayStack<T> implements IStack<T> {
  // 定义一个数组/链表, 用于存储元素
  private data: T[] = [];

  // 实现栈中相关的操作方法
  // push方法: 将一个元素压入到栈中
  push(element: T): void {
    this.data.push(element);
  }

  // pop方法: 将栈顶的元素弹出栈(返回出去, 并且从栈顶移除掉)
  pop(): T | undefined {
    return this.data.pop();
  }

  // peek方法: 看一眼栈顶元素, 但是不进行任何的操作
  // T | undefined联合类型 如果没有数据栈是pop()不出任何东西值,返回值为undefined类型
  peek(): T | undefined {
    return this.data[this.data.length - 1];
  }

  // isEmpty: 判断栈是否为空
  isEmpty(): boolean {
    return this.data.length === 0;
  }

  // 返回栈的数据个数
  size(): number {
    return this.data.length;
  }
}

export default ArrayStack;

03_实现栈结构Stack(链表)

import IStack from './IStack'

class LinkedStack<T> implements IStack<T> {
  // 创建一个链表结构

  push(element: T): void {
    throw new Error('Method not implemented.')
  }
  pop(): T | undefined {
    throw new Error('Method not implemented.')
  }
  peek(): T | undefined {
    throw new Error('Method not implemented.')
  }
  isEmpty(): boolean {
    throw new Error('Method not implemented.')
  }
  size(): number {
    throw new Error('Method not implemented.')
  }
}

export {}

IStack接口的封装

import IList from "../types/IList"

// 定义栈的接口
interface IStack<T> extends IList<T> {
  push(element: T): void
  pop(): T | undefined
  // peek(): T | undefined
  // isEmpty(): boolean
  // size(): number
}

export default IStack

types-》 IList.ts
export default interface IList<T> {
  // peek
  peek(): T | undefined
  // 判断是否为空
  isEmpty(): boolean
  // 元素的个数
  size(): number
}

十进制转二进制（面试题）

前提知识：

接口

相当于一个约束，让对象遵循约束，保持一致

泛型(Generics)：

泛型是指在定义函数、接口或者类的时候。不预先指定具体的类型，而在使用的时候在指定类型的一种特性

泛型变量T T表示任何类型

// 泛型(Generics)：是指在定义函数、接口或者类的时候。不预先指定具体的类型，而在使用的时候在指定类型的一种特性

// 泛型变量T    T表示任何类型
// 基础写法
function f4(x: number, y: number): number[] {
  return [x, y];
}

f4(10, 20);

function f5(x: string, y: string): string[] {
  return [x, y];
}

f5("1111", "111");

function f6(x: boolean, y: boolean): boolean[] {
  return [x, y];
}

f6(true, false);

// 泛型写法 泛型最关键是写在定义函数后参数前的位置，调用函数后传入参数前的位置
function f7<T>(x: T, y: T): T[] {
  return [x, y];
}
f7<number>(10, 20);
f7<string>("1111", "111");
f7<boolean>(true, false);

function f8(x: string): number {
  return x.length;
}

f8("forever fsf");
//   报错 ，T是  T表示任何类型 但是并不是任何类型都有length属性，所以我们需要要泛型约束
function f9<T>(x: T): number {
  return x.length;
}

f9<string>("forever fsf");

//   泛型约束 extends
interface LengthNum {
    // 泛型约束 ,类型必须有length属性
  length: number;
}
// 这里的T任意类型就受到了LengthNum的泛型约束--传入的类型中必须有length属性
function f10<T extends LengthNum>(x: T): number {
    return x.length;
}
f10<string>("forever fsf");
// 报错 类型“number”不满足约束“LengthNum”。
f10<number>("forever fsf");

泛型接口

// 泛型接口
// 定义函数,判断传入的参数是否相同
// js写法
// let fn1 = function (s1, s2) {
//   return s1 == s2;
// };
// fn1("a", "b");
// ts基本写法
let fn2 = function (s1: string, s2: string): boolean {
  return s1 == s2;
};
fn2("a", "b");

// 另一个实例函数
// js写法
// let fn3 = function (x, y) {
//   if (x > y) {
//     return true;
//   } else {
//     return false;
//   }
// };
// fn3("a", "b");
// ts基本写法
let fn4 = function (x: string, y: string): boolean {
  if (x > y) {
    return true;
  } else {
    return false;
  }
};
fn4("x", "y");

// ts定义接口写法
// 定义规范 共同的部分提取出来，定义规范，变成接口
// interface InspectFn {
//   (x: string, y: string): boolean;
// }

// let fn1: InspectFn = function (s1, s2) {
//   return s1 == s2;
// };

// fn1("x", "y");
// 定义规范 共同的部分提取出来，定义规范，变成接口
// let fn3: InspectFn = function (x, y) {
//   if (x > y) {
//     return true;
//   } else {
//     return false;
//   }
// };

// 下一步，对我们的接口类型添加泛型
// 先阶段意思表示 只要是传入两个参数，返回值是boolean类型的，都可以收到这个接口的约束
interface InspectFn {
  <T>(x: T, y: T): boolean;
}
let fn1: InspectFn = function (s1, s2) {
  return s1 == s2;
};

fn1<string>("x", "y");

let fn3: InspectFn = function (x, y) {
  if (x > y) {
    return true;
  } else {
    return false;
  }
};
fn3<number>(10, 5);

要把十进制转化成二进制，我们可以将该十进制数字和2整除（二进制是满二进一），直到结果是0为止。

计算出来的余数：后放进来的余数，在组成二进制的时候是放在高位的

04_面试题一-十进制转二进制

console.log(stack.pop()); 打印的时候 调用方法的时候，里面的变量或者值也会改变值

import ArrayStack from "./02_实现栈结构Stack(重构)"

function decimalToBinary(decimal: number): string {
  // 1.创建一个栈, 用于存放余数
  const stack = new ArrayStack<number>()

  // 2.使用循环: 
  // while: 不确定次数, 只知道循环结束跳转 
  // for: 知道循环的次数时
  while (decimal > 0) {
    const result = decimal % 2
    stack.push(result)

    decimal = Math.floor(decimal / 2)
  }ts

  // 3.所有的余数都已经放在stack中, 以此取出即可
  let binary = ''
  while (!stack.isEmpty()) {
    binary += stack.pop()
  }

  return binary
}


console.log(decimalToBinary(35))
console.log('------')
console.log(decimalToBinary(100))

export {}

有效的括号 – 字节、华为等面试题

https://leetcode.cn/problems/valid-parentheses/description/

if语句的写法

import ArrayStack from "./02_实现栈结构Stack(重构)";
// 成对出现，一一对应
function isValid(s: string): boolean {
  // 1.创建栈结构
  const stack: string[] = [];

  // 2.遍历s中的所有的括号
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c === "(") {
      stack.push(")");
    } else if (c === "{") {
      stack.push("}");
    } else if (c === "[") {
      stack.push("]");
    } else {
      if (c !== stack.pop()) return false;
    }
  }

  return stack.length === 0;
}

console.log(isValid("()"));
console.log(isValid("([)]){}"));
console.log(isValid("(]"));

export {};

switch语句写法

import ArrayStack from './02_实现栈结构Stack(重构)'
// 成对出现，一一对应
function isValid(s: string): boolean {
  // 1.创建栈结构
  const stack: string[] = []

  // 2.遍历s中的所有的括号
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    switch (c) {
      case "(":
        stack.push(")")
        break
      case "{":
        stack.push("}")
        break
      case "[":
        stack.push("]")
        break
      default:
        if (c !== stack.pop()) return false
        break
    }
  }

  return stack.length === 0
}

console.log(isValid("()"))
console.log(isValid("([]){}"))
console.log(isValid("(]"))

export {}

第一章：内容回顾

注意点：不管在哪里调用方法都会执行，不论是全局调用，局部调用，console.log打印调用，甚至是if等条件语句中调用都会执行

到底什么是线性结构

十进制转二进制的计算过程

有效括号的解题思路

一. 邂逅数据结构与算法

1.1. 编程尽头、数据结构

1.2. 实际的应用场景

• 源码： Vue/React/Webpack/Java…
• 大厂面试

1.3. 如何学习数据结构与算法

• 优质的文章
• 看书: 算法
• LeetCode
• 视频课程

二. 线性结构 - 数组

2.1. 什么线性结构

2.2. 数组 - 连续的内存

三. 栈结构 - Stack

3.1. 栈结构的认识和特性

• 先进后出
• 后进先出

3.2. 栈结构的特性 - 笔试题

3.3. 栈结构的封装和实现

3.4. 栈结构的代码重构

• 泛型
• 接口设计

3.5. 面试题一 - 十进制转二进制

3.6. 面试题二 - 有效的括号