【当前排名42710】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/spiral-matrix-ii/submissions/589626378/
一次过

var generateMatrix = function (n) {
  const arr = new Array(n).fill(0).map(() => new Array(n).fill(0));
  const fill = (x, y, len, def) => {
    for (let index = x; index < len; index++) {
      arr[x][index] = def++;
    }
    def--;
    for (let index = y; index < len; index++) {
      arr[index][len - 1] = def++;
    }
    def--;
    for (let index = len - 1; index >= x; index--) {
      arr[len - 1][index] = def++;
    }
    def--;
    for (let index = len - 1; index >= x+1; index--) {
      arr[index][x] = def++;
    }
    return def;
  };
  const layout = Math.ceil(n / 2);
  let def = 1;
  let len = n;
  for (let index = 0; index < layout; index++) {
    def = fill(index, index, len, def);
    len--;
  }
  return arr
};

李恒道

https://leetcode.cn/problems/text-justification/submissions/589723367/?envType=study-plan-v2&envId=top-interview-150
硬编码题，不喜欢这种

var fullJustify = function (words, maxWidth) {
    let stack = [];
    let len = 0;
    const ans = []
    const handList = () => {
        if(stack.length==1){
            ans.push(stack[0]+new Array(maxWidth-stack[0].length).fill(" ").join(''))
            stack.pop()
            len = 0;
            return
        }
        const spaceNum = stack.length - 1;
        const spaceWidth = Math.floor((maxWidth - len) / spaceNum)
        let extraSpace = maxWidth - len - (spaceWidth * spaceNum)
        let spaceWidthStr = new Array(spaceWidth).fill(" ").join('')
        let str = ""
        while (stack.length !== 0) {
            str += stack.shift();
            if (stack.length !== 0) {
                str += spaceWidthStr
            }
            if (extraSpace !== 0) {
                str += " "
                extraSpace--
            }
        }
        len = 0;
        ans.push(str)
    }
    for (let index = 0; index < words.length; index++) {
        const word = words[index];
        if (len + word.length + stack.length > maxWidth) {
            handList()
        }

        stack.push(word);
        len += word.length

    }
    stack=[stack.join(" ")]
    handList()
    return ans
};

李恒道

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/submissions/589726283/?envType=study-plan-v2&envId=top-interview-150
层序递归
秒了

var connect = function (root) {
    if(root==null){
        return null
    }
    let stack = []
    stack.push(root);
    right = null;
    let nextStack = []
    while (stack.length !== 0) {
        let item = stack.pop()
        item.next = right;
        right = item;
        item.right && nextStack.unshift(item.right);
        item.left && nextStack.unshift(item.left);
        if (stack.length == 0) {
            stack = nextStack;
            nextStack = [];
            right = null;
        }
    }
    return root
};

李恒道

https://leetcode.cn/problems/split-the-array/submissions/589763029/
打卡题

var isPossibleToSplit = function (nums) {
  const cache = new Map();
  const chache2 = new Map();
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    if (!cache.has(num)) {
      cache.set(num, 1);
    } else if (!chache2.has(num)) {
      chache2.set(num, 1);
    }else{
        return false
    }
  }
  return true
};

李恒道

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/submissions/589783956/?envType=study-plan-v2&envId=top-interview-150
看的答案
这个题做的还是挺有意思的

var findSubstring = function (s, words) {
  const wordsCount = words.length;
  const len = words[0].length;
  const cache = new Map();
  const ans = [];
  for (const word of words) {
    cache.set(word, (cache.get(word) ?? 0) + 1);
  }
  for (let index = 0; index < len; index++) {
    const temp = new Map();
    let pos = index;
    while (pos + len <= s.length) {
      const str = s.substring(pos, pos + len);
      pos += len;
      temp.set(str, (temp.get(str) ?? 0) + 1);

      if (pos - index > len * wordsCount) {
        const pre = s.substring(
          pos - len * (wordsCount+1),
          pos - len * (wordsCount )
        );
        if (temp.get(pre) == 1) {
          temp.delete(pre);
        } else {
          temp.set(pre, (temp.get(pre) ?? 0) - 1);
        }
        if (temp.get(pre) !== cache.get(pre)) {
          continue;
        }
      }
      if (temp.get(str) !== cache.get(str)) {
        continue;
      }
      let isSame = true;
      for (let [key, value] of cache) {
        if (temp.get(key) !== value) {
          isSame = false;
          break;
        }
      }
      if (isSame) {
        ans.push(pos - len * wordsCount);
      }
    }
  }
  return ans
};

李恒道

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/submissions/589786867/
N叉树，length扣半天

