未命名

发表于 2022-03-09

1.手写create

// 将传入的对象作为原型
function create(){
	function F(){};
    F.prototype = obj;
    return new F();
}

2.手写instanceof

// 首先获取实例的原型
// 获取对象的原型
// 一直循环判断实例的原型等于类对象的原型,  直到实例原型为null,  因为原型链最终为null

function myInstanceof(left, right){
    let proto = Object.getPrototypeOf(left),
    prototype = right.prototype;
    
    while(true){
        if(!proto) return false;
        if(proto === protoype) reutrn true;
        
        proto = Object.getPrototype(proto);
    }
}

3.手写new操作符

// 调用new
// 首先创建一个新的对象
// 设置obj.__proto__ = Fn.prototype
function myNew(Fn, ...args){
	let newObj = {};
    // 判断一个参数是否是一个函数
    newObj.__proto__ = Fn.prototype;
    let res = Fn.call(obj, ...args);
    if((res !== null) && (typeof res === 'object' || typeof res === 'function')) return res;
    return obj;
}

4 手写Promise

const PENDING = 'pending';
    const RESOLVE = 'resolve';
    const REJECT = 'rejected';
    function myPromise(fn){
      let self = this;
      
    }

5 手写Promise.then

6 手写promiseAll

function promiseAll(promises){
    // 判断是否是数组
	if(!Array.isArray(promises)){
        console.error('not a array');
        return;
    }
        
    let resCnt = 0;
    let len = promises.length;
    let resolveRes = [];
    for(let i = 0; i < len; i++){
        Promise.resolve(promises[i]).then(val => {
            resCnt++;
            resolveRes[i] = val;
            if(resCnt === len) return resolve(resolveRes);
        }, error => rejected(error))
    }
}

let p1 = new Promise(function (resolve, reject){
    setTimeout(function (){
        resolve(1);
    }, 1000);
})

let p2 = new Promise(function (resolve, reject) {
    setTimeout(function (){
        resolve(2);
    }, 2000);
})

let p3 = new Promise(function (resolve, reject){
    setTimeout(function(){
        resolve(3);
    }, 3000);
});
promiseAll([p3, p2, p1]).then(res => console.log(res));

7 手写race

Promise.race = function (args){
    return new Promise((resolve, reject) => {
        for(let i = 0; i < args.length; i++){
            Promise.resolve(args[i]).then(val => resolve(val), err => reject(err));
        }
    })
}

8 手写防抖

function debounce(fn, wait){
    let timer = null;
    // 返回要绑定的函数
    return function (){
        clearTimeout(timer);
        timer = setTimeout(()=> {
            fn.apply(this, arguments);
        }, wait);
    }
}

9 手写节流

function throttle(fn, delay){
    let pre = new Date();
    return function (){
		let cur = new Date();
        if(cur - pre >= delay){
            // 依旧要返回一个函数
            return fn.apply(this, arguments);
        }
    }
}

10 手写类型判断函数

function getType(val){
    // 判断数据是null
    if(val === null){
        return val + '';
    }
    if(typeof val === 'object'){
        let valClass = Object.prototype.toString().call(val);
        type = valClass.split(' ')[1].split('');
        type.pop();
        return type.join('').tolowerCase();
    }
    else{
        return typeof val;
    }
    
}

11. 手写 call 函数

Function.prototype.myCall = function (context){
    // this指向的是被call调用的函数
    // 不是函数就报错
    if(typeof this !== 'function') return new Error('type Error');
	// 获取args参数
    let args = [...arguments].slice(1);
    let res = null;
    // 判断context是否存在, 不存在就指向window
	context = context || window;
    // 定义一个函数转移到this上
    context.fn = this;
    // 返回函数的执行结果
    return context.fn(args);
}

12. 手写 apply 函数

Function.prototype.muApply = function (){
    // 判断调用对象是否为函数
    if(typeof this !== 'function') return new Error('type error');
    
    let res = null;
    context = context || window;
    if(arguments[1]){
        res = context.fn(...arguments[1]);
    }
    else {
        res = context.fn();
    }
    return res;
}

13 手写 bind 函数

Function.prototype.myBind = function (context){
    if(typeof this !== 'function') return new Error('type error');
    
    let args = Array.from(arguments);
    _this = args.shift();
    return () => {
        this.apply(_this, args);
    }
}

15 实现ajax

