算法

Question

算法

Opened this issue 2 years ago · 39 comments

TinyScript commented 2 years ago

Day - 01

完成算法：https://leetcode-cn.com/problems/add-to-array-form-of-integer/submissions/

思路：

1. 数组的单位计算处理

使用倒序遍历

2. k值的单位计算处理

计算前k取10的模
临时存储取模后的k用于计算
计算后k/10向下取整，并赋值到k

3. 进位数处理

新增进位存储变量，设为carry
num[i] + tempK + carry得到计算后的数result
每次计算后carry归零
result大于10，carry + 1，或取 result / 10 的向下取整数

4. 最高位数进1处理

遍历完成后，如果进位变量有值，对需要返回的数组进行unshift或push
推荐push + reverse，因为unshift会新增并填充，还要把原来的索引值再全部向后移动一次

5. 如何保证num和k的值被加完

num没有被遍历完，或k的位数没有被处理完

var addToArrayForm = function(num, k) {
  const result = [];
  let carry = 0;
  let i = num.length - 1;
  
  while(i >= 0 || k !== 0) {
    const tempK = k % 10;
    const tempNum = num[i] || 0
    const newNum = tempNum + tempK + carry;
    if(carry) carry = 0;
    i--;
    k = Math.floor(k / 10);
    if(newNum < 10) {
      result.push(newNum);
      continue;
    }
    carry++;
    result.push(newNum % 10);
  }
  if(carry) result.push(carry);
  return result.reverse();
};

addToArrayForm([2,7,4], 181); // => [4, 5, 5]

优化版：

思路：

处理num数组从后往前计算
处理k每位阶的取值
记录相加后的进位符
以上3点做加法循环，直到k = 0且num遍历完

var addToArrayForm = function(num, k) {
  const result = [];
  let carry = 0;
  let cur = num.length - 1;

  while(cur >= 0 || k !== 0) {
    const value = num[cur] || 0;
    const tempK = k % 10;
    const sum = value + tempK + carry;
    carry = Math.floor(sum / 10);
    k = Math.floor(k / 10);
    result.push(sum % 10);
    cur--;
  }
  if(carry) result.push(carry);
  return result.reverse();
};

实现柯里化：

思路

动态规划：
判断被柯里化函数的入参长度与执行时的入参长度是否满足
满足，执行被柯里化函数
不满足，返回一个递归自己的函数

function curry(func) {
  return function _curry(...args) {
      return args.length >= func.length 
           ? func(...args)
           : function(..._args) {
               return _curry(...[...args, ..._args])
           }
  }
}
function sum(a, b, c) {
  return a + b + c;
}

let curriedSum = curry(sum);

console.log(curriedSum(1, 2, 3)); // 6, still callable normally
console.log(curriedSum(1)(2, 3)); // 6, currying of 1st arg
console.log(curriedSum(1)(2)(3)); // 6, full currying

Answer 1 · 2022-03-29T12:37:59.000Z

Day - 02

完成算法：https://leetcode-cn.com/problems/shortest-distance-to-a-character/

第一版：

var shortestToChar = function(s, c) {
  const len = s.length;
  const result = new Array(len);
  let mainCur = 0;
  let subCur = 0;
  let prevSign = 0;
  let nextSign = 0;
  
  while(mainCur < len) {
    while(!nextSign && subCur < len) {
      if(s[subCur] === c) {
        if(mainCur === 0) prevSign = subCur
        nextSign = subCur;
        subCur++;
        break;
      }
      subCur++;
    }
    const prev = Math.abs(prevSign - mainCur)
    const next = Math.abs(nextSign - mainCur)
    const currDistance = Math.min(prev, next);
    if(!currDistance) {
        prevSign = nextSign
        nextSign = 0
    }
    
    result[mainCur] = currDistance
    mainCur++
  }
  return result
};

第二版：

var shortestToChar = function(s, c) {
    const len = s.length;
    const arr = [-Infinity];
    const result = [];
    for(let i = 0; i < len; i++) {
        s.charAt(i) === c && arr.push(i);
    }
    arr.push(Infinity);
    for(let i = 0; i < len; i++) {
      if(s.charAt(i) === c) {
        arr.shift();
        result.push(0);
        continue;
      }
      const resNum = Math.min(i - arr[0], arr[1] - i);
      result.push(resNum);
    }
    return result;
};

第三版：

思路

第一次遍历字符串，收集关键索引
第二次遍历字符串，根据关键索引计算距离
计算距离时，取关键索引最前2个值进行计算，取最小值
为了计算方便，关键索引数组的前后可加正负最大值

var shortestToChar = function(s, c) {
  const len = s.length;
  const result = [];
  const keyArr = [-Infinity];
  for(let i = 0; i < len; i++) {
    if(s.charAt(i) === c) keyArr.push(i);
  }
  keyArr.push(Infinity);
  let idx = 1, prev = keyArr[idx - 1], next = keyArr[idx];
  for(let i = 0; i < len; i++) {
    const dist = Math.min(i - prev, next - i);
    result.push(dist);
    if(i === next) {
      idx++;
      prev = next;
      next = keyArr[idx];
    }
  }
  return result;
};

Symbol实现，参考：https://gist.github.com/liril-net/4436fb0bdc8f8ddecbdd34bdfa571b14
第一版：

function SymbolPolyfill(description) {
  if(this instanceof SymbolPolyfill) throw new TypeError('Symbol is not a constructor');
  if(description !== undefined) {
    descString = String(description)
  }
  const symbol = Object.create(SymbolPolyfill.prototype)
  Object.defineProperties(symbol, {
      __Description__: { value: description },
      __Name__: { value: generateName(description) },
  })
  return symbol
}

var generateName = (function() {
    const createdMap = {}
    return function (description) {
        let suffix = createdMap[description]
        if(!suffix) suffix = 0
        suffix += 1
        createdMap[description] = suffix
        return `@@${description}${suffix}`
    }
})()
var symbolA = SymbolPolyfill('a')
var symbolA1 = SymbolPolyfill('a')

第二版：

思路：

禁止new，将desc转String
使用实例对象作为唯一值
给实例对象添加辨别属性，使用传入的desc入参填充

function SymbolPolyfill(desc) {
  if(this instanceof SymbolPolyfill) throw new Error('SymbolPolyfill is not a constructor.');
  if (desc) { desc = String(desc); }

  const symbol = Object.create(SymbolPolyfill.prototype);
  Object.defineProperties(symbol, {
      __Name__: defineValue(getName(desc)),
      __Description__: defineValue(desc)
  })
  return symbol;
}

function defineValue(value) {
    return {
        value,
        configurable: true,
        enumable: false,
        writable: false
    }
}

var getName = (() => {
  const m = new Map();
  return value => {
    const count = m.get(value) || 0;
    m.set(value, count + 1);
    return `@@${value}_${count + 1}`
  }
})()

Answer 2 · 2022-03-30T15:28:20.000Z

Day - 03

算法：https://leetcode-cn.com/problems/design-a-stack-with-increment-operation/

思路：

索引从-1开始增减
push时，注意maxSize的边界处理
pop时，注意所以小于0的处理
increment时，注意k值与maxSize的最小值处理

var CustomStack = function(maxSize) {
  this.stack = new Array(maxSize);
  this.cur = -1;
  this.boundary = maxSize - 1;
};

CustomStack.prototype.push = function(x) {
  if(this.cur >= this.boundary) return;
  this.cur++;
  this.stack[this.cur] = x;
};

CustomStack.prototype.pop = function() {
  if(this.cur < 0) return -1;
  const pop = this.stack[this.cur]
  this.stack[this.cur] = undefined;
  this.cur--;
  return pop;
};

CustomStack.prototype.increment = function(k, val) {
  const minLen = Math.min(this.stack.length, k);
  for(let i = 0; i < minLen; i++) {
    this.stack[i] += val;
  }
};

实现 allSettled：

function allSettled(promises) {
  if(!Array.isArray(promises)) {
    return Promise.resolve([]);
  }
  
  const len = promises.length;
  if(!len) return Promise.resolve([]);
  
  const result = new Array(len);
  // 原本使用result.length === len，但是这样无法使用new Array(len)，后续改用times
  let resolve, times = 0;
  for(let i = 0; i < len; i++) {
    const promise = transferPromise(promises[i]);
    promise
      .then(value => (result[i] = { status: 'fulfilled', value }))
      .catch(reason => (result[i] = { status: 'rejected', reason }))
      .finally(() => {
        times++;
        if(times !== len) return;
        resolve(result)
      })
  }
  return new Promise(res => { resolve = res })
}

function transferPromise(target) {
  if(target instanceof Promise) return target;
  return Promise.resolve(target);
}

第二版：

思路：

判断promises是否空数组，做Promise.resolve([])处理
遍历promises，并对then、catch相应状态做处理
根据不同的状态生成新的结构，根据索引塞入result数组中
在finally统计已完成的promise数量是否与promises长度对应，再控制新的promise bus做resolve

function allSettled(promises) {
  if(!Array.isArray(promises)) throw new TypeError(`${ promises } is not iterable.`)

  const len = promises.length;
  if(!len) return Promise.resolve([])

  const result = new Array(len);
  let count = 0, resolve;
  
  for(let i = 0; i < len; i++) {
    const promise = Promise.resolve(promises[i]);
    promise
    .then(value => result[i] = { status: 'fulfilled', value })
    .catch(reason => result[i] = { status: 'rejected', reason })
    .finally(() => {
      if(++count !== len) return;
      resolve(result);
    })
  }

  return new Promise(res => resolve = res);
}

Answer 3 · 2022-03-31T17:11:25.000Z

Day - 04

实现算法：https://leetcode-cn.com/problems/decode-string/

思路：

遍历s，未碰到']'字符时，一直收集
碰到']'后，向前取非'['字符拼接
碰到'['字符后，向前取数字字符拼接
碰到非数字后（字母、[、]，3中情况），根据数字拼接字符串
下一轮循环