var levelOrder = function (root) {
    if(root==null){
return []

    }
  const stack = [];
  stack.push(root);
  const ans = [];
  while (stack.length !== 0) {
    const num = stack.length;
    const list = [];
    for (let index = 0; index < num; index++) {
      const item = stack.shift();
      for (let indey = 0; indey < item.children.length; indey++) {
        const children = item.children[indey];
        stack.push(children);
      }
      list.push(item.val);
    }
    ans.push(list);
  }

  return ans
};

李恒道

https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/submissions/589795796/?envType=study-plan-v2&envId=top-interview-150
堆问题，但是没处理hash，没有什么思路，一会看一眼题解

class MaxHeap {
  constructor(comparator = (a, b) => a - b) {
    this.heap = [];
    this.comparator = comparator;
  }

  // 获取父节点索引
  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点索引
  leftChildIndex(index) {
    return 2 * index + 1;
  }

  // 获取右子节点索引
  rightChildIndex(index) {
    return 2 * index + 2;
  }

  // 交换两个节点
  swap(index1, index2) {
    const temp = this.heap[index2];
    this.heap[index2] = this.heap[index1];
    this.heap[index1] = temp;
  }

  // 向堆中插入元素
  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  // 堆化上移
  heapifyUp() {
    let index = this.heap.length - 1;
    while (
      index > 0 &&
      this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) > 0
    ) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

  // 移除堆顶元素
  extractMax() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return max;
  }

  // 堆化下移
  heapifyDown(index) {
    let largest = index;
    const left = this.leftChildIndex(index);
    const right = this.rightChildIndex(index);

    if (
      left < this.heap.length &&
      this.comparator(this.heap[left], this.heap[largest]) > 0
    ) {
      largest = left;
    }

    if (
      right < this.heap.length &&
      this.comparator(this.heap[right], this.heap[largest]) > 0
    ) {
      largest = right;
    }

    if (largest !== index) {
      this.swap(index, largest);
      this.heapifyDown(largest);
    }
  }

  // 获取堆顶元素
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null;
  }

  // 获取堆的大小
  size() {
    return this.heap.length;
  }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @Return {number[][]}
 */
var kSmallestPairs = function (nums1, nums2, k) {
  this.maxHeap = new MaxHeap((a, b) => {
    const total1 = nums1[a.pos1] + nums2[a.pos2];
    const total2 = nums1[b.pos1] + nums2[b.pos2];
    return total2 - total1;
  }); // 默认比较器，构建最大堆
  const cache = new Map();
  this.maxHeap.insert({
    pos1: 0,
    pos2: 0,
  });
  const ans = [];
  for (let index = 0; index < k; index++) {
    const node = this.maxHeap.extractMax();
    const tag = `${node.pos1} ${node.pos2}`;
    if (cache.has(tag)) {
      index--;
      continue;
    }
    cache.set(tag,1)
    ans.push([nums1[node.pos1], nums2[node.pos2]]);
    if (node.pos1 + 1 < nums1.length && node.pos2 < nums2.length) {
      this.maxHeap.insert({
        pos1: node.pos1 + 1,
        pos2: node.pos2,
      });
    }

    if (node.pos2 + 1 < nums2.length && node.pos1 < nums1.length) {
      this.maxHeap.insert({
        pos1: node.pos1,
        pos2: node.pos2 + 1,
      });
    }
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/bitwise-and-of-numbers-range/submissions/589797664/?envType=study-plan-v2&envId=top-interview-150
看了一眼答案
规律题太抽象了...

var rangeBitwiseAnd = function (left, right) {
  const num = 32 - Math.clz32(left ^ right);
  return left&(~((1<<num)-1))
};

李恒道

https://leetcode.cn/problems/reverse-bits/description/?envType=study-plan-v2&envId=top-interview-150
不知道为什么t>>> 0结果就对了
感觉有截断什么的

var reverseBits = function (n) {
  let result = 0;
  for (let index = 0; index < 32; index++) {
    if (n & (1 << index)) {
      result = result | (1 << (31 - index));
    }
  }
  return result>>> 0;
};

李恒道

https://leetcode.cn/problems/making-file-names-unique/submissions/589829921/
主要最后有一个卡测例

var getFolderNames = function (names) {
    const cache = new Map();
    const jump = new Map()
    const ans = []
    for (let index = 0; index < names.length; index++) {
        let name = names[index];
        if (cache.has(name)) {
            let pos = (jump.get(name) ?? 0) + 1
            let checkName = name + `(${pos})`
            while (cache.has(checkName)) {
                pos++;
                checkName = name + `(${pos})`
            }
            jump.set(name, pos)
            cache.set(checkName, true)
            ans.push(checkName)
        } else {
            cache.set(name, true)
            ans.push(name)
        }
    }
    return ans
};