leetcode之奇妙的异或运算

89 阅读 0 评论 59 点赞

我是靠谱客的博主精明月饼，最近开发中收集的这篇文章主要介绍leetcode之奇妙的异或运算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

leetcode之奇妙的异或运算

开始之前，我们先了解一下异或的概念：
来源：百度百科
这是百度百科上异或的解释，这里精简一下：
两数异或，相同为0，不同为1.
另外，异或有两个重要的性质：

满足交换律
一个数异或0还是它本身（在后面会用到这两个性质）

1. leetcode 136 来源：leetcode#136

这个题比较简单，但如果用异或操作，可以不使用额外空间来实现。
原理就是：
先对数组中所有元素进行异或运算。
nums[0] ^ nums[1] ^ … ^ nums[nums.length - 1]
利用上面提到的两个性质：
利用交换律将相同的元素交换在一起执行异或运算，这样可得到：只出现一次的数字^0，再根据第二条性质，所以最后异或得到的结果就为只出现一次的数字。

代码如下：

class Solution {
    public int singleNumber(int[] nums) {//异或运算;
    int single=nums[0];
    for(var i=1;i<nums.length;i++){
        single^=nums[i];
    }
    return single;
    }
}

2. leetcode 389

来源：leetcode#389

这道题的思路也基本相同，只不过是把整型数组变成了字符串而已。

这道题我们可以把两个字符串看成两个字符数组，分别对两个字符串中的char元素进行异或：
s.charAt(0)^s.charAt(1) ^… ^s.charAt(s.length()-1) ^ t.charAt(0) ^ t.charAt(1) ^… ^t.charAt(t.length()-1)

利用上面提到的两个性质：

利用交换律将相同的元素交换在一起执行异或运算，可得到：被添加的字母的ASCII码值^0，再根据第二条性质，所以最后异或得到的结果就为被添加的字母的ASCII码值，最后再利用类型转换转换为char型就得到了最后的结果。

代码如下：

class Solution {    
public char findTheDifference(String s, String t) {        
int ret = 0;        
for( int i = 0; i < s.length(); ++i ){            
	ret ^= s.charAt(i);        
}                
for( int i = 0; i < t.length(); ++i ){            
	ret ^= t.charAt(i);        
}
   return (char)ret;    
 
  }
 
 }