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

李恒道

https://leetcode.cn/problems/happy-number/submissions/576209580/?envType=study-plan-v2&envId=top-interview-150
缓存秒了

var isHappy = function (n) {
  const cache = new Map();
  while (true) {
    if (cache.has(n)) {
      return false;
    }
    cache.set(n, true);
    let newN = 0;
    while (n != 0) {
      newN += (n % 10) * (n % 10);
      n = parseInt(n / 10);
    }
    n = newN;
    if(newN==1){
      break;
    }
  }
  return true
};

李恒道

https://leetcode.cn/problems/valid-sudoku/submissions/576211089/?envType=study-plan-v2&envId=top-interview-150
脑筋急转弯题

var isValidSudoku = function (board) {

  for (let index = 0; index < board.length; index++) {
    const hasNum = new Array(10).fill(false);
    for (let indey = 0; indey < board[0].length; indey++) {
      const char = board[index][indey];
      if (char !== ".") {
        if (hasNum[char]) {
          return false;
        }
        hasNum[char] = true;
      }
    }
  }
  //竖排
  for (let index = 0; index < board[0].length; index++) {
    const hasNum = new Array(10).fill(false);
    for (let indey = 0; indey < board.length; indey++) {
      const char = board[indey][index];
      if(char=='5'){
        debugger
      }
      if (char !== ".") {
        if (hasNum[char]) {
          return false;
        }
        hasNum[char] = true;
      }
    }
  }
  for (let x = 0; x < board[0].length / 3; x++) {
    for (let y = 0; y < board.length / 3; y++) {
      const hasNum = new Array(10).fill(false);
      for (let index = 0; index < 3; index++) {
        for (let indey = 0; indey < 3; indey++) {
          const char = board[x * 3 + index][y * 3 + indey];
          if (char !== ".") {
            if (hasNum[char]) {
              return false;
            }
            hasNum[char] = true;
          }
        }
      }
    }
  }
  return true;
};

李恒道

https://leetcode.cn/problems/reverse-pairs/submissions/587579007/
考察归并排序问题
一次过！

function merge(arr, l, m, r) {
    var result = [];
    let check2 = m + 1;
    let ans = 0;
    for (let index = l; index <= m; index++) {
        while (arr[index] > arr[check2] * 2 && check2 <= r) {
            check2++
        }
        ans += check2 - m - 1
    }
    let pos1 = l;
    let pos2 = m + 1;
    while (pos1 <= m && pos2 <= r) {
        if (arr[pos1] < arr[pos2]) {
            result.push(arr[pos1++]);
        }
        else {
            result.push(arr[pos2++]);
        }
    }
    while (pos1 <= m) {
        result.push(arr[pos1++]);
    }
    while (pos2 <= r) {
        result.push(arr[pos2++]);
    }
    for (let index = 0; index < result.length; index++) {
        arr[l++] = result[index]
    }

    return ans;
}

function mergeSort(arr, l, r) {
    if (l == r) return 0;
    const mid = l + Math.floor((r - l) / 2);
    return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}

/**
 * @param {number[]} nums
 * @Return {number}
 */
