手写算法: 买卖股票的最佳时机

121. 买卖股票的最佳时机

解法一：贪心算法

1. 一次循环找到最低买入点，与当前的价格比较，计算出最大利润

2. Number.MAX_VALUE 表示在 JavaScript 里所能表示的最大数值

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let res = 0;
  let minPrice = Number.MAX_VALUE;
  for (let i = 0; i < prices.length; i++) {
    // 每次都拿当天价格跟最小价进行比较
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else {
      // 计算利润，把大的存起来
      res = Math.max(res, prices[i] - minPrice);
    }
  }
  return res;
};

思路

动态规划五部曲：

1. 确定 dp 数组（dp table）以及下标的含义

• dp[i][0] 表示第 i 天持有股票所得最多现金, 其实一开始现金是 0，那么加入第 i 天买入股票现金就是-prices[i],这是一个负数。(可以看作只买入没有卖出，就是负的)

• dp[i][1] 表示第 i 天不持有股票所得最多现金

2. 确定递归公式

• 如果第 i 天持有股票为 dp[i][0]，

  • 第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 dp[i - 1][0]
  • 第 i 天买入股票，那么所得现金就是买入今天的股票后所得现金，即-prices[i]

  那么取最大的，dp[i][0] = Max(dp[i - 1][0], -prices[i])，即 dp[i][0]存储的是最小买入价格

• 如果第 i 天不持有股票 dp[i][1]，

  • 第 i-1 天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 dp[i - 1][1]
  • 第 i 天卖出股票，那么所得现金就是按照今天股票价格卖出后所得现金，即 prices[i] + dp[i - 1][0] (当天股票价格 + 买入价格)

同样取最大的，dp[i][1] = Max(dp[i - 1][1], prices[i] + dp[i - 1][0])

/**
 * 动态规划解法
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  const len = prices.length;
  // 构建dp数组
  let dp = new Array(len).fill([0, 0]);

  // 初始化dp
  dp[0] = [-prices[0], 0];

  for (let i = 1; i < len; i++) {
    // 更新
    dp[i] = [
      Math.max(dp[i - 1][0], -prices[i]),
      Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]),
    ];
  }
  return dp[len - 1][1];
};

手写题：寻找合适开会的时间

82. 寻找合适开会的时间

思路

1. 拉平数组，按开始时间升序。

2. 遍历已排序好的数组，间时间初始从 0 开始，命名 prevEnd,记录当前最大的结时间点，每次都要拿当前的 end 与上一次的 prevEnd 相比，因为的间段有可能重复，而且这里是用 start 初始时间进行排序。

3. 遍历结束后，看 prevEnd 是等于 24,不等于的话直接将后面那一段都识为空闲时间[prevEnd, 24]

// type Interval = [number, number]

/**
 * @param {Interval[][]} schedules
 * @return {Interval[]}
 */
function findMeetingSlots(schedules) {
  // your code here
  let time = schedules.flat();
  time.sort((a, b) => a[0] - b[0]);

  let result = [];
  let prevEnd = 0;
  time.forEach(t => {
    let [start, end] = t;
    if (prevEnd < start) {
      result.push([prevEnd, start]);
    }
    prevEnd = Math.max(prevEnd, end);
  });
  if (prevEnd !== 24) {
    result.push([prevEnd, 24]);
  }
  return result;
}

JS 简答题

to primitive

56. to primitive

// case 1
const obj1 = {
  valueOf() {
    return 1;
  },
  toString() {
    return '100';
  },
};

console.log(obj1 + 1);
console.log(parseInt(obj1));

// case 2
const obj2 = {
  [Symbol.toPrimitive]() {
    return 200;
  },

  valueOf() {
    return 1;
  },
  toString() {
    return '100';
  },
};

console.log(obj2 + 1);
console.log(parseInt(obj2));

// case 3
const obj3 = {
  toString() {
    return '100';
  },
};

console.log(+obj3);
console.log(obj3 + 1);
console.log(parseInt(obj3));

