不使用额外空间交换2个数据的源代码

  最近做求职笔试题,遇到比较有意思的题目,题目或多或少涉及到《剑指Offer》的思路和知识点,如果不是刷书两遍,估计不会做出来,分享一下互相学习!

************************************************************

1、不使用额外空间交换2个数据, 请写出任意3种方法,并阐明其优缺点。

  样例: int a = 2; int b = 3 ;   不再声明任何变量,使得 a = 3, b =2;

  解题思路: 部分参考自 http://www.cnblogs.com/cornucopia2015/p/4896791.html   不使用中间变量而交换两个数值变量的值,通常有三种做法: 1、加减法   a = a + b; b = a - b; a = a - b;   该方法可以交换整型和浮点型数值的变量,缺点是在处理浮点型的时候有可能会出现精度的损失。 2、乘除法   a = a * b; b = a / b; a = a / b;   该方法可以处理整型和浮点型变量,但在处理浮点型变量时也存在精度损失问题,而且乘除法比加减法要多一条约束:b必不为0,否则会报错。 3、异或法   a ^= b; // a=a^b   b ^= a; // b=b^(a^b)=b^a^b=b^b^a=0^a=a   a ^= b; // a=(a^b)^a=a^b^a=a^a^b=0^b=b   这里需要用到异或运算的一个性质:任何一个数字异或它自己都等于0。异或法可以完成对整型变量的交换,对于浮点型变量它无法完成交换。 4、栈法 (需要额外空间,不推荐)   push a; push b; pop a; pop b;   使用反向的出栈顺序来完成交换,它虽然没有显式的使用临时变量,但还是会用到额外的存贮空间,不太符合题意。

源代码:

  https://github.com/wylloong/TinyPrograms/blob/master/Coding%20Interviews/ExchangeWithoutTemp.cpp

************************************************************ 2、给定一个数组,数组中除了某个特定数字只出现1次,其余数字均出现2次。请编写函数,找出该数字。要求,空间复杂度O(n),时间复杂度O(n)。   1. 主程序需要包含对给定的2个测试文件的文件读取操作。   2. 请编写计时器类,并且对每个文件样例的输入和运算时间进行测量。

  解题思路: Google面试题,必须结合异或的性质,任何一个数字异或它自己都等于0,参考《剑指Offer》的面试题56:数组中数字出现的次数。

源代码:   https://github.com/wylloong/TinyPrograms/blob/master/Coding%20Interviews/FindNumsAppearOnce.cpp

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏韦弦的微信小程序

Swift 数数并说 - LeetCode

1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"), 即 21。 21 被读作 "one 2",...

492
来自专栏用户2442861的专栏

python数字图像处理(12):基本图形的绘制

skimage.draw.set_color(img, coords, color)

642
来自专栏函数式编程语言及工具

Scalaz(31)- Free :自由数据结构-算式和算法的关注分离

   我们可以通过自由数据结构(Free Structure)实现对程序的算式和算法分离关注(separation of concern)。算式(Abstrac...

1929
来自专栏向治洪

android绘制虚线

有的时候我们需要一种虚线效果,比如图片的边框,愤怒的小鸟的飞翔路径,那么怎么绘制这些虚线呢?方法很多,目前我觉得好的有两种: 一、自己创建模式,一个点一个点的绘...

1906
来自专栏CSDN技术头条

算法入门,其实可以像读小说一样有趣

我琢磨着目录,心想终于要把这些主题搞明白了。但那本书深奥难懂,看了几周后我就放弃了。直到遇到一位优秀的算法教授后,我才认识到这些概念是多么地简单而优雅。

4064
来自专栏和蔼的张星的图像处理专栏

671. 循环单词重复加标记

The words are same rotate words if rotate the word to the right by loop, and get...

723
来自专栏张善友的专栏

VS.Net 2005 Design-Time Integration

Introduction This article provides an overview of the VS.NET 2005 Design-Time I...

1828
来自专栏决胜机器学习

《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置 (原创内容,转载请注明来源,谢谢) 一、问题 ? 如上述棋盘,假设将为点A,帅为点B。将只能在d10...

3476
来自专栏技术小站

c++(三)

函数在调用之前必须进行声明或者定义,函数的声明:返回值类型 函数名(参数类型 参数名称.......);其中参数名称可以省略;

863
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

933

扫码关注云+社区