算法学习100天——1 初识
2022/2/26 12:22:26
本文主要是介绍算法学习100天——1 初识,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法学习100天——1 初识
一、位运算
-
5种符号 ^(异或) &(与) ~(非) |(或) >>(右移) <<(左移)
异或
可以看做是 二进制无进位相加 ,
0^N = N,N^N = 0
满足交换律和结合律
三者结合使用
求最右侧为1的那一位: N & (~N + 1)
求某一位是否为0:设a = 00000100, N & a ==0 ? N的第三位为0 : N第三位不为0
-
例题:
a. 一个数组,有一个数出现了奇次,其他出现了偶次,找到这个数
/** * 这个题没有难度,只是利用异或的性质 * a^b^c^b^c = a^b^b^c^c = a^0^0 = a */ class Solution { public int singleNumber(int[] nums) { int m = 0; for(int n : nums){ m ^= n; } return m; } }
b. 一个数组,有两个数出现了奇次,其他出现了偶次,找到这两个数
/** * 解题思路: * 1. 通过位运算得到a^b * 2. 不同的两个数异或,结果中总有一位为1,根据这个位置为1的情况, * 可以将数组中所有数分为两类,一类是该位为1,一类是为0 * 3. 因为是根据a^b的结果来分的,则a和b一定分布于不同的两组中 * 4. 再将两组分别异或,就得到了a和b * 【注】第4步也可以这样: * 将a^b的值与某一组异或,一定能得到a或b,再与a^b异或,得到另一个 * * 这个题的难度在于: * 1.用位运算只能取得这个两个奇次异或(即a^b)的值 * 2.根据a^b中为1的位将数组分为两组 */ class Solution { public int[] singleNumbers(int[] nums) { int m = 0; // 1.找到a^b for(int n : nums){ m = m ^ n; } // 2.根据a^b的结果为1的那一位,将数组分为两组数 int a = m; // 这里得到异或结果最右侧为1的那一位,m&(按位取反再加一) int rightOne = m & (~m + 1); for(int n : nums){ // 这里判断n的那一位是否0,是的话就与a^b异或 if((n & rightOne) == 0){ a ^= n; } } return new int[]{a, a ^ m}; } }
这篇关于算法学习100天——1 初识的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)