var decodeString = function(s) {
  const stack = [];
  for(var char of s) {
    if(char !== ']') {
      stack.push(char);
      continue;
    }
    let curr = stack.pop();
    let str = '';
    while(curr !== '[') {
      str = curr + str;
      curr = stack.pop();
    }
    curr = stack.pop();
    let num = '';
    while(!isNaN(curr)) {
      num = curr + num;
      curr = stack.pop();
    }
    stack.push(curr);
    stack.push(str.repeat(num))
  }
  return stack.join('');
};

实现is函数：Object.is(value1, value2)

思路:

根据ECMA的SameValue规范，总结出以下需要特殊处理的内容：
处理NaN相同的判断
处理+-0不同的判断

function is(a, b) {
  if(a !== a) {
    return b !== b;
  }

  if(a === 0 && b === 0) {
    return 1 / a === 1 / b;
  }

  return a === b
}

Answer 4 · 2022-04-01T10:15:41.000Z

Day - 05

实现算法：https://leetcode-cn.com/problems/implement-queue-using-stacks/

思路：

cur指针初始化0，head指针初始化0
push时，cur指针++
pop时，head指针++
peek时，通过head指针
empty时，判断cur与head是否相等

var MyQueue = function() {
  this.queue = new Array(100);
  this.head = 0;
  this.cur = 0;
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
  this.queue[this.cur] = x;
  const isBondary = this.cur !== this.queue.length - 1
  this.cur = isBondary ? this.cur + 1 : 0;
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
  const result = this.queue[this.head];
  this.queue[this.head] = undefined;
  const isBondary = this.head !== this.queue.length - 1;
  this.head = isBondary ? this.head + 1 : 0;
  return result;
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
  return this.queue[this.head];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
  return this.cur === this.head
};

实现时针、分针夹角计算：
请计算出时钟的时针和分针的角度（两个角度的较小者，四舍五入）。时间以HH:mm的格式传入。

思路：

拆解YY:mm，1分 = 6°，1时 = 30°
计算mm角度mm * 6，并计算时针偏移量角度mm/60 * 30°
计算YY角度YY * 30°，并与偏移量角度相加
差角，时针 - 分针
取较小差角，判断差角是大于180°时，使用360° - 差角

function angle(time) {
  const [hours, minutes] = time.split(':');
  const HOUR_ANGLE = 360 / 12;
  const MINUTE_ANGLE = 360 / 60;
  
  const hourAngle = hours % 12 * HOUR_ANGLE;
  const hourOffsetAngle = minutes / 60 * HOUR_ANGLE;
  const minuteAngle = minutes * MINUTE_ANGLE;
  const calcAngle = Math.abs(hourAngle + hourOffsetAngle - minuteAngle);
  const finalAngle = calcAngle > 180 ? 360 - calcAngle : calcAngle;
  return Math.round(finalAngle);
}
angle('01:15') // 53°

Answer 5 · 2022-04-06T16:34:18.000Z

Day - 06

实现算法：https://leetcode-cn.com/problems/max-chunks-to-make-sorted-ii/solution/zui-duo-neng-wan-cheng-pai-xu-de-kuai-ii-by-leetco/

思路：

待补充

var maxChunksToSorted = function(arr) {
  const sortArr = arr.slice().sort();
  const map = new Map();
  let ans = 0;
  let nonzero = 0;
  for(let i = 0; i < arr.length; ++i) {
    const x = arr[i], y = sortArr[i];
    map.set(x, (map.get(x) ?? 0) + 1);
    if(map.get(x) === 0) nonzero--;
    if(map.get(x) === 1) nonzero++;

    map.set(y, (map.get(y) ?? 0) - 1);
    if(map.get(y) === -1) nonzero++;
    if(map.get(y) === 0) nonzero--;
    if(nonzero === 0) ans++;
  }

  return ans;
};

编程题：实现URLSearchParams。
第一版：未使用map

class MyURLSearchParams {
  /**
  * @params {string} init
  */
  constructor(init) {
    const search = this.formatSearchList(init)
    this.search = search.reduce((obj, item) => {
      if(!obj[item.key]) obj[item.key] = [];
      obj[item.key].push(item.value);
      return obj;
    }, {})
  }
  
  formatSearchList(str) {
    return str.replace(/^.*\?/, '').split('&').map(s => {
      const [k, v] = s.split('=');
      return { key: k, value: v }
    });
  }

  /** 
  * @params {string} name
  * @params {any} value
  */
  append(name, value) {
    if(!this.search[name]) this.search[name] = [];
    this.search[name].push(String(value));
  }
  
  /**
  * @params {string} name
  */
  delete(name) {
    delete this.search[name];
  }

  getEntiresBySearch() {
    const search = this.search;
    return Object.keys(search).reduce((arr, key) => {
      const valueArr = search[key].map(v => [key, v]);
      return arr.concat(valueArr);
    }, [])
  }
  
  /**
  * @returns {Iterator} 
  */
  *entries() {
    const entries = this.getEntiresBySearch();
    for(let i = 0; i < entries.length; i++) {
      yield entries[i];
    }
  }
  
  /**
  * @param {(value, key) => void} callback
  */
  forEach(callback) {
    const entries = this.getEntiresBySearch();
    entries.forEach(([k, v]) => {
      callback(v, k, this);
    })
  }
  
  /**
  * @param {string} name
  * returns the first value of the name
  */
  get(name) {
    const _name = name.replace(/^.*\?/, '');
    const value = this.search[_name];
    if(!Array.isArray(value)) return null;
    return this.search[_name][0];
  }
  
  /**
  * @param {string} name
  * @return {string[]}
  * returns the value list of the name
  */
  getAll(name) {
    return this.search[name] ?? [];
  }
  
  /**
  * @params {string} name
  * @return {boolean}
  */
  has(name) {
    return Boolean(this.search[name]);
  }
  
  /**
  * @return {Iterator}
  */
  *keys() {
    const entries = this.getEntiresBySearch();
    for(let i = 0; i < entries.length; i++) {
      yield entries[i][0];
    }
  }
  
  /**
  * @param {string} name
  * @param {any} value
  */
  set(name, value) {
    this.search[name] = [String(value)];
  }
  
  // sor all key/value pairs based on the keys
  sort() {
    const entries = this.getEntiresBySearch();
    const newEntries = entries.sort((a,b) => a[0].charCodeAt() - b[0].charCodeAt());
    const newSearch = newEntries.reduce((obj, entry) => {
      const [k, v] = entry
      if(!obj[k]) obj[k] = [];
      obj[k].push(v);
      return obj;
    }, {})
    this.search = newSearch;
  }
  
  /**
  * @return {string}
  */
  toString() {
    const search = this.search;
    return Object.keys(search).reduce((str, k) => {
      const serialize = search[k].reduce((_str, v) => {
        return _str + `&${k}=${v}`
      }, '');
      return str + serialize
    }, '').substring(1);
  }
  
  /**
  * @return {Iterator} values
  */
  *values() {
    const entries = this.getEntiresBySearch();
    for(let i = 0; i < entries.length; i++) {
      yield entries[i][1];
    }
  }
}

第二版：使用map

Answer 6 · 2022-04-07T10:17:17.000Z

Day - 07

实现算法：https://leetcode-cn.com/problems/rotate-list/

思路：

取链表实际长度，为了处理k > 链表长度的场景，从1开始方便计算
计算k取模并右移k次后，最后一个节点的位置
连接链表首位节点成环
链表右移至通过k计算的尾部节点
通过尾部节点，做链表去环处理

var rotateRight = function(head, k) {
  // 1. 取链表长度，因为涉及到长度处理的原因，所以从1开始计算
  let n = 1;
  let node = head;
  if(!head || !head.next || k === 0) return head;
  while(node.next) {
    node = node.next;
    n++;
  }
  // 2. 取右移k次后，最后一个节点的位置，如果k大于链表长度，取链表长度的模
  n = n - k % n;
  // 3. 链表首位相接成环
  node.next = head;
  // 4. 开始计算右移，最终得出来的node为尾部节点
  while(n) {
    node = node.next;
    n--;
  }
  // 5. 链表去环
  const result = node.next;
  node.next = null;
  return result;
};

Answer 7 · 2022-04-08T09:56:22.000Z

Day - 08

实现算法：https://leetcode-cn.com/problems/swap-nodes-in-pairs/

思路：

快慢指针node与preNode
两两替换：定义计数器变量count mod 2
满足2时，node、node.next、node.next.next进行替换，即使从1 -> 2 -> 3 => 2 -> 1 -> 3，看上去只是1和2替换，但这里还要注意1和2替换后，还要让1和3链上
替换时记得变更head节点，以及快节点替换完毕后，要链上慢节点

var swapPairs = function(head) {
  let count = 0;
  let node = head;
  let preNode = null;
  if(!head) return head;
  while(node.next) {debugger
    if(count % 2 === 0) {
      const temp1 = node;
      const temp2 = node.next.next;
      node = node.next;
      if(count === 0) head = node;
      node.next = temp1;
      temp1.next = temp2;
      if(preNode) preNode.next = node;
    }
    preNode = node;
    node = node.next;
    count++;
  }
  return head;
};

编程题：实现Object.create。
参考：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Object/create#polyfill

思路：

根据polyfill，非object对象都需要throw错误
接下来是需要new一个实例，并且改写实例的__proto__即可

function myObjectCreate(proto) {
  if(typeof proto !== "object" || proto === null) {
    throw new Error(`Expected object but received ${proto === null ? "null" : typeof proto}`);
  }
  const o = new Object();
  o.__proto__ = proto;
  return o;
}

Answer 8 · 2022-04-11T10:12:30.000Z

Day - 09

实现算法：https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

// Definition for singly-linked list.
class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}
// Definition for a binary tree node.
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

