-
异或：相同为 0，不同为 1。也可用
不进位加法来理解 -
异或操作的一些特点：
x ^ 0 = x x ^ 1s = ~x x ^ (~x) = 1s # 注意 1s = ~0 x ^ x = 0 c = a ^ b # a ^ c = b, b ^ c = a 交换两个数 a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c # associative
- 将 x 最右边的 n 位清零：
x & (~0 << n) - 获取 x 的第 n 位值(0 或者 1)：
(x >> n) & 1 - 获取 x 的第 n 位的幂值：
x & (1 << n) - 仅将第 n 位置为 1：
x | (1 << n) - 仅将第 n 位置为 0：
x & (~(1 << n)) - 将 x 最高位至第 n 位(含)清零：
x & ((1 << n) - 1) - 将第 n 位至第 0 位(含)清零：
x & (~((1 << (n + 1)) - 1))
- 判断奇偶
x % 2 == 1—>(x & 1) == 1x % 2 == 0—>(x & 1) == 0
x >> 1—> x / 2，即:x = x / 2；—>x = x >> 1;mid = ( left + right) / 2；—>mid = (left + right) >> 1;x = x & (x - 1)清零最低位的 1x & -x=> 得到最低位的 1x & ~x=> 0
- 排序算法
- 比较类排序
- 通过比较来决定元素见的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序
- 非比较类排序
- 不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序
- 比较类排序
- 选择排序（Selection Sort）：每次找最小值，然后放到待排序数组的起始位置
- 插入排序（Insertion Sort）：从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
- 冒泡排序（Bubble Sort）：嵌套循环，每次查看相邻的元素如果逆序，则交换
- 快速排序（Quick Sort）：数组取标杆 pivot，将小元素放在 pivot 左边，大元素放右侧，然后依次对右边和右边的子数组继续快排；已达到整个序列有序
- 归并排序（Merge Sort）- 分治
- 把长度为 n 的输入序列分成两个长度 n/2 的子序列
- 对这两个子序列分别采用归并排序
- 将两个排序好的子序列合并成一个最终的排序序列
- 堆排序（Heap Sort） - 堆插入 O(logN)，取 最大/最小 O(1)
- 数组元素依次建立小顶堆
- 依次取顶堆元素，并删除
- 总结：归并 和 快排具有相似性，但步骤顺序相反
- 归并：先排序左右子数组，然后合并两个有序的子数组
- 快排：先调配出左右子数组，然后对于左右子数组进行排序
- 计数排序（Counting Sort）： 计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存储在额外开辟的数组空间中；然后依次把计数大于 1 的填充回原数组
- 桶排序（Bucket Sort）：桶排序的工作原理，假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或者递归方式继续使用桶排序进行排）
- 基数排序（Radix Sort）：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序
-
class Solution: def hammingWeight(self, n: int) -> int: # 位运算 ans = 0 while n: n = n & (n - 1) ans += 1 return ans def hammingWeight(self, n: int) -> int: # 暴力求解，O(n) ans = 0 for i in bin(n): if i != 1: continue ans += 1 return ans # return bin(n).count('1') # 内置方法求解
-
class Solution: def isPowerOfTwo(self, n: int) -> bool: # 暴力求解 ans = 1 while ans < n: ans <<= 1 return ans == n def isPowerOfTwo(self, n: int) -> bool: # 位运算：获取二进制中最右边的 1 if n == 0: return False return n & -n == n
-
用自己熟悉的编程语言，手写各种初级排序代码，提交到学习总结中