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

李恒道

https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/submissions/572181751/?envType=study-plan-v2&envId=top-interview-150

双指针

var twoSum = function(numbers, target) {
  let l=0,r=numbers.length-1;
  while(l!=r){
    const total=numbers[l]+numbers[r]
    if(total==target){
      return [l+1,r+1]
    }else if(total<target){
      l++
    }else{
      r--
    }
  }
};

李恒道

https://leetcode.cn/problems/is-subsequence/submissions/572198403/?envType=study-plan-v2&envId=top-interview-150
简单题
秒了

var isSubsequence = function(s, t) {
  if(s.length==0){
    return true
  }
  let l1=0;l2=0;
  while (l2<t.length&&l1.length!=s.length) {
    if(s[l1]==t[l2]){
      l1++;
      l2++;
      if(l1==s.length){
        return true
      }
    }else{
      l2++
    }
  }
  return false
};

李恒道

https://leetcode.cn/problems/maximum-gap/submissions/572420356/

桶排，太复杂了...
凹了好久

var maximumGap = function (nums) {
    if (nums.length < 2) {
        return 0
    }
    let min = nums[0];
    let max = nums[0];
    for (let index = 0; index < nums.length; index++) {
        min = Math.min(min, nums[index])
        max = Math.max(max, nums[index])
    }
    const bucket = new Array(nums.length).fill(undefined);
    const sep = Math.ceil((max - min) / nums.length)
    const getBucketIndex = (num) => {
        return Math.floor((num - min) / (sep == 0 ? 1 : sep))
    }
    for (let index = 0; index < nums.length; index++) {
        const bucketIndex = getBucketIndex(nums[index])
        if (bucket[bucketIndex] == undefined) {
            bucket[bucketIndex] = {}
            bucket[bucketIndex].max = nums[index]
            bucket[bucketIndex].min = nums[index]
        } else {
            bucket[bucketIndex].max = Math.max(bucket[bucketIndex].max, nums[index])
            bucket[bucketIndex].min = Math.min(bucket[bucketIndex].min, nums[index])
        }
    }
    let lastNum = bucket[0].max;
    let result = bucket[0].max - bucket[0].min;
    for (let index = 1; index < bucket.length; index++) {
        if (bucket[index] !== undefined) {
            let currentNum = bucket[index].min;
            result = Math.max(result, currentNum - lastNum);
            lastNum = bucket[index].max;
        }
    }

    return result
};

李恒道

https://leetcode.cn/problems/binary-tree-cameras/submissions/572441200/
状态二叉树dp

var minCameraCover = function (root) {
  const dfs = (root) => {
    if (root == null) {
      return {
        has_camera: Number.MAX_SAFE_INTEGER,
        has_cover: 0,
        no_cover: Number.MAX_SAFE_INTEGER,
      };
    }
    // 放了相机，没放相机但是覆盖，没被覆盖
    const left = dfs(root.left);
    const right = dfs(root.right);
    let has_camera =
      Math.min(left.no_cover, left.has_camera, left.has_cover) +
      Math.min(right.no_cover, right.has_camera, right.has_cover) +
      1;
    let no_cover = left.has_cover + right.has_cover;
    let has_cover = Math.min(
      left.has_camera + right.has_camera,
      left.has_camera + right.has_cover,
      left.has_cover + right.has_camera
    );
    return {
      has_camera,
      no_cover,
      has_cover,
    };
  };
  let result = dfs(root);
  return Math.min(result.has_camera, result.has_cover);
};

李恒道

https://leetcode.cn/problems/egg-drop-with-2-eggs-and-n-floors/submissions/572446595/
这题没A出来
考虑鸡蛋掉落的最坏情况

var twoEggDrop = function (n) {
  const dp = new Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
  dp[0] = 0;
  dp[1]=1
  for (let index =2; index < dp.length; index++) {
    for (let indey = 1; indey <= index; indey++) {
      dp[index] = Math.min(
        dp[index],
        Math.max(indey - 1, dp[index - indey]) + 1
      );
    }
  }
  return dp.pop();
};