思路一：

拿到链表中所有节点的值，存储至数组，如果数组为无序，则进行升序排序
取数组中间索引作为当前层的头节点
左右子节点则，按二分法思路递归
分治：
4-1. 重复2、3，直到4-2
4-2. start索引大于end索引，返回null
分治结束，返回树头treeNode

function sortedListToBST(head: ListNode | null): TreeNode | null {
  const arr: number[] = [];
  while(head) {
    arr.push(head.val);
    head = head.next;
  }

  const buildBST = (start: number, end: number): TreeNode | null => {
    if(start > end) return null;
    const mid: number = Math.ceil((start + end) / 2);
    const node: TreeNode = new TreeNode(arr[mid]);
    node.left = buildBST(start, mid - 1);
    node.right = buildBST(mid + 1, end);
    return node;
  }

  return buildBST(0, arr.length - 1);
};

思路二：

定义快慢指针fast、slow，fast走2，slow走1
存储前一个slow节点，用于切断链表
fast走到终点时，slow则走到链表的一半，取slow作为当前层的二叉树root节点
切断slow节点之前的链表，分治递归left（从head开始）与right从（slow.next）开始
left与right节点递归，重复1-4，直到链表切成一个节点。
返回链表的头节点

function sortedListToBST(head: ListNode | null): TreeNode | null {
  if(head === null) return null;
  // 1. 定义快慢指针，慢跑1，快跑2，并记录慢指针的前一个节点
  let fast = head;
  let slow = head;
  let prev = null;
  // 2. fast跑完整个list，slow跑完list.length
  while(fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  // 3. 取slow当前位置作为当前层的root节点
  const root = new TreeNode(slow.val);
  // 4. 处理root.left与root.right
  if(prev !== null) {
    prev.next = null;
    root.left = sortedListToBST(head);
  }
  root.right = sortedListToBST(slow.next);
  return root;
};

思路三：

根据二叉搜索树中序遍历的结果，还原为遍历前二叉树

计算链表长度len，记录链表头指针headNode
使用二分法递归，按照二叉树中序遍历的逻辑，优先走left叶节点的递归，直接递归到最底部的左叶节点null，此时递归出栈后的上一个节点就是最底部的左叶节点，以此左叶节点为参照，找到最小的二叉树结构，进行优先构建：
取headNode链表节点进行左叶节点构建，即root.left，构建完毕headNode指针向headNode.next走
继续取headNode构建最小二叉树的root节点
递归headNode.right可能存在的叶节点，重复2
最终得到一个中序遍历前的二叉搜索树

function sortedListToBST(head: ListNode | null): TreeNode | null {
  // 1. 计算链表长度
  let len = 0;
  let headNode = head;
  while(head) {
    len++;
    head = head.next;
  }
  // 2. 递归分治，取数组**节点mid做为最小二叉树树根
  const buildBST = (start, end): TreeNode | null => {
    // 6. 递归至start > end时，代表到最底部，开始向上操作
    if(start > end) return null;
    const mid = Math.ceil((start + end) / 2);
    // 3. 左叶节点截取数组0, mid - 1，重复2
    const left = buildBST(start, mid - 1);
    // 5. 每个最小二叉树左叶节点处理完毕后，建立根节点，且控制链表指针往后挪（按中序遍历顺序挪动）
    const root = new TreeNode(headNode.val);
    headNode = headNode.next;
    root.left = left;
    // 4. 右叶节点截取mid + 1, arr.length - 1，重复2
    root.right = buildBST(mid + 1, end);
    return root;
  }
  return buildBST(0, len - 1)
};

编程题：实现EventEmitter

实现一个eventName多次subscribe，并且每次subscribe时返回一个sub对象
实现emit
实现sub.release，释放订阅

class EventEmitter {
  constructor() {
    this.eventMap = new Map();
  }

  subscribe(eventName, callback) {
    if(typeof callback !== 'function') return false;
  	if(!this.eventMap[eventName]) this.eventMap[eventName] = [];
    this.eventMap[eventName].push(callback);
    return {
      release: () => {
        const idx = this.eventMap[eventName].indexOf(callback);
        this.eventMap[eventName].splice(idx, 1);
      }
    }
  }
  
  emit(eventName, ...args) {
  	const eventList = this.eventMap[eventName];
    if(!Array.isArray(eventList)) return false;
    eventList.forEach(callback => {
      callback(...args);
    })
  }
}

Answer 9 · 2022-04-13T09:27:20.000Z

Day - 10

实现算法：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

思路一：

暴力法

第一次遍历塞入Set中
第二次遍历与Set比较是否存在重复
存在重复返回相应节点
不存在重复返回null
时间O(m+n)，空间O(m)（m为HeadA）

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  const set = new Set();
  while(headA) {
    set.add(headA);
    headA = headA.next;
  }

  while(headB) {
    if(set.has(headB)) {
      return headB;
    }
    headB = headB.next;
  }
  return null;
};

思路二：

双指针

场景1，链表A与链表B有相交节点C，且A和B长度相等，正常遍历即可
场景2，链表A与链表B有相交节点C，A和B长度不相等
2-1. 已知长度A + C + B === B + C + A
2-2. 使用双指针走链表A与链表B
2-3. A指针走完后往链表B走，B指针走完往链表A走，由于最终走的步伐相等，最终都会走到相交节点C上
2-4. 得到相交节点C
场景3，链表A与链表B没有相交节点，且A和B长度相等，正常遍历至null即可
场景4，链表A与链表B没有相交节点，A和B长度不相等
4-1. 同2-1
4-2. 同2-2
4-3. A指针走完后往链表B走，B指针走完往链表A走，由于最终走的步伐相等，最终都会走到null节点
4-4. 最终A与B指针都会指向null
时间：O(m+n)，空间O(1)

终上所述，只需要单次循环遍历即可，最终只需要判断指针A或指针B

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  const headNodeA = headA;
  const headNodeB = headB;
  while(headA !== headB) {
    headA = headA === null ? headNodeB : headA.next;
    headB = headB === null ? headNodeA : headB.next;
  }
  return headA;
};

Answer 10 · 2022-04-13T10:37:16.000Z

Day - 11

实现算法：https://leetcode-cn.com/problems/linked-list-cycle-ii/
暴力法

思路

开辟一个Set集合空间收集已遍历过的节点
遍历时保持与Set集合做校验，存在即有环
复杂度：时间O(n)，空间O(n)

function detectCycle(head: ListNode | null): ListNode | null {
    const set = new Set();
    while(head) {
      if(set.has(head)) return head;
      set.add(head);
      head = head.next;
    }
    return null;
};

双指针

思路

上下文说明：

a = 头节点到环的距离
b = 入环后走过的距离
c = 当前相遇点到环头的距离

公式推导：

slow = a + b
fast = 2 * slow
fast = a + n(b + c) + b
=> 2(a + b) = a + n(b + c) + b
=> 2a + 2b = a + nb + nc + b
a = nb - b + nc
a = nb - b + nc - c + c
a = (n - 1)(b + c) + c

该公式代表`a到入环的距离`，为`fast与slow相遇节点到入环节点的距离` + `n - 1圈`

先通过fast + 2，slow + 1的方式找到是否有环，以及相遇的节点c
找到相遇节点后，根据上面推导出来的公式可得：遍历头节点head与相遇节点c直到相遇
相遇点即为入环点（不知道为何，根据公式推导而来，反复画链表验证后确实如此）
处理边界场景：无环，单节点环场景
复杂度：时间O(n)，空间O(1)

function detectCycle(head) {
  if(!head || !head.next) return null;
  if(head === head.next) return head;
  let fast = head;
  let slow = head;
  while(fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if(fast === slow) break;
  }
  while(fast && fast.next) {
    if(fast === head) return head;
    head = head.next;
    fast = fast.next;
  }
  return null
};

编程题：实现Promise.any

思路

只有一个成功，返回成功的
全部失败，返回失败的error对象，并返回所有reject信息

function any(promises) {
  // your code here
  const len = promises.length;
  let resolve, reject, errors = [];
  for(let i = 0; i < len; i++) {
    promises[i]
    .then(resp => resolve(resp))
    .catch(error => { errors[i] = error })
    .finally(() => {
      if(errors.length !== len) return
      const rejectInfo = new Error(
        'No Promise in Promise.any was resolved', 
        errors
      )
      reject(rejectInfo)
    })
  }
  return new Promise((res, rej) => {
    resolve = res;
    reject = rej;
  })
}

Answer 11 · 2022-04-15T15:11:09.000Z

Day - 12

实现算法，LRU缓存：https://leetcode-cn.com/problems/lru-cache/submissions/

思路

建立双向链表、Map存储空间cache
put时将新的节点insert到尾结点tail.prev，同时对前后节点做插入处理，并录入缓存cache
get时将缓存中的节点继续insert到尾结点tail.prev，同时对前后节点做插入处理
get边界：缓存中没有，返回-1
put边界1：缓存长度如大于限定长度capacity，则清理头节点head之前的节点，并删除缓存cache中对应的key
put边界2：缓存如果有相同的key，删除原cacheNode，并继续insert新的Node

class DoubleLink {
  key: number;
  val: number;
  prev: DoubleLink | void;
  next: DoubleLink | void;

  constructor(key: number, val: number) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }

  removeNode() {
    if(this.prev) {
      this.prev.next = this.next;
    }
    if(this.prev && this.next) {
      this.next.prev = this.prev
    }
    this.prev = null;
    this.next = null;
    return this;
  }

  addNode(node) {
    this.next = node;
    node.prev = this;
  }

  insertNode(node) {
    if(this.prev) {
      this.prev.next = node;
      node.prev = this.prev;
    }
    this.prev = node;
    node.next = this;
  }
}
class LRUCache {
  cache: Map<number, DoubleLink> = new Map();
  head: DoubleLink = new DoubleLink(0, 0);
  tail: DoubleLink = new DoubleLink(0, 0);
  capacity: number;
  constructor(capacity: number) {
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    const cacheNode = this.cache.get(key);
    if(cacheNode) {
      cacheNode.removeNode();
      this.tail.insertNode(cacheNode);
      return cacheNode.val;
    }
    return -1;
  }

