1803.统计异或值在范围内的数对有多少
链接：1803.统计异或值在范围内的数对有多少
难度：Hard
标签：位运算、字典树、数组
简介：给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。
题解 1 - cpp
- 编辑时间：2023-01-05
- 执行用时：432ms
- 内存消耗：132.2MB
- 编程语言：cpp
- 解法介绍：字典树，按位遍历，对于当前点找和 target 前缀一样，当前位小的数量。
#include <vector>
#include <numeric>
#include <iostream>
#include <unordered_map>
// bestlyg
#define X first
#define Y second
#define lb(x) ((x) & (-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug freopen("input","r",stdin)
#define PII pair<int,int>
#ifdef DEBUG
#define log(frm, args...) { printf(frm, ##args);}
#else
#define log(frm, args...)
#endif
typedef long long ll;
using namespace std;
class UnionFind {
public:
int n;
vector<int> data, cnt;
UnionFind(int n): n(n), data(vector<int>(n, 0)), cnt(vector<int>(n, 1)) {
iota(data.begin(), data.end(), 0);
}
int size(int v) { return cnt[find(v)]; }
int find(int v) {
if (data[v] == v) return v;
return data[v] = find(data[v]);
}
void uni(int v1, int v2) {
int p1 = find(v1), p2 = find(v2);
if (p1 != p2) {
cnt[p1] += cnt[p2];
data[p2] = p1;
}
}
bool same(int v1, int v2) { return find(v1) == find(v2); }
};
int pos2Idx(int x, int y, int size) { return x * size + y; }
void idx2Pos(int idx, int size, int &x, int &y) { x = idx / size; y = idx % size; }
vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// START
const int MAX = 14;
struct TrieNode {
int sum, val;
TrieNode *children[2];
TrieNode(int val): sum(0), val(val) { children[0] = children[1] = nullptr; }
~TrieNode() {
delete children[0];
delete children[1];
}
};
struct Trie {
TrieNode *root;
Trie(): root(new TrieNode(0)) {}
void add(int num) {
TrieNode *p = root;
for (int i = MAX; i >= 0; i--) {
int tag = (num >> i) & 1;
TrieNode *next = p->children[tag];
if (next == nullptr) next = p->children[tag] = new TrieNode(tag);
p = next;
p->sum += 1;
}
}
int get(int num, int x) {
TrieNode *p = root;
int sum = 0;
for (int i = MAX; i >= 0; i--) {
int tag = (num >> i) & 1;
if ((x >> i) & 1) {
if (p->children[tag] != nullptr) sum += p->children[tag]->sum;
if (p->children[tag ^ 1] == nullptr) return sum;
p = p->children[tag ^ 1];
} else {
if (p->children[tag] == nullptr) return sum;
p = p->children[tag];
}
}
sum += p->sum;
return sum;
}
~Trie() {
log("~trie
");
delete root;
}
};
class Solution {
public:
int comp(vector<int> &nums, int num) {
Trie trie;
int ans = 0;
for (int i = 1; i < nums.size(); i++) {
trie.add(nums[i - 1]);
ans += trie.get(nums[i], num);
}
return ans;
}
int countPairs(vector<int>& nums, int low, int high) {
return comp(nums, high) - comp(nums, low - 1);
}
};
// END
#ifdef LOCAL
int main() {
Solution s;
// vector<int> nums = {1,4,2,7};
// int low = 2;
// int high = 6;
vector<int> nums = {9,8,4,2,1};
int low = 5;
int high = 14;
cout << s.countPairs(nums, low, high) << endl;
return 0;
}
#endif
题解 2 - rust
- 编辑时间：2023-01-05
- 执行用时：132ms
- 内存消耗：4.6MB
- 编程语言：rust
- 解法介绍：同上。
pub use std::{cell::RefCell, rc::Rc};
const MAX: i32 = 14;
struct TrieNode {
sum: i32,
children: [Option<Rc<RefCell<TrieNode>>>; 2],
}
impl TrieNode {
fn new() -> TrieNode {
TrieNode {
sum: 0,
children: [None, None],
}
}
}
struct Trie {
root: Option<Rc<RefCell<TrieNode>>>,
}
impl Trie {
fn new() -> Trie {
Trie {
root: Some(Rc::new(RefCell::new(TrieNode::new()))),
}
}
fn add(&self, num: i32) {
let mut p = self.root.clone().unwrap();
let mut i = MAX;
while i >= 0 {
let tag = ((num >> i) & 1) as usize;
let mut next: Option<Rc<RefCell<TrieNode>>> = None;
if p.as_ref().borrow().children[tag].is_none() {
let node = Rc::new(RefCell::new(TrieNode::new()));
p.borrow_mut().children[tag] = Some(node.clone());
next = Some(node.clone());
} else {
let node = p.as_ref().borrow().children[tag].clone();
next = node
}
p = next.unwrap();
p.borrow_mut().sum += 1;
i -= 1;
}
}
fn get(&self, num: i32, x: i32) -> i32 {
let mut p = self.root.clone().unwrap();
let mut sum = 0;
let mut i = MAX;
while i >= 0 {
let tag = ((num >> i) & 1) as usize;
if ((x >> i) & 1) == 1 {
if p.as_ref().borrow().children[tag].is_some() {
let child = p.as_ref().borrow().children[tag].clone();
sum += child.unwrap().as_ref().borrow().sum;
}
if p.as_ref().borrow().children[tag ^ 1].is_none() {
return sum;
}
let next = p.as_ref().borrow().children[tag ^ 1].clone();
p = next.unwrap();
} else {
if p.as_ref().borrow().children[tag].is_none() {
return sum;
}
let next = p.as_ref().borrow().children[tag].clone();
p = next.unwrap();
}
i -= 1;
}
sum += p.as_ref().borrow().sum;
sum
}
}
impl Solution {
fn comp(nums: &Vec<i32>, num: i32) -> i32 {
let trie = Trie::new();
let mut ans = 0;
for i in 1..nums.len() {
trie.add(nums[i - 1]);
ans += trie.get(nums[i], num);
}
ans
}
pub fn count_pairs(nums: Vec<i32>, low: i32, high: i32) -> i32 {;
Solution::comp(&nums, high) - Solution::comp(&nums, low - 1)
}
}
题解 3 - typescript
- 编辑时间：2023-01-05
- 执行用时：7316ms
- 内存消耗：47.1MB
- 编程语言：typescript
- 解法介绍：暴力模拟。
function countPairs(nums: number[], low: number, high: number): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const v = nums[i] ^ nums[j];
if (v >= low && v <= high) ans++;
}
}
return ans;
}
题解 4 - rust
- 编辑时间：2023-01-05
- 执行用时：436ms
- 内存消耗：2.2MB
- 编程语言：rust
- 解法介绍：暴力。
impl Solution {
pub fn count_pairs(nums: Vec<i32>, low: i32, high: i32) -> i32 {
let mut ans = 0;
for i in 0..nums.len() {
for j in i + 1..nums.len() {
let val = nums[i] ^ nums[j];
if val >= low && val <= high {
ans += 1;
}
}
}
ans
}
}