var reversePairs = function (nums) {
    return mergeSort(nums, 0, nums.length - 1)
};```

李恒道

https://leetcode.cn/problems/copy-list-with-random-pointer/submissions/587584803/
简单题，多次遍历即可

var copyRandomList = function (head) {
    if(head==null){
        return head
    }
    let node = head;
    while (node !== null) {
        let next = node.next;
        node.next = {
            val: node.val,
            next: next,
            random: null,
        }
        node = next;
    }
    node = head;
    while (node !== null) {
        node.next.random = node.random?.next ?? null;
        node = node.next.next;
    }
    node = head;
    let newNode = node.next;
    let ret = newNode
    while (node !== null) {
        node.next = node.next.next;
        node = node.next
        newNode.next = node?.next ?? null;
        newNode = newNode.next
    }
    return ret
};

李恒道

https://leetcode.cn/problems/check-completeness-of-a-binary-tree/submissions/587588536/
感觉到bfs了
但是边界没扣好
看了一眼答案

var isCompleteTree = function (root) {
    const stack = [root];
    let pre = root;
    while (stack.length !== 0) {
        const item = stack.shift();
        if (item !== null) {
            if (pre == null) {
                return false
            }
            stack.push(item.left);
            stack.push(item.right);
        }
        pre = item;

    }
    return true
};

李恒道

https://leetcode.cn/problems/network-delay-time/submissions/587598445/
dj算法，没记下来，要好好背一下QAQ

var networkDelayTime = function (times, n, k) {
    const g = new Array(n).fill(0).map(() => new Array(n).fill(Infinity))
    for (let index = 0; index < times.length; index++) {
        const [x1, x2, z] = times[index];
        g[x1 - 1][x2 - 1] = z
    }
    const dis = new Array(n).fill(Infinity)
    const vis = new Array(n).fill(false)
    dis[k - 1] = 0;
    while (true) {
        let x = -1
        for (let index = 0; index < dis.length; index++) {
            if (vis[index] !== true && (x == -1 || dis[index] < dis[x])) {
                x = index;
            }
        }
        if (x == -1) {
            const result= Math.max(...dis)
            return result===Infinity?-1:result
        }
        for (let index = 0; index < dis.length; index++) {
            dis[index] = Math.min(dis[index], dis[x] + g[x][index])
        }
        vis[x]=true
    }
};

李恒道

https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-i/submissions/587607803/
前缀树+dp

var minValidStrings = function (words, target) {
    const tree = {}
    for (let index = 0; index < words.length; index++) {
        const word = words[index].split("");
        let node = tree
        for (let index = 0; index < word.length; index++) {
            const char = word[index];
            if (node[char] == undefined) {
                node[char] = {}
            }
            node = node[char]
        }
        node.end = true
    }
    const dp = new Array(target.length + 1).fill(Number.MAX_SAFE_INTEGER);
    dp[dp.length - 1] = 0;
    for (let index = target.length - 1; index >= 0; index--) {
        let node = tree;
        let pos = index;
        while (pos < target.length) {
            node = node[target[pos]]
            if (node == undefined) {
                break;
            }
            const num = dp[pos+1];
            if (num !== Number.MAX_SAFE_INTEGER) {
                dp[index] = Math.min(dp[index], num + 1)
            }
            pos++
        }
    }
    return dp[0]===Number.MAX_SAFE_INTEGER?-1:dp[0]
};

李恒道

https://leetcode.cn/problems/stickers-to-spell-word/submissions/587794484/
一个&&和&扣了一个小时...

var minStickers = function (stickers, target) {
    const allT = (1 << target.length) - 1;
    const cache = new Map();
    const dfs = (status) => {
        if (status == allT) {
            return 0;
        }
        if (cache.has(status)) {
            return cache.get(status)
        }
        let ans = Number.MAX_SAFE_INTEGER
        for (let index = 0; index < stickers.length; index++) {
            const sticker = stickers[index];
            let newStatus = status
            for (let indey = 0; indey < sticker.length; indey++) {
                const char = sticker[indey];
                for (let indez = 0; indez < target.length; indez++) {
                    const tchar = target[indez];
                    if (tchar == char && ((newStatus & (1 << indez)) === 0)) {
                        newStatus = newStatus | (1 << indez)
                        break;
                    }

                }
            }
            if (newStatus !== status) {
                ans = Math.min(ans, dfs(newStatus) + 1)
            }
        }
        cache.set(status, ans)
        return ans
    }
    const ans = dfs(0)
    return ans == Number.MAX_SAFE_INTEGER ? -1 : ans
};

李恒道

https://leetcode.cn/problems/maximum-subarray-min-product/
大数问题扣了半天...

var maxSumMinProduct = function (nums) {
    const left = new Array(nums.length).fill(-1);
    const right = new Array(nums.length).fill(-1);
    const sum = new Array(nums.length).fill(-1);
    const getSum = (l, r) => {
        if (l == -1) {
            if (r == -1) {
                return sum[sum.length - 1]
            }
            return sum[r-1]
        }
        if (r == -1) {
            return sum[sum.length - 1] - sum[l]
        }
        return sum[r - 1] - sum[l]
    }
    sum[0] = nums[0]
    for (let index = 1; index < nums.length; index++) {
        sum[index] = sum[index - 1] + nums[index]
    }
    let stack = [];
    for (let index = 0; index < nums.length; index++) {
        const num = nums[index];
        while (stack.length !== 0 && nums[stack[stack.length - 1]] >= num) {
            stack.pop()
        }
        if (stack.length !== 0) {
            left[index] = stack[stack.length - 1]
        }
        stack.push(index)
    }

    stack = [];
    for (let index = nums.length - 1; index >= 0; index--) {
        const num = nums[index];
        while (stack.length !== 0 && nums[stack[stack.length - 1]] >= num) {
            stack.pop()
        }
        if (stack.length !== 0) {
            right[index] = stack[stack.length - 1]
        }
        stack.push(index)
    }
    let ans = 0n
    const bigIntMax = (...args) => args.reduce((m, e) => e > m ? e : m);
    for (let index = 0; index < nums.length; index++) {
        const num = nums[index];
        const l = left[index];
        const r = right[index];
        const sum = getSum(l, r);
        ans = BigInt(bigIntMax(ans, BigInt(sum) * BigInt(num) ));
    }
    return Number(ans%BigInt(10**9+7))
};

李恒道

https://leetcode.cn/problems/maximal-rectangle/submissions/587821910/
柱形的变形题

var largestRectangleArea = function (heights) {
    const n = heights.length;
    const left = Array(n).fill(-1);
    const st = [];
    for (let i = 0; i < n; i++) {
        const x = heights[i];
        while (st.length && x <= heights[st[st.length - 1]]) {
            st.pop();
        }
        if (st.length) {
            left[i] = st[st.length - 1];
        }
        st.push(i);
    }

    const right = Array(n).fill(n);
    st.length = 0;
    for (let i = n - 1; i >= 0; i--) {
        const x = heights[i];
        while (st.length && x <= heights[st[st.length - 1]]) {
            st.pop();
        }
        if (st.length) {
            right[i] = st[st.length - 1];
        }
        st.push(i);
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
    }
    return ans;
};

/**
 * @param {character[][]} matrix
 * @Return {number}
 */
var maximalRectangle = function (matrix) {
    let ans = 0;
    for (let start = 0; start < matrix.length; start++) {
        let stack = new Array(matrix[0].length).fill(0);
        for (let index = start; index < matrix.length; index++) {
            //每行的数字都加上
            for (let indey = 0; indey < matrix[0].length; indey++) {
                const num = matrix[index][indey];
                stack[indey] += parseInt(num);
                if (parseInt(num) == 0) {
                    stack[indey] = 0
                }
            }
            ans = Math.max(ans, largestRectangleArea(stack))
        }
    }
    return ans

};