专栏首页DHUtoBUAA不使用额外空间交换2个数据的源代码

不使用额外空间交换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 条评论
登录 后参与评论

相关文章

  • 赋值运算符函数__from <剑指Offer>

            前段时间忙于项目,难得偷得几日闲,为即将到来的就业季做准备。在面试时,应聘者要注意多和考官交流,只有具备良好的沟通能力,才能充分了解面试官的需求...

    waylon
  • 快速排序算法思路分析和C++源代码(递归和非递归)

      快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试...

    waylon
  • 基于8211lib库对s57电子海图的解析和存储

      电子海图是为适用航海需要而绘制的包含海域地理信息和航海信息的一种数字化的专题地图,符合国际标准的电子海图数据统称为S-57电子海图。本文主要在S-57电子海...

    waylon
  • 漫画:神奇的找出只出现一次的数字!

    第136题:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    程序员小浩
  • LeetCode 1450. 在既定时间做作业的学生人数

    给你两个整数数组 startTime(开始时间)和 endTime(结束时间),并指定一个整数 queryTime 作为查询时间。

    Michael阿明
  • 整理数据时的16个常用Excel函数

    示例:下表D:F列中,如果填充“完成”大于1个,则在G列返回达标,否则返回不达标。

    用户5495712
  • 经验之谈,这16个Excel函数,几乎可以解决80%的数据统计工作!

    在日常工作中,数据统计是工作中最重要的一部分。今天把Excel中最常用的统计函数整理了出来,共16个。为了方便同学们理解,选取的全是贴近应用的示例。

    1480
  • AutoClip: 源分离网络的自适应梯度裁剪(CS SD)

    梯度剪切是一种改进梯度下降的已知方法,但是需要手动选择修剪阈值超参数。我们提出了AutoClip——一种基于训练过程中观察到的梯度规范记录来自动、自适应地选择梯...

    Rosalie
  • 多款iPhone遭遇中国禁售令!福建法院判决高通胜诉苹果

    但并非是苹果CFO在巴基斯坦意外被捕,而是与另一家美国公司高通的全球专利诉讼,在中国率先宣判了。

    量子位
  • 旋转时钟H5源码

    叮当叮

扫码关注云+社区

领取腾讯云代金券