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

李恒道

https://leetcode.cn/problems/length-of-last-word/submissions/570106650/?envType=study-plan-v2&envId=programming-skills
随手来一道练习题
今日收工

func lengthOfLastWord(s string) int {
    var word string
    for index := len(s) - 1; index >= 0; index-- {
        if s[index:index+1] == " " && word != "" {
            break
        }
        if s[index:index+1] != " " {
            word += s[index : index+1]
        }
    }
    return len(word)
}

李恒道

https://leetcode.cn/problems/max-submatrix-lcci/submissions/571458474/
这题挺难凹的

var getMaxMatrix = function (matrix) {
    let maxValue = Number.MIN_SAFE_INTEGER;
    let top = undefined;
    let bottom = undefined;
    let right = undefined;
    let size = undefined;
    const findMax = (arr, localTop, localBottom) => {
        let currentValue = arr[0];
        if (maxValue < currentValue) {
            maxValue = currentValue;
            right = 0;
            size = 0;
            top = localTop;
            bottom = localBottom;
        }
        const dp = new Array(arr.length).fill(0);
        dp[0] = arr[0] <= 0 ? 0 : arr[0]
        let left = 0;
        let localRight = 0;
        for (let index = 1; index < arr.length; index++) {
            const num = arr[index];
            if (dp[index - 1] + arr[index] <= arr[index]) {
                left=index;
                dp[index] = num
            } else {
                if (num <= 0) {
                    dp[index] = dp[index - 1] + num
                } else {
                    dp[index] = dp[index - 1] + num
                }
            }
            if(currentValue<dp[index]){
                localRight=index
                currentValue=dp[index]
            }
            if (maxValue < currentValue) {
                maxValue = currentValue;
                right = localRight;
                size = left;
                top = localTop;
                bottom = localBottom;
            }
        }
    }
    for (let index = 0; index < matrix.length; index++) {
        const arr = new Array(matrix[0].length).fill(0)
        for (let indey = index; indey < matrix.length; indey++) {
            //添加每一行的值
            for (let indez = 0; indez < arr.length; indez++) {
                arr[indez] += matrix[indey][indez];
            }
            findMax(arr, index, indey)
            //查找最大的正方形
        }
    }
    return [top, size, bottom, right]
};

李恒道

https://leetcode.cn/problems/the-skyline-problem/submissions/571618493/?envType=problem-list-v2&envId=XVBr8pQX
轮廓线问题
被我写的一团乱麻A过了

class MaxHeadp {
  heap;
  border;
  compare;
  constructor(nums, compare) {
    this.heap = nums;
    this.border = nums.length - 1;
    this.compare = compare ?? ((a, b) => a - b);
    this.initHeap();
  }
  initHeap() {
    const endIndex = this.getTopNode(this.border);
    for (let index = endIndex; index >= 0; index--) {
      this.downNode(index);
    }
  }
  //有多少个元素
  haveNum() {
    return this.border + 1;
  }
  //弹出最顶的
  pop(index = 0) {
    if (this.border === -1) {
      return undefined;
    }
    const temp = this.heap[index];
    this.heap[index] = this.heap[this.border];
    this.border--;
    this.downNode(index);
    return temp;
  }
  //插入元素
  insert(node) {
    this.border++;
    this.heap[this.border] = node;
    this.upNode(this.border);
  }
  getNode(callback,index=0) {
    if (index <= this.border) {
      const result = callback(this.heap[index]);
      if (result == 0) {
        return { index, item: this.heap[index] };
      }
      const index1 = this.getNode(callback,this.getLeftNode(index));
      if (index1.item !== undefined) {
        return index1;
      }

      const index2 = this.getNode(callback,this.getRightNode(index));
      if (index2.item !== undefined) {
        return index2;
      }
    }
    return { index: -1, item: undefined };
  }
  swap(x, y) {
    let temp = this.heap[x];
    this.heap[x] = this.heap[y];
    this.heap[y] = temp;
  }
  downNode(index) {
    let left = this.getLeftNode(index);
    let right = this.getRightNode(index);
    while (left <= this.border || right <= this.border) {
      let maxIndex = undefined;
      if (left <= this.border || right <= this.border) {
        maxIndex =
          this.compare(this.heap[left], this.heap[right]) < 0 ? right : left;
      } else {
        maxIndex = left <= this.border ? right : left;
      }
      // if (this.heap[index] < this.heap[maxIndex]) {
      if (this.compare(this.heap[index], this.heap[maxIndex]) < 0) {
        this.swap(index, maxIndex);
        index = maxIndex;
        left = this.getLeftNode(index);
        right = this.getRightNode(index);
      } else {
        break;
      }
    }
  }
  upNode(index) {
    while (index != 0) {
      const parentIndex = this.getTopNode(index);
      if (this.compare(this.heap[parentIndex], this.heap[index]) < 0) {
        this.swap(parentIndex, index);
        index = parentIndex;
      } else {
        break;
      }
    }
  }
  getTopNode(index) {
    return Math.floor((index - 1) / 2);
  }
  getLeftNode(index) {
    return (index + 1) * 2 - 1;
  }
  getRightNode(index) {
    return (index + 1) * 2;
  }
}

