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

李恒道

https://leetcode.cn/problems/hamming-distance/submissions/593245703/
简单题

/**
 * @param {number} x
 * @param {number} y
 * @Return {number}
 */
var hammingDistance = function(x, y) {
    x=x^y;
    let ans=0;
    while(x!==0){
      if(x&1){
        ans++
      }
      x=x>>1
    }
    return ans
};

李恒道

无语了
这题我以为是位压缩
结果是傻缓存

/**
 * @param {number} size
 */
var Bitset = function (size) {
  const bits = new Array(size).fill(0);
  this.bits = bits;
  this.nums = 0;
  this.flipStatus = false;
};

/**
 * @param {number} idx
 * @Return {void}
 */
Bitset.prototype.fix = function (idx) {
  if (this.flipStatus) {
    if (this.bits[idx] == 1) {
      this.bits[idx] = 0;
      this.nums--;
    }
  } else {
    if (this.bits[idx] == 0) {
      this.bits[idx] = 1;
      this.nums++;
    }
  }
};

/**
 * @param {number} idx
 * @return {void}
 */
Bitset.prototype.unfix = function (idx) {
  if (this.flipStatus) {
    if (this.bits[idx] == 0) {
      this.bits[idx] = 1;
      this.nums++;
    }
  } else {
    if (this.bits[idx] == 1) {
      this.bits[idx] = 0;
      this.nums--;
    }
  }
};

/**
 * @return {void}
 */
Bitset.prototype.flip = function () {
  this.flipStatus = !this.flipStatus;
};

/**
 * @return {boolean}
 */
Bitset.prototype.all = function () {
  if(this.flipStatus){
    return this.nums==0
  }
  return this.nums == this.bits.length;
};

/**
 * @return {boolean}
 */
Bitset.prototype.one = function () {
  if(this.flipStatus){
    return this.nums<this.bits.length
  }
  return this.nums > 0;
};

/**
 * @return {number}
 */
Bitset.prototype.count = function () {
  if(this.flipStatus){
    return this.bits.length-this.nums
  }
  return this.nums;
};

/**
 * @return {string}
 */
Bitset.prototype.toString = function () {
  if(this.flipStatus){
    let ans=""
    for (let index = 0; index < this.bits.length; index++) {
      ans+=this.bits[index]==1?"0":"1"
    }
    return ans
  }else{
    return this.bits.join("")
  }
};

李恒道

https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/submissions/593320881/
今天比较困难
终于凹过了

var RandomizedCollection = function () {
  this.arr = [];
  this.map = new Map();
};

/**
 * @param {number} val
 * @Return {boolean}
 */