// 创建XMLHttpRequest对象
let xhr = new XMLHttpRequest();	// 创建 Http 请求
// 在open方法上创建一个http请求,  open方法所需要的参数是请求的方法,  请求的地址, 是否一异步,  用户认证的信息
xhr.open('GET', 'server_url', true)
//在发起请求前,  可以为对象添加一些信息和监听函数
//setRequestHeader方法添加头信息
xhr.onreadystatechange = function (){
    if(this.readyState !== 4) return;
    // 当请求成功时
    if(this.status === 200) handle(this.response);
    else {
        console.error(this.statusText);
    }
    
}
// 设置请求失败的监听函数
xhr.onerror = function(){
    console.error(this.statusText);
};
// 设置请求头信息
xhr.responseType = 'json';
xhr.setRequestHeader('Accept', 'application/json');
// 发送Http
xhr.send(null)

使用Promise封装AJAX请求

未命名

发表于 2022-03-08

this执行上下文

this不是在写函数时确定指向的, 它是在函数执行中才能确定上下文, this是执行上下文环境的一部分

var a = {
    name: 'A',
    fn: function (){
        console.log(this.name);
    }
}
a.fn()   // this === a
a.fn.call({name: 'B'}) // this === {name: 'B'}
var fn1 = a.fn;
fn1();  // this === window

0.1 + 0.2 === 0.3问题

function numberEpsilon(arg1, arg2){
    return Math.abs(arg1 - arg2) < Number.EPSILON;
}
console.log(numberEpsilon(0.1 + 0.2, 0.3)) // true

深拷贝

function deepCopy(obj){
      var res = Array.isArray(obj) ? [] : {};
      for(let key of obj){
        if(obj.hasOwnProperty(key)){
          if(typeof obj[key] === 'object'){
            res[key] = deepCopy(obj[key]);   //递归复制
          }
          else {
            res[key] = obj[key];
          }
        }
      }
      return result;
    }

浏览器缓存知识

浏览器第一次加载资源, 服务器返回200, 浏览器从服务器下载资源文件, 并缓存资源文件与response header, 以供下次加载对比使用

下一次加载资源, 由于强制缓存优先级高, 先比较上一次返回200的时间差, 如果没有超过cache-control设置的max-age, 则没有过期, 并命中强缓存, 从本地读取资源. 如果不支持http1.1 则用expires判断是否过期

如果资源已经过期, 则表明强制缓存没有被命中, 则开始协商缓存, 向服务器发送带有if-none-match和if-modified-since的请求

服务器收到请求后, 优先根据ETag的值判断被请求的文件有没有被修改, ETag值则一致则没有修改, 命中协商缓存返回304; 如果不一致则返回新资源带上新的ETag并返回200

未命名

发表于 2022-03-08

判断一个对象为空对象的几种方法

方法一:

将对象转换成字符串

1 2	let obj = {} console.log(JSON.stringfy(obj) === "{}")

方法二:

for in 循环

let res = function(obj){
    for(let key in obj){
        return false;
    }
    return ture;
}
console.log(obj);

方法三:

1	console.log(Object.keys(obj).length);

方法四:

1	console.log(Object.getOwnPropertyNames(obj).length === 0)

用reduce实现Map

Array.prototype._map = function (fn, thisArg){
        const result = [];
        this.reduce((prev, curr, index, array) => {
          result[index] = fn.call(thisArg, array[index], index, array);
        }, 0);
        return result;
      }

手写trim

String.prototype._trim = function (str){
        let i, j;
        for(i = 0; i < str.length; i++){
          if(str[i] !== ' ') break;
        }

        for(j = str.length - 1; j >= 0; j--){
          if(str[j] !== ' ') break;
        }
        return str.slice(i, j + 1);
      }

手写Promise

function proAll(promises){

        let len = promises.length;
        let result = Array(len);
        let countEnd = 0;

        return new Promise((resolve, reject) => {
          if(len === 0) resolve(result);

          for(let i = 0; i < len; i++){
            let promise = promises[i];

            Promise.resolve(promise).then(
              (data) => {
                result[countEnd++] = data;
                if(countEnd === len) resolve(result);
              },
              (err) => {
                reject(err);
              }
            );
          }
        });
      } 

      const promise1 = Promise.resolve(3);
      const promise2 = 42;
      const promise3 = new Promise((resolve, reject) => {
        setTimeout(resolve, 100, 'foo');
      });
      console.log(proAll([promise1, promise2, promise3]));

闭包的两个作用