var getSkyline = function (buildings) {
  const posArr = [];
  for (let index = 0; index < buildings.length; index++) {
    const build = buildings[index];
    posArr.push({
      pos: build[0],
      height: build[2],
    });
    posArr.push({
      pos: build[1],
      height: -build[2],
    });
  }
  posArr.sort((a, b) => {
    if (a.pos !== b.pos) {
      return a.pos - b.pos;
    } else {
      return b.height - a.height;
    }
  });
  const maxHeightHeap = new MaxHeadp([], (a, b) => {
    return a.height - b.height;
  });
  const ret = [];
  for (let index = 0; index < posArr.length; index++) {
    if (index === 3) {
      debugger;
    }
    const posItem = posArr[index];
    const { item: node, index: posIndex } = maxHeightHeap.getNode(
      (a) => a.height - Math.abs(posItem.height)
    );
    if (node !== undefined) {
      if (posItem.height > 0) {
        node.times++;
      } else {
        if (node.times == 1) {
          maxHeightHeap.pop(posIndex);
        } else {
          node.times--;
        }
      }
    } else {
      maxHeightHeap.insert({
        pos: posItem.pos,
        times: 1,
        height: posItem.height,
      });
    }
    const result = maxHeightHeap.heap[0];
    if (maxHeightHeap.border == -1) {
      if (ret[ret.length - 1][1] !== 0) {
        ret.push([posItem.pos, 0]);
      }
    } else {
      if (index == posArr.length - 1 || posArr[index + 1].pos !== posItem.pos) {
        if (ret.length==0||ret[ret.length - 1][1] !== result.height) {
          ret.push([posItem.pos, result.height]);
        }
      }
    }
  }
  return ret;
};

李恒道

https://leetcode.cn/problems/longest-common-prefix/submissions/571650018/?envType=study-plan-v2&envId=top-interview-150

来个简单题睡觉了

var longestCommonPrefix = function (strs) {
    let minLen = strs[0].length;
    for (let index = 1; index < strs.length; index++) {
        minLen = Math.min(minLen, strs[index].length)
    }
    let preFix = ""
    for (let index = 0; index < minLen; index++) {
        const globalChar = strs[0][index]
        for (let indey = 1; indey < strs.length; indey++) {
            const char = strs[indey][index];
            if(globalChar!==char){
                return preFix;
            }
        }
        preFix+=globalChar
    }
    return preFix
};

李恒道

https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/submissions/571858393/
基础dfs

var bstFromPreorder = function (preorder) {
    const build = (l, r) => {
        if(l>r){
            return null
        }
        const node = {
            val: preorder[l],
        }
        let border = l + 1;
        while (border <= r) {
            if (preorder[border] < preorder[l]) {
                border++;
            } else {
                break;
            }
        }
        node.left = build(l + 1, border - 1)
        node.right = build(border, r)
        return node

    }
    return build(0, preorder.length - 1)
};

李恒道

https://leetcode.cn/problems/minimum-size-subarray-sum/submissions/571876069/?envType=study-plan-v2&envId=top-interview-150

基础滑窗题

