跳到主要内容

12 篇博文 含有标签「设计」

查看所有标签

· 阅读需 3 分钟

1、题干

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...]

实现 SmallestInfiniteSet 类:

  • SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
  • int popSmallest() 移除 并返回该无限集中的最小整数。
  • void addBack(int num) 如果正整数 num 存在于无限集中,则将一个 num 添加 到该无限集最后。

 

示例:

输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]

解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 已经在集合中,所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ,因为 1 是最小的整数,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ,并将其从集合中移除。
smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ,因为 1 在上一步中被添加到集合中,
// 且 1 是最小的整数,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ,并将其从集合中移除。

 

提示:

  • 1 <= num <= 1000
  • 最多调用 popSmallestaddBack 方法 共计 1000

2、思路

两个思路:

  • 优先队列:直接用优先队列存取数据即可,但要注意数字不能重复,总体最差时间复杂度 O(nlogn)O(n\log{n})
  • 暴力:由于数据范围比较小,可以使用计数排序的思路存取数据进行暴力求解,总体最差时间复杂度 O(n2)O(n^2)

3、代码

优先队列

const N = 1001;
class SmallestInfiniteSet {
nums = new Array(N).fill(1);
minQueue = new MinPriorityQueue();
constructor() {
for (let i = 1; i < N; i++) {
this.minQueue.enqueue(i);
}
}

popSmallest(): number {
const n = this.minQueue.dequeue().element;
this.nums[n] = 0;
return n;
}

addBack(num: number): void {
if (this.nums[num]) return;
this.nums[num] = 1;
this.minQueue.enqueue(num);
}
}

暴力

class SmallestInfiniteSet {
nums: number[] = [];
constructor() {
this.nums = new Array(1001).fill(1);
}

popSmallest(): number {
const k = this.nums.findIndex((n, i) => i > 0 && n > 0);
this.nums[k] = 0;
return k;
}

addBack(num: number): void {
this.nums[num] = 1;
}
}

· 阅读需 3 分钟

1、题干

给你一个数组 nums ,请你完成两类查询。

  1. 其中一类查询要求 更新 数组 nums 下标对应的值
  2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的  ,其中 left <= right

