Toypipi's blog

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 拼接到一起

对象

1. 什么是对象

   • 多个数据的封装体
   • 用来保存多个数据的容器
   • 一个对象代表现实中的一个事物

2. 为什么要用对象

   • 统一管理多个数据

3. 对象的组成

   • 属性：属性名（字符串）和属性值（任意）组成
   • 方法：一种特别的属性（属性值是函数）

4. 如何访问对象内部数据

   • .属性名：编码简单，有时不能用
   • [‘属性名’]：编码麻烦，能通用

5. FAQ

   • 什么时候必须用[‘属性名’]的方式
     • 属性名包含特殊字符：- 空格
     • 变量名不确定