网站建设技术外包,小游戏网站怎么做,电商运营主要是做什么,搜索引擎推广的优势文章目录 异或的性质求异或和问题[421. 数组中两个数的最大异或值](https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/)[2935. 找出强数对的最大异或值 II](https://leetcode.cn/problems/maximum-strong-pair-xor-ii/) 异或前缀和问题#xff08;最..回… 文章目录 异或的性质求异或和问题[421. 数组中两个数的最大异或值](https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/)[2935. 找出强数对的最大异或值 II](https://leetcode.cn/problems/maximum-strong-pair-xor-ii/) 异或前缀和问题最..回文串、串字符出现奇/偶次[1371. 每个元音包含偶数次的最长子字符串](https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/) [1542. 找出最长的超赞子字符串](https://leetcode.cn/problems/find-longest-awesome-substring/)「求长度」[1915. 最美子字符串的数目](https://leetcode.cn/problems/number-of-wonderful-substrings/)「求个数」 与 或 | 异或 ^ 异或的性质
如果 a ^ b c 成立那么a ^ c b 与 b ^ c a 均成立。即 如果有三个数满足其中两个数的异或值等于另一个值那么这三个数的顺序可以任意调换。
说明利用这条性质可以不使用第 3 个变量而交换两个变量的值。
异或运算可以看作 「二进制下不进位的加法」所以常常用来解决一些和奇偶性相关的问题
求异或和问题
421. 数组中两个数的最大异或值
中等
给你一个整数数组 nums 返回 nums[i] XOR nums[j] 的最大运算结果其中 0 ≤ i ≤ j n 。
示例 1
输入nums [3,10,5,25,2,8]
输出28
解释最大运算结果是 5 XOR 25 28.示例 2
输入nums [14,70,53,83,49,91,36,80,92,51,66,70]
输出127提示
1 nums.length 2 * 1050 nums[i] 231 - 1 https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/solutions/2511644/tu-jie-jian-ji-gao-xiao-yi-tu-miao-dong-1427d/ 异或性质、假设修正
class Solution {// 把 nums数组的数转成二进制来思考看最高位、次高位..。能不能是1?// 如果 a ^ b max 成立那么一定有 max ^ b a 成立// 因此假设 max 的数位i 可以为1然后// 问题转化为两数之和用哈希表记录遍历结果求max^ba是否存在public int findMaximumXOR(int[] nums) {int max 0;for(int x : nums) max Math.max(max, x);// 得到为1的最高比特位int highBit 31 - Integer.numberOfLeadingZeros(max);int ans 0, mask 0;SetInteger seen new HashSet();for(int i highBit; i 0; i--){ // 从最高比特位开始枚举seen.clear();mask | 1 i; // 将[hightbit,i]位置都变为1int newAns ans | (1 i); // 假定第 i 位可以为1for(int x : nums){x mask; // 保留前缀低于 i 的比特位置为 0if(seen.contains(newAns ^ x)){ans newAns; // 这个bit位可以时1break;}seen.add(x);}}return ans;}
}2935. 找出强数对的最大异或值 II
困难
给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件则称其为 强数对
|x - y| min(x, y)
你需要从 nums 中选出两个整数且满足这两个整数可以形成一个强数对并且它们的按位异或XOR值是在该数组所有强数对中的 最大值 。
返回数组 nums 所有可能的强数对中的 最大 异或值。
注意你可以选择同一个整数两次来形成一个强数对。
示例 1
输入nums [1,2,3,4,5]
输出7
解释数组 nums 中有 11 个强数对(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 7 。示例 2
输入nums [10,100]
输出0
解释数组 nums 中有 2 个强数对(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 0 数对 (100, 100) 的异或值也是 100 XOR 100 0 。示例 3
输入nums [500,520,2500,3000]
输出1020
解释数组 nums 中有 6 个强数对(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 1020 另一个异或值非零的数对是 (5, 6) 其异或值是 2500 XOR 3000 636 。提示
1 nums.length 5 * 1041 nums[i] 220 - 1
class Solution {public int maximumStrongPairXor(int[] nums) {Arrays.sort(nums);int highBit 31 - Integer.numberOfLeadingZeros(nums[nums.length - 1]);int ans 0, mask 0;MapInteger, Integer mp new HashMap();for (int i highBit; i 0; i--) { // 从最高位开始枚举mp.clear();mask | 1 i;int newAns ans | (1 i); // 这个比特位可以是 1 吗for (int y : nums) {int maskY y mask; // 低于 i 的比特位置为 0if (mp.containsKey(newAns ^ maskY) mp.get(newAns ^ maskY) * 2 y) {ans newAns; // 这个比特位可以是 1break;}mp.put(maskY, y);}}return ans;}
}异或前缀和问题最…回文串、串字符出现奇/偶次 参考一步步优化从前缀和到前缀异或和附题单https://leetcode.cn/problems/can-make-palindrome-from-substring/solution/yi-bu-bu-you-hua-cong-qian-zhui-he-dao-q-yh5p/ 注意使用两数之和方法最后会求字串的长度和个数
求长度map中value存sum[i]第一次出现的位置求个数map中value存sum[i]出现的次数
1371. 每个元音包含偶数次的最长子字符串
中等
给你一个字符串 s 请你返回满足以下条件的最长子字符串的长度每个元音字母即 ‘a’‘e’‘i’‘o’‘u’ 在子字符串中都恰好出现了偶数次。
示例 1
输入s eleetminicoworoep
输出13
解释最长子字符串是 leetminicowor 它包含 eio 各 2 个以及 0 个 au 。示例 2
输入s leetcodeisgreat
输出5
解释最长子字符串是 leetc 其中包含 2 个 e 。示例 3
输入s bcbcbc
输出6
解释这个示例中字符串 bcbcbc 本身就是最长的因为所有的元音 aeiou 都出现了 0 次。提示
1 s.length 5 x 10^5s 只包含小写英文字母。
class Solution {public int findTheLongestSubstring(String s) {int n s.length();// 用 bit位 标识对应字母奇偶性// sum[i] 标识 s[0:i) 的子串中每种字母出现次数的奇偶性int[] sum new int[n1];for(int i 0; i n; i){int bit 0;// 每个元音字母即 aeiou 在子字符串中都恰好出现了偶数次。if(check(s.charAt(i)))bit 1 (s.charAt(i) - a);sum[i1] sum[i] ^ bit; }int res 0;// 问题化为两数之和 a ^ b 0MapInteger, Integer map new HashMap();for(int i 0; i n; i){// 注意求最长串长度map中只保存sum第一次出现位置if(map.containsKey(sum[i]))res Math.max(res, i - map.get(sum[i]));elsemap.put(sum[i], i);}return res;}public boolean check(Character c){return c a || c e || c i || c o || c u;}
}1542. 找出最长的超赞子字符串「求长度」
困难
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件
该字符串是 s 的一个非空子字符串进行任意次数的字符交换后该字符串可以变成一个回文字符串
示例 1
输入s 3242415
输出5
解释24241 是最长的超赞子字符串交换其中的字符后可以得到回文 24142示例 2
输入s 12345678
输出1示例 3
输入s 213123
输出6
解释213123 是最长的超赞子字符串交换其中的字符后可以得到回文 231132示例 4
输入s 00
输出2提示
1 s.length 10^5s 仅由数字组成
class Solution {/**进行任意次数的字符交换后该字符串可以变成一个回文字符串 字符串「不同字符出现次数」为奇数的个数 1*/public int longestAwesome(String s) {int n s.length();int[] sum new int[n1];for(int i 0; i n; i){int bit 1 (s.charAt(i) - 0);sum[i1] sum[i] ^ bit;}int res 0;// 问题转化为两数之和 // a ^ b 1 / 10 / 100 / 1000...MapInteger, Integer map new HashMap();for(int i 0; i n; i){// 字符串「不同字符出现次数」为奇数的个数 0if(map.containsKey(sum[i]))res Math.max(res, i - map.get(sum[i]));// 字符串「不同字符出现次数」为奇数的个数 1for(int j 0; j 10; j){int target (1 j);// a ^ b target a target ^ bif(map.containsKey(target ^ sum[i]))res Math.max(res, i - map.get(target ^ sum[i]));}// 注意求最长串长度map中只保存sum第一次出现位置if(!map.containsKey(sum[i]))map.put(sum[i], i);}return res;}
}1915. 最美子字符串的数目「求个数」
中等
如果某个字符串中 至多一个 字母出现 奇数 次则称其为 最美 字符串。
例如ccjjc 和 abab 都是最美字符串但 ab 不是。
给你一个字符串 word 该字符串由前十个小写英文字母组成a 到 j。请你返回 word 中 最美非空子字符串 的数目*。如果同样的子字符串在 word 中出现多次那么应当对 每次出现 分别计数。*
子字符串 是字符串中的一个连续字符序列。
示例 1
输入word aba
输出4
解释4 个最美子字符串如下所示
- aba - a
- aba - b
- aba - a
- aba - aba示例 2
输入word aabb
输出9
解释9 个最美子字符串如下所示
- aabb - a
- aabb - aa
- aabb - aab
- aabb - aabb
- aabb - a
- aabb - abb
- aabb - b
- aabb - bb
- aabb - b示例 3
输入word he
输出2
解释2 个最美子字符串如下所示
- he - h
- he - e提示
1 word.length 105word 由从 a 到 j 的小写英文字母组成
class Solution {public long wonderfulSubstrings(String word) {int n word.length();int[] sum new int[n1];for(int i 0; i n; i){int bit (1 (word.charAt(i) - a));sum[i1] sum[i] ^ bit;}long res 0;MapInteger, Integer map new HashMap();// 某个字符串中 至多一个 字母出现 奇数 次for(int i 0; i n; i){if(map.containsKey(sum[i]))res map.get(sum[i]);for(int j 0; j 11; j){int target (1 j);if(map.containsKey(target ^ sum[i]))res map.get(target ^ sum[i]);}map.merge(sum[i], 1, Integer::sum);}return res;}
}
