当前位置:网站首页>LeetCode刷题:位运算(找不同 和 只出现一次的数字)
LeetCode刷题:位运算(找不同 和 只出现一次的数字)
2022-07-21 14:25:00 【散一世繁华,颠半世琉璃】
1.常见的位运算
按位与&:(1&1=1,1&0=0,0&1=0,0&0=0);
按位或 | : (1 | 1=1,1 | 0=1,0 | 1=1,0 | 0=0);
按位非 ~: ( ~1=0, ~0=1);
按位异或 ^ : (1^1=0 ,1^0=1, 0^1=1, 0^0=0);
异或运算有以下三个性质。
任何数和 0做异或运算,结果仍然是原来的数,即 a ⊕ 0 = a a \oplus 0=a a⊕0=a。
任何数和其自身做异或运算,结果是 0,即 a ⊕ a = 0 a \oplus a=0 a⊕a=0。
异或运算满足交换律和结合律,即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b a \oplus b \oplus a=b \oplus a \oplus a=b a⊕b⊕a=b⊕a⊕a=b ⊕ ( a ⊕ a ) = b ⊕ 0 = b \oplus (a \oplus a)=b \oplus0=b ⊕(a⊕a)=b⊕0=b。
简单来说,如果参与异或的两个数相同,则它们异或的结果便为0,而0与任何数的异或就是该数本身,利用该性质,我们可以极大地简化我们的程序。
接下来请具体看下面两个LeetCode题目。
2.找不同
给定两个字符串 s 和 t ,它们只包含小写字母。
字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例一:
示例二:
1.思路分析
我们利用异或运算,将两个字符串s和t的所有字符进行异或运算,最终得到的就是那最后一个不同的字符的ASCll编码,注意,最后返回的时候需要强转为char类型。具体代码如下所示:
class Solution {
public char findTheDifference(String s, String t) {
int sum=0;
for(int i=0;i<s.length();i++){
sum^=s.charAt(i);
}
for(int j=0;j<t.length();j++){
sum^=t.charAt(j);
}
return (char)sum;
}
}
2.结果展示
3.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例一:
示例二:
1.思路分析
同样的,该题与上一题找不同类似,同样是找到在数组中无法配对的数字,即如果将数组中的所有元素进行异或运算,最后的结果就是那个只出现一次的数字。具体代码如下所示:
class Solution {
public int singleNumber(int[] nums) {
int result=0;
for(int num:nums){
result=result^num;
}
return result;
}
}
2.结果展示
以上两个题目是进行异或运算的典型例题,可以极大地简化我们的程序。所以,我们在日常的编程中要熟练掌握并运用位运算。
边栏推荐
- 过d盾asp webshell+冰蝎免杀马探讨
- ssm框架文件上传已经实现怎么映射到数据库
- 64. Minimum path and
- haproxy2.6负载安装配置
- Attack and defense world ---mfw
- Navicate 连接阿里云(两种方式及原理讲解)
- Technical team: 4 suggestions for code review initiator
- leetcode 724. Find the central subscript of the array
- Kyligence 出席华为全球智慧金融峰会,加速拓展全球市场
- Relevant use cases of QT events
猜你喜欢
随机推荐
申万宏源证券股票低佣金开户靠谱吗,可靠安全吗
Bypass some dog SQL and XSS
Can or could
07.Octave语言的使用-变量、数值、向量、矩阵
leetcode 1732. Find the highest altitude
What is the culprit of the failure of digital transformation?
小道仙博客【开源个人博客】
Detr code
Study assignment:
leetcode 1582. 二进制矩阵中的特殊位置
Navicate 连接阿里云(两种方式及原理讲解)
数字化转型失败的罪魁祸首是什么?
C language problem solving number sequence
技术团队:给代码评审发起者的4个建议
bypass 某狗sql和xss
leetcode 724. Find the central subscript of the array
Leetode 416. Divide equal sum subsets
Zabbix3.0 alarm settings
开源进销存系统,10分钟搞定,建议收藏!
How to realize visualization of basic equipment efficiently