【优选算法系列】【专题五位运算】第一节.常见的位运算（面试题 01.01. 判定字符是否唯一和268. 丢失的数字）
文章目录
- 前言
- 常见的位运算
- 一、判定字符是否唯一
- 1.1 题目描述
- 1.2 题目解析
- 1.2.1 算法原理
- 1.2.2 代码编写
- 二、丢失的数字
- 2.1 题目描述
- 2.2 题目解析
- 2.2.1 算法原理
- 2.2.2 代码编写
- 总结
前言
常见的位运算
1.基础位运算：
2.给一个数n，确定它的二进制表示中的第x位是0还是1；
通过让这个n先向右移x位，再&上1即可；
即( n >> x ) & 1;
图示示例：
3.将一个数n的二进制表示的第x位修改成1；
通过先让1<< x位，然后让n |= 上前面的1<< x；
即：n |= （1<< x）
图示示例：
4.将一个数n的二进制表示的第x位修改成0；
通过先让1<< x位，再取其反，然后让n &= 上前面的 ~（1<< x）；
即 n &= （~（1<< x））；
图示示例：
5.位图思想
6.提取一个数（n）二进制表示中最右侧的1；
即：n & ~n；
~n：将最右侧的1，左边的区域全部变成相反。
图示说明：
7.干掉一个数（n）二进制表示中最右侧的1；
即：n & （n - 1）；
~n：将最右侧的1（包含1），右边的区域全部变成相反。
图示示例：
8.运算符的优先级
能加括号加括号即可
9.异或（^）运算的运算律
（1）a ^ 0 = a
（2）a ^ a = 0 （消xiao）
（3）a ^ b ^ c = a ^ （b ^ c）
一、判定字符是否唯一
1.1 题目描述
描述：
实现一个算法，确定一个字符串
s的所有字符是否全都不同。
限制：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
示例1：
示例2：
1.2 题目解析
2.2.1 算法原理
2.2.2 代码编写
二、丢失的数字
2.1 题目描述
描述：
给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都 独一无二
示例1：
示例2：
示例3：
示例4：
2.2 题目解析
2.2.1 算法原理
2.2.2 代码编写
总结