李恒道

https://leetcode.cn/problems/combinations/submissions/572773506/?envType=study-plan-v2&envId=top-interview-150

dfs题，感觉最近打回溯和链表丝滑多了

var combine = function (n, k) {
    const result = []
    const dfs = (ans, l) => {
        if (ans.length == k) {
            result.push([...ans])
            return
        } else if ((k - ans.length) > (n - l)) {
            return
        }
        for (let index = l + 1; index <= n; index++) {
            ans.push(index);
            dfs(ans,index);
            ans.pop();
        }
    }
    dfs([], 0)

    return result;
};

李恒道

https://leetcode.cn/submissions/detail/572746217/
鸡蛋掉落题，这个是真难

var superEggDrop = function (k, n) {
    // k蛋数量
    const dp = new Array(k + 1).fill(0).map(() => new Array(n + 1).fill(Number.MAX_SAFE_INTEGER))
    for (let index = 0; index < dp[0].length; index++) {
        dp[1][index] = index
    }
    for (let index = 0; index < dp.length; index++) {
        dp[index][0] = 0;
    }
    for (let index = 2; index < dp.length; index++) {
        for (let indey = 1; indey < dp[0].length; indey++) {
            const layoutHeight = indey;
            let l = 0, r = layoutHeight;
            while (l <= r) {
                const center = Math.floor((l + r) / 2);
                let result1 = dp[index - 1][center - 1] ?? Number.MIN_SAFE_INTEGER //随着楼层增高逐渐增大
                let result2 = dp[index][layoutHeight - center] //随着楼层增高逐渐变小
                dp[index][indey] = Math.min(dp[index][indey], Math.max(result1, result2) + 1);
                if (result1 <= result2) {
                    l = center + 1
                } else {
                    r = center - 1
                }
            }
            // for (let currentLayout = 1; currentLayout <= layoutHeight; currentLayout++) {
            //     dp[index][indey] = Math.min(dp[index][indey], Math.max(dp[index - 1][currentLayout - 1], dp[index][layoutHeight - currentLayout]) + 1)
            // }
        }
    }
    return dp.pop().pop()
};

李恒道

https://leetcode.cn/submissions/detail/572771593/
反转链表，一波过

var reverseBetween = function (head, left, right) {
    let reverNum = right - left + 1;
    const reverse = (node) => {
        let ret = node;
        let endNode = node;
        let current = node.next;
        reverNum--
        while (reverNum !== 0) {
            const next = current.next;
            current.next = ret;
            ret = current;
            current = next;
            reverNum--;
        }
        endNode.next = current;
        return ret
    }
    left = left - 1;
    right = right - 1;
    if (left == 0) {
        return reverse(head)
    } else {
        let headNode = head
        let lastNode = headNode
        while (left != 0) {
            lastNode = headNode
            headNode = headNode.next;
            left--;
        }
        lastNode.next = reverse(headNode)
    }
    return head
};

李恒道

https://leetcode.cn/problems/maximum-height-of-a-triangle/submissions/572777112/
基础题

var maxHeightOfTriangle = function (red, blue) {
    let line1 = 0;
    let lint2 = 0;
    let isLine1 = true;
    let times = 1;
    let ret=0;
    while (true) {
        if (isLine1) {
            line1 += times;
        } else {
            lint2 += times;
        }
        if((red>=line1&&blue>=lint2)||(blue>=line1&&red>=lint2)){
            ret++
            isLine1=!isLine1
            times++;
        }else{
            break
        }
    }
    return ret
};

李恒道

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/submissions/573065097/?envType=study-plan-v2&envId=top-interview-150

链表基础题
秒了

var deleteDuplicates = function (head) {
    let result = {
        next: head
    };
    let pre = result;
    while (head != null) {
        if (head.next?.val == head.val) {
            let val = head.val
            while (val == head?.val) {
                head = head.next;
            }
            pre.next = head;
        }else{
            pre = head;
            head = head.next;
        }
    }
    return result.next
};