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

李恒道

https://leetcode.cn/problems/find-the-median-of-the-uniqueness-array/submissions/597033222/
这题照着答案看的，是真的复杂
还需要再研究

var medianOfUniquenessArray = function (nums) {
  const n=nums.length
  let l = 0,
    right = nums.length; // 中位数个数，不可能是0，可能是right
  const k = Math.floor(((n * (n + 1)) / 2 + 1) / 2);
  //判断从数量上是否满足k，如果满足可以往左逼，如果不满足说明越界了
  const check = (kinds) => {
    let left = 0;
    let map = new Map();
    let ans = 0;
    for (let index = 0; index < nums.length; index++) {
      const num = nums[index];
      map.set(num, (map.get(num) ?? 0) + 1);
      while (map.size > kinds) {
        map.set(nums[left], map.get(nums[left]) - 1);
        if (map.get(nums[left]) == 0) {
          map.delete(nums[left]);
        }
        left++;
      }
      ans += index-left+1;
    }
    return ans>=k?true:false;
  };
  while (l + 1 < right) {
    const mid = Math.floor((l + right) / 2);

    if (check(mid)) {
      //如果符合
      right = mid;
    } else {
      l = mid;
    }
  }
  return right
};

李恒道

https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-ii/submissions/597036800/
这题难度真的压力报表
陆陆续续搞了两三个小时才理解一个大概
很多种数据结构组合到一起
太精妙了

const binaryFind = (arr, num) => {
  let l = 0,
    r = arr.length - 1;
  while (l < r) {
    const mid = Math.floor((r + l) / 2);
    if (arr[mid] < num) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return r;
};
var countKConstraintSubstrings = function (s, k, queries) {
  const ans = [];
  const numsArr = new Array(s.length + 1).fill(0);
  const leftArr = new Array(s.length).fill(0);
  var countKConstraintSubstrings1 = function (s, k, l, r) {
    const times = [0, 0];
    let left = l;
    let ans = 0;
    for (let index = left; index <= r; index++) {
      const pos = s[index].charCodeAt() - 48;
      times[pos]++;
      while (times[0] > k && times[1] > k) {
        const leftPos = s[left++].charCodeAt() - 48;
        times[leftPos]--;
      }
      ans += index - left + 1;
      numsArr[index + 1] = numsArr[index] + index - left + 1;
      leftArr[index] = left;
    }
    return ans;
  };
  countKConstraintSubstrings1(s, k, 0, s.length - 1);
  for (const [l, r] of queries) {
    if (leftArr[r] <= l) {
      ans.push(((r - l + 2) * (r - l + 1)) / 2);
    } else {
      const j = binaryFind(leftArr, l);
      const add1 = ((j - l + 1) * (j - l)) / 2;
      let add2 = numsArr[r+1]-numsArr[j];
      // for (let index = j; index <= r; index++) {
      //   add2 += index - leftArr[index] + 1;
      // }
      ans.push(add1 + add2);
    }
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/1GxJYY/submissions/597038543/
一次过
神经刀了

var beautifulBouquet = function (flowers, cnt) {
  const times = new Map();
  let left = 0;
  let ans = 0;
  const mod = 10 ** 9 + 7;
  for (let index = 0; index < flowers.length; index++) {
    const flower = flowers[index];
    times.set(flower, (times.get(flower) ?? 0) + 1);
    while (times.get(flower) > cnt) {
      const leftFlower = flowers[left++];
      times.set(leftFlower, times.get(leftFlower) - 1);
    }
    ans += index - left + 1;
    ans %= mod;
  }
  return (ans %= mod);
};

李恒道

https://leetcode.cn/problems/binary-subarrays-with-sum/submissions/597742837/
秒了

var numSubarraysWithSum = function (nums, goal) {
  let left = 0;
  let total = 0;
  let ans = 0;
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    total += num;
    while (total > goal) {
      total -= nums[left++];
    }
    let tempLeft=left;
    let tempTotal=total
    while(tempTotal==goal&&tempLeft<=index){
      tempTotal -= nums[tempLeft++];
      ans++;
    }
  }
  return ans;
};

李恒道

https://leetcode.cn/problems/count-number-of-nice-subarrays/submissions/597746946/
1600分秒了~

var numberOfSubarrays = function (nums, k) {
  let left1 = 0;
  let left2 = 0;
  let total1 = 0;
  let total2 = 0;
  let ans = 0;
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    total1 += num % 2;
    total2 += num % 2;
    while (total1 > k) {
      total1 -= nums[left1++] % 2;
    }
    while (total2 >= k) {
      total2 -= nums[left2++] % 2;
    }
    ans += left2 - left1;
  }
  return ans;
};

李恒道

https://leetcode.cn/submissions/detail/597841365/
打卡题

var removeDuplicates = function (nums) {
  let left = 2;
  for (let index = 2; index < nums.length; index++) {
    const num = nums[index];
    if(num==nums[left-2]){
      continue;
    }
    nums[left++]=num
  }
  return left
};

李恒道

https://leetcode.cn/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii/submissions/597842370/
这题感觉到了
但是aeiou的边界没判断好
要好好看一下答案

var countOfSubstrings = function (word, k) {
  const map1 = new Map();
  const map2 = new Map();
  let total1 = 0;
  let total2 = 0;
  let left1 = 0;
  let left2 = 0;
  let ans = 0;
  const checkStr = "aeiou";
  for (let index = 0; index < word.length; index++) {
    const char = word[index];
    if (checkStr.indexOf(char) !== -1) {
      map1.set(char, (map1.get(char) ?? 0) + 1);
      map2.set(char, (map2.get(char) ?? 0) + 1);
    } else {
      total1++;
      total2++;
    }
    while (total1 > k && map1.size == 5) {
      const char = word[left1++];
      if (checkStr.indexOf(char) !== -1) {
        map1.set(char, (map1.get(char) ?? 0) - 1);
        if (map1.get(char) == 0) {
          map1.delete(char);
        }
      } else {
        total1--;
      }
    }
    while (total2 >= k && map2.size == 5) {
      const char = word[left2++];
      if (checkStr.indexOf(char) !== -1) {
        map2.set(char, (map2.get(char) ?? 0) - 1);
        if (map2.get(char) == 0) {
          map2.delete(char);
        }
      } else {
        total2--;
      }
    }
      ans += left2-left1;

  }
  return ans;
};

李恒道

https://leetcode.cn/problems/subarrays-with-k-different-integers/submissions/597843171/
酸爽
过了

var subarraysWithKDistinct = function(nums, k) {
  const map1 = new Map();
  const map2 = new Map();
  let left1 = 0;
  let left2 = 0;
  let ans = 0;
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    map1.set(num, (map1.get(num) ?? 0) + 1);
    map2.set(num, (map2.get(num) ?? 0) + 1);
    while (map1.size >k) {
      const num = nums[left1++];
      map1.set(num, (map1.get(num) ?? 0) -1);
      if (map1.get(num) == 0) {
        map1.delete(num);
      }
    }
    while (map2.size >=k) {
      const num = nums[left2++];
      map2.set(num, (map2.get(num) ?? 0) - 1);
      if (map2.get(num) == 0) {
        map2.delete(num);
      }
    }
    ans += left2-left1;
  }
  return ans
};

