手写算法: Triple Inversion

Triple Inversion

class Solution {
  solve(nums) {
    let list = new Array(),
      result = 0;
    for (let i = 0; i < nums.length; i++) {
      let where = this.find(list, nums[i] * 3);
      // where代表在排序好数组的位置，被length减去，代表有多少个i比j*3要大
      result += list.length - where;
      // 塞入数组，每次塞入都是一个正确的排序
      list.splice(this.find(list, nums[i]), 0, nums[i]);
    }
    return result;
  }

  find(list, target) {
    let left = 0,
      right = list.length;
    while (left < right) {
      let mid = left + ((right - left) >> 1);
      if (list[mid] > target) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return right;
  }
}

// test
const s = new Solution();
s.solve([7, 1, 2]);

手写题: 返回 DOM tree 中”左边“的元素

158. 返回 DOM tree 中”左边“的元素

/**
 * @param {Element} root
 * @param {Element} target
 * @return {Elemnt | null}
 */
function previousLeftSibling(root, target) {
  // your code here
  let q = [root];

  while (q.length) {
    const n = q.length;
    let prev = null;

    for (let i = 0; i < n; i++) {
      const cur = q.shift();
      console.log(111, cur);
      if (cur === target) {
        return prev;
      }
      q.push(...cur.children);
      prev = cur;
    }
  }
  return null;
}