姚永坤的小窝

基础知识 动态规划问题的一般形式就是求最值。 求解动态规划的核心问题是穷举。 动态规划问题一定会具备最优子结构。 只有找到并列出正确的状态转移方程才能正确的穷举。 要符合最优子结构就需要子问题间必须相互独立。 斐波那契数列常见方式为递归，代码如下： 1234function fib(n){ if(n==1||n==2) return 1; return fib(n-1)+fib(n-2);} 递归算法的时间复杂度等于子问题个数乘以解决一个子问题需要的时间。 其中：子问题个数就是递归树中节点的总数，二叉节点总数为制数级别，故为O(2^n)。 时间复杂度为制数级别十分费时。 重叠子问题观察下面的递归树：可以发现存在大量的重复计算 构建备忘录解决重叠子问题步骤： 1、 构造备忘录（数组/字典）； 2、 计算出子问题的答案先将其存储在备忘录中，再返回； 3、 每次遇到一个子问题先去备忘录中查询，如果已存在答案直接使用。 1234567891011function fib(n){ if(n<1) return 0; ...

题目给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。 解题思路1、暴力破解优先处理nums2中的数值，找出每个数值对应题目要求的数，然后使用map进行存储：nums2的值为key，下一个比它大的值为value。然后遍历nums1，对应map中的值输出结果。 代码123456789101112131415161718192021222324252627/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */var nextGreaterElement = function(nums1, nums2) { let dic = new Map(); ...

题目给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 解题思路思路一：哈希统计对数组进行遍历，使用map对所有的数值进行统计；然后再对map进行遍历找出符合题目要求的数值。时间复杂度O(n)，空间复杂度O(n)。 代码123456789101112131415161718192021/** * @param {number[]} nums * @return {number[]} */var majorityElement = function(nums) { let count = new Map(); for(let i=0;i<nums.length;i++){ if(count.has(nums[i])){ count.set(nums[i],count.get(nums[i])+1); }else{ count.set(nums[i],1); } ...

理解对象 创建自定义对象的通常方式是创建object的一个新实例，然后再给它添加属性和方法。 也可以使用对象字面量进行创建。 12345678910111213141516let person = new Object(); person.name = "Nicholas"; person.age = 29; person.job = "Software Engineer"; person.sayName = function() { console.log(this.name); };//===========等价于============let person = { name: "Nicholas", age: 29, job: "Software Engineer", sayName() { console.log(this.name); } }; 属性类型 属性分两种:数据属性 ...

题目给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。 错误解题历程错误一思路 根据题目要求找出数组中的最大值，遍历数组中每一个元素如果比最大值小那么就将该值加一，否则不变； 当首次遇到与最大值相等的值的时候该值不变并标记，下次遇到时加一； 遍历数组判断是否全部相等； 结果当遇到的数组最大值较大或者数组长度较长时的时候循环次数较多导致代码运行超时。 代码1234567891011121314151617181920212223242526272829303132333435363738/** * @param {number[]} nums * @return {number} */var minMoves = function(nums) { let a =0; let flag = true; let maxN = 0; while(flag){ maxN = Math.max(...nums); let ...

迭代与迭代器定义 官方定义的迭代意思是：按照顺序反复多次执行一段程序,通常会有明确的终止条件。 实际上计数循环就是最简单的迭代。 循环是迭代机制的基础，这是因为它可以指定迭代的次数，以及每次迭代要执行什么操作。每次循环都会在下一次迭代开始之前完成，而每次迭代的顺序都是事先定义好的。 迭代会在一个有序集合上进行。(“有序”可以理解为集合中所有项都可以按照既定的顺序被遍历到,特别是开始和结束项有明确的定义。)数组是JavaScript 中有序集合的最典型例子。 迭代器模式 迭代器模式（特别是在 ECMAScript这个语境下)描述了一个方案，即可以把有些结构称为“可迭代对象”( iterable)，因为它们实现了正式的工terable接口，而且可以通过迭代器工terator消费。 基本上，可以把可迭代对象理解成数组或集合这样的集合类型的对 可迭代协议 可迭代协议指的是Iterable接口 实现工terable接口(可迭代协议)要求同时具备两种能力:支持迭代的自我识别能力和创建实现Iterator接口的对象的能力。 实现可迭代协议的所有类型都会白动兼容接收可迭代对象的任何语言特性。 接收 ...

基本API 使用new关键字实例化一个空的WeakSet: 弱集合中的值只能是object或者继承自object的类型，尝试使用非对象设置值会抛出TypeError。 如果想在初始化时填充弱集合，则构造函数可以接收-一个可迭代对象，其中需要包含有效的值。可迭代对象中的每个值都会按照迭代顺序插入到新实例中: 123456789101112131415161718const val1 = {id: 1}, val2 = {id: 2}, val3 = {id: 3}; // 使用数组初始化弱集合const ws1 = new WeakSet([val1, val2, val3]); alert(ws1.has(val1)); // true alert(ws1.has(val2)); // true alert(ws1.has(val3)); // true // 初始化是全有或全无的操作// 只要有一个值无效就会抛出错误，导致整个初始化失败const ws2 = new WeakSet([val1, " ...

基本API 创建的同时初始化实例： 123456789101112// 使用数组初始化集合 const s1 = new Set(["val1", "val2", "val3"]); alert(s1.size); // 3 // 使用自定义迭代器初始化集合const s2 = new Set({ [Symbol.iterator]: function*() { yield "val1"; yield "val2"; yield "val3"; } }); alert(s2.size); // 3 初始化之后，可以使用： add ()增加值； has()查询； size取得元素数量； delete()删除元素； 123456789101112131415const s = new Set(); alert(s.has("Matt")) ...

WeakMap是Map 的“兄弟”类型,其API也是Map的子集。 WeakMap中的”weak”(弱).描述的是JavaScript垃圾回收程序对待“弱映射”中键的方式。 基本API 可以使用 new 关键字实例化一个空的 WeakMap： 1const wm = new WeakMap(); 弱映射中的键只能是 Object 或者继承自 Object的类型,尝试使用非对象设置键会抛出TypeError。 值的类型没有限制。 如果想在初始化时填充弱映射，则构造函数可以接收一个可迭代对象，其中需要包含键/值对数组。可迭代对象中的每个键/值都会按照迭代顺序插人新实例中: 12345678910111213141516171819202122232425262728const key1 = {id: 1}, key2 = {id: 2}, key3 = {id: 3};// 使用嵌套数组初始化弱映射const wm1 = new WeakMap([ [key1, "val1"] ...

内存占用 Object 和 Map 的工程级实现在不同浏览器间存在明显差异，但存储单个键/值对所占用的内存数量都会随键的数量线性增加。批量添加或删除键/值对则取决于各浏览器对该类型内存分配的工程实现。不同浏览器的情况不同，但给定固定大小的内存，Map 大约可以比 Object 多存储 50%的键/值对; 插入性能 向object和 Map中插入新键/值对的消耗大致相当，不过插人Map在所有浏览器中一般会稍微快一点儿。对这两个类型来说，插入速度并不会随着键/值对数量而线性增加。如果代码涉及大量插入操作，那么显然 Map 的性能更佳。 查找速度 与插入不同，从大型object和 Map中查找键/值对的性能差异极小，但如果只包含少量键/值对,则object有时候速度更快。在把object 当成数组使用的情况下（比如使用连续整数作为属性)，浏览器引擎可以进行优化，在内存中使用更高效的布局。这对Map来说是不可能的。对这两个类型而言,查找速度不会随着键/值对数量增加而线性增加。如果代码涉及大量查找操作，那么某些情况下可能选择Obiect更好一些。 删除性能 使用delete删除object ...