  put(key: number, value: number): void {
    const cacheNode = this.cache.get(key)
    const node = new DoubleLink(key, value);
    this.cache.set(key, node);
    this.tail.insertNode(node);
    if(cacheNode) {
      cacheNode.removeNode();
      return;
    }
    if(this.cache.size > this.capacity && this.head.next) {
      const head = this.head.next.removeNode();
      this.cache.delete(head.key);
    }
  }
}

编程题：实现Promise.race

function race(promises) {
  let resolve, reject;
  for(let i = 0, len = promises.length; i < len; i++) {
    promises[i].then(resolve).catch(reject);
  }
  return new Promise((res, rej) => {
    resolve = res;
    reject = rej;
  })
}

Answer 12 · 2022-04-19T11:51:07.000Z

Day - 13

实现算法：二叉树的最大深度

思路：

dfs中序遍历思路，直接到左侧left的左叶节点，到最深处后往右侧right的右叶节点
只要到了null节点后返回0
非null节点时，则判断left和right节点的执行结果取最大值，并+1，得到的就是当前节点的深度
直到root节点，得到整棵树的深度
时间复杂度：O(n)

function maxDepth(root: TreeNode | null): number {
  if(!root) return 0;
  const left = maxDepth(root.left);
  const right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

编程题：实现对象合并时，只更新不相同的值

思路：

判断判断类型是否相等，不相等返回false
类型不相等，判断是否为对象，非对象时代表基础类型，必定false
如果是对象，state与modify拆成每个属性进行判断，只要存在不相等，就为true
每次对象递归，都需要判断一次state与modify的key长度是否相等

type ProduceFunc = <T>(base: T, receipe: (draft: T) => any) => void

const state = [
  {
    name: 'BFE',
  },
  {
    name: '.',
  }
]

const compare = (base: any, modify: any) => {
  if(typeof base !== typeof modify) return false;
  if(typeof base !== 'object') return base === modify;
  let isEqual = true;
  for(let key of Object.keys(base)) {
    if(compare(base[key], modify[key])) {
      modify[key] = base[key];
      continue;
    }
    isEqual = false;
  }
  return Object.keys(base).length === Object.keys(modify).length && isEqual;
}

const produce: ProduceFunc = (base, recipe) => {
  // your code here
  const modify = JSON.parse(JSON.stringify(base))
  recipe(modify)
  if(compare(base, modify)) return base;
  return modify;
}

const newState = produce(state, draft => {
  draft.push({name: 'dev'})
  draft[0].name = 'bigfrontend'
  draft[1].name = '.' // set为相同值。
})

Answer 13 · 2022-04-22T04:03:57.000Z

Day - 14

实现算法：相同的树

思路

用dfs深度遍历
递归判断树1和树2的节点同时为null，返回true
若不是同时为空，只要存在一个null，返回false
判断树1和树2节点的val是否相同
进行左右节点的dfs

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if(p === q) return true;
  if(p === null || q === null) return false;
  if(p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

编程题：实现JSX解析

思路：

字符串转JSX

针对传入的code进行parse，通过slice(1)与indexOf('>')拆开标签，得到标签名
拆完整个开标签后，对children进行逐个字符串遍历
如果字符非<开头，则可当做文本节点进行字符作为children的收集
如果字符为<，则在不影响循环字符的索引情况下，向下递归，寻找是否有/字符，有为闭合标签，结束本次children的收集（这点的逻辑应该后置，一般情况下有嵌套的场景都不会立即遇上闭合标签，都是先逐级递归开放标签，类似括号嵌套算法的思路: [(())]）
如果没找到/，但找到了>字符，代表需要重复第一点进行标签拆解（开始递归，从第1点开始，直到满足第4点为止）
边界：注意一些允许空格的场景判断，以及开闭标签的/字符处理

JSX转AST

只是数据结构的转变

type JSXOpeningElement = {
  tag: string
}

type JSXClosingElement = {
  tag: string
}

type JSXChildren = Array<string | JSXElement>

type JSXElement= {
  openingElement: JSXOpeningElement
  children: JSXChildren
  closingElement: JSXClosingElement
}

function checkCloseTag(str: string, i: number): boolean {
  if(str[i] === '/') return true;
  if(str[i] === '>') return false;
  return checkCloseTag(str, i + 1);
}

function parseChildren(str: string): [JSXChildren, number] {
  // 判断当前标签是否结束
  // 非结束标签，则进行递归parse函数，并收集文字
  // 递归完毕后拿到子元素的内容，存到child数组中备用号
  // 如果既不是openTag也不是closeTag，则按文字处理，收集字符文字
  const children = [];
  let text = '';
  let i = 0;

  for(; i < str.length; i++) {
    if(str[i] !== '<') {
      text += str[i];
      continue;
    }
    // 闭合标签
    if(checkCloseTag(str, i)) break;
    if(text) {
      children.push(text);
      text = '';
    }
    const childTag = codeParse(str.slice(i));
    children.push(formatJSX(childTag));
    i += childTag.closeTagEndIndex;
  }
  if(text) children.push(text);
  return [ children, i ]
}

function parseTag(str: string): [number, string, boolean] {
  const tagEndIndex = str.indexOf('>');
  let tagName = str.slice(1, tagEndIndex).trim();
  let isClose = false;
  if(tagName[0] === '/') {
    tagName = tagName.slice(1).trim();
    isClose = true
  }
  return [tagEndIndex, tagName, isClose]
}

function formatJSX({ openTagName, closeTagName, children }: Record<string, any>) {
  return {
    openingElement: { tag: openTagName },
    closingElement: { tag: closeTagName },
    children
  }
}

function codeParse(code: string) {
  code = code.trim()
  if (
    (code[0] !== "<" || code[code.length - 1] !== ">") ||
    code.split("<").length !== code.split(">").length
  ) {
    throw new Error("");
  }
  // 记录当前字符的位置
  let i = 1
  // 解析开标签
  const [ openTagEndIndex, openTagName ] = parseTag(code);
  // 去掉开标签字符
  code = code.substr(openTagEndIndex + 1, code.length)
  // 同步字符的索引
  i += openTagEndIndex;
  // 解析子节点
  const [ children, skipIndex ] = parseChildren(code)
  //  去掉子节点的字符
  code = code.substr(skipIndex, code.length)
  // 同步位置
  i += skipIndex;
  // 闭合标签，接下来两个行代码同上
  const [ closeTagEndIndex, closeTagName, isClose ] = parseTag(code);
  code = code.substr(closeTagEndIndex, code.length)
  i += closeTagEndIndex;

  if(!isClose || openTagName !== closeTagName) {
    throw new Error(`isClose: ${isClose}, openTagName: ${openTagName}, closeTagName: ${closeTagName}`);
  }
  return {
    openTagName,
    closeTagName,
    children,
    closeTagEndIndex: i // 目的是为了子节点碰到标签需要递归时，知道目前位置到哪里了
  }
}

function parse(code: string): JSXElement {
  // your code here
  const codeJSON = codeParse(code);
  return formatJSX(codeJSON);
}

function generate(ast: JSXElement | string): Record<string, any> | string {
  if(typeof ast === 'string') return ast;
  const tagName = ast.openingElement.tag;
  const type = tagName[0] === tagName[0].toUpperCase() ? Heading : tagName
  const node = {
    type,
    props: {
      children: ast.children.map(generate)
    }
  }
  return node;
}

const str = "  <  a  >  bfe.dev  <  /  a  >  "
console.log((parse(str)))

Answer 14 · 2022-04-22T16:21:21.000Z

Day - 15

实现算法：129. 求根节点到叶节点数字之和

思路一：

dfs深度优先

每次向下一层节点移动时，都会把上一级累加的节点向下传递，并且位数进一（prevSum * 10），这样累加才能起到类似字符拼接的效果
当左右叶节点都为null时，代表到达最根部，代表当前路径累加结束，得到该路径的累加值
因为到达最根部才算一次结果，所以每次向上return时都要进行一次left与right的累加，直到递归的顶部root节点，会以left与right的总和进行累加，类似CEO只需要对接left与right两个VP角色一样。（应该可以理解为分治）
时间：O(n)，取决于节点个数
空间：O(n)，递归栈空间消耗，取决于树的高度，最坏情况下节点数 === 树高 === 栈消耗（链表）

var sumNumbers = function(root) {
  const dfs = (root, prevSum = 0) => {
    if(!root) return null;
    const sum = prevSum * 10 + root.val;
    if(root.left === null && root.right === null) return sum;
    return dfs(root.left, sum) + dfs(root.right, sum)
  }
  return dfs(root);
};

思路二：

BFS广度优先

广度优先基本概念，每次读到的节点node，都要使用队列存储node.left与node.right
由于该题要记录的是拼接值，所以还需加一个拼接值的队列，用于记录当前节点走过路径每一个值的拼接累加
即有两个队列：节点队列：queueNode与节点对应路径路净值队列：queueNum
剩下的按广度优先遍历方式走，按3种场景处理
场景1：叶尾节点，累加当前节点对应的路径值即可
场景2、3：单边存在叶节点，继续广度优先遍历

var sumNumbers = function(root) {
  if(root === null) return 0;
  let sum = 0;
  // 广度优先的两个队列：记录节点，与当前节点累计的拼接值
  const queueNode = [root], queueNum = [root.val];
  while(queueNode.length) {
    // 取出root，后续存root.left与root.right，以此类推，永远都是把上一层的所有子节点先跑完
    const node = queueNode.shift();
    // 取出当前节点对应的累计拼接值，思路上一行的node
    const num = queueNum.shift();
    const left = node.left, right = node.right;
    // 场景1：到达叶尾节点场景，因为在下来之前已经把当前节点加上了，这里只需累加至sum变量做统计即可
    if(left === null && right === null) {
      sum += num;
      continue;
    }
     // 场景2：只有单左叶节点场景
    if(left) {
      queueNode.push(left);
      queueNum.push(num * 10 + left.val);
    }
    // 场景3：只有单右叶节点场景
    if(right) {
      queueNode.push(right);
      queueNum.push(num * 10 + right.val);
    }
  }
  return sum;
};

编程题: 去除字符

给定只含有a、b 和 c的字符串，请去掉其中的b 和 ac。

removeChars('ab') // 'a'
removeChars('abc') // ''
removeChars('cabbaabcca') // 'caa'

思路：

使用括号栈的思路存a
如果有c则pop一次a的记录，如果有c栈没有a，则将c字符收集起来
如果出现b字符，不收集
直到字符遍历结束后，如果栈中还存在a，则将栈的a进行拼接后收集

function removeChars(str) {
  const arrStr = str.split('');
  const stack = [];
  let result = ''
  for(let i = 0; i < arrStr.length; i++) {
    if(str[i] === 'a') {
        stack.push(str[i]);
        continue;
    }
    if(str[i] === 'c' && stack.length) {
        stack.pop();
        continue;
    }
    if(str[i] === 'b') continue;
    result += str[i];
  }
  result = result + stack.join('')
  return result;
}
removeChars('acacabbaabcca')

Answer 15 · 2022-04-22T16:22:53.000Z

Day - 16

实现算法：513. 找树左下角的值

思路一：

BFS广度优先

第一层循环判断队列是否还有节点
第二层循环消费上一层所有节点，并收集上一层所有子叶节点
每次判断队列是否有值的循环，去尝试拿一次最左叶节点的值（队列首个节点为最深层左下角节点）

var findBottomLeftValue = function(root) {
  if(!root) return null;
  const queue = [root];
  let result = null;
  while(queue.length) {
    result = queue[0]; // 每层都尝试拿一次最左的值
    for(let i = 0, len = queue.length; i < len; i++) {
      const node = queue.shift();
      if(node.left) queue.push(node.left);
      if(node.right) queue.push(node.right);
    }
  }
  return result.val;
};

思路二：

DFS深度优先

靠记录最深路径，取首个最深路径的节点值作为结果存储
DFS一般是先左再右遍历，所以首次开辟更深一层的节点，就是当前这一层最左的值

var findBottomLeftValue = function(root) {
  let maxPath = 0;
  let resNode = root;
  const dfs = (root, curPath = 1) => {
    const isEnd = !Boolean(root.left) && !Boolean(root.right);
    console.log(root, maxPath, curPath)
    if(isEnd && maxPath < curPath) {
      maxPath = curPath;
      resNode = root.val;
    }
    curPath++
    if(root.left) dfs(root.left, curPath);
    if(root.right) dfs(root.right, curPath);
  }
  dfs(root);
  return resNode;
};

编程题: 实现一个LazyMan

思路：

关键点：待执行队列、链式调用、每次执行完某个动作，都要run一次
每次向待执行队列queue push时，都要激活一次清空队列的命令run，因为程序并不知道你什么时候才算push完毕，算是一种技巧性思路
run的时候，从队列queue取函数执行，都要用Promise包裹一层，保证按序执行
记录sleepFirst的次数，单纯用unshift会有执行顺序问题

LazyMan(“Hank”)
// 输出:
// Hi! This is Hank!

LazyMan(“Hank”).sleep(10).eat(“dinner”)
// 输出：
// Hi! This is Hank!
// 等待10秒..
// Wake up after 10
// Eat dinner~

LazyMan(“Hank”).eat(“dinner”).eat(“supper”)
// 输出:
// Hi This is Hank!
// Eat dinner~
// Eat supper~
LazyMan(“Hank”).eat(“supper”).sleepFirst(5)
// 输出:
// 等待5秒
// Wake up after 5
// Hi This is Hank!
// Eat supper

class LazyMan {
  constructor(name = 'tiny') {
    this.queue = [];
    this.timer = null;
    this.firstCount = 0;
    console.log(`Hi! This is ${name}!`)
  }

  run() {
    if(this.timer) clearTimeout(this.timer);
    this.timer = setTimeout(() => { 
      if(!this.queue.length) return;
      const fn = this.queue.shift();
      Promise.resolve(fn()).then(this.run.bind(this))
    });
    return this;
  }

  eat(str) {
    this.queue.push(() => console.log(str))
    return this.run();
  }

  sleep(time) {
    const p = () => new Promise(resolve => setTimeout(() => {
        console.log(`Wake up after ${time}`)
        resolve();
    }, time * 1000))
    this.queue.push(p)
    return this.run()
  }

  sleepFirst(time) {
    const p = () => new Promise(resolve => setTimeout(() => {
        console.log(`等待${time}秒`)
        resolve();
    }, time * 1000))
    this.queue.splice(this.firstCount, 0, p)
    this.firstCount++;
    return this.run()
  }
}
var l = new LazyMan();
l.sleep(3).eat('dinner').sleep(3).eat('supper').sleepFirst(1).sleepFirst(2);

Answer 16 · 2022-04-22T16:24:16.000Z

Day - 17

实现算法：297. 二叉树的序列化与反序列化

思路一：

BFS广度优先遍历
serialize按广度优先生成string
deserialize也按广度优先的顺序拆解string，并生成二叉树

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
  if(root === null) return null;
  const queue = [root];
  const result = [];
  while(queue.length) {
    const node = queue.shift();
    result.push(node ? node.val : 'null');
    if(!node) continue;
    queue.push(node.left ? node.left : null);
    queue.push(node.right ? node.right : null);
  }
  console.log(result.join(','))
  return result.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if(!data) return null;
    const arr = data.split(',')
    const root = new TreeNode(arr.shift());
    const queue = [root];
    while(queue.length) {
      const node = queue.shift();
      if(node === 'null') continue;
      const left = arr.shift()
      if(left !== 'null') {
        node.left = new TreeNode(left);
        queue.push(node.left);
      }
      const right = arr.shift()
      if(right !== 'null') {
        node.right = new TreeNode(right);
        queue.push(node.right);
      }
    }
    return root;
};

思路二：

序列化：按DFS优先遍历的顺序记录字符串
反序列化：同上的优先遍历顺序，通过字符串生成树

var serialize = function(root) {
  const result = [];
  const dfs = (root, result) => {
    if(root === null) {
      result.push('null')
      return 'null';
    }
    result.push(root.val);
    dfs(root.left, result);
    dfs(root.right, result);
  }
  dfs(root, result);
  return result.join(',');
};

var deserialize = function(data) {
    if(!data) return null;
    const arr = data.split(',')
    const dfs = (arr) => {
      const val = arr.shift();
      if(val === 'null') return null;
      const root = new TreeNode(val);
      root.left = dfs(arr);
      root.right = dfs(arr);
      return root;
    }
    return dfs(arr);
};

编程题: 渲染百万条结构简单的大数据时怎么使用分片**优化渲染 todo

Answer 17 · 2022-04-22T16:29:04.000Z

Day - 18

实现算法：987. 二叉树的垂序遍历

思路：

使用dfs拿到每个节点的row、col、value三个值
并按col、row、value进行升序排序
- 即col相等，按row排；row相等，按value排
排序完成后装箱，记录当前的最大值，与col进行对比，不相等则代表不同列，新建一块数组空间收集

var verticalTraversal = function(root) {
  const entries = dfs(root);
  entries.sort((a,b) => {
    if(a[1] !== b[1]) return a[1] - b[1];
    if(a[0] !== b[0]) return a[0] - b[0];
    return a[2] - b[2];
  })
  const result = [];
  let maxNum = -Number.MAX_VALUE
  for(let arr of entries) {
    if(arr[1] !== maxNum) {
      maxNum = arr[1];
      result.push([arr[2]])
      continue;
    }
    result[result.length - 1].push(arr[2]);
  }
  return result
};

const dfs = (root, row = 0, col = 0, nodes = []) => {
  if(root === null) return null;
  nodes.push([row, col, root.val]);
  dfs(root.left, row + 1, col - 1, nodes);
  dfs(root.right, row + 1, col + 1, nodes);
  return nodes;
}

编程题：请实现 DOM2JSON 一个函数，可以把一个 DOM 节点输出 JSON 的格式

思路：

简单的递归和属性筛选，通过elem.childNodes属性递归

function dom2JSON(elem) {
  const json = {
    nodeType: elem.nodeType
  }
  if(elem.nodeType === 1) {
    json.tagName = elem.tagName.toLowerCase();
    json.className = elem.className;
    console.log(elem, elem.attributes)
    json.attrs = Object.keys(elem.attributes).reduce((obj, key) => {
      const attr = elem.attributes[key];
      if(attr.name === 'class') return obj;
      obj[attr.name] = attr.nodeValue;
      return obj;
    }, {})
    json.children = Array.from(elem.childNodes).map(dom2JSON);
    return json;
  }
  json.children = [elem.nodeValue]
  return json
}

Answer 18 · 2022-04-25T13:31:20.000Z

Day - 19

实现算法：1. 两数之和

思路：

通过HashMap记录跑过的数字及索引
遍历直至找到map中存在target - num的值
返回target - num的索引，及当前索引
由于使用了HashMap查找，查找时的速度是O(1)，所以整体的时间复杂度为O(N)，取决于数组长度，空间复杂度O(N)，取决于HashMap的开销。
暴力法即双循环，时间复杂度为O(n^2)，空间复杂度O(1)，最坏情况下都需要匹配一次

var twoSum = function(nums, target) {
  const map = new Map();
  for(let i = 0; i < nums.length; i++) {
    const t = target - nums[i]
    if(map.has(t)) return [map.get(t), i];
    map.set(nums[i], i);
  }
};

编程题：实现函数柯里化compose

function compose(...fns){
  return fns.reduce((a, b) => ...args => a(b(...args)))
}
const multiply20 = (price) => price * 20;
const divide100 = (price) => price / 100;
const normalizePrice = (price) => price.toFixed(2);
const discount = compose(normalizePrice, divide100, multiply20);
discount(200.0); //40.00

Answer 19 · 2022-04-25T13:32:17.000Z

Day - 20

实现算法：347. 前 K 个高频元素

思路：

根据二叉堆 + 优先队列概念，最大堆会优先将最大值踢出队列，最小堆会优先将最小值优先踢出队列
取高频元素代表会频繁记录，并再记录的同时踢出最小元素，所以使用最小堆结构符合题目思路
时间复杂度：遍历数组O(N) + 堆操作O(logN)，即O(N logN)

var topKFrequent = function(nums, k) {
  if(!nums.length) return [];
  const m = new Map();
  nums.sort().forEach(num => {
    let count = m.get(num);
    if(!count) count = 0;
    m.set(num, ++count);
  })

  const p = new PriorityQueue();
  const entries = m.entries()
  for(let [num,v] of entries) {
    if(p.queue.length < k) {
      p.enqueue(v, num)
      continue;
    }
    const head = p.getHead();
    console.log(num, v, head.p, p.queue.length)
    if(v > head.p) {
      p.outqueue();
      p.enqueue(v, num);
    }
  }
  return p.queue.sort((a,b) => {
    if(a.p !== b.p) return b.p - a.p;
    return a.p - b.p;
  }).map(({v}) => v);
};

class PriorityQueue {
  queue = [];

  getHead() { return this.queue[0] }

  enqueue(p, v) {
    this.queue[this.queue.length++] = {p, v};
    this.upAdjust();
  }

  upAdjust() {
    let childIndex = this.queue.length - 1;
    let parentIndex = Math.floor((childIndex - 1) / 2);
    let temp = this.queue[childIndex];
    while(childIndex > 0 && temp.p < this.queue[parentIndex].p) {
      this.queue[childIndex] = this.queue[parentIndex];
      childIndex = parentIndex;
      parentIndex = Math.floor((childIndex - 1) / 2);
    }
    this.queue[childIndex] = temp;
  }

  outqueue() {
    if(!this.queue.length) return null;
    const head = this.queue[0]
    const last = this.queue.pop();
    if(this.queue.length) {
      this.queue[0] = last;
      this.downAdjust();
    }
    return head;
  }

  downAdjust(parentIndex = 0) {
    const temp = this.queue[parentIndex];
    let childIndex = 1;
    while(childIndex < this.queue.length) {
      const nextChildIndex = childIndex + 1;
      if(
          nextChildIndex < this.queue.length
          && this.queue[nextChildIndex].p < this.queue[childIndex].p
      ) childIndex++;
      if(temp.p <= this.queue[childIndex].p) break;
      this.queue[parentIndex] = this.queue[childIndex];
      parentIndex = childIndex;
      childIndex = 2 * parentIndex + 1;
    }
    this.queue[parentIndex] = temp;
  }
}

编程题：请使用vue或者react实现断点续传 todo

Answer 20 · 2022-05-08T19:10:24.000Z

Day - 21

实现算法：447. 回旋镖的数量

思路：

O式距离代表点与点的坐标值之间相减平方。（(x1 - x2)^2 + (y1 - y2)^2）
回旋镖代表以某个坐标点为基准，有2个点的O式距离相等即可。
以一个基点为主，枚举各个点之间的距离，每个点都作为一次单独的距离统计。（双循环枚举）
最后统计按 num * (num - 1)的公式进行统计，这里不太理解。（猜想：一个回旋镖最多只会满足2个点，但是可以来回统计，假设一个基点有4个相同距离，则有6种连线方式，满足回旋则是2倍的数量）

var numberOfBoomerangs = function(points) {
  let count = 0;
  for(let i = 0; i < points.length; i++) {
    const m = new Map();
    for(let j = 0; j < points.length; j++) {
      const [x1,y1] = points[i];
      const [x2,y2] = points[j];
      const distance = Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2);
      const historyDistance = m.get(distance) || 0
      m.set(distance, historyDistance + 1);
    }
    for(let [_, times] of m.entries()) {
      count += times * (times - 1);
    }
  }
  return count
};

