手写算法: 存在重复元素

217. 存在重复元素

哈希表

将数组中的每个元素，都插入哈希表中，在插入元素的时候判断是否存在哈希表中，若已存在则说明有重复元素

时间复杂度O(n)， 空间复杂度O(n)

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
  let set = new Set();
  for (const num of nums) {
    if (set.has(num)) {
      return true;
    }
    set.add(num);
  }
  return false;
};

sort

先将数组进行排序，相同数字在一段连续的内存中，判断前后元素是否相等，就可以找到是否存在重复元素。

时间复杂度O(nlogn)， 空间复杂度O(logn)

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i + 1]) {
      return true;
    }
  }
  return false;
};

手写算法：存在重复元素 II

219. 存在重复元素 II

哈希表

遍历数组，将元素存在哈希表中，判断元素是否存在，存在的话，用当前的下标 减去 之前的下标，若是小于等于 k，那么就 return true

时间复杂度O(n)，空间复杂度O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i]) && i - map.get(nums[i]) <= k) {
      return true;
    }
    map.set(nums[i], i);
  }
  return false;
};

滑动窗口

因为要在 k 的范围内，找到重复的元素，如果超过这个范围就不符合下表相见小于 k 的要求。

所以可以把 k 看作是一个滑动窗口的范围，只有在这范围内的重复元素才有效，当 i > k 时， 就将 i - k - i 移出窗口。

var containsNearbyDuplicate = function(nums, k) {
  let set = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (i > k) {
      set.delete(nums[i - k - 1]);
    }
    if (set.has(nums[i])) return true;
    set.add(nums[i]);
  }
  return false;
};

手写题: 找到最大的差

107.找到最大的差

function largestDiff(arr) {
  if (!arr.length) return 0;
  let min = Infinity,
    max = -Infinity;
  for (const num of arr) {
    min = Math.min(num, min);
    max = Math.max(num, max);
  }
  return Math.abs(min - max);
}

// 解法二：完全利用API，Math.max()没有入参时结果为-Infinity
function largestDiff(arr) {
  if (!arr.length) return 0;
  return Math.max(...arr) - Math.min(...arr);
}

JS 简答题

Implicit Coercion III

35. Implicit Coercion III

console.log( [] + {} )
console.log( + {} )
console.log( + [] )
console.log( {} + [])
console.log( ({}) + [])
console.log( ({}) + [])
console.log( ({}) + [])
console.log( {} +  + [])
console.log( {} +  + [] + {} )
console.log( {} +  + [] + {}  + [])

解析

首先要ToPrimitive(), 当传进来的为object， 要使用toString()或者valueOf()转为基础类型，再进行运算。

([]).toString(); // ''
({}).toString(); // '[object Object]'


console.log( [] + {} ); // '' + '[object Object]' ==> '[object Object]'
console.log( + {} ); // +{} ==> 转换成数字 ==> Number('[object Object]') ==> NaN
console.log( + [] ); // +[] ==> Number('') ==> 0
console.log( {} + []); // '[object Object]' + '' ==> '[object Object]'
console.log( ({}) + []);
console.log( ({}) + []);
console.log( ({}) + []); // 这三个跟前面都是一样的
console.log( {} +  + []); // '[object Object]' + 0 ==> 0会转换成字符串 ==> '[object Object]0'
console.log( {} +  + [] + {} ) // '[object Object]' + '0' + '[object Object]' ==> '[object Object]0[object Object]'
console.log( {} +  + [] + {}  + []) // '[object Object]' + '0' + '[object Object]' + '' ==> '[object Object]0[object Object]'

Prototype

48. Prototype

function Foo() { }
Foo.prototype.bar = 1
const a = new Foo()
console.log(a.bar)

Foo.prototype.bar = 2
const b = new Foo()
console.log(a.bar)
console.log(b.bar)

Foo.prototype = {bar: 3}
const c = new Foo()
console.log(a.bar)
console.log(b.bar)
console.log(c.bar)

前面都是指向同一个内存地址，后面指向了其他的内存地址