var minSubArrayLen = function (target, nums) {
    let l = 0; r = 0;
    let result = nums[0];
    let minLen = Number.MAX_SAFE_INTEGER
    while (l <= r && l < nums.length) {
        if (result < target) {
            if (r < nums.length-1) {
                r++;
                result += nums[r];
            } else {
                result -= nums[l];
                l++;
            }
        } else {
            minLen = Math.min(minLen, r - l+1);
            result -= nums[l];
            l++;
        }
    }
    return minLen==Number.MAX_SAFE_INTEGER?0:minLen
};

李恒道

https://leetcode.cn/submissions/detail/571930586/

感觉上应该用DC3，但是找不到js版本的
就看了一下题解用双指针过的

var lastSubstring = function (s) {
  let i = 0,
    j = 1,
    k = 0;
  while (j + k < s.length) {
    if (s[i + k] == s[j + k]) {
      k++;
    } else if (s[i + k] < s[j + k]) {
      i = i + k + 1;
      k = 0;
      if (i == j) {
        j = i + 1;
      }
    } else {
      j = j + k + 1;
      k = 0;
      if (i == j) {
        j = i + 1;
      }
    }
  }
  return s.slice(i);
};

李恒道

https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
前缀树问题
但是我是真想不通为什么要出这个狗螺蛳粉边界卡

class Tree {
  head;
  constructor() {
    this.head = {};
  }
  add(num) {
    let head = this.head;
    for (let index = 31; index >= 0; index--) {
      const bit = (num >> index) & 1;
      head[bit] = head[bit] ?? {};
      head = head[bit];
    }
  }
  getMaxXor(num) {
    let head = this.head;
    let result = num;
    for (let index = 31; index >= 0; index--) {
      let bit = ((num >> index) & 1) == 0 ? 1 : 0;
      if (head[bit] == undefined) {
        bit = bit==0?1:0;
      }
      result = result ^ (bit << index);
      head = head[bit];
    }
    return result;
  }
}
var findMaximumXOR = function (nums) {
  const tree = new Tree();
  tree.add(nums[0]);
  let result = 0;
  for (let index = 1; index < nums.length; index++) {
    const num = nums[index];
    result = Math.max(result, tree.getMaxXor(num));
    tree.add(num)
    if(result==1073741823){
      break;
    }
  }
  return result;
};

李恒道

好吧，是我复杂度问题

李恒道

https://leetcode.cn/problems/maximum-xor-with-an-element-from-array/submissions/572171968/
这个确实难，完全是对着题解的海量题硬凹了一个优化打过去的

var maximizeXor = function (nums, queries) {
    function generateTree(maxBit) {
        let treeHead = { min: Number.MAX_SAFE_INTEGER }
        let querie = 0
        const add = (num) => {
            let head = treeHead;
            head.min = Math.min(head.min, num)
            for (let index = maxBit; index >= 0; index--) {
                const bit = (num >> index) & 1;
                head[bit] = head[bit] ?? {
                    min: Number.MAX_SAFE_INTEGER
                };
                head = head[bit];
                head.min = Math.min(head.min, num)
            }
        }
        getMaxXor = (num) => {
            let head = treeHead;
            if (head.min > querie) {
                return -1
            }
            let result = num;
            for (let index = maxBit; index >= 0; index--) {
                let bit = ((num >> index) & 1) == 0 ? 1 : 0;
                if (head[bit] == undefined || head[bit].min > querie) {
                    bit = bit == 0 ? 1 : 0;
                }
                result = result ^ (bit << index);
                head = head[bit];
            }
            return result;
        }
        return {
            setQuery: (num) => {
                querie = num
            },
            add,
            getMaxXor
        }
    }

    const tree = generateTree(31 - Math.clz32(Math.max(...nums)));
    let maxXor = Number.MIN_SAFE_INTEGER;
    if (queries.length == 1) {
        for (let index = 0; index < nums.length; index++) {
            const num = nums[index];
            if (num <= queries[0][1]) {
                maxXor = Math.max(maxXor, num ^ queries[0][0])
            }
        }
        return [maxXor]

    }
    for (let index = 0; index < nums.length; index++) {
        const num = nums[index];
        tree.add(num)
    }
    let result = [];
    for (let index = 0; index < queries.length; index++) {
        const [num, query] = queries[index];
        tree.setQuery(query)
        result.push(tree.getMaxXor(num));
    }
    return result;
};