编程题：实现类型体操Trim

type Ident = ' ' | '\t' | '\n'
type Trim<T extends string> = T extends `${Ident}${infer TL}` 
                            ? Trim<TL> 
                              : T extends `${infer TR}${Ident}` 
                              ? Trim<TR> 
                            : T;

Answer 21 · 2022-05-08T19:24:21.000Z

Day - 22

实现算法：3. 无重复字符的最长子串

思路一：for循环滑动窗口

使用for循环做滑动窗口，i可以看做是左侧窗口边界，pointer是右侧边界
每次循环都要将左侧边界右移一次（有疑问看第4点），首次除外
for循环开始后，使用while循环让pointer指针一直右移，并使用set结构记录，直到出现重复的值后停止while循环，并统计max值
由于for的i加1代表pointer指针已经出现重复了，进入一次新的for循环，直到左侧边界不会出现与set重复的字符即可

// 版本1
var lengthOfLongestSubstring = function(s) {
  const set = new Set(), len = s.length;
  let pointer = -1, max = 0;
  for(let i = 0; i < len; i++) {
    if(i !== 0) set.delete(s[i - 1]);
    // 判断是否到最后一个字符，如果没到则看有没重复字符
    while(pointer + 1 < len && !set.has(s[pointer + 1])) {
      pointer++;
      set.add(s[pointer]);
    }
    max = Math.max(max, set.size);
  }
  return max;
};

