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

李恒道

二分，简单题
https://leetcode.cn/problems/binary-search/submissions/569521757/

var search = function (nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const center = Math.floor((left + right) / 2);
        if (nums[center] < target) {
            left = center + 1
        } else if (nums[center] > target) {
            right = center - 1
        } else {
            return center
        }
    }
    return -1
};

李恒道

https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer/submissions/569521965/
链表基础题

var getDecimalValue = function (head) {
    let result = 0;
    while (head !== null) {
        result*=2;
        result += head.val;
        head=head.next
    }
    return result
};

李恒道

https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/submissions/569522962/
链表~秒了

var nodesBetweenCriticalPoints = function (head) {
    let firstNode = null;
    let lastNode = null;
    let lastVal = null;
    let pos = -1;
    let Max = -1;
    let Min = Number.MAX_SAFE_INTEGER;
    while (head !== null) {
        pos++;
        if (lastVal == null || head.next == null) {
            lastVal = head.val;
            head = head.next;
            continue;
        }
        if ((lastVal < head.val && head.next.val < head.val) || (lastVal > head.val && head.next.val > head.val)) {
            if (firstNode !== null) {
                Max = pos - firstNode
            } else {
                firstNode = pos
            }
            if (lastNode !== null) {
                Min = Math.min(Min, pos - lastNode)
                lastNode = pos
            } else {
                lastNode = pos
            }
        }
        lastVal=head.val;
        head = head.next;
    }
    return [Min==Number.MAX_SAFE_INTEGER?-1:Min,Max]
};

李恒道

https://leetcode.cn/problems/merge-nodes-in-between-zeros/submissions/569523251/
接近百分百！
开心

var mergeNodes = function (head) {
    let ptr = head
    while (head !== null) {
        if (head.val == 0 && head.next !== null) {
            while (head.next.next.val !== 0) {
                head.next.val += head.next.next.val;
                head.next.next = head.next.next.next;
            }
        }
        head = head.next
    }
    ptr = ptr.next;
    head = ptr
    while (head !== null) {
        if (head.next.val == 0) {
            head.next=head.next.next
        }
        head = head.next
    }
    return ptr

};

李恒道

https://leetcode.cn/problems/contains-duplicate-ii/submissions/569525278/
滑窗过了
偏简单的题

var containsNearbyDuplicate = function (nums, k) {
  const cache = new Map();
  k=Math.min(nums.length,k)
  for (let index = 0; index <= k; index++) {
    const num = nums[index];
    if (cache.has(num)) {
      return true;
    }
    cache.set(num, index);
  }
  for (let index = k + 1; index < nums.length; index++) {
    cache.delete(nums[index - k - 1]);
    const num = nums[index];
    if (cache.has(num)) {
      return true;
    }
    cache.set(num, index);
  }
  return false;
};

李恒道

https://leetcode.cn/problems/max-pair-sum-in-an-array/submissions/569525653/
基础哈希题
一次过

var maxSum = function (nums) {
  const cache = new Map();
  let result = -1;
  for (let index = 0; index < nums.length; index++) {
    let num = nums[index];
    let maxNum = 0;
    while (num !== 0) {
      const tailNum = num % 10;
      num = Math.floor(num / 10);
      maxNum = Math.max(maxNum, tailNum);
    }
    if (cache.has(maxNum)) {
      const lastNum = cache.get(maxNum);
      result = Math.max(result, lastNum + nums[index]);
      if (lastNum < nums[index]) {
        cache.set(maxNum, nums[index]);
      }
    } else {
      cache.set(maxNum, nums[index]);
    }
  }
  return result
};

李恒道

https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/submissions/569525779/
改改又过一题

var maximumSum = function (nums) {
  const cache = new Map();
  let result = -1;
  for (let index = 0; index < nums.length; index++) {
    let num = nums[index];
    let totalNum = 0;
    while (num !== 0) {
      const tailNum = num % 10;
      num = Math.floor(num / 10);
      totalNum = totalNum + tailNum;
    }
    if (cache.has(totalNum)) {
      const lastNum = cache.get(totalNum);
      result = Math.max(result, lastNum + nums[index]);
      if (lastNum < nums[index]) {
        cache.set(totalNum, nums[index]);
      }
    } else {
      cache.set(totalNum, nums[index]);
    }
  }
  return result;
};

李恒道

https://leetcode.cn/problems/max-number-of-k-sum-pairs/submissions/569526086/
过了~

var maxOperations = function (nums, k) {
  const cache = new Map();
  let result = 0;
  for (let index = 0; index < nums.length; index++) {
    let num = nums[index];

    if (cache.has(k - num)) {
      result++;
      if (cache.get(k - num) == 1) {
        cache.delete(k - num);
      } else {
        cache.set(k - num, cache.get(k - num) - 1);
      }
    } else {
      cache.set(num, (cache.get(num) ?? 0) + 1);
    }
  }
  return result;
};

李恒道

https://leetcode.cn/problems/target-sum/submissions/569711739/
基础dp，dfs秒了

var findTargetSumWays = function (nums, target) {
    const cache = new Map()
    const dfs = (index, rest) => {
        const flag = `${index} ${rest}`
        if (cache.has(flag)) {
            return cache.get(flag)
        }
        if (index >= nums.length) {
            return rest == 0 ? 1 : 0
        }
        const result = dfs(index + 1, rest + nums[index]) + dfs(index + 1, rest - nums[index])
        cache.set(flag, result);
        return result
    }
    return dfs(0, target)
};

李恒道

https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/submissions/569712767/
递归缓存秒了

var longestIncreasingPath = function (matrix) {
    const cache = new Map()
    const dfs = (posX, posY) => {
        const flag = `${posX} ${posY}`
        if (cache.has(flag)) {
            return cache.get(flag)
        }
        const arr = [[-1, 0], [0, -1], [+1, 0], [0, +1]]
        let result = 1;
        for (let index = 0; index < arr.length; index++) {
            const [relX, relY] = arr[index];
            const x = posX - relX;
            const y = posY - relY
            if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0) {
                continue;
            }
            if (matrix[x][y] > matrix[posX][posY]) {
                result = Math.max(result, dfs(x, y) + 1)
            }
        }
        cache.set(flag, result)
        return result
    }
    let result = 0;
    for (let index = 0; index < matrix.length; index++) {
        for (let indey = 0; indey < matrix[0].length; indey++) {
            const len = dfs(index, indey)
            result = Math.max(result, len)
        }
    }
    return result
};