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

李恒道

https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked

没做出来
这题比较鸡贼
利用了前缀和以及hash
以末尾点为判断来看前边有多少种

var subarraySum = function (nums, k) {
    const numMap = new Map()
    let result = 0
    let sum = 0
    numMap.set(0, 1)
    for (const num of nums) {
        sum += num
        if (numMap.has(sum - k)) {
            result+=numMap.get(sum-k)
        }
        if (numMap.has(sum)) {
            numMap.set(sum, numMap.get(sum) + 1)
        }else{
            numMap.set(sum, 1)
        }
    }

    return result

};

李恒道

https://leetcode.cn/problems/sliding-window-maximum/submissions/557702437/?envType=study-plan-v2&envId=top-100-liked
想拿单调栈解来着
他妈写反判断了...

var maxSlidingWindow = function (nums, k) {
    const stack = []
    const ans = []
    for (let index = 0; index < k; index++) {
        const num = nums[index];
        while (num > nums[stack[stack.length-1]]) {
            stack.pop()
        }
        stack.push(index)
    }
    ans.push(nums[stack[0]])
    for (let index = k; index < nums.length; index++) {
        const num = nums[index];
        while (num > nums[stack[stack.length-1]]) {
            stack.pop()
        }
        while(stack[0]<=index-k||nums[stack[0]]<=num){
            stack.shift()
        }
        stack.push(index)
        ans.push(nums[stack[0]])
    }
    return ans;
};

李恒道

大小堆的解就不提了
解法3是真的天才

李恒道

https://leetcode.cn/problems/minimum-window-substring/submissions/557713308/?envType=study-plan-v2&envId=top-100-liked
差一点
边界太多了...
没憋出来

var minWindow = function (s, t) {
    const typeMap = new Map()
    let tpyeNum = 0
    for (let index = 0; index < t.length; index++) {
        const char = t[index];
        if (typeMap.has(char)) {
            typeMap.set(char, typeMap.get(char) + 1)
        } else {
            typeMap.set(char, 1)
            tpyeNum++;
        }
    }
    let left = -1
    let right = -1
    let result=""
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        right++
        if (typeMap.has(char)) {
            typeMap.set(char, typeMap.get(char) - 1)
            if (typeMap.get(char) == 0) {
                tpyeNum--;
            }
        }
        if (tpyeNum == 0) {
            while (true) {
                const char = s[left]
                if (typeMap.has(char)) {
                    if (typeMap.get(char) < 0) {
                        typeMap.set(char, typeMap.get(char) + 1)
                        left++;
                    } else if (typeMap.get(char) == 0) {
                        break;
                    }
                } else {
                    left++;
                }
            }
            const newResult=s.substring(left,right+1)
            result=(result==""||newResult.length<result.length)?newResult:result
        }

    }
    return result
};

李恒道

https://leetcode.cn/problems/maximum-subarray/submissions/557728791/?envType=study-plan-v2&envId=top-100-liked
这个没思路
但是解太草了...

var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};

李恒道

https://leetcode.cn/problems/merge-intervals/submissions/557733294/?envType=study-plan-v2&envId=top-100-liked
排序之后区间合并，复杂度NlogN

var merge = function (intervals) {
    intervals.sort((a, b) => {
        return a[0] - b[0]
    })
    const result = []
    for (let index = 0; index < intervals.length; index++) {
        const arr = intervals[index];
        const last = result[result.length - 1]??[0,-1]
        if (arr[0]>=last[0]&&arr[0]<=last[1]){
            last[1]=Math.max(arr[1],last[1])
        }else if (arr[1]>=last[0]&&arr[1]<=last[1]){
            last[0]=Math.max(arr[0],last[0])
        }else{
            result.push(arr)
        }
    }
    return result
};

李恒道

https://leetcode.cn/problems/rotate-array/submissions/558244872/?envType=study-plan-v2&envId=top-100-liked
只会题解1
题解2和3太神奇了
3反转还算能理解
2利用了公倍数酷酷一顿换算最后能得到环路数来进行遍历
真的牛逼

李恒道

https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
前缀和变种
easy

var productExceptSelf = function (nums) {
  const suffix = []
  const prefix = []
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    prefix[index] = num * (prefix[index - 1] ?? 1)
  }
  for (let index = nums.length - 1; index >= 0; index--) {
    const num = nums[index];
    suffix[index] = num * (suffix[index + 1] ?? 1)
  }
  const answer = []
  for (let index = 0; index < suffix.length; index++) {
    answer.push((prefix[index - 1] ?? 1) * (suffix[index + 1] ?? 1))
  }
  return answer
};

李恒道

https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked
将数组自身做正整数的存储数组
每个数字只跳动一次
复杂度ON

var firstMissingPositive = function (nums) {
  for (let index = 0; index < nums.length; index++) {
    let num = nums[index];
    while (true) {
      if (num <= 0 || num > nums.length) {
        break;
      }
      const nextNum = nums[num - 1]
      if (nextNum <= 0 || nextNum > nums.length) {
        //不需要设置了
        nums[num - 1] = num
        break;
      }
      if (nextNum == num) {
        break;
      }
      nums[num - 1] = num
      num = nextNum
    }
  }
  let minNum = 1
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    if (minNum == num) {
      minNum++
    }
  }
  return minNum
};```

李恒道

https://leetcode.cn/problems/set-matrix-zeroes/?envType=study-plan-v2&envId=top-100-liked
我本来想标记a字符...
感觉有点太取巧了，虽然比方法1强
方法2和3不太喜欢
太凹了
学了2的思路自己写了一下

var setZeroes = function (matrix) {
  let rowZero = false
  let colZero = false
  for (let index = 0; index < matrix[0].length; index++) {
    const num = matrix[0][index]
    if (num === 0) {
      rowZero = true
    }
  }
  for (let index = 0; index < matrix.length; index++) {
    const num = matrix[index][0]
    if (num === 0) {
      colZero = true
    }
  }
  for (let index = 0; index < matrix.length; index++) {
    const row = matrix[index];
    for (let indey = 0; indey < row.length; indey++) {
      const num = row[indey];
      if (num === 0) {
        matrix[index][0] = 0
        matrix[0][indey] = 0
      }

    }
  }
  for (let index = 1; index < matrix.length; index++) {
    const row = matrix[index];
    for (let indey = 1; indey < row.length; indey++) {
      if (matrix[index][0] === 0 | matrix[0][indey] === 0) {
        matrix[index][indey] = 0
      }
    }
  }
  if (rowZero) {
    for (let index = 0; index < matrix[0].length; index++) {
      matrix[0][index] = 0
    }
  }
  if (colZero) {
    for (let index = 0; index < matrix.length; index++) {
      matrix[index][0] = 0
    }
  }
  return matrix
};