实现 NumArray 类:

  • NumArray(int[] nums) 用整数数组 nums 初始化对象
  • void update(int index, int val)nums[index] 的值 更新val
  • int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的  (即,nums[left] + nums[left + 1], ..., nums[right]

 

示例 1:

输入
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出
[null, 9, null, 8]

解释
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

 

提示:

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • 调用 updatesumRange 方法次数不大于 3 * 104 

2、思路

树状数组

3、代码

class NumArray {
treeNums = [];

constructor(nums: number[]) {
const sums = new Array(nums.length + 1).fill(0);
this.treeNums = new Array(nums.length + 1).fill(0);

for (let i = 1; i < sums.length; i++) {
sums[i] = nums[i - 1] + sums[i - 1];
this.treeNums[i] = sums[i] - sums[i - this.lowbit(i)];
}
}

lowbit(i: number) {
return i & -i;
}

sum(r: number) {
let ans = 0;

while (r > 0) {
ans += this.treeNums[r];
r = r - this.lowbit(r);
}

return ans;
}

update(i: number, val: number): void {
const d = val - this.sumRange(i, i);

i += 1;
while (i < this.treeNums.length) {
this.treeNums[i] += d;
i = i + this.lowbit(i);
}
}

sumRange(left: number, right: number): number {
left += 1, right += 1;
return this.sum(right) - this.sum(left - 1);
}
}

· 阅读需 3 分钟

1、题干

设计一个算法:接收一个字符流,并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如,words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a''x''y''z' ,你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类:

  • StreamChecker(String[] words) :构造函数,用字符串数组 words 初始化数据结构。
  • boolean query(char letter):从字符流中接收一个新字符,如果字符流中的任一非空后缀能匹配 words 中的某一字符串,返回 true ;否则,返回 false

 

示例:

输入:
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
输出:
[null, false, false, false, true, false, true, false, false, false, false, false, true]

解释:
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ,因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ,因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ,因为 'kl' 在 words 中

 

提示:

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 200
  • words[i] 由小写英文字母组成
  • letter 是一个小写英文字母
  • 最多调用查询 4 * 104

2、思路

  • 构造函数:字典树存储所有单词的逆序串
  • query:数组存储字符流,按字符流逆序查找字典树中是否存在该后缀

3、代码

class StreamChecker {
letters = [];
trie = { end: false };

constructor(words: string[]) {
for (const word of words) this.add(word);
}

query(letter: string): boolean {
this.letters.push(letter);
return this.find(this.letters);
}

add(word: string) {
let t = this.trie;
for (let i = word.length - 1; i > -1; i--) {
if (!t[word[i]]) t[word[i]] = { end: false };
t = t[word[i]];
}
t.end = true;
}

find(letters: string[]) {
let t = this.trie;
for (let i = letters.length - 1; i > -1; i--) {
t = t[letters[i]];
if (!t) return false;
if (t.end) return true;
}
return t.end;
}
}

4、复杂度

  • 时间复杂度:构造函数 O(mn)O(mn),query O(mk)O(mk),其中 n为单词数,m 为单词长度,k 为查询次数
  • 空间复杂度:O(mn+k)O(mn+k)

5、执行结果

image.png

· 阅读需 5 分钟

1、题干

你需要设计一个包含验证码的验证系统。每一次验证中,用户会收到一个新的验证码,这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了,那么它会在 currentTime (可能与之前的 currentTime 不同)时刻延长 timeToLive 秒。

请你实现 AuthenticationManager 类:

  • AuthenticationManager(int timeToLive) 构造 AuthenticationManager 并设置 timeToLive 参数。
  • generate(string tokenId, int currentTime) 给定 tokenId ,在当前时间 currentTime 生成一个新的验证码。
  • renew(string tokenId, int currentTime) 将给定 tokenId 且 未过期 的验证码在 currentTime 时刻更新。如果给定 tokenId 对应的验证码不存在或已过期,请你忽略该操作,不会有任何更新操作发生。
  • countUnexpiredTokens(int currentTime) 请返回在给定 currentTime 时刻,未过期 的验证码数目。

如果一个验证码在时刻 t 过期,且另一个操作恰好在时刻 t 发生(renew 或者 countUnexpiredTokens 操作),过期事件 优先于 其他操作。

 

示例 1:

输入:
["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"]
[[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]]
输出:
[null, null, null, 1, null, null, null, 0]

解释:
AuthenticationManager authenticationManager = new AuthenticationManager(5); // 构造 AuthenticationManager ,设置 timeToLive = 5 秒。
authenticationManager.renew("aaa", 1); // 时刻 1 时,没有验证码的 tokenId 为 "aaa" ,没有验证码被更新。
authenticationManager.generate("aaa", 2); // 时刻 2 时,生成一个 tokenId 为 "aaa" 的新验证码。
authenticationManager.countUnexpiredTokens(6); // 时刻 6 时,只有 tokenId 为 "aaa" 的验证码未过期,所以返回 1 。
authenticationManager.generate("bbb", 7); // 时刻 7 时,生成一个 tokenId 为 "bbb" 的新验证码。
authenticationManager.renew("aaa", 8); // tokenId 为 "aaa" 的验证码在时刻 7 过期,且 8 >= 7 ,所以时刻 8 的renew 操作被忽略,没有验证码被更新。
authenticationManager.renew("bbb", 10); // tokenId 为 "bbb" 的验证码在时刻 10 没有过期,所以 renew 操作会执行,该 token 将在时刻 15 过期。
authenticationManager.countUnexpiredTokens(15); // tokenId 为 "bbb" 的验证码在时刻 15 过期,tokenId 为 "aaa" 的验证码在时刻 7 过期,所有验证码均已过期,所以返回 0 。

 

提示:

  • 1 <= timeToLive <= 108
  • 1 <= currentTime <= 108
  • 1 <= tokenId.length <= 5
  • tokenId 只包含小写英文字母。
  • 所有 generate 函数的调用都会包含独一无二的 tokenId 值。
  • 所有函数调用中,currentTime 的值 严格递增 。
  • 所有函数的调用次数总共不超过 2000 次。

2、思路

根据题意模拟,token 存储在哈希表中;generaterenew 直接读写哈希表,时间复杂度 O(1)O(1)countUnexpiredTokens 需要遍历哈希表中所有值,时间复杂度为 O(n)O(n)

由于所有函数调用次数最多为 20002000,所以时间复杂度的最大量级为 100010001000*1000,基本不会出现超时

3、代码

class AuthenticationManager {
timeToLive: number;
tokenMap: Map<string, number>;

constructor(timeToLive: number) {
this.timeToLive = timeToLive;
this.tokenMap = new Map();
}

generate(tokenId: string, currentTime: number): void {
this.tokenMap.set(tokenId, currentTime + this.timeToLive);
}

renew(tokenId: string, currentTime: number): void {
if (this.tokenMap.get(tokenId) > currentTime) this.generate(tokenId, currentTime);
}

countUnexpiredTokens(currentTime: number): number {
let ans = 0;
for (const t of this.tokenMap.values()) {
if (t > currentTime) ans++;
}
return ans;
}
}

4、复杂度

  • 时间复杂度:generate O(1)O(1)renew O(1)O(1)countUnexpiredTokens O(n)O(n)
  • 空间复杂度:O(n)O(n)

5、执行结果

image.png

· 阅读需 6 分钟

1、题干

给你两个整数 m 和 k ,以及数据流形式的若干整数。你需要实现一个数据结构,计算这个数据流的 MK 平均值 。

MK 平均值 按照如下步骤计算:

  1. 如果数据流中的整数少于 m 个,MK 平均值 为 -1 ,否则将数据流中最后 m 个元素拷贝到一个独立的容器中。
  2. 从这个容器中删除最小的 k 个数和最大的 k 个数。
  3. 计算剩余元素的平均值,并 向下取整到最近的整数 。

请你实现 MKAverage 类:

  • MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。
  • void addElement(int num) 往数据流中插入一个新的元素 num 。
  • int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数 ,结果需 向下取整到最近的整数

 

示例 1:

输入:
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
输出:
[null, null, null, -1, null, 3, null, null, null, 5]

解释:
MKAverage obj = new MKAverage(3, 1);
obj.addElement(3); // 当前元素为 [3]
obj.addElement(1); // 当前元素为 [3,1]
obj.calculateMKAverage(); // 返回 -1 ,因为 m = 3 ,但数据流中只有 2 个元素
obj.addElement(10); // 当前元素为 [3,1,10]
obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]
// 删除最小以及最大的 1 个元素后,容器为 [3]
// [3] 的平均值等于 3/1 = 3 ,故返回 3
obj.addElement(5); // 当前元素为 [3,1,10,5]
obj.addElement(5); // 当前元素为 [3,1,10,5,5]
obj.addElement(5); // 当前元素为 [3,1,10,5,5,5]
obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]
// 删除最小以及最大的 1 个元素后,容器为 [5]
// [5] 的平均值等于 5/1 = 5 ,故返回 5

 

提示:

  • 3 <= m <= 105
  • 1 <= k*2 < m
  • 1 <= num <= 105
  • addElement 与 calculateMKAverage 总操作次数不超过 105 次。

这10分真的十分难拿,临场肯定写不出来,没有第三方库肯定也写不出来

2、思路

3棵二叉搜索树保存最近 m 个数字,其中 trees[0] 保存最小的 k 个数、trees[1] 保存中间的 m - 2*k 个数、trees[2] 保存最大的 k 个数。保存中间数字之和 sum,并在添加元素时更新,以便快速计算平均值。

addElement 时先进行移除操作,再进行插入操作:

  • 若当前已超过 m 个数,则从树中移除倒数第 m+1 个数,然后将处于后方树中最小的数字往前方的树填充
  • 将当前数字插入第一棵树,然后将前方树中多余的最大数字往后方的树填充

calculateMKAverage 直接使用中间数字之和 sum 求平均

3、代码

var MKAverage = function (m, k) {
this.m = m;
this.k = k;

this.nums = [];
this.trees = [new AVLTree(), new AVLTree(), new AVLTree()];
this.sum = 0;
};

MKAverage.prototype.addElement = function (num) {
this.nums.push(num);
const trees = this.trees;

// remove
if (this.nums.length > this.m) {
const n = this.nums[this.nums.length - this.m - 1];
let i = trees.findIndex(t => t.contains(n));

if (i === 1) this.sum -= n;
trees[i].remove(n);

for (; i < trees.length - 1 && trees[i + 1].size > 0; i++) {
const tmin = trees[i + 1].min();
trees[i + 1].remove(tmin);
trees[i].insert(tmin);
if (i === 0) this.sum -= tmin;
else if (i === 1) this.sum += tmin;
}
}

// insert
for (let i = 0; i < trees.length; i++) {
const c = i !== 1 ? this.k : this.m - 2 * this.k;
trees[i].insert(num);
if (i === 1) this.sum += num;

if (trees[i].size <= c) break;

num = trees[i].max();
trees[i].remove(num);
if (i === 1) this.sum -= num;
}
};

MKAverage.prototype.calculateMKAverage = function () {
return this.nums.length < this.m ? -1 : (this.sum / (this.m - 2 * this.k)) >> 0;
};

// https://github.com/w8r/avl/
function print(root,printNode){if(printNode===void 0)printNode=function(n){return n.key};var out=[];row(root,'',true,function(v){return out.push(v)},printNode);return out.join('')}function row(root,prefix,isTail,out,printNode){if(root){out((""+prefix+(isTail?'└── ':'├── ')+(printNode(root))+"\n"));var indent=prefix+(isTail?' ':'│ ');if(root.left){row(root.left,indent,false,out,printNode)}if(root.right){row(root.right,indent,true,out,printNode)}}}function isBalanced(root){if(root===null){return true}var lh=height(root.left);var rh=height(root.right);if(Math.abs(lh-rh)<=1&&isBalanced(root.left)&&isBalanced(root.right)){return true}return false}function height(node){return node?(1+Math.max(height(node.left),height(node.right))):0}function loadRecursive(parent,keys,values,start,end){var size=end-start;if(size>0){var middle=start+Math.floor(size/2);var key=keys[middle];var data=values[middle];var node={key:key,data:data,parent:parent};node.left=loadRecursive(node,keys,values,start,middle);node.right=loadRecursive(node,keys,values,middle+1,end);return node}return null}function markBalance(node){if(node===null){return 0}var lh=markBalance(node.left);var rh=markBalance(node.right);node.balanceFactor=lh-rh;return Math.max(lh,rh)+1}function sort(keys,values,left,right,compare){if(left>=right){return}var pivot=keys[(left+right)>>1];var i=left-1;var j=right+1;while(true){do{i++}while(compare(keys[i],pivot)<0);do{j--}while(compare(keys[j],pivot)>0);if(i>=j){break}var tmp=keys[i];keys[i]=keys[j];keys[j]=tmp;tmp=values[i];values[i]=values[j];values[j]=tmp}sort(keys,values,left,j,compare);sort(keys,values,j+1,right,compare)}function DEFAULT_COMPARE(a,b){return a>b?1:a<b?-1:0}function rotateLeft(node){var rightNode=node.right;node.right=rightNode.left;if(rightNode.left){rightNode.left.parent=node}rightNode.parent=node.parent;if(rightNode.parent){if(rightNode.parent.left===node){rightNode.parent.left=rightNode}else{rightNode.parent.right=rightNode}}node.parent=rightNode;rightNode.left=node;node.balanceFactor+=1;if(rightNode.balanceFactor<0){node.balanceFactor-=rightNode.balanceFactor}rightNode.balanceFactor+=1;if(node.balanceFactor>0){rightNode.balanceFactor+=node.balanceFactor}return rightNode}function rotateRight(node){var leftNode=node.left;node.left=leftNode.right;if(node.left){node.left.parent=node}leftNode.parent=node.parent;if(leftNode.parent){if(leftNode.parent.left===node){leftNode.parent.left=leftNode}else{leftNode.parent.right=leftNode}}node.parent=leftNode;leftNode.right=node;node.balanceFactor-=1;if(leftNode.balanceFactor>0){node.balanceFactor-=leftNode.balanceFactor}leftNode.balanceFactor-=1;if(node.balanceFactor<0){leftNode.balanceFactor+=node.balanceFactor}return leftNode}var AVLTree=function AVLTree(comparator,noDuplicates){if(noDuplicates===void 0)noDuplicates=false;this._comparator=comparator||DEFAULT_COMPARE;this._root=null;this._size=0;this._noDuplicates=!!noDuplicates};var prototypeAccessors={size:{configurable:true}};AVLTree.prototype.destroy=function destroy(){return this.clear()};AVLTree.prototype.clear=function clear(){this._root=null;this._size=0;return this};prototypeAccessors.size.get=function(){return this._size};AVLTree.prototype.contains=function contains(key){if(this._root){var node=this._root;var comparator=this._comparator;while(node){var cmp=comparator(key,node.key);if(cmp===0){return true}else if(cmp<0){node=node.left}else{node=node.right}}}return false};AVLTree.prototype.next=function next(node){var successor=node;if(successor){if(successor.right){successor=successor.right;while(successor.left){successor=successor.left}}else{successor=node.parent;while(successor&&successor.right===node){node=successor;successor=successor.parent}}}return successor};AVLTree.prototype.prev=function prev(node){var predecessor=node;if(predecessor){if(predecessor.left){predecessor=predecessor.left;while(predecessor.right){predecessor=predecessor.right}}else{predecessor=node.parent;while(predecessor&&predecessor.left===node){node=predecessor;predecessor=predecessor.parent}}}return predecessor};AVLTree.prototype.forEach=function forEach(callback){var current=this._root;var s=[],done=false,i=0;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();callback(current,i++);current=current.right}else{done=true}}}return this};AVLTree.prototype.range=function range(low,high,fn,ctx){var Q=[];var compare=this._comparator;var node=this._root,cmp;while(Q.length!==0||node){if(node){Q.push(node);node=node.left}else{node=Q.pop();cmp=compare(node.key,high);if(cmp>0){break}else if(compare(node.key,low)>=0){if(fn.call(ctx,node)){return this}}node=node.right}}return this};AVLTree.prototype.keys=function keys(){var current=this._root;var s=[],r=[],done=false;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();r.push(current.key);current=current.right}else{done=true}}}return r};AVLTree.prototype.values=function values(){var current=this._root;var s=[],r=[],done=false;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();r.push(current.data);current=current.right}else{done=true}}}return r};AVLTree.prototype.at=function at(index){var current=this._root;var s=[],done=false,i=0;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();if(i===index){return current}i++;current=current.right}else{done=true}}}return null};AVLTree.prototype.minNode=function minNode(){var node=this._root;if(!node){return null}while(node.left){node=node.left}return node};AVLTree.prototype.maxNode=function maxNode(){var node=this._root;if(!node){return null}while(node.right){node=node.right}return node};AVLTree.prototype.min=function min(){var node=this._root;if(!node){return null}while(node.left){node=node.left}return node.key};AVLTree.prototype.max=function max(){var node=this._root;if(!node){return null}while(node.right){node=node.right}return node.key};AVLTree.prototype.isEmpty=function isEmpty(){return!this._root};AVLTree.prototype.pop=function pop(){var node=this._root,returnValue=null;if(node){while(node.left){node=node.left}returnValue={key:node.key,data:node.data};this.remove(node.key)}return returnValue};AVLTree.prototype.popMax=function popMax(){var node=this._root,returnValue=null;if(node){while(node.right){node=node.right}returnValue={key:node.key,data:node.data};this.remove(node.key)}return returnValue};AVLTree.prototype.find=function find(key){var root=this._root;var subtree=root,cmp;var compare=this._comparator;while(subtree){cmp=compare(key,subtree.key);if(cmp===0){return subtree}else if(cmp<0){subtree=subtree.left}else{subtree=subtree.right}}return null};AVLTree.prototype.insert=function insert(key,data){if(!this._root){this._root={parent:null,left:null,right:null,balanceFactor:0,key:key,data:data};this._size++;return this._root}var compare=this._comparator;var node=this._root;var parent=null;var cmp=0;if(this._noDuplicates){while(node){cmp=compare(key,node.key);parent=node;if(cmp===0){return null}else if(cmp<0){node=node.left}else{node=node.right}}}else{while(node){cmp=compare(key,node.key);parent=node;if(cmp<=0){node=node.left}else{node=node.right}}}var newNode={left:null,right:null,balanceFactor:0,parent:parent,key:key,data:data};var newRoot;if(cmp<=0){parent.left=newNode}else{parent.right=newNode}while(parent){cmp=compare(parent.key,key);if(cmp<0){parent.balanceFactor-=1}else{parent.balanceFactor+=1}if(parent.balanceFactor===0){break}else if(parent.balanceFactor<-1){if(parent.right.balanceFactor===1){rotateRight(parent.right)}newRoot=rotateLeft(parent);if(parent===this._root){this._root=newRoot}break}else if(parent.balanceFactor>1){if(parent.left.balanceFactor===-1){rotateLeft(parent.left)}newRoot=rotateRight(parent);if(parent===this._root){this._root=newRoot}break}parent=parent.parent}this._size++;return newNode};AVLTree.prototype.remove=function remove(key){if(!this._root){return null}var node=this._root;var compare=this._comparator;var cmp=0;while(node){cmp=compare(key,node.key);if(cmp===0){break}else if(cmp<0){node=node.left}else{node=node.right}}if(!node){return null}var returnValue=node.key;var max,min;if(node.left){max=node.left;while(max.left||max.right){while(max.right){max=max.right}node.key=max.key;node.data=max.data;if(max.left){node=max;max=max.left}}node.key=max.key;node.data=max.data;node=max}if(node.right){min=node.right;while(min.left||min.right){while(min.left){min=min.left}node.key=min.key;node.data=min.data;if(min.right){node=min;min=min.right}}node.key=min.key;node.data=min.data;node=min}var parent=node.parent;var pp=node;var newRoot;while(parent){if(parent.left===pp){parent.balanceFactor-=1}else{parent.balanceFactor+=1}if(parent.balanceFactor<-1){if(parent.right.balanceFactor===1){rotateRight(parent.right)}newRoot=rotateLeft(parent);if(parent===this._root){this._root=newRoot}parent=newRoot}else if(parent.balanceFactor>1){if(parent.left.balanceFactor===-1){rotateLeft(parent.left)}newRoot=rotateRight(parent);if(parent===this._root){this._root=newRoot}parent=newRoot}if(parent.balanceFactor===-1||parent.balanceFactor===1){break}pp=parent;parent=parent.parent}if(node.parent){if(node.parent.left===node){node.parent.left=null}else{node.parent.right=null}}if(node===this._root){this._root=null}this._size--;return returnValue};AVLTree.prototype.load=function load(keys,values,presort){if(keys===void 0)keys=[];if(values===void 0)values=[];if(this._size!==0){throw new Error('bulk-load: tree is not empty');}var size=keys.length;if(presort){sort(keys,values,0,size-1,this._comparator)}this._root=loadRecursive(null,keys,values,0,size);markBalance(this._root);this._size=size;return this};AVLTree.prototype.isBalanced=function isBalanced$1(){return isBalanced(this._root)};AVLTree.prototype.toString=function toString(printNode){return print(this._root,printNode)};Object.defineProperties(AVLTree.prototype,prototypeAccessors);

4、复杂度

  • 时间复杂度:addElementO(logn)O(logn)calculateMKAverageO(1)O(1)
  • 空间复杂度:O(n)O(n)

5、执行结果

image.png

· 阅读需 4 分钟

1、题干

在考场里,一排有 N 个座位,分别编号为 0, 1, 2, ..., N-1 。

当学生进入考场后,他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位,他会坐在编号最小的座位上。(另外,如果考场里没有人,那么学生就坐在 0 号座位上。)

返回 ExamRoom(int N) 类,它有两个公开的函数:其中,函数 ExamRoom.seat() 会返回一个 int (整型数据),代表学生坐的位置;函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。

 

示例:

输入:["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出:[null,0,9,4,2,null,5]
解释:
ExamRoom(10) -> null
seat() -> 0,没有人在考场里,那么学生坐在 0 号座位上。
seat() -> 9,学生最后坐在 9 号座位上。
seat() -> 4,学生最后坐在 4 号座位上。
seat() -> 2,学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5,学生最后坐在 5 号座位上。

 

提示:

  1. 1 <= N <= 10^9
  2. 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
  3. 保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。

2、代码

class ExamRoom {
n = -1;
min = Infinity;
max = -Infinity;
set = new Set<number>();
pq = new PriorityQueue({
compare: (a: [number, number], b: [number, number]): number => {
const da = (a[1] - a[0]) / 2 >> 0, db = (b[1] - b[0]) / 2 >> 0;
return da !== db ? db - da : a[0] - b[0];
}
});

constructor(n: number) {
this.n = n;
}

seat(): number {
let i = 0;
if (this.set.size) {
let found = false;
while (!found && this.pq.size()) {
const [n1, n2] = this.pq.dequeue();
if (n2 - n1 < 1 || !this.set.has(n1) || !this.set.has(n2)) continue;

const [m1, m2] = this.pq.front() || [];
if (n1 === m1 && n2 === m2) continue;

i = (n1 + n2) / 2 >> 0;
if (this.set.has(i) && this.set.has(i + 1)) continue;

if ((n2 - n1) / 2 >> 0 <= this.min || (n2 - n1) / 2 >> 0 < this.n - 1 - this.max) {
this.pq.enqueue([n1, n2]);
break;
}

found = true;
if (this.set.has(i)) i = i + 1;

this.pq.enqueue([n1, i]);
this.pq.enqueue([i, n2]);
}

if (!found) {
if (this.n - 1 - this.max > this.min) {
i = this.n - 1;
this.pq.enqueue([this.max, i]);
} else {
i = 0;
this.pq.enqueue([i, this.min]);
}
}
}

this.set.add(i);
if (i < this.min) this.min = i;
if (i > this.max) this.max = i;
return i;
}

leave(p: number): void {
this.set.delete(p);
const nums = [...this.set].sort((a, b) => a - b);

this.min = !nums.length ? Infinity : nums[0];
this.max = !nums.length ? -Infinity : nums[nums.length - 1];

const i = nums.findIndex(n => n > p);
if (i > 0) this.pq.enqueue([nums[i - 1], nums[i]]);
}
}

3、执行结果

image.png

· 阅读需 4 分钟

1、题干

设计一个使用单词列表进行初始化的数据结构,单词列表中的单词 互不相同 。 如果给出一个单词,请判定能否只将这个单词中一个字母换成另一个字母,使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类:

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构,dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ,判定能否只将字符串中 一个 字母换成另一个字母,使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以,返回 true ;否则,返回 false

 

示例:

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ,所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

 

提示:

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100search

 

注意:本题与主站 676 题相同: https://leetcode-cn.com/problems/implement-magic-dictionary/

2、解法1-字符串比较

数组存储字典,查找时直接进行字符串比较,如果不匹配的字符数量为1返回true,否则继续查找直至结束返回false

3、代码

var MagicDictionary = function () {
this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
for (let i = 0; i < this.dict.length; i++) {
if (searchWord.length !== this.dict[i].length) continue;

let diff = 0;
for (let j = 0; j < searchWord.length; j++) {
if (diff > 1) break;
if (searchWord[j] !== this.dict[i][j]) diff++;
}

if (diff === 1) return true;
}

return false;
};

4、执行结果

image.png

5、解法2-哈希表

哈希表存储字典,查找时对源字符串的每一位做替换,若替换后哈希表存在该字符串则返回true,否则继续查找直至结束返回false

6、代码

var MagicDictionary = function () {
this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
for (let i = 0; i < searchWord.length; i++) {
const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
for (let j = 97; j < 123; j++) {
const c = String.fromCharCode(j);
if (c === searchWord[i]) continue;
if (this.dict.has(pre + c + post)) return true;
}
}

return false;
};

7、执行结果

  • 执行用时: 860 ms
  • 内存消耗: 48.3 MB

· 阅读需 4 分钟

1、题干

设计一个使用单词列表进行初始化的数据结构,单词列表中的单词 互不相同 。 如果给出一个单词,请判定能否只将这个单词中一个字母换成另一个字母,使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类:

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构,dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ,判定能否只将字符串中 一个 字母换成另一个字母,使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以,返回 true ;否则,返回 false

 

示例:

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ,所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

 

提示:

  • 1 <= dictionary.length <= 100
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写英文字母组成
  • dictionary 中的所有字符串 互不相同
  • 1 <= searchWord.length <= 100
  • searchWord 仅由小写英文字母组成
  • buildDict 仅在 search 之前调用一次
  • 最多调用 100search

 

注意:本题与主站 676 题相同: https://leetcode-cn.com/problems/implement-magic-dictionary/

2、解法1-字符串比较

数组存储字典,查找时直接进行字符串比较,如果不匹配的字符数量为1返回true,否则继续查找直至结束返回false

3、代码

var MagicDictionary = function () {
this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
for (let i = 0; i < this.dict.length; i++) {
if (searchWord.length !== this.dict[i].length) continue;

let diff = 0;
for (let j = 0; j < searchWord.length; j++) {
if (diff > 1) break;
if (searchWord[j] !== this.dict[i][j]) diff++;
}

if (diff === 1) return true;
}

return false;
};

4、执行结果

image.png

5、解法2-哈希表

哈希表存储字典,查找时对源字符串的每一位做替换,若替换后哈希表存在该字符串则返回true,否则继续查找直至结束返回false

6、代码

var MagicDictionary = function () {
this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
for (let i = 0; i < searchWord.length; i++) {
const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
for (let j = 97; j < 123; j++) {
const c = String.fromCharCode(j);
if (c === searchWord[i]) continue;
if (this.dict.has(pre + c + post)) return true;
}
}

return false;
};

7、执行结果

  • 执行用时: 860 ms
  • 内存消耗: 48.3 MB

· 阅读需 3 分钟

1、题干

请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排,则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排,注意,这里的时间是半开区间,即 [start, end), 实数 x 的范围为,  start <= x < end

当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生重复预订。

每次调用 MyCalendar.book方法时,如果可以将日程安排成功添加到日历中而不会导致重复预订,返回 true。否则,返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

 

示例:

输入:
["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]
输出: [null,true,false,true]
解释:
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false ,第二个日程安排不能添加到日历中,因为时间 15 已经被第一个日程安排预定了
MyCalendar.book(20, 30); // returns true ,第三个日程安排可以添加到日历中,因为第一个日程安排并不包含时间 20

 

 

提示:

  • 每个测试用例,调用 MyCalendar.book 函数最多不超过 1000次。
  • 0 <= start < end <= 109

 

注意:本题与主站 729 题相同: https://leetcode-cn.com/problems/my-calendar-i/

2、解题思路

理想解法是使用平衡二叉搜索树,因为其查找和写入的时间复杂度都是 O(logn)O(logn),但是 JS 没有自带这样的数据结构,手写难度较大,因此采用暴力解法实现。

3、复杂度

  • 时间复杂度:O(n2)O(n^2)
  • 空间复杂度:O(n)O(n)

4、代码

var MyCalendar = function () {
this.matrix = [];
};

MyCalendar.prototype.book = function (start, end) {
for (let [s, e] of this.matrix) {
if (!(start > e || end - 1 < s)) return false;
}
return this.matrix.push([start, end - 1]), true;
};

5、执行结果

执行用时: 212 ms 内存消耗: 47.3 MB

· 阅读需 4 分钟

1、题干

设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。

请实现 KthLargest 类:

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val)val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。

 

示例:

输入:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出:
[null, 4, 5, 5, 8, 8]

解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8

 

提示:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104
  • 题目数据保证,在查找第 k 大元素时,数组中至少有 k 个元素

 

注意:本题与主站 703 题相同: https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

2、解法1-优先队列

使用优先队列解题,初始化时把所有元素加入到最小优先队列pq中,添加元素时直接把元素加入pq,若pq元素个数小于k则直接返回-1,若pq元素个数超过k则逐一移除最后返回队头元素。


3、代码

var KthLargest = function (k, nums) {
this.k = k;
this.pq = new MinPriorityQueue({ compare: (a, b) => a - b });
for (const n of nums) this.pq.enqueue(n);
};

KthLargest.prototype.add = function (val) {
this.pq.enqueue(val);
if (this.pq.size() < this.k) return -1;
while (this.pq.size() > this.k) this.pq.dequeue();
return this.pq.front();
};

4、复杂度

  • 时间复杂度:O(nlogn)O(nlogn)
  • 空间复杂度:O(n)O(n)

5、执行结果

执行用时: 132 ms 内存消耗: 46.6 MB


6、解法2-计数排序

对数据流使用计数排序,首次确定第 k 大元素 kIdx 需要遍历所有元素;此后添加数据需要再确定第 k 大元素时,如果添加的数据比 kIdx 小则直接返回 kIdx ;如果添加的数据比 kIdx 小则从下标 kIdx 开始在容器 list 找到更大且元素值不为0的下标返回即可。


这个题目中使用该算法坑略多,只作参考,不建议使用。


7、复杂度

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)

8、代码

var KthLargest = function (k, nums) {
this.k = k;
this.size = nums.length;
this.kIdx = -1;
this.list = new Array(2e4 + 1).fill(0);
for (const n of nums) this.list[n + 1e4]++;
};

KthLargest.prototype.add = function (val) {
(val += 1e4), this.list[val]++, this.size++;
if (this.size < this.k) return -1;

if (this.kIdx < 0) {
for (let i = this.list.length - 1, k = this.k; i >= 0; i--) {
if (k < this.list[i]) this.list[i] = k;
if ((k -= this.list[i]) <= 0) {
this.kIdx = i;
break;
}
}
return this.kIdx - 1e4;
}

if (this.size > this.k && val >= this.kIdx) {
this.list[this.kIdx]--;
for (let i = this.kIdx; i < this.list.length; i++) {
if (this.list[i]) {
this.kIdx = i;
break;
}
}
}

return this.kIdx - 1e4;
};

9、执行结果

1.png