湘潭网站建设 都来磐石网络,网站维修合同,wordpress vip视频解析,ppt设计说明2932. 找出强数对的最大异或值 I
题意
找出强数对的最大异或值
解法 暴力
其实不用记录所有的异或值#xff0c;直接维护最大值就行了。
class Solution {
public:int maximumStrongPairXor(vectorint nums) {unordered_mapint, int mp;int n nums…2932. 找出强数对的最大异或值 I
题意
找出强数对的最大异或值
解法 暴力
其实不用记录所有的异或值直接维护最大值就行了。
class Solution {
public:int maximumStrongPairXor(vectorint nums) {unordered_mapint, int mp;int n nums.size();for(int i 0; i n; i){for(int j i 1; j n; j){if(abs(nums[i] - nums[j]) min(nums[i], nums[j])){int tmp nums[i] ^ nums[j];mp[tmp];}}}int ans 0;for(auto m : mp){if(m.first ans){ans m.first;}}return ans;}
};复杂度
时间复杂度 O ( n 2 ) O(n^2) O(n2)。 空间复杂度 O ( n ) O(n) O(n) - O ( 1 ) O(1) O(1). 2933. 高访问员工
题意
字符串处理计算每个员工的有效访问次数
解法 按名字排序时间再筛选
先按名字把所有访问记录给分出来对每个人的访问时间排序并判断是否有效。
class Solution {
public:vectorstring findHighAccessEmployees(vectorvectorstring access_times) {vectorstring ans;unordered_mapstring, vectorstring mp; for(auto v : access_times){mp[v[0]].push_back(v[1]);}for(auto m : mp){string name m.first;vectorstring tmp m.second;if(tmp.size() 3) continue;sort(tmp.begin(), tmp.end());for(int i 0; i tmp.size() - 2; i){int st stoi(tmp[i].substr(0, 2)) * 60 stoi(tmp[i].substr(2, 2));int ed stoi(tmp[i 2].substr(0, 2)) * 60 stoi(tmp[i 2].substr(2, 2));if(ed - st 60){ans.push_back(name);break;}}}return ans;}
};复杂度
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。 空间复杂度 O ( n ) O(n) O(n)。 100117. 最大化数组末位元素的最少操作次数
题意
每次可以互换两个数组中下标相同的数求最少操作次数使得数组最后一个数大于数组中其他所有数
解法 分类讨论
首先由于只能交换下标相同的数因此两个数组的两个最大值是固定的。
那么本质上只有两种情况nums1[n - 1] 和 nums2[n - 1] 交换或者不交换。
只要确定了数组的最大值就可以开始交换了。假设 nums1 的最大值为 max1nums2 的最大值为 max2。遍历所有下标比较 nums1[i] 、nums2[i]、max1 以及 nums2分类讨论即可。
class Solution {
public:int minOperations(vectorint nums1, vectorint nums2) {int n nums1.size();int max1 nums1[n - 1], max2 nums2[n - 1];int ans 0;// 不交换 max1 max2for(int i 0; i n - 1; i){if(nums1[i] max1 nums2[i] max2) continue;else if(nums1[i] max2 nums2[i] max1){ans;continue;}else{ans -1;break;}}int ans2 1;// 交换 max1 max2for(int i 0; i n - 1; i){if(nums1[i] max2 nums2[i] max1) continue;else if(nums1[i] max1 nums2[i] max2){ans2;continue;}else{ans2 -1;break;}}if(ans -1 ans2 -1) return -1;if(ans -1) return ans2;if(ans2 -1) return ans;return min(ans, ans2);}
};复杂度
时间复杂度 O ( n ) O(n) O(n)。 空间复杂度 O ( 1 ) O(1) O(1)。 100124. 找出强数对的最大异或值 II
题意
在强数对中寻找最大异或值。
解法1 哈希表 二进制串转换 贪心
从数据范围来看暴力解的时间复杂度为 O ( n 2 ) O(n^2) O(n2)会超时。所以需要优化。比较容易的是想到用 map 来存已经出现过的数但是由于数据范围较大数的重复率较低map 的作用不大所以这里应该是 用 map 来存储出现过的前缀见后文。
1. 异或值 因为题目要求的是最大异或值所以首先要关注 异或 的特性
异或是一种位运算所以 位与位独立。若 a ^ b c则 a ^ c c ^ a bb ^ c c ^ b a。
所以可以将数转换为二进制串来进行异或计算。同时要想得到最大的异或值那么应当 使结果从高位到低位尽量每一位都为 1 1 1 。
注意到数的大小为 [ 0 , 2 20 − 1 ] [0, 2^{20} - 1] [0,220−1]因此可以将所有的数转换为 20 20 20 位的二进制串。同时得到的最大异或值也应当可以用 20 20 20 位的二进制串来表示。
而要使最大异或值最大正如前面提到的一样应当 使结果从高位到低位尽量每一位都为 1 1 1 。因此从高位到低位对于每一位都假设最大异或值可以取到 1 1 1然后去数组 nums[] 中寻查找看能否成立。
2. 强数对 再看强数对的概念对于强数对 ( x , y ) (x, y) (x,y)显然若 x ≤ y x \leq y x≤y则满足 x ≤ y ≤ 2 x x \leq y \leq 2x x≤y≤2x。因此先对数组 nums[] 进行排序从而简化后面的查找。
对于第 i i i 位能否为 1 1 1最直接的办法是遍历所有的强数对但这必然造成 O ( n 2 ) O(n^2) O(n2) 的复杂度所以这里应当采用 map 来优化假设当前遍历到数 n对于之前遍历过的 num将 num i 先保存在 map前缀原来的值 中这样寻找只需花费 O ( 1 ) O(1) O(1) 的时间复杂度由于数组 nums[] 是有序的所以必然能够保证 n ≥ n u m n \geq num n≥num因此这里只需要判断 n ≤ 2 ∗ n u m n \leq 2 * num n≤2∗num 即可。
这样的话对于每一位只要遍历一遍数组 nums[] 即可同时在遍历数组 nums[] 的同时更新 map以及判断是否可以使最大异或值的当前位为 1 1 1若可以为 1 1 1 则可以提前结束当前位的遍历。因此时间复杂度为 O ( n l o g C ) O(n logC) O(nlogC)其中C 为数组 nums[] 中最大值的二进制位数。
误区 之前一直在纠结 map 的存储方式如果以 前缀原来的值 来存储的话那么会导致相同前缀的 num 被 覆盖这不会导致部分强数对被遗漏没有遍历到吗求最值必然要遍历所有值
答案是会的。但是没有影响。 对于第 i i i 位能否为 1 1 1只需要数的前 i i i 位做运算即可本质上只需要第 i i i 位但是前面的位的值已经决定了所以要在满足前 i − 1 i - 1 i−1 为的前提下来判断第 i i i 位。所以即便之前的 n u m num num 被覆盖了他也不会影响前 i i i 位的异或值。同时由于覆盖之前 n u m num num 的 n u m ′ num num′ 必然大于等于 n u m num num数组 nums[] 有序因此更容易使 n ≤ 2 ∗ n u m n \leq 2 * num n≤2∗num 这个条件满足。
class Solution {
private:static const int HIGH_BIT 19;
public:int maximumStrongPairXor(vectorint nums) {int n nums.size();int x 0;sort(nums.begin(), nums.end());for(int k HIGH_BIT; k 0; k--){unordered_mapint, int mp;int x_next x * 2 1;bool found false;for(int n : nums){mp[n k] n; if(mp.count(x_next ^ (n k)) mp[x_next ^ (n k)] * 2 n){found true;break;} }if(found) x x_next;else x x_next - 1;}return x;}
};复杂度
时间复杂度 O ( n l o g n n l o g C ) O(nlogn n logC) O(nlognnlogC)。 O ( n l o g n ) O(nlogn) O(nlogn) 是排序的时间。其中C 为数组 nums[] 中最大值的二进制位数。 空间复杂度 O ( n ) O(n) O(n)map 的空间最坏情况没有重复的数那么在 k 0 时所有的数都会被存储到 map 中。
解法2 0-1 Trie / 字典树
同样是将数转换为二进制串来优化时间。
注意字典树的根节点没有意义。
struct Trie{Trie* left nullptr; // 0Trie* right nullptr; // 1int cnt 0; // 他的孩子数 或者说 经过它的字符串的数量Trie() {};
};class Solution {
private:static const int high_bit 19;Trie* root new Trie();public:void insertNum(int num){Trie* cur root;for(int k high_bit; k 0; k--){int bit (num k) 1;if(bit 0) // 当前位 只与 cur的孩子 有关系{if(!cur-left){cur-left new Trie();}cur cur-left;}else{if(!cur-right){cur-right new Trie();}cur cur-right;}cur-cnt; // 孩子}}void deleteNum(int num){Trie* cur root;for(int k high_bit; k 0; k--){int bit (num k) 1;if(bit 0)cur cur-left;elsecur cur-right;cur-cnt--;}}int calXor(int num){Trie* cur root;int tmp 0;int x 0;for(int k high_bit; k 0; k--){int bit (num k) 1;if(bit 0){if(cur-right cur-right-cnt 0) // 右孩子存在{cur cur-right;x x * 2 1;}else if(cur-left cur-left-cnt 0) // 左孩子存在{cur cur-left;x x * 2;}}else{if(cur-left cur-left-cnt 0){cur cur-left;x x * 2 1;}else if(cur-right cur-right-cnt 0){cur cur-right;x x * 2;}}}return x;}int maximumStrongPairXor(vectorint nums) {int n nums.size();sort(nums.begin(), nums.end());int l 0, r 0;int ans 0;while(l n) // [l, r){if(r n nums[r] nums[l] * 2){insertNum(nums[r]);ans max(ans, calXor(nums[r]));r;}else if(r n nums[r] nums[l] * 2){deleteNum(nums[l]);l;}else if(r n){deleteNum(nums[l]);l;}}return ans;}
};复杂度
时间复杂度 O ( n l o g n n l o g C ) O(nlogn nlogC) O(nlognnlogC)。 O ( n l o g n ) O(nlogn) O(nlogn) 是排序的时间。其中C 为数组 nums[] 中最大值的二进制位数。 空间复杂度 O ( n l o g C ) O(nlogC) O(nlogC)map 的空间最坏情况没有重复的数那么在 k 0 时所有的数都会被存储到 map 中。
