参考自:《算法零基础第16讲》
如果有老板对位 *** 作还不太清楚,可参考这篇文章
文章链接: C语言:位 *** 作
- 前言
- 交换变量的值
- 示例
- 面试题 16.01. 交换数字
- 方法一(行不通):加减运算
- 方法二:位运算(异或)
- 代码
- 方法三:偷鸡法
- 面试题 05.07. 配对交换
- 分析
- 代码
学过C语言的人,在指针那一章节,肯定见过通过指针传递给函数形参,交换变量。
示例比如在生活中,你要把一瓶酱油和一瓶醋相交换瓶子,能够想到的就是找一个空瓶子,
1.先将其中一种比如酱油倒入空瓶
2.再将醋倒入之前酱油空出来的瓶子
3.再将酱油倒入之前醋空出来的瓶子。
常用方法为
void Swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }
但在有些题目中,他不允许让你使用中间变量,那为了做题,可以尝试加减法 。
方法:
void Swap(int* a, int* b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; }
这是简单的数学问题,在做题时候,可能这种方法也不让用。
面试题 16.01. 交换数字原题链接: 面试题 16.01. 交换数字
方法一(行不通):加减运算因为题目不让用中间变量,所以利用上面讲到加减法,来试一试这个题目
class Solution { public: vectorswapNumbers(vector & numbers) { if (numbers[0] == numbers[1]) return numbers; numbers[0] = numbers[0] + numbers[1]; numbers[1] = numbers[0] - numbers[1]; numbers[0] = numbers[0] - numbers[1]; return numbers; } };
用这种方法,一旦两个数据加起来超过了整型范围,就是错误的
同样,就算刚开始使用减法,也是行不通的,因为数据本身可能是负的。
方法二:位运算(异或)如果C语言学过位 *** 作,就知道异或这个概念。
符号: ^
概念 :二元运算符 ^,对于每一位,如果两个运算对象中相应的位一个为1,但不是两个为1,结果为1。
示例 :
(1001 0010) ^ (0101 1011) 结果:(1100 1001)代码
class Solution { public: vectorswapNumbers(vector & numbers) { if (numbers[0] == numbers[1]) return numbers; numbers[0] = numbers[0] ^ numbers[1]; numbers[1] = numbers[0] ^ numbers[1]; numbers[0] = numbers[0] ^ numbers[1]; return numbers; } };
有些老板这里不理解了,为什么你这三下异或就能解决 ?
分析:
由此可得,一个数据对同一个数据异或两次,结果还为原始数据。
方法三:偷鸡法说实话,C++可以这样搞,很让人无语。。。
class Solution { public: vector面试题 05.07. 配对交换swapNumbers(vector & numbers) { return {numbers[1], numbers[0]}; } };
原题链接: 面试题 05.07. 配对交换
这里如果还没学到位运算的老板,可以看这篇文章 :
文章链接: C语言:位 *** 作
注意题目,是让交换位,如 位0 与 位1,而不是十进制的权位。
方法:
我们可以利用两个常量
0x5555 5555
0xaaaa aaaa
用二进制表示为:
0101 0101 0101 0101 0101 0101 0101 0101
1010 1010 1010 1010 1010 1010 1010 1010
1.拿这两个常量利用与运算符(&),可以将原始数据的奇数位和偶数位提取出来
2.再分别进行左移和右移
3.再将数据或运算(|),得到最终结果 。
示例:
class Solution { public: int exchangeBits(int num) { int odd = 0x55555555 & num; int even = 0xaaaaaaaa & num; odd = (odd << 1); even = (even >> 1); return (odd | even); } };
这节主要方法还是位 *** 作,还不太明白的老板们可以查看这篇文章,真心希望能有所帮助
文章链接:C语言:位 *** 作
感谢收看~~
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)