RandomizedCollection.prototype.insert = function (val) {
  this.arr.push(val);
  let ans = false;
  if (!this.map.has(val)) {
    ans = true;
    this.map.set(val, new Set());
  }
  const nums = this.map.get(val);
  nums.add(this.arr.length - 1);
  return ans;
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function (val) {
  if (!this.map.has(val)) {
    return false;
  }
  const nums = this.map.get(val);
  const pos = nums.values().next().value;
  this.map.get(val).delete(pos)
  if (pos !== this.arr.length - 1) {
    const temp = this.arr[this.arr.length - 1];
    this.map.get(temp).delete(this.arr.length - 1);
    this.arr[this.arr.length - 1] = this.arr[pos];
    this.arr[pos] = temp;
    this.map.get(temp).add(pos);
  }
  this.arr.pop();
  if (nums.size == 0) {
    this.map.delete(val);
  }
  return true;
};

/**
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function () {
  return this.arr[Math.floor(Math.random() * this.arr.length)];
}

李恒道

https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-i/submissions/593514403/
打卡题

var minimumSubarrayLength = function (nums, k) {
  const count = new Array(32).fill(0);
  let left = 0;
  let xorNum = 0;
  let ans=Number.MAX_SAFE_INTEGER
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    xorNum = xorNum | num;
    for (let pos = 0; pos < 32; pos++) {
      if (num & (1 << pos)) {
        count[pos] += 1;
      }
    }
    if (xorNum >= k) {
      while (xorNum >= k&&left<=index) {
        ans=Math.min(ans,index-left+1)
        const lastNum = nums[left];
        for (let pos = 0; pos < 32; pos++) {
          if (lastNum & (1 << pos)) {
            count[pos] -= 1;
          }
          if (count[pos] == 0) {
            xorNum = xorNum & ~(1 << pos);
          }
        }
        left++;
      }
    }
  }
  return ans==Number.MAX_SAFE_INTEGER?-1:ans
};

李恒道

https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-ii/submissions/593514559/
一摸一样的题

var minimumSubarrayLength = function (nums, k) {
  const count = new Array(32).fill(0);
  let left = 0;
  let xorNum = 0;
  let ans=Number.MAX_SAFE_INTEGER
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    xorNum = xorNum | num;
    for (let pos = 0; pos < 32; pos++) {
      if (num & (1 << pos)) {
        count[pos] += 1;
      }
    }
    if (xorNum >= k) {
      while (xorNum >= k&&left<=index) {
        ans=Math.min(ans,index-left+1)
        const lastNum = nums[left];
        for (let pos = 0; pos < 32; pos++) {
          if (lastNum & (1 << pos)) {
            count[pos] -= 1;
          }
          if (count[pos] == 0) {
            xorNum = xorNum & ~(1 << pos);
          }
        }
        left++;
      }
    }
  }
  return ans==Number.MAX_SAFE_INTEGER?-1:ans
};

李恒道

https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/submissions/593516945/
改一改又凑活一个

var minimumDifference = function (nums, k) {
  const count = new Array(32).fill(0);
  let left = 0;
  let xorNum = 0;
  let ans = Math.abs(k - nums[0]);
  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];
    ans = Math.min(ans, Math.abs(num - k));
    xorNum = xorNum | num;
    for (let pos = 0; pos < 32; pos++) {
      if (num & (1 << pos)) {
        count[pos] += 1;
      }
    }
    if (xorNum >= k) {
      while (xorNum >= k && left <= index) {
        ans = Math.min(ans, Math.abs(xorNum - k));
        const lastNum = nums[left];
        for (let pos = 0; pos < 32; pos++) {
          if (lastNum & (1 << pos)) {
            count[pos] -= 1;
          }
          if (count[pos] == 0) {
            xorNum = xorNum & ~(1 << pos);
          }
        }
        left++;
      }
    }
    if (left <= index) {
      ans = Math.min(ans, Math.abs(xorNum - k));
    }
  }
  return ans;
};

王一之

ggnb 6w名了

李恒道

王一之 发表于 2025-1-16 14:31
ggnb 6w名了

1w名应该是够呛了
越打越没意思，300题以后就开始有边界感了
现在每天挑挑捡捡的打题

会的不做，会了还做什么
不会的不做，我不会还做什么

李恒道

https://leetcode.cn/submissions/detail/594018370/
2500分题第一次拿下！

function maxValue(nums, k) {
  const MX = 1 << 7;
  const n = nums.length;
  //原本是三层，index，当前index排第几个数字，xor的结果
  //因为从右到左计算，排列的时候如果不选当前数字，则之前的结果依然要继承
  //所以可以忽略index，使用两层来依次递推
  let xorArr = new Array(k + 1).fill(0).map((i) => new Array(MX).fill(false));
  xorArr[0][0] = true;
  let suf = new Array(n - k);

  for (let index = nums.length - 1; index >= 0; index--) {
    const num = nums[index];
    //根据index遍历到结尾有多少元素，即多少可能
    //例如当前元素排第四，后面有两个元素
    //则后面的元素只可能是第二个，第一个，第零个，所以边界是n - k - 1
    //而为了插入当前元素，最大只能为k-1个，所以边界是k - 1
    //之所以倒序是因为如果为true，则会设置当前个数+1的某个位置为true
    //如果正序会导致顺序错误
    for (let rank = Math.min(k - 1, n - k - 1); rank >= 0; rank--) {
      for (let xorNum = 0; xorNum < MX; xorNum++) {
        if (xorArr[rank][xorNum]) {
          xorArr[rank + 1][xorNum | num] = true;
        }
      }
    }
    //比如k有2个，一共六个元素，这时一定只有0到4的下坐标符合要求
    //所以要判断n-k
    if (index <= n - k) {
      //拷贝k个数字的数组
      suf[index] = [...xorArr[k]];
    }
  }
  //与上方同理，计算前缀
  xorArr = new Array(k + 1).fill(0).map((i) => new Array(MX).fill(false));
  xorArr[0][0] = true;
  let pre = new Array(n - k);
  for (let index = 0; index < n - k; index++) {
    const num = nums[index];
    for (let rank = Math.min(k - 1, index); rank >= 0; rank--) {
      for (let xorNum = 0; xorNum < MX; xorNum++) {
        if (xorArr[rank][xorNum]) {
          xorArr[rank + 1][xorNum | num] = true;
        }
      }
    }
    if (index >= k - 1) {
      pre[index] = [...xorArr[k]];
    }
  }
  //计算前缀和后缀的xor
  let ans = 0;
  for (let rank = k - 1; rank < n - k; rank++) {
    for (let xorNum = 0; xorNum < MX; xorNum++) {
      if (pre[rank][xorNum]) {
        //取该位置之后的后缀
        for (let xorNumSuf = 0; xorNumSuf < MX; xorNumSuf++) {
          if (suf[rank + 1][xorNumSuf]) {
            //前缀和后缀都存在，取最大的ans
            ans = Math.max(ans, xorNum ^ xorNumSuf);
          }
        }
      }
    }
  }
  return ans;
}

console.log(maxValue([4, 2, 5, 6, 7], 2));

李恒道

https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/
一次过！

var maxValueOfCoins = function (piles, k) {
    const cache=new Map()
  const dfs = (pos, times) => {
    if(times==0){
        return 0
    }
    if(pos>=piles.length){
        return 0
    }
    const tag=`${pos} ${times}`
    if(cache.has(tag)){
        return cache.get(tag)
    }
    let ans = dfs(pos + 1, times);
    let add = 0;
    let cond= Math.min(times, piles[pos].length)
    for (let index = 0; index < cond; index++) {
      add += piles[pos][index];
      ans = Math.max(ans, dfs(pos + 1, --times) + add);
    }
    cache.set(tag,ans)
    return ans
  };
  return dfs(0, k);
};