1 .A + B 问题
给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。
加减法在底层是使用二进制来进行运算的。
加法，
位运算
- 按位求反
~
运来为1，变为0，0变为1；~1010=0101 - 与运算
&
两个对应位置都为1，则为1，否则为0。1010 & 1011=·1010 - 或运算
|
两个对应位置都为0，则为0，否则为1。1010 | 1011 = 1011 - 异或运算
^
两个对应位置只有一个为1，则为1，否则为0。1010 ^ 1011 = 0001
加法分为两部分，某一位相加，和产生进位。
不考虑进位的情况下，二进制：1+1=0，0+1=1。这符合异或运算。
然后再加上这一位产生的进位。如果两个对应为上都为1，那么应该产生进位1 & 1 = 1，1 & 0 = 0，这符合与运算。
如果当前应该进位，那么下一位应该加1，也就是本位进位，下一位加1，所以应该使用移位运算，进行左移一位1&1<<1
所以加法是：异或运算进行相加，而与运算进行进位。
a + b = a^b + (a&b)<<1
题目要求不能使用加法，所以，是个递归a+b = add(a^b,(a&b)<<1)
当，其中任意一个为0时（通常是不产生进位，第二个参数为0），那么结束，第一个参数也就是最终的值。
代码
int add(a,b)
{
if(a == 0)
{
return b;//通常因为起始输出的a就是0
}
if(b == 0)
{
return a;//通常因为，在递归中不产生进位。
}
return add(a^b,(a&b)<<1);
}
拓展
如果是减法那？
相减使用的是还是异或运算，借位使用的仍然是与运算。但是，1-0和0-1，并不一定是否要借位啊。
减去一个数等于加上这个数的相反数。而按位求反，正式求一个数的相反数(不考虑进位)。
但是这又涉及到第一位的问题。
暂时无解。
2. 阶乘结果尾部的0
设计一个算法，计算出n阶乘中尾部零的个数
先计算出阶乘结果，然后再不断的%10，记录次数，当不是0的时候返回。
这种肯定不行。
数学的方法：
这些相乘的数中，含有多少个因数5，就有多少个0，因为偶数比因数5多的多。比如25，含2个。125含3个。
b=n/10结果为，有多少个5的倍数：1,5，、、25、、、100、
b/5结果为，5的倍数中，多出的因数5：25,125
在继续，然后把数值相加。
long long trailingZeros(long long n) {
long long count{0};
long long tmp=n;
while(tmp != 0)
{
tmp=tmp/5;
count+=tmp;
}
return count;
}
3. 统计数字
计算数字k在0到n中的出现的次数，k可能是0~9的一个值
貌似目前只能挨个比较。
int digitCounts(int k, int n) {
int count = 0;
for(int i = 0;i<=n;i++)
{
int number = i;
while(number/10)
{
if(number % 10 == k)
{
count++;
}
number = number/10;
}
if(number == k)
count++;
}
return count;
}
目前知道的只有这种。
还有一种是按照位来判断的。
看原理应该是除了第一位以外的其他都相同。
按位分析
4. 丑数 II
设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
这个丑数也就是，因数是如上几个的都是丑数。
按照惯例，
- 从1到n，暴力的判断是否是丑数，记录是第几个，然后返回。这种显然不行。
明显不行啊。应该是大于O(3n)？？中间空的多了可能更大。
好像也可以。 - 从1开始构造整个丑数队列。
构造这个丑数数列：
- 暴力的构造
就是从头到尾挨个构造 - 将构造好的丑数存起来，然后从中取最小的。
如上的丑数都有
2^a * 3^b * 5^c的形式。
所以，我们每次讲讲一个数，乘2,3,5分别存在三个容器中。再从中取最小的插入到构造的丑数队列。
第一次我们将,1*2,1*3,1*5放入q2,q3,q5中，然后再从中取最小的，放入构造好的容器中。
取出的元素假设是m，那么将m*2,m*3,m*5,放入到容器中。
这里存在一个问题：就是会重复
如果m从q2中取出，那么分别乘放入三个容器中
如果从q3中取出，那么只相乘放入q3,q5中即可。
如果从q5中取出，那么只相乘放入q5。
原因在于：
如果我们从q5中取出元素y他应该是由5x得来的。也就是此刻最小的元素是5x,那么之前，我们一定遇到过2x，也就是一定添加过2x*5，此时如果在，添加y*2 = 5x*2，便会重复。
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int64_t uglyNum(int64_t n)
{
deque<int64_t> two;
deque<int64_t> three;
deque<int64_t> five;
two.push_back(1);
int64_t i = 0;
int64_t tmp;
INT
int64_t twoMin;
int64_t threeMin;
int64_t fiveMin;
int64_t ret;
while(i != n)
{
i++;
twoMin = two.empty()?INT64_T:two.front();
threeMin = three.empty()?INT64_T:three.front();
fiveMin = five.empty()?INT64_T:five.front();
tmp = min(min(twoMin,threeMin),fiveMin);
if(tmp==twoMin)
{
ret=twoMin;
two.push_back(2*ret);
three.push_back(3*ret);
five.push_back(5*ret);
two.pop_front();
continue;
}
if(tmp == threeMin)
{
ret=three.front();
three.push_back(3*ret);
five.push_back(5*ret);
three.pop_front();
continue;
}
if(tmp == fiveMin)
{
ret=five.front();
five.push_back(5*ret);
five.pop_front();
continue;
}
}
return ret;
}
int64_t main()
{
int64_t i;
while(cin>>i)
{
cout<<"ugly :"<<uglyNum(i)<<endl;
}
}
网友评论