摘要:数组定义为下标从开始且。请返回中所有元素按位异或后得到的结果。样例输入输出解释数组为,其中。为按位异或运算符。也就是只有是奇数并且是奇数的时候,最终结果的最低位才会是。
非常感谢你阅读本文~
欢迎【?点赞】【⭐收藏】【?评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~
给你两个整数,n 和 start 。
数组 nums 定义为:nums[i] = start + 2 * i(下标从 0 开始)且 n == nums.length 。
请返回 nums 中所有元素按位异或(XOR)后得到的结果。
输入: n = 5, start = 0输出: 8解释: 数组 nums 为 [0, 2, 4, 6, 8],其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。
输入: n = 4, start = 3输出: 8解释: 数组 nums 为 [3, 5, 7, 9],其中 (3 ^ 5 ^ 7 ^ 9) = 8.
输入: n = 1, start = 7输出: 7
输入: n = 10, start = 5输出: 2
我们可以直接按照题意,暴力循环,那么时间复杂度就是O(n),是否有时间复杂度为O(1)的算法呢?
记x为变量,^是异或操作,则异或运算满足以下性质:
只要我们可以实现函数sumXor(x),那么题目计算就可以做到O(1)的时间复杂度,根据 性质6 和 性质2 我们只需要考虑x除以4的余数,也就是最低2位,可以得到如下推导:
x % 4 = 0 的二进制位:xx…x00
x % 4 = 1 的二进制位:xx…x01
x % 4 = 2 的二进制位:xx…x10
x % 4 = 3 的二进制位:xx…x11
class Solution { public int xorOperation(int n, int start) { int s = start >> 1, e = n & start & 1; int ret = sumXor(s - 1) ^ sumXor(s + n - 1); return ret << 1 | e; } public int sumXor(int x) { switch (x & 3) { case 0: return x; case 1: return 1; case 2: return x | 1; default: // x & 3 == 3 return 0; } }}
int xorOperation(int n, int start) { int s = start >> 1, e = n & start & 1; int ret = sumXor(s - 1) ^ sumXor(s + n - 1); return ret << 1 | e;}int sumXor(int x) { switch (x & 3) { case 0: return x; case 1: return 1; case 2: return x | 1; default: // x & 3 == 3 return 0; }}
class Solution {public: int xorOperation(int n, int start) { int s = start >> 1, e = n & start & 1; int ret = sumXor(s - 1) ^ sumXor(s + n - 1); return ret << 1 | e; } int sumXor(int x) { switch (x & 3) { case 0: return x; case 1: return 1; case 2: return x | 1; default: // x & 3 == 3 return 0; } }};
class Solution: def xorOperation(self, n: int, start: int) -> int: def sumXor(x): if x % 4 == 0: return x if x % 4 == 1: return 1 if x % 4 == 2: return x | 1 return 0 s = start >> 1 e = n & start & 1 ans = sumXor(s - 1) ^ sumXor(s + n - 1) return ans << 1 | e
func xorOperation(n, start int) (ans int) { s, e := start>>1, n&start&1 ret := sumXor(s-1) ^ sumXor(s+n-1) return ret<<1 | e}func sumXor(x int) int { switch x & 3 { case 0: return x case 1: return 1 case 2: return x | 1 default: return 0 }}
impl Solution { pub fn xor_operation(n: i32, start: i32) -> i32 { let s = start >> 1; let e = n & start & 1; let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1); return ret << 1 | e } fn sum_xor(x: i32) -> i32 { match x & 3 { 0 => x, 1 => 1, 2 => x | 1, _ => 0 } }}
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/122565.html
摘要:请你构建一个同样长度的数组,其中,对于每个,都满足。返回构建好的数组。从开始的排列是一个由到和也包含在内的不同整数组成的数组。 非常感谢你阅读本文,欢迎【?点赞...
摘要:入门,第一个这是一门很新的语言,年前后正式公布,算起来是比较年轻的编程语言了,更重要的是它是面向程序员的函数式编程语言,它的代码运行在之上。它通过编辑类工具,带来了先进的编辑体验,增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了,总结过去的 2017,相信小伙们一定有很多收获...
摘要:入门,第一个这是一门很新的语言,年前后正式公布,算起来是比较年轻的编程语言了,更重要的是它是面向程序员的函数式编程语言,它的代码运行在之上。它通过编辑类工具,带来了先进的编辑体验,增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了,总结过去的 2017,相信小伙们一定有很多收获...
摘要:入门,第一个这是一门很新的语言,年前后正式公布,算起来是比较年轻的编程语言了,更重要的是它是面向程序员的函数式编程语言,它的代码运行在之上。它通过编辑类工具,带来了先进的编辑体验,增强了语言服务。 showImg(https://segmentfault.com/img/bV1xdq?w=900&h=385); 新的一年不知不觉已经到来了,总结过去的 2017,相信小伙们一定有很多收获...
摘要:选择排序算法实现实现选择排序,记录最小元素的索引,最后才交换位置说明交换两个数组中的元素,在中有更简单的写法,这是的语法糖,其它语言中是没有的。和语言中比较器的实现前面我们说到了,我们为了突出排序算法的思想,将所有的例子仅限在数组排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...
阅读 2062·2021-10-14 09:43
阅读 2148·2019-08-30 15:55
阅读 704·2019-08-30 14:23
阅读 1987·2019-08-30 13:21
阅读 1208·2019-08-30 12:50
阅读 2171·2019-08-29 18:46
阅读 2251·2019-08-29 17:28
阅读 2326·2019-08-29 17:21