数组中只出现一次的数字II

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

分析

本题是有两个未知数,是”Single Number”这道题的扩展,直接做异或肯定是不行的。有没有办法把两个未知数分开,使得可以分别应用Single Number的解法呢?
设x,y是那两个未知数,那么如果对这个数组做异或的话,结果实质上等于x^y,因为其他数都出现了两次,被抵消了。
但是仅仅是通过最后异或出来的值,是没办法区分出x和y的,但是足以帮助我们把 x和y划分到不同的子数组中去。

代码:

阅读全文

数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。

分析

新建一个boolean数组arr,遍历numbers数组,并令arr[numbers[i]] = true。如果arr[numbers[i]] == true,说明numbers[i]重复了。

代码:

阅读全文

整数中1出现的次数(从1到n整数中1出现的次数)

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

分析

将每个数组转成字符串,算出每个字符串里的“1”的个数。

代码:

阅读全文


Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :