792. 匹配子序列的单词数
给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例:
输入:
S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]
输出: 3
解释: 有三个是 S 的子序列的单词: “a”, “acd”, “ace”。
注意:
- 所有在words和 S 里的单词都只由小写字母组成。
- S 的长度在 [1, 50000]。
- words 的长度在 [1, 5000]。
- words[i]的长度在[1, 50]。
思路：两个字符串是否满足子序列，我们使用双指针来判断，
这里借用了这个思路，将每个子序列的指针变量pos保存到hash中，和words中的子序列构成一个元组 value， key为当前比对到的字符。
/*** @param {string} s* @param {string[]} words* @return {number}*/var numMatchingSubseq = function(s, words) {// 初始化字符-子串hash表，value格式为：[w, pos]const r = words.reduce((r, w) => {const ch = w.charAt(0);if (r.has(ch)) {r.get(ch).push([w, 0]);} else {r.set(ch, [[w, 0]]);}return r;}, new Map());let ans = 0;for (let i = 0; i < s.length; i++) {const ch = s.charAt(i);const list = r.get(ch);// 查找hash表中是否存在该字符开头的子串。if (list && list.length) {let len = list.length;while (len--) {// 找到子串，将pos向后移动，若pos大于子序列t的长度，说明是子序列，结果集加一let [t, pos] = list.shift();pos ++;if (pos >= t.length) {// 结果集计数ans ++;continue;}// 更新hash表，将当前字符和pos位置存储到hash表中。const tch = t.charAt(pos);if (!r.has(tch)) {r.set(tch, []);}r.get(tch).push([t, pos]);}}}return ans;};
1804. 实现 Trie （前缀树） II
/**
* Initialize your data structure here.
*/
var Trie = function() {
this.root = new Array(27).fill(undefined);
};
/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word.charCodeAt(i) - 97;
if (node[ch] === undefined) {
node[ch] = new Array(27).fill(undefined);
}
node = node[ch];
}
node[26] = word;
};
Trie.prototype.__find = function(key) {
let node = this.root;
for (let i = 0; i < key.length; i++) {
let ch = key.charCodeAt(i) - 97;
if (node[ch] !== undefined) {
node = node[ch];
} else {
return;
}
}
return node;
}
/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let node = this.__find(word);
if (node) {
return node[26] !== undefined;
}
return false;
};
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let results = [];
const _startWith = (node, key) => {
if (!node) {
return;
}
if (node[26] !== undefined) {
results.push(key.join(''));
}
for (let ch = 0; ch < 26; ch++) {
key.push(ch);
_startWith(node[ch], key);
key.pop();
};
};
_startWith(this.__find(prefix), Array.from(prefix));
return results.length > 0;
};
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/
421. 数组中两个数的最大异或值
/**
* @param {number[]} nums
* @return {number}
*/
var findMaximumXOR = function(nums) {
if (nums.length < 2) return 0;
const tr = [undefined, undefined];
for (let i = 0; i < nums.length; i++) {
insert(tr, nums[i]);
}
let ans = Number.MIN_SAFE_INTEGER;
for (let i = 0; i < nums.length; i++) {
ans = Math.max(ans, nums[i] ^ srearch(tr, nums[i]));
}
return ans;
};
function insert(root, x) {
// 高位存储来Trie的前面，所以我们从左向右存储
for(let i = 30; i >= 0; i--){
// 取第i位的数字，this.len - 1...0
let u = (x>>i) & 1;
// 若第u位为空，则创建一个新节点，然后root移动到下一个节点
if(root[u] === undefined) {
root[u] = [undefined, undefined];
}
root = root[u];
}
}
function srearch(root, x){ // 在前缀树中寻找 x 的最大异或值
// res表示最大异或值，每次res*2表示左移一位，+u表示加上当前的最低位数字
let res = 0;
for(let i = 30; i >= 0; i--){
let u = (x>>i) & 1;
// 若 x 的第 u 位存在，取相反的方向搜索，因为异或总是|值|相反才取最大值的
if (root[u ^ 1]) {
u ^= 1;
}
res |= u << i;
root = root[u];
}
return res;
}
1707. 与数组中元素的最大异或值
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]
提示：
1 <= nums.length, queries.length <= 105
queries[i].length == 2
0 <= nums[j], xi, mi <= 109
思路：排序 + 暴力计算xor值
/**
* @param {number[]} nums
* @param {number[][]} queries
* @return {number[]}
*/
var maximizeXor = function(nums, queries) {
let ans = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < queries.length; i++) {
let [x, m] = queries[i];
if (m < nums[0]) {
ans.push(-1);
continue;
}
let pos = search(nums, m, (p) => p - m);
let s = Number.MIN_SAFE_INTEGER;
for (let j = 0; j < pos; j++) {
s = Math.max(s, nums[j] ^ x);
}
ans.push(s);
}
return ans;
};
function search(d, t, comp) {
let l = 0; r = d.length;
while (l < r) {
let mid = l + ((r - l) >>> 1);
let cp = comp(d[mid], t);
if (cp === 0) {
l = mid + 1;
} else if (cp < 0) {
l = mid + 1;
} else if (cp > 0) {
r = mid;
}
}
return l;
}
解法二：Trie树 + 贪心选择不同位
/**
* @param {number[]} nums
* @param {number[][]} queries
* @return {number[]}
*/
var maximizeXor = function(nums, queries) {
const tr = [undefined, undefined, Number.MAX_SAFE_INTEGER];
for (let v of nums) {
insert(tr, v);
}
let ans = [];
for (let i = 0; i < queries.length; i++) {
let [s, m] = queries[i];
ans[i] = search(tr, s, m);
}
return ans;
};
function insert(root, x) {
// 在前缀树中插入值
root[2] = Math.min(root[2], x);
// 高位存储来Trie的前面，所以我们从左向右存储
for(let i = 30; i >= 0; i--){
// 取第i位的数字，this.len - 1...0
let u = (x>>i) & 1;
// 若第u位为空，则创建一个新节点，然后root移动到下一个节点
if(root[u] === undefined) {
root[u] = [undefined, undefined, Number.MAX_SAFE_INTEGER];
}
root = root[u];
root[2] = Math.min(root[2], x);
}
}
function search(root, x, limit) { // 在前缀树中寻找 x 的最大异或值
if (root[2] > limit) {
return -1;
}
// res表示最大异或值，每次res*2表示左移一位，+u表示加上当前的最低位数字
let res = 0;
for(let i = 30; i >= 0; i--){
let b = (x>>i) & 1;
// 若 x 的第 b 位存在，取相反的方向搜索，因为异或总是|值|相反才取最大值的
if (root[b ^ 1] && root[b ^ 1][2] <= limit) {
res |= 1 << i;
b ^= 1;
}
root = root[b];
}
return res;
}
若有收获，就点个赞吧
0 人点赞
