青海网站建设推广_深圳绿色建筑信息平台_西安疫情最新消息_谷歌浏览器下载官方正版

23

分治

var mergeKLists = function(lists) {if (!lists || lists.length === 0) return null;function mergeTwoLists(l1, l2) {if (!l1) return l2;if (!l2) return l1;if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}function merge(lists, left, right) {//通过下标分治if (left === right) return lists[left];//边界：只有一个链表const mid = Math.floor((left + right) / 2);const l1 = merge(lists, left, mid);const l2 = merge(lists, mid + 1, right);return mergeTwoLists(l1, l2);}return merge(lists, 0, lists.length - 1);
};

438

和78差不多

var findAnagrams = function(s, p) {//const vis = new Set();const mapt=new Map();const maps=new Map();//let less=p.length;const ans=[];/*  不能用 set ，因为可能窗口中有多个相同的目标字符，得用 Map比对数目 //数组模拟队列for(r=0;r<p.length;r++){if (vis.has(s[r])) continue;vis.add(s[r]);if (p.has(s[r])) less--}*/for(let i of p){mapt.set(i,(mapt.get(i)||0)+1);}let less=mapt.size;let l=0;let r=0;for(;r<p.length;r++){maps.set(s[r],(maps.get(s[r])||0)+1);if (mapt.has(s[r]) && maps.get(s[r])===mapt.get(s[r])) less--;//注意：只有第一次相等时才减}//出来 r=p.length//r++while(r<s.length){if (less===0){ans.push(l);}if (mapt.has(s[l]) && mapt.get(s[l])===maps.get(s[l])) less++;//))) less++;maps.set(s[l],maps.get(s[l])-1);maps.set(s[r],(maps.get(s[r])||0)+1);if (mapt.has(s[r]) && maps.get(s[r])===mapt.get(s[r])) less--;l++;r++;}if(less===0) ans.push(l);return ans;
};

线段树

class SegmentTreeLazy {constructor(nums) {this.n = nums.length;this.tree = new Array(this.n * 4).fill(0);this.lazy = new Array(this.n * 4).fill(0);this.build(nums, 0, 0, this.n - 1);}build(nums, node, l, r) {if (l === r) {this.tree[node] = nums[l];} else {const mid = Math.floor((l + r) / 2);//二分分治this.build(nums, node * 2 + 1, l, mid);this.build(nums, node * 2 + 2, mid + 1, r);this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];}                                           //归并}pushDown(node, l, r) {if (this.lazy[node] !== 0) {const mid = Math.floor((l + r) / 2);const left = node * 2 + 1, right = node * 2 + 2;this.tree[left] += this.lazy[node] * (mid - l + 1);this.tree[right] += this.lazy[node] * (r - mid);this.lazy[left] += this.lazy[node];this.lazy[right] += this.lazy[node];this.lazy[node] = 0;}}updateRange(qL, qR, val, node = 0, l = 0, r = this.n - 1) {if (qR < l || qL > r) return;if (qL <= l && r <= qR) {this.tree[node] += val * (r - l + 1);this.lazy[node] += val;return;}this.pushDown(node, l, r);const mid = Math.floor((l + r) / 2);this.updateRange(qL, qR, val, node * 2 + 1, l, mid);this.updateRange(qL, qR, val, node * 2 + 2, mid + 1, r);this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];}queryRange(qL, qR, node = 0, l = 0, r = this.n - 1) {if (qR < l || qL > r) return 0;if (qL <= l && r <= qR) return this.tree[node];this.pushDown(node, l, r);const mid = Math.floor((l + r) / 2);const leftSum = this.queryRange(qL, qR, node * 2 + 1, l, mid);const rightSum = this.queryRange(qL, qR, node * 2 + 2, mid + 1, r);return leftSum + rightSum;}
}