// case 4
const obj4 = {
  valueOf() {
    return 1;
  },
};

console.log(obj4 + 1);
console.log(parseInt(obj4));

// case 5
const obj5 = {
  [Symbol.toPrimitive](hint) {
    return hint === 'string' ? '100' : 1;
  },
};

console.log(obj5 + 1);
console.log(parseInt(obj5));

解析

当对象转成原始对象时，都会使用Symbol.toPrimitive，它会先调用 valueOf(),不行再调用 toString()。也可以自定义Symbol.toPrimitive。

• obj1

  1. 先 valueOf() ==> 1+1

  2. parseInt(string, radix),接收的入参为 thing 类型。如果传进来的不是 string 类型，那么先 toString(),再进行计算。

  3. obj1.toString()得到'100',再 parseInt('100')得到 100

• obj2

  自定义 Symbol.toPrimitive() 每次都先拿到 200

• obj3

  先 toString()得到'100',再进行操作。

• obj4

  1. parseInt(),入参需要 string, 0bj4.toString()拿到'[object Object]'

  2. parseInt('[object Object]') ===> NaN

• obj5

  1. lint 不为'string',拿到 1,1+1

  2. obj5 为 'string',拿到 100，再进行 parseInt()

再看一题 ⬇️ ⬇️

// An object without Symbol.toPrimitive property.
var obj1 = {};
console.log(+obj1); // NaN
console.log(`${obj1}`); // "[object Object]"
console.log(obj1 + ''); // "[object Object]"

// An object with Symbol.toPrimitive property.
var obj2 = {
  [Symbol.toPrimitive](hint) {
    if (hint == 'number') {
      return 10;
    }
    if (hint == 'string') {
      return 'hello';
    }
    return true;
  },
};
console.log(+obj2); // 10        -- hint is "number"
console.log(`${obj2}`); // "hello"   -- hint is "string"
console.log(obj2 + ''); // "true"    -- hint is "default"

Hoisting IIII

32. Hoisting IIII

var a = 1;
function a() {}

console.log(typeof a);

var b;
function b() {}
b = 1;

console.log(typeof b);

function c() {}
var c = 1;

console.log(typeof c);

var d = 1;

(function() {
  d = '2';
  console.log(typeof d);
  function d() {}
})();

console.log(typeof d);

var e = 1;
const f = function e() {};

console.log(typeof e);

解析

关键就是看这个闭包，函数声明会提升

(function() {
  // 函数声明提升，相当于在闭包内部新增了一个变量d 是function d() {}
  console.log(d);

  // 赋值d
  d = '2';
  // 此时d是'2'
  console.log(typeof d);
  function d() {}
})();

// 闭包里面新建了个d，不影响全局作用域下的，所以此时d还是1
console.log(typeof d);

arguments

12. arguments

function log(a, b, c, d) {
  console.log(a, b, c, d);
  arguments[0] = 'bfe';
  arguments[3] = 'dev';

  console.log(a, b, c, d);
}

log(1, 2, 3);

解析

arguments 是指实参的长度，现在只传进来 3 个参数，那么 argument 的长度为 3，arguments[3]自然是 undefined

Implicit Coercion IV

46. Implicit Coercion IV

const foo = [0];
if (foo) {
  console.log(foo == true);
} else {
  console.log(foo == false);
}

解析

考点：

1. [0],布尔值Boolean([0])为 true

2. 判断 foo == true, [0]会先转成原始对象再跟 true 相比较。

[0].valueOf(); // 拿到的还是[0], 再进行toString
[0].toString(); // '0'

true; // 转换成原始数据类型为1

0 == 1; // false

instanceOf 2

87. instanceOf 2

console.log(Function instanceof Object);
console.log(Object instanceof Function);
console.log(Function instanceof Function);
console.log(Object instanceof Object);

解析

Object.__proto__.constructor 指向 Function

Function.__proto__.constructor 又指向 Object

形成了一个闭环