// 版本2
var lengthOfLongestSubstring = function(s) {
  const set = new Set(), len = s.length;
  let pointer = 0, max = 0;
  for(let i = 0; i < len; i++) {
    if(i !== 0) set.delete(s[i - 1]);
    while(pointer < len && !set.has(s[pointer])) {
      set.add(s[pointer]);
      pointer++;
    }
    max = Math.max(max, set.size);
  }
  return max;
}

思路二：left、right的while循环双指针滑动窗口

大致思路与for循环类似，双指针滑动窗口
区别1：可读性更高
区别2：right每次都要进行一次计算，for循环只会在右侧边界出现重复时进行max计算

var lengthOfLongestSubstring = function(s) {
  const set = new Set(), len = s.length;
  let left = 0, right = 0, max = 0;
  while(right < len) {
    if(set.has(s[right])) {
      set.delete(s[left]);
      left++;
      continue;
    }
    set.add(s[right]);
    right++;
    max = Math.max(max, right - left);
  }
  return max;
}

Day - 23

实现算法：30. 串联所有单词的子串

思路：

题意：
- 字符串数组必须全部使用上，但不分顺序
- 数组内字符长度一致如['foo', 'bar', 'cdd', 'egg']或['aaaa', 'bbbb']或['aaaaa', 'bbbbb']

由于子串单词不需要按序比较，所以只需统计单词出现的次数即可（map或obj存储）
利用双循环跑滑动窗口，由于只需满足子串长度，所以第一层循环只需到 i + wordsTotalLen的长度即可

第二层循作为窗口范围，即当前i + wordsTotalLen作为窗体，使用 j + 数组单个字符长度裁剪，对之前存储map对象进行对比

如果map中出现此单词，做递减，并用count统计数组内单词是否使用完，如果使用完毕，代表当前i位置出现过该子串
若果未出现，或者map中单词数量为0，代表该字符未匹配到数组子串，第一层循环的i往下走
时间：最优O(n)，最差O(n - k * k)，k：数组字符总长度(words[0] * words.length)
空间：O(m)，m：数组字符的单词数

var findSubstring = function(s, words) {
  const len = s.length;
  const wordSize = words[0].length;
  const wordTotalLen = wordSize * words.length;
  const ans = [];
  const wordMap = words.reduce((obj, word) => {
    obj[word] = (obj[word] || 0) + 1;
    return obj
  }, {})

  for(let i = 0, actualLen = len - wordTotalLen; i <= actualLen; i++) {
    const tempMap = { ...wordMap };
    let count = words.length;
    for(let j = i; j < i + wordTotalLen; j += wordSize) {
      const word = s.slice(j, j + wordSize);
      if(!(word in tempMap) || tempMap[word] <= 0) break;
      tempMap[word]--;
      count--;
    }
    if(count === 0) ans.push(i);
  }
  return ans;
};

编程题：手写vuex新版和老版 todo

Answer 22 · 2022-05-08T19:31:12.000Z

Day - 24

实现算法：Delete Sublist to Make Sum Divisible By K

思路：

没看明白，先记录后续再回来看看

class Solution {
  solve(nums, k) {
    if(!nums.length) return -1;
    let target = 0;
    target = nums.reduce((a,b) => a+b) % k;
    if (target == 0) return 0;
    const map = new Map();
    map.set(0,0);
    let pos = 0, now = 0, ans = nums.length;
    for(let num of nums) {
      pos++;
      now = (now + num) % k;
      if(map.has((now + k - target) % k)) {
        ans = Math.min(ans, pos - map.get((now + k - target) % k))
      }
      map.set(now, pos);
    }
    return ans === nums.length ? -1 : ans;
  }
}

编程题：实现类型体操 Partial

思路：

题目的思路较简单，围绕着筛选和剔除，并全部重写对象，再合并的思路即可完成
剔除：重新设一个剔除掉没有K属性的对象
筛选：重新设一个筛选出有K属性的对象，并标记为?可选属性
以上两点需要注意，如果想返回对应的类型，可先keyof后再传入，否则再extends之后就没法再拿到当前约束单个的keyof T