// 封装私有变量
function Nin(){
        let private = 10;

        this.getPrivate = function (){
          return private;
        }

        this.addPrivate = function (){
          private++;
        }
      }

      let nin = new Nin();

      console.log(nin.private);

      console.log(nin.getPrivate());
      nin.addPrivate();
      console.log(nin.getPrivate());


// 处理回调函数

function fun(){
        let tick = 0;
        console.log("tick init", tick);
        const timer = setInterval(() => {
          if(tick < 100){
            console.log('tick is less then 100', tick);
            tick += 1;
          }
          else {
            clearInterval(timer);
            console.log('now tick is ', tick);
          }
        }, 10);
        
      }
      fun();

手写二叉树

function TreeNode(val, left, right){
      this.val = (val === undefined ? 0 : val);
      this.left = (left === undefined ? null : left);
      this.right = (right === undefined ? null : right);
    }

手写promise.race

function PromiseRace(promises){
      if(!Array.isArray(promises)) throw new Error('promise must be an array');

      return new Promise(function (resolve, reject) {
        promises.forEach(p => resolve(p), err => reject(err));
      })
    }

手写promise

class Promise{
  constructor(fn) {
    this.status = 'pending';
    this.resolve = undefined;
    this.reject = undefined;

    let resolve = val => {
      if(this.status === 'pending'){
        this.status = 'resolved';
        this.resolve = val;
      }
    }

    let reject = val => {
      if(this.status === 'pending'){
        this.status = 'rejected';
        this.reject = val;
      }
    }

    try {
      fn(resolve, reject);
    }
    catch(e) {
      reject(e);
    }
  }
  then (onResolved, onRejected){
    if(this.status === 'resolved') onResolved(this.resolve);
    if(this.status === 'rejected') onRejected(this.reject);
  }
}

手写防抖

function debounce(fn, wait){
      let timer = null;
      let args = arguments;
      return new function(){
        if(timer !== null){
          clearTimeout(timer)
        }
        else {
          timer = setTimeout(() => {
            fn.apply(this, args);
          }, wait);
        }
      }
    }

手写节流

function throttle(fn, wait){
      let curTime = new Date();

      return function(){
        let context = this,
            args = arguments,
            nowTime = new Date();
          if(nowTime - curTime >= wait){
            fn.apply(context, args);
          }
      }
    }

js9

发表于 2022-03-02

原型修改、重写

function Person(name){
    this.name = name
}
Person.pototype.getName = function (){}
var p = new Person('hello')
console.log(p.__proto__ === Person.prototype) 
// true
console.log(p.__proto__ === p.constructor.prototype)   // true
// 重写原型
Person.prototype = {
    getName: funciton() {}
}

获取对象非原型链上的属性

function iterate(obj){
	var res = []
    for(var key in obj){
        if(obj.hasOwnProperty(key))
            res.push(key+': ' )
    }
}

闭包理解

闭包是指有权访问另一个函数作用域中变量的函数

js8

发表于 2022-03-01

三种获取对象原型的方法

Constructor.prototype是构造函数指向原型对象的方法
Object.getPrototypeOf(obj)是ES5中用来获取obj对象的原型对象的标准方法。
obj.__proto__是获取obj对象的原型对象的非标准方法。

实现Instanceof

instanceof运算符用于判断构造函数的prototype属性是否出现在对象的原型链中的任何位置

function myInstanceof(left, right){
      // 获取对象的原型
      let proto = Object.getPrototypeOf(left)
      // 获取构造函数对象的原型
      let prototype = right.prototype
    
      while(true){
        if(!proto) return false
        if(proto === prototype) return true
        // 如果没有找到, 就继续从其原型上找
        proto = Object.getPrototypeOf(proto)
      }
    }

解决0.1+0.2 !== 0.3

function numberEpsilon(arg1, arg2){
      return Math.abs(arg1 - arg2) < Number.EPSILON
    }
    console.log(numberEpsilon(0.1 + 0.2, 0.3)); // true
    console.log(0.1 + 0.2 === 0.3); //false

js包装类型

js中基本类型是没有属性和方法的,为了方便操作基本类型,在调用基本类型时js会在后台隐式将基本类型转换为对象

let、const、var区别

(1) 块级作用域由{}包括, let和const具有块级作用域, var不存在块级作用域,解决了两个问题

内层变量可以覆盖外层变量

用来计数的循环变量泄漏为全局变量

var存在变量提升, let, const不存在变量提升, 变量只能在声明后使用

var会给全局添加属性

var允许重复声明, const, let不允许

给let, const命令声明变量之前, 该变量都是不可用的, 语法上成为暂时性死区, var声明不存在