李恒道

https://leetcode.cn/problems/find-smallest-letter-greater-than-target/submissions/597844219/
秒了

var nextGreatestLetter = function(letters, target) {
    let ans=letters[0]
    let left=0,right=letters.length-1;
    while(left<=right){
      const mid=Math.floor((right+left)/2)
      const char=letters[mid];
      if(char<=target){
        left=mid+1;
      }else{
        right=mid-1;
        ans=char
      }
    }
    return ans
};

李恒道

https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/submissions/597847873/
过了

const findMin = (arr, target) => {
  let left = 0,
    right = arr.length - 1;
  let ans = -1;
  while (left <= right) {
    const mid = Math.floor((right + left) / 2);
    const char = arr[mid];
    if (char < target) {
      left = mid + 1;
      ans = mid;
    } else {
      right = mid - 1;
    }
  }
  return ans;
};
const findMax = (arr, target) => {
  let left = 0,
    right = arr.length - 1;
  let ans = -1;
  while (left <= right) {
    const mid = Math.floor((right + left) / 2);
    const char = arr[mid];
    if (char <= target) {
      left = mid + 1;
    } else {
      right = mid - 1;
      ans = mid;
    }
  }
  return ans;
};
var maximumCount = function (nums) {
  const min = findMin(nums, 0) + 1;
  let max = findMax(nums, 0);
  if (max != -1) {
    max = nums.length - max;
  }
  return Math.max(max, min);
};