interface Demo {
  a: string,
  b: number
}

// bad
type Exclude<T, K> = keyof T extends K ? never : keyof T;
Exclude<Demo, 'a'>

// goods
type Exclude<T, K> = T extends K ? never : T;
Exclude<keyof Demo, 'a'>

最后进行类型合并

type Merge<T> = { [K in keyof T]: T[K] };
type Exclude<T, K> = T extends K ? never : T;
type Include<T, K> = T extends K ? T : never;
type PartialByKeys<T, K = keyof T> = { [ k in Exclude<keyof T, K> ]: T[k]} & { [ k in Include<keyof T, K> ]?: T[k] }

扩展：

封装了Omit对象属性剔除与Merge对象合并

type Merge<T> = { [ k in keyof T]: T[k] };
type Include<T, K> = T extends K ? T : never;
type Exclude<T, K> = T extends K ? never : T;
type Pick<T, K extends keyof T> = { [ k in K ]: T[k] };
type Omit<T, K> = Pick<T, Exclude<keyof T, K>>;

type Partial<T, K> = Merge<Omit<T, K> & { [ k in keyof Include<keyof T, K> ]?: T[k] }>

Answer 23 · 2022-05-08T19:31:46.000Z

Day - 25

实现算法：876. 链表的中间结点

思路一：

完全遍历得到长度后，再根据链表总长度的一半，遍历找到对应的中间节点
时间：O(N)要遍历链表长度，空间：O(1)

var middleNode = function(head) {
  let curr = 0, len = 0, node = head;
  while(node) {
    len++;
    node = node.next;
  }
  const mid = Math.floor(len/2);
  node = head;
  while(curr < mid) {
    curr++;
    node = node.next;
  }
  return node;
};

思路二：

使用数组作为额外空间，遍历链表时都存入相应的节点
链表遍历完毕后，取数组长度的一半作为索引，取中间值
时间：O(N)同思路一，空间：O(N)数组与链表长度一致

var middleNode = function(head) {
  let node = head;
  const arr = [];
  while(node) {
    arr.push(node);
    node = node.next;
  }
  return arr[Math.floor(arr.length / 2)]
};

编程题：简单实现双向绑定Two-way binding

// 实现model满足下面的逻辑
const input = document.createElement('input')
const state = { value: 'BFE' }
model(state, input)

console.log(input.value) // 'BFE'
state.value = 'dev'
console.log(input.value) // 'dev'
input.value = 'BFE.dev'
input.dispatchEvent(new Event('change'))
console.log(state.value) // 'BFE.dev'

思路：

数据侧，使用了defineProperty拦截setter，拿到setter给的val后对DOM进行操作
DOM侧，熟悉DOM则非常简单，利用了元素本身支持的事件派发api，只需定义callback并且操作state即可

type State = {value: string};

function model(state: State, element: HTMLInputElement) {
  Object.keys(state).forEach((_key: string) => {
    const key = _key as keyof State ;
    element[key] = state[key];
  })
  // your code here
  defineProperty(state, 'value', null, (newVal: any) => {
    element.value = newVal;
  });

  element.addEventListener('change', () => {
    state.value = element.value;
  })
}

function defineProperty(obj: HTMLInputElement | Record<string, any>, key: string, getter: Function | null, setter: Function | null) {
  let value: any;
  Object.defineProperty(obj, key, {
    get: () => {
      getter && getter(value);
      return value;
    },
    set: (newVal: any) => {
      setter && setter(newVal);
      value = newVal;
    }
  })
}

Answer 24 · 2022-05-08T19:33:51.000Z

Day - 26

实现算法：26. 删除有序数组中的重复项

思路：

题目要求不开销新的空间，且数组为升序状态，可以考虑使用滑动窗口的思路处理
利用快慢指针进行比较，slow与fast从0开始往前推
只要fast与slow不同，则slow进一位取fast的值
重复2、3点直到fast大于数组长度后即可
取slow最终值 + 1即为需要替换第k项的位置（slow是索引，k是长度，所以需要slow + 1）
时间：O(n)因为fast、slow会根据数组长度移动n次
空间：O(1)，没有额外的开销

var removeDuplicates = function(nums) {
  const len = nums.length;
  let slow = 0, fast = 1;
  while(fast < len) {
    if(nums[fast] !== nums[fast-1]) {
      slow++;
      nums[slow] = nums[fast];
    }
    fast++;
  }
  // 索引转长度
  return slow + 1;
};

编程题：实现类型体操OmitThisParameter

function foo(this: {a: string}) {}
foo() // Error

const bar = foo.bind({a: 'BFE.dev'})
bar() // OK


type Foo = (this: {a: string}) => string
type Bar = MyOmitThisParameter<Foo> // () => string

思路：

使用bind柯里化后，如提前填入参数，后续再次执行新返回的函数时，则可以省略入参
取传入的泛型T是否给箭头函数约束，并推断返回类型R
如果满足约束，则返回一个() => R函数，否则返回never

type MyOmitThisParameter<T> = T extends (...args: any[]) => infer R ? () => R : never;

Answer 25 · 2022-05-08T19:34:21.000Z

Day - 27

实现算法：35. 搜索插入位置

思路：

由于题目要求O(logN)，并且给的数组为有序，可直接考虑二分法
使用快慢指针实现二分法，通过取中间值不断通过取中间值，对left与right指针的间隔范围进行缩减
时间：O(logN)，空间：O(1)

var searchInsert = function(nums, target) {
  const len = nums.length;
  let left = 0, right = len - 1, ans = len;
  while(left <= right) {
    const mid = Math.floor((right - left) / 2) + left;
    if(nums[mid] < target) {
      left = mid + 1;
      continue;
    }
    right = mid - 1;
    ans = mid;
  }
  return ans;
};

编程题：实现React useCallback原理

思路：

核心**是每次函数刷新，将第一次创建的函数进行缓存
根据新老depList依赖列表逐值比较，出现不同再更换函数
可考虑用闭包实现对fn与depList进行缓存，起到React.useCallback的效果

function _useCallback() {
  let lastFn: () => void, lastDeps: DependencyList;
  return function (fn: () => void, deps: DependencyList) {
    if(lastDeps) {
      const notSame = deps.some((item: unknown, i: number) => {
        console.log(item, deps[i], 1111)
        return item !== lastDeps[i]
      });
      if(notSame) {
        lastFn = fn;
        lastDeps = deps;
      }
      return lastFn;
    }
    lastFn = fn;
    lastDeps = deps;
    return lastFn;
  }
}

const useCallback = _useCallback();

Answer 26 · 2022-05-09T08:11:50.000Z

Day - 28

实现算法：239. 滑动窗口最大值

思路：

使用单调递减普通队列维护最大值，每次遍历只取队首存入答案队列
需要保证单调递减队列的队头，始终要在滑动窗口内
保证数组值的单调递减
针对第2点：遍历时，需要不断的用nums的索引去对比单调队列头索引是否在窗体之外，即queue[0] < i - k
时间：O(n)，空间：O(k)，k：窗口范围

var maxSlidingWindow = function(nums, k) {
  const result = [];
  // anchor1: 单调递减普通队列，用于存储nums索引，存储规则：根据nums值单调递减存储nums
  const queue = []; 
  // 取前3个值的最大值，因为必须跑到3才会出现第一个result，为了保证可读性，所以单独处理
  for(let i = 0; i < k; i++) {
    // anchor3: 判断队列最后记录的值是否小于当前值nums[i]，小于则删除last值
    while(queue.length && nums[getArrLastVal(queue)] < nums[i]) queue.pop();
    queue.push(i); // 无论如何新值索引总会被记录
  }
  result.push(nums[queue[0]]);
  // 从k开始往后取
  for(let i = k, len = nums.length; i < len; i++) {
    // anchor2: 先判断queue中有没超出k的值，要始终保持k长度的窗口
    if(queue[0] <= i - k) queue.shift();
    // anchor3: 如果没有超出，则清除比nums[i]小的值
    while(queue.length && nums[getArrLastVal(queue)] < nums[i]) queue.pop();
    queue.push(i);
    // 除了前三位，后续每移动一次都要得到一个值
    result.push(nums[queue[0]]);
  }
  return result;
};

function getArrLastVal(arr) {
  return arr[arr.length - 1];
}

编程题: 实现React useMemo原理

思路：

useMemo作用是固化函数返回值，并根据依赖项更新。
上下文：fn为useMemo(fn, deps)传入的函数fn，result为result = useMemo(fn, deps)的返回值，deps为依赖列表
核心思路与useCallback相似，缓存依赖列表deps与函数返回值fn()（useCallback是函数地址）
缓存使用map + 按序的key进行缓存，并且在每次执行完所有useMemo后，把key清零，方便下次update重新计算（不严谨）
如果last依赖项与新依赖项不一致，执行函数并返回新的返回值
如果一致，返回历史值，不执行，使用以前的result

function _useMemo() {
  let timer: NodeJS.Timeout, key: number = -1;
  const m = new Map();
  return function(fn: (...args: any[]) => any, deps: DependencyList) {
    key++;
    const currKey = key;
    const { deps: lastDeps } = m.get(currKey) || {};
    timer && clearTimeout(timer);
    timer = setTimeout(() => { key = -1 });
    if(lastDeps!) {
      const isChanged = deps.some((item, i) => item !== lastDeps[i])
      if(isChanged) {
        m.set(currKey, { result: fn(), deps });
      }
      return m.get(currKey).result;
    }
    m.set(currKey, { result: fn(), deps });
    return m.get(currKey).result;
  }
}

const useMemo = _useMemo();

Answer 27 · 2022-05-12T16:59:36.000Z

Day - 29

实现算法：997. 找到小镇的法官

思路：