var, let可以不用设置初始值, const必须设置初始值

let可以改变指针指向, const不可以改变指针指向

const属性修改问题

const保证变量指向的地址不可改变, 对于基本的数据类型(数值, 字符串, 布尔值), 其值就保存在变量指向的那个内存地址中, 等同与常量

对于引用类型来说(对象, 数组), 变量指向数据的内存地址, 保存的只是一个指针, const只能保证这个指针固定不动, 数据结构内部不可控

箭头函数

箭头函数时es6提出的, 它没有prototype, 也没有自己的指向, 所以不可以new一个箭头函数

new操作符的实现步骤如下:

1、创建一个对象

2、将对象的proto属性指向构造函数的prototype

3、构造函数肚饿this指向该对象，为这个对象挂载属性和方法

4、返回新的对象

上面的二、三步箭头函数无法执行

箭头函数和普通函数区别

箭头函数比普通函数更简洁

如果不需要返回值, 且只有一句话, 可以给语句前面加一个void, 再调用一个函数

let fn = () => void fun()

箭头函数没有自己的this

箭头函数不会创建自己的this, 它继承了自己作用域上一层的this

箭头函数指向的this不会改变

var id = 'GLOBAL';
var obj = {
	id: 'OBJ',
	a: function(){
		console.log(this.id)
	},
	b: () => {
		console.log(this.id)
	}
};
obj.a() // 'OBJ'
obj.b(); // 'GLOBAL'
new obj.a() // undefine
new obj.b() // Uncaught TypeError: obj.b is..

对象obj的方法b是使用箭头函数定义的, 这个函数中this就永远指向它定义时所处的全局执行环境this, 即便这个函数时作为对象obj的方法调用, this依旧指向window对象定义对象的大括号{}无法形成一个单独的执行环境, 它依然处于全局环境中

call() bind() apply() 等方法不能改变箭头函数this指向

var id = 'Global'
let fun1 = () => {
	console.log(this.id)
}
fun1();	// 'Global'
fun1.call({id: 'obj'})	// 'Global'
fun1.apply({id: 'obj'})	// 'Global'
fun1.bind({id: 'obj'})()	// 'Global'

箭头函数不能作为构造函数使用

没有arguments

扩展运算符

1.对象扩展运算符

对象的扩展运算符(…)用于取出参数对象中的所有可遍历属性, 拷贝到当前对象中

1 2	let bar = {a: 1, b: 2} let baz = {...bar} // {a: 1, b: 2}

上述方法等价于

1 2	let bar = {a: 1, b: 2} let baz = Object.assign({}, bar) //

Object.assign()方法用于对象的合并, 将源对象source的所有可枚举属性, 复制到目标对象(target)

Object.assign方法第一个参数是目标对象, 后面参数是源对象(如果有同名属性, 后面会覆盖前面)

1 2	let bar = {a: 1, b: 2} let baz = {...bar, ...{a: 2, b: 4}} //被覆盖

2.数组扩展运算符

1
2
3

console.log(...[1,2,3]) // 1 2 3
console.log(...[1, [2, 3, 4], 5]) 
// 1 [2, 3, 4] 5

数组扩展运算符的应用

function add(x, y){
    return x + y
}
const numbers = [1, 2]
add(...numbers) // 3

复制数组

1 2	const arr1 = [1,2] const arr2 = [...arr1]

扩展运算符会取出参数对象中所有可用属性, 拷贝到当前对象中

合并数组

1
2
3

const arr1 = ['two', 'three'];
const arr2 = ['one', ...arr1, 'four', 'five']
// ['one', 'two', 'three', 'four', 'five']

将字符串转换为真正的数组

1	[...'hello']

对数组和对象的结构

解构是ES6提供的新的提取数据的模式,这种模式能够从对象或数组中针对性拿到想要的东西

数组解构

1	const [a,b,c] = [1,2,3]

或者留空

1	const [a,,c] = [1,2,3] // a: 1, c: 3

对象结构

解构对象是以属性名称为匹配条件

const stu = {
	name: 'Bob',
	age: 24
}

解构属性

1 2	const {name, age} = stu //name: 'Bob' age: 24 // 调换位置也一样

new操作符实现(手写)

1.首先创建了一个新的空对象

2.设置原型, 将对象的原型设置为函数的prototype对象

3.让函数的this指向这个对象, 指向构造函数的代码

4.返回对象

