Toypipi's blog

1. 作用域与作用域链

   • 作用域

     • 理解
       • 代码段所在的区域
       • 它是静态的（相对于上下文对象），在编写代码时就确定了
     • 分类
       • 全局作用域
       • 函数作用域
       • 块作用域
     • 作用
       • 隔离变量，不同作用域下同名变量不会有冲突

   • 作用域与执行上下文

     • 区别 1
       • 全局作用域外，每个函数都会创建自己的作用域，作用域在函数定义时就已经确定了，而不是在调用时确定
       • 全局执行上下文环境是在全局作用域确定后，js 代码马上执行之前创建
       • 函数执行上下文环境是在调用函数时，函数体代码执行之前创建
     • 区别 2
       • 作用域是静态的，只要函数定义好了就一直存在，且不会变化
       • 上下文环境是动态的，调用函数时创建，函数调用结束时上下文环境就自动释放
     • 联系
       • 执行上下文环境（对象）是从属于所在的作用域
       • 全局上下文环境 ==> 全局作用域
       • 函数上下文环境 ==> 对应的函数使用域

   • 作用域链

leetcode 题库里面的一道题，官方讲解得很清楚，记录一下。

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解法一，比较容易想到的解法就是暴力求解，嵌套 for 循环，时间复杂度 O（n²），空间复杂度 O(1)。
题目要求，数组中同一个元素在答案里不能重复出现，所以，第二层 for 循环只需要在 i 之后的元素中寻找。

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
};

1. 原型与原型链

   • 原型(prototype)

     • 函数的 prototype 属性
       • 每个函数都有一个 prototype 属性，它默认指向一个 Object 空对象（即称为：原型对象)
       • 原型对象中有一个 constructor ，它指向函数对象

   • 显式原型与隐式原型

     • 每个函数 function 都有一个 prototype，即显式原型(属性)
     • 每个实例对象都有一个 __proto__，可称为隐式原型（属性）
     • 对象的隐式原型的值为其对应构造函数的显示原型的值

   • 原型链

     • 访问一个对象的属性时：
       • 先在自身属性中查找，找到返回
       • 如果没有，再沿着 __proto__ 这条链向上查找，找到返回
       • 如果最终没有找到，返回 undefined
     • 别名：隐式原型连
     • 作用：查找对象的属性（方法）
     • 原型继承
       • 构造函数的实例对象自动拥有构造函数原型对象的属性（方法）
       • 利用的就是原型链
     • 原型属性问题
       • 读取对象的属性值时，会自动到原型链中查找
       • 设置对象的属性值时，不会查找原型链，如果当前对象中没有此属性，直接添加此属性并设置值
       • 方法一般定义在原型中，属性一般通过构造函数定义在对象本身上

   • 探索 instanceof

     • 表达式：A instanceof B
     • 如果 B 函数的显示原型对象在 A 对象的原型链上，返回 true，否则返回 false

时间复杂度和空间复杂度是用于衡量算法效率的概念。

1. 时间复杂度：
   时间复杂度描述了算法运行时间随输入规模增长而增加的速率。它表示算法执行所需的时间与输入数据的大小之间的关系。通常用大 O 符号（O）来表示时间复杂度。
   例如，如果一个算法的时间复杂度为 O(n)，意味着随着输入数据的大小 n 增加，算法的运行时间会线性增长。如果时间复杂度为 O(n^2)，则表示随着输入数据的大小 n 增加，算法的运行时间会按二次方增长。一般而言，时间复杂度越低，算法执行速度越快。

2. 空间复杂度：
   空间复杂度描述了算法执行所需的额外空间随输入规模增长而增加的速率。它表示算法使用的额外内存空间与输入数据的大小之间的关系。通常也用大 O 符号（O）来表示空间复杂度。
   例如，如果一个算法的空间复杂度为 O(n)，意味着随着输入数据的大小 n 增加，算法使用的额外内存空间也会线性增长。如果空间复杂度为 O(1)，则表示算法使用的额外内存空间是常数，与输入数据的大小无关。

在进行算法分析时，我们通常关注算法的时间复杂度和空间复杂度，以便评估算法的效率和资源利用情况。较低的时间复杂度和空间复杂度通常意味着更优秀的算法。然而，要根据具体情况选择合适的算法，因为某些情况下可能需要在时间和空间之间进行权衡。

问题 1：输入一个数组 [1,2,3,4,5,6,7]，k=3，即旋转 3 步，输出 [5,6,7,1,2,3,4]

思路 1：把末尾的元素挨个 pop ，然后 unshift 到数组前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function rotateArray(arr, k) {
  const length = arr.length;
  if (!k || length === 0) return arr;
  k = Math.abs(k % length);
  for (let i = 0; i < k; i++) {
    const lastElement = arr.pop();
    arr.unshift(lastElement);
  }
  return arr;
}

const inputArray = [1, 2, 3, 4, 5, 6, 7];
const k = 3;
const rotatedArray = rotateArray(inputArray, k);
console.log(rotatedArray); // Output: [5, 6, 7, 1, 2, 3, 4]

思路 2：把数组拆分，最后 concat 拼接到一起