题意：n个人，按1 - n序号排列，且都信任法官（除法官自己）
即：trust[i] = [编号, 信任人]，可以做一个出入度的图模型
建立出入度模型：
- 因为不需要知道具体只想谁，所以只做出入度统计即可
- 法官拥有所有人的入度，即n - 1，但出度为0
- 村民没有入度，出度全都为1
建立完毕后，从第一个村民开始遍历查到第n个村民，满足入度 n - 1，出度 0的编号者，即为法官
如果没有找到法官按题意返回-1
时间：O(n + m)，m为trust长度，需要构造出入度
空间：O(m)，m同上，记录出入度的空间，与trust长度一致

var findJudge = function(n, trust) {
  const inDegress = new Array(n + 1).fill(0)
  const outDegress = new Array(n + 1).fill(0)
  for(let edge of trust) {
    const [x, y] = edge;
    ++inDegress[y];
    ++outDegress[x];
  }
  for(let i = 1; i <= n; i++) {
    if(inDegress[i] === n - 1 && outDegress[i] === 0) return i;
  }
  return -1;
};

编程题：实现React useState原理

思路：

useState思路与之前useCallback与useMemo几乎一致，甚至更简便。
核心：每次setState时，都需使用createRoot得到的root.render函数进行update视图。
使用map + 按序key对state的值进行缓存，后续setState让视图刷新时，还需要到缓存中找相应的state
每次setState完毕后都需要清零key值，否则涉及到后续update视图，会因为一直key++而找不到以前缓存的map.get(key)

type UseState = <T>(arg: T) => [T, (newState: T) => void];

function _useState(): UseState {
  const stateMap: Map<number, any> = new Map();
  let key: number = 0;
  let timer: NodeJS.Timeout;
  return function<T>(initState: T) {
    const state: T = stateMap.has(key) ? stateMap.get(key) : initState;
    const currKey: number = key;
    const setState = (newState: T) => {
      stateMap.set(currKey, newState);
      key = 0;
      timer && clearTimeout(timer);
      timer = setTimeout(update)
    }
    key++;
    return [state, setState];
  }
}

const useState = _useState();

Answer 28 · 2022-05-12T17:00:52.000Z

Day - 30

实现算法：886. 可能的二分法

思路：

根据题意采集：
- 1-n人
- 分成任意两组
- 如果组内存在互相不喜欢的人，不允许在一组
- 根据第三点，给定dislike数组，dislike[i] = [Ai, Bi]，即A不喜欢B
- 综上所属，2个组，存在互不喜欢，且存在相互喜欢（即不讨厌），就可以形成分组，可使用二分图的思路拆成两队
- 该题的结果是问是否能组队，那么我们只需判断二分图即可。
什么是二分图
- 图结构的节点相连接的过程，相邻的节点即颜色不可一致（在现实中可以理解为性质不一致）
二分图形成的过程
- 根据给定的二维数组，组成一个图结构，根据索引序号作为节点，第二维数组存与该节点链接的节点。
- 图与树不一样，它需要做访问记录visited，否则会死循环（基本知识）
- 做染色记录，相邻节点的颜色必须不同于自己的颜色，如果相同，可直接判为非二分图
- 根据以上的思路，对每个未被visited的节点进行遍历染色
- 综上所述，dislike => 图 => 遍历图 => 发现相邻节点颜色全部不同 => 满足二分图

var possibleBipartition = function(n, dislikes) {
  // 先建图
  const graph = new Array(n + 1).fill(0).map(() => []);
  for(let edge of dislikes) {
    const [ self, other ] = edge;
    graph[self].push(other);
    graph[other].push(self);
  }
  // 访问图节点记录表，染色节点记录表
  const visited = new Array(n + 1).fill(false);
  const colored = new Array(n + 1).fill(false);
  let ok = true;
  // 开始逐个节点遍历
  const traverse = (graph, self) => {
    if(!ok) return;
    // 标记已访问，防止重复运行
    visited[self] = true;
    // 访问对立的图节点，即连了边的节点
    for(let other of graph[self]) {
      // 如果已经被访问过，则判断是否与自己的颜色一致，一致代表非二分图
      if(visited[other]) {
        if(colored[self] === colored[other]) ok = false;
        continue; // continue是为了跑完所有节点，如果单纯为了判断二分图，可以直接break
      }
      // 未被访问过，需要染色且访问被连线的节点（与自己链接点颜色必须对立，否则不满足二分图）
      colored[other] = !colored[self];
      // 顺着节点走
      traverse(graph, other);
    }
  }
  // 逐个遍历，如果当前的i节点被访问过，则直接跳过
  for(let i = 1; i <= n; i++) {
    if(!visited[i]) traverse(graph, i);
  }
  // 返回是否能成二分图
  return ok;
};

编程题：请使用你熟悉的语言或技术或框架实现一个autocomplete组件
todo

Answer 29 · 2022-05-12T17:01:33.000Z

Day - 31

todo
实现算法：1203. 项目管理
【前置知识】
图论
拓扑排序
BFS & DFS

编程题: 实现Object.assign原理

function objectAssign(...objList) {
  const [firstObj, ...restObj] = objList;
  for(let obj of restObj) {
    Object.keys(obj).forEach(key => {
      firstObj[key] = obj[key];
    });
  }
  return firstObj
}
objectAssign({a: 1}, {a:2, b:1}, {a:3,c:2})
// {a: 3, b: 1, c: 2}

Answer 30 · 2022-05-18T04:37:43.000Z

Day - 32

实现算法：1203. 项目管理

编程题: 实现深拷贝

Answer 31 · 2022-05-18T04:38:46.000Z

Day - 33

实现算法：657. 机器人能否返回原点

编程题: 实现instanceof

Answer 32 · 2022-05-18T04:39:31.000Z

Day - 34

实现算法：1904. 你完成的完整对局数

编程题：实现Array.prototype.map()

Answer 33 · 2022-05-19T15:15:38.000Z

Day - 35

实现算法：1737. 满足三条件之一需改变的最少字符数

编程题：实现Array.prototype.reduce()

Answer 34 · 2022-05-19T15:16:49.000Z

Day - 36

实现算法：912. 排序数组

编程题：实现ThisParameterType

Answer 35 · 2022-06-23T14:06:36.000Z

Day - 37

实现算法：69. x 的平方根

编程题：实现_.chunk()

chunk([1,2,3,4,5], 1)
// [[1], [2], [3], [4], [5]]

chunk([1,2,3,4,5], 2)
// [[1, 2], [3, 4], [5]]

chunk([1,2,3,4,5], 3)
// [[1, 2, 3], [4, 5]]

chunk([1,2,3,4,5], 4)
// [[1, 2, 3, 4], [5]]

chunk([1,2,3,4,5], 5)
// [[1, 2, 3, 4, 5]]

Answer 36 · 2022-06-23T14:08:04.000Z

Day - 38

实现算法：278. 第一个错误的版本

编程题：实现parseToMoney

实现千位分隔符
// 保留三位小数
parseToMoney(1234.56); // return ‘1,234.56’
parseToMoney(123456789); // return ‘123,456,789’
parseToMoney(1087654.321); // return ‘1,087,654.321’

Answer 37 · 2022-06-23T14:10:55.000Z

Day - 39

实现算法：三重反转
给定一个整数列表 nums，返回满足 nums[i] > nums[j] * 3 的对 i < j 的数量。

约束：
n ≤ 100,000 其中 n 是 nums 的长度

编程题：返回DOM tree中”左边“的元素
给定一个DOM tree和目标节点，请找出其左边的节点。

就像上图那样，绿色<a/>的左边是蓝色的<button/>。注意它们并不一定需要有共同的父节点。

如果没有的话，返回null。

你的代码的时间和空间复杂度是多少？

Answer 38 · 2022-06-23T14:12:38.000Z

Day - 40

实现算法：最小光半径
给你一个整数列表，代表一维线上房屋的坐标。您有 3 盏路灯，您可以将它们放在坐标线上的任何位置，坐标 x 处的一盏灯照亮了 [x - r, x + r] 中的房屋，包括在内。返回所需的最小 r，以便我们可以放置 3 盏灯并且所有的房子都被点亮。

约束

n ≤ 100,000 其中 n 是 nums 的长度

Answer 39 · 2022-06-23T14:15:58.000Z

Day - 41

实现算法：第K对距离
给定一个整数列表 nums 和一个整数 k，返回 nums 中每对元素 (x, y) 的第 k 个（0 索引）最小 abs(x - y)。注意 (x, y) 和 (y, x) 被认为是同一对。

约束：

n ≤ 100,000 其中 n 是 nums 的长度

Day - 01

思路：

1. 数组的单位计算处理

2. k值的单位计算处理

3. 进位数处理

4. 最高位数进1处理

5. 如何保证num和k的值被加完

思路：

思路

Day - 02

思路

思路：

Day - 03

思路：

思路：

Day - 04

思路：

思路:

Day - 05

思路：

思路：

Day - 06

思路：

Day - 07

思路：

Day - 08

思路：

思路：

Day - 09

思路一：

思路二：

思路三：

Day - 10

思路一：

思路二：

Day - 11

思路

思路

上下文说明：

公式推导：

该公式代表a到入环的距离，为fast与slow相遇节点到入环节点的距离 + n - 1圈

思路

Day - 12

思路

Day - 13

思路：

思路：

Day - 14

思路

思路：

字符串转JSX

JSX转AST

Day - 15

思路一：

dfs深度优先

思路二：

BFS广度优先

思路：

Day - 16

思路一：

BFS广度优先

思路二：

DFS深度优先

思路：

Day - 17

思路一：

思路二：

Day - 18

思路：

思路：

Day - 19

思路：

Day - 20

思路：

Day - 21

思路：

Day - 22

思路一：for循环滑动窗口

思路二：left、right的while循环双指针滑动窗口

Day - 23

该公式代表`a到入环的距离`，为`fast与slow相遇节点到入环节点的距离` + `n - 1圈`