function Dog(name){
      this.name = name
    }
    Dog.prototype.sayName = function (){
      console.log(this.name)
    }

    function _new(fn, ...args){
      // 先用object创建一个新对象
      const obj = Object.create(fn.prototype)
      // obj指向构造函数原型了, 再修改this指针
      const res = fn.apply(obj, args)
      return res instanceof Object ? res : obj
    }
    let dog = _new(Dog, '大毛')
    dog.sayName()

lc26

发表于 2022-03-01

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  let dummy = new ListNode(-1)
  dummy.next = head
  let cur = dummy
  while(cur.next && cur.next.next){
    let node1 = cur.next
    let node2 = cur.next.next.next
    
    cur.next = cur.next.next
    cur.next.next = node1
    cur.next.next.next = node2

    cur = cur.next.next
  }
  return dummy.next

};

19. 删除链表的倒数第 N 个结点

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  let sum = 0;
  let cur = head
  while(cur){
    sum++
    cur = cur.next
  }
  
  let cnt = 0;
  let dummy = new ListNode(-1)
  dummy.next = head
  cur = dummy
  while(cur){
    if(cnt === sum - n) {
      if(cur.next) cur.next = cur.next.next
      else cur.next = null
    }
    cnt++
    if(cur) cur = cur.next
  }
  return dummy.next
};

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let sub = 0
    let aa = headA, bb = headB
    let cntA = 0, cntB = 0
    while(aa){
      cntA++
      aa = aa.next
    }
    while(bb){
      cntB++
      bb = bb.next
    }
    aa = headA, bb = headB
    

    if(cntA < cntB){
      [aa, bb] = [bb, aa];
      [cntA, cntB] = [cntB, cntA];
    }
    sub = cntA - cntB;
    while(sub-- && aa){
      aa = aa.next
    }
    while(aa){
      if(aa == bb){
        return aa
      }
      aa = aa.next
      bb = bb.next
    }
    return null
};

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head, slow = head
    do{
      if(!fast || !fast.next) return null
      fast = fast.next.next;
      slow = slow.next;
    }while(fast !== slow)

    let node = head
    while(node!== slow){
      node = node.next
      slow = slow.next
    }
    return node
};

计网

发表于 2022-02-28

为什么需要三次握手

第一次: 客户端给服务器发送syn报文

第二次: 服务器收到syn报文后, 会应答一个syn+ack报文

第三次: 客户端收到syn + ack报文, 会回应一个ack报文, 至此三次握手建立

第一次时, 客户端发送网络包, 服务器得到结论, 服务器接收能力和客户端发送能力正常. 第二次服务器发包, 客户端收到后得到结论, 客户端收发能力正常, 服务器收发能力正常, 但服务器还不知道. 所以第三次客户端发包给服务器接收后, 服务器才能确定双方都能正常接收网络包

刚开始时客户端处于closed状态, 服务端处于listen状态

1、第一次握手：客户端给服务器发一个syn报文，并指明客户端的初始化序列号ISN（c），此时客户端处于syn_send状态

2、第二次握手：服务器接收到syn报文后，会以自己的syn报文作为应答，并且也是制定了自己的初始化序列号ISN（s），同时会把同时会把ISN + 1作为ACK的值，表示自己已经收到了客户端的SYN，此时服务器处于SYN_RCVD的状态

3、第三次握手：客户端收到SYN报文后，会发送一个ACK报文，也一样把服务器ISN + 1作为ACK的值，表示已经接受了服务器SYN报文，此时客户端处于established状态

三次握手的作用

确认上方接受能力、发送能力是否正常

指定自己的初始化序列号，为后面的可靠传输做准备

1、（ISN）是固定的吗

三次握手的一个重要功能是客户端和服务端交换ISN（Initial Sequence Number），以便让对方知道接下来接受数据如何按照序列号组装数据。ISN是随机生成的，否则攻击者很容易猜出

2、什么是半连接队列

服务器第一次接受到客户端的syn后会处于SYN_REVD状态，会将请求连接放在一个队列里，称为半连接队列

三次握手前两次不能携带数据，第三次可以

四次挥手

开始时双方都处于establised状态，客户端先发起请求关闭

1、第一次挥手：客户端发送一个fin报文，报文中会指定一个序列号。此时客户端处于FIN_WAIT1状态

2、第二次挥手：服务端收到FIN后，会发送ACK报文，且吧客户端序列号值+1

js7

发表于 2022-02-28

New

js中new的作用是通过构造函数创建实例对象

1
2
3

function Foo(name){
  this.name = name
}

new经历了什么过程

new帮我们做了4件事情:

帮我们创建了空对象

把空对象的原型__ proto __ 指向了构造函数的原型对象

使用call方法, 将本来指向window的this改成了指向obj实例, 这样我们再去向构造函数传参时, 参数就会被挂载到实例上

返回对象

数据结构1

发表于 2022-02-28

1.数组

数组是存放在连续空间上的相同类型的数据集合

数组可以通过下标索引获取对应数据

数组下标是从0开始的

数组内存空间是连续的

链表

链表是通过指针串联在一起的结构, 每个结点由两部分组成: 数据域和指针域, 最后一个指针域指向null

单链表

单链表中指针只能指向下一个结点

双链表

每个结点有两个指针域, 一个指向上一个节点, 一个指向下一个结点, 可以向前后查询

数组在内存中是连续分布的, 链表在内存中是不连续分布的, 链表通过指针域指针连接在内存各个结点

class ListNode {
  val;
  next = null;
  constructor(value) {
    this.val = value;
    this.next = null;
  }
}

lc25

发表于 2022-02-28

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
  let slow = 0
  for(let fast = 0; fast < nums.length; fast++){
    if(val !== nums[fast]) nums[slow++] = nums[fast]
  }
  return slow
};

977. 有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
  let n = nums.length - 1
  let ans = new Array(n).fill(0)
  for(let i = 0, j = nums.length - 1; i <= j;){
    if(nums[i] * nums[i] > nums[j] * nums[j]) ans[n--] = nums[i] * nums[i++]
    else ans[n--] = nums[j] * nums[j--]
  }
  return ans
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  let l = 0, r = 0, minLen = Number.MAX_VALUE , sum = 0, subLen = 0
  while(r < nums.length){
    sum += nums[r]
    while(sum >= target){
      subLen = r - l + 1
      minLen = minLen < subLen ? minLen : subLen
      sum -= nums[l++]
    }
    r++
  }
  return minLen === Number.MAX_VALUE ? 0 : minLen
};

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1 2	输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  if(matrix.length === 0) return []
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
  let res = []
  while(top < bottom && left < right){
    for (let i = left; i < right; i++) res.push(matrix[top][i]); 
    for (let i = top; i < bottom; i++) res.push(matrix[i][right]);
    for (let i = right; i > left; i--) res.push(matrix[bottom][i]);
    for (let i = bottom; i > top; i--) res.push(matrix[i][left]);
    right--;
    top++;
    bottom--;
    left++;

  } 

  if(top === bottom) {
    for(let i = left; i <= right; i++) res.push(matrix[top][i])
  }

  else if(left === right) {
    for(let i = top; i <= bottom; i++) res.push(matrix[i][left])
  }
  return res
};

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

1 2	输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1 2	输入：n = 1 输出：[[1]]

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  const ans = new Array(n).fill(0).map(() => new Array(n).fill(0))
  let left = 0, right = n - 1, top = 0, bottom = n - 1
  let k = 1
  while(left < right && top < bottom){
    for(let i = left; i < right; i++) ans[top][i] = k++
    for(let i = top; i < bottom; i++) ans[i][right] = k++
    for(let i = right; i > left; i--) ans[bottom][i] = k++
    for(let i = bottom; i > top; i--) ans[i][left] = k++
    bottom--
    right--
    left++
    top++
  }

  if(top === bottom) {
    for(let i = left; i <= right; i++) ans[top][i] = k++
  }
  else if(left === right) {
    for(let i = top; i <= bottom; i++) ans[i][left] = k++
  }
  return ans
};

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：

输入：head = [], val = 1
输出：[]
示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

var removeElements = function(head, val) {
  if(head === null) return null
  head.next = removeElements(head.next, val)
  return head.val === val ? head.next : head
};

var removeElements = function(head, val) {
  let dummy = new ListNode(-1)
  dummy.next = head
  let cur = head, pre = dummy
  while(cur){
    while(cur && cur.val === val){
      pre.next = cur.next
      cur = pre.next
    }
    
    if(cur) {
      cur = cur.next
      pre = pre.next
    }
  }

  return dummy.next
};

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1 2	输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

示例 3：

1 2	输入：head = [] 输出：[]

var reverseList = function(head) {
  
  let cur = head, pre = null
  while(cur){
    let temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  return pre
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  return reverse(null, head)
};

function reverse(pre, cur){
  if(cur === null) return pre
  let temp = cur.next
  cur.next = pre
  pre = cur
  cur = temp
  return reverse(pre, cur)
}