1 .A + B 問(wèn)題
給出兩個(gè)整數(shù)a和b, 求他們的和, 但不能使用 + 等數(shù)學(xué)運(yùn)算符。
加減法在底層是使用二進(jìn)制來(lái)進(jìn)行運(yùn)算的。
加法，
位運(yùn)算
- 按位求反
~
運(yùn)來(lái)為1，變?yōu)?，0變?yōu)?；~1010=0101 - 與運(yùn)算
&
兩個(gè)對(duì)應(yīng)位置都為1，則為1，否則為0。1010 & 1011=·1010 - 或運(yùn)算
|
兩個(gè)對(duì)應(yīng)位置都為0，則為0，否則為1。1010 | 1011 = 1011 - 異或運(yùn)算
^
兩個(gè)對(duì)應(yīng)位置只有一個(gè)為1，則為1，否則為0。1010 ^ 1011 = 0001
加法分為兩部分，某一位相加，和產(chǎn)生進(jìn)位。
不考慮進(jìn)位的情況下，二進(jìn)制：1+1=0，0+1=1。這符合異或運(yùn)算。
然后再加上這一位產(chǎn)生的進(jìn)位。如果兩個(gè)對(duì)應(yīng)為上都為1，那么應(yīng)該產(chǎn)生進(jìn)位1 & 1 = 1，1 & 0 = 0，這符合與運(yùn)算。
如果當(dāng)前應(yīng)該進(jìn)位，那么下一位應(yīng)該加1，也就是本位進(jìn)位，下一位加1，所以應(yīng)該使用移位運(yùn)算，進(jìn)行左移一位1&1<<1
所以加法是：異或運(yùn)算進(jìn)行相加，而與運(yùn)算進(jìn)行進(jìn)位。
a + b = a^b + (a&b)<<1
題目要求不能使用加法，所以，是個(gè)遞歸a+b = add(a^b,(a&b)<<1)
當(dāng)，其中任意一個(gè)為0時(shí)（通常是不產(chǎn)生進(jìn)位，第二個(gè)參數(shù)為0），那么結(jié)束，第一個(gè)參數(shù)也就是最終的值。
代碼
int add(a,b)
{
if(a == 0)
{
return b;//通常因?yàn)槠鹗驾敵龅腶就是0
}
if(b == 0)
{
return a;//通常因?yàn)?，在遞歸中不產(chǎn)生進(jìn)位。
}
return add(a^b,(a&b)<<1);
}
拓展
如果是減法那？
相減使用的是還是異或運(yùn)算，借位使用的仍然是與運(yùn)算。但是，1-0和0-1，并不一定是否要借位啊。
減去一個(gè)數(shù)等于加上這個(gè)數(shù)的相反數(shù)。而按位求反，正式求一個(gè)數(shù)的相反數(shù)(不考慮進(jìn)位)。
但是這又涉及到第一位的問(wèn)題。
暫時(shí)無(wú)解。
2. 階乘結(jié)果尾部的0
設(shè)計(jì)一個(gè)算法，計(jì)算出n階乘中尾部零的個(gè)數(shù)
先計(jì)算出階乘結(jié)果，然后再不斷的%10，記錄次數(shù)，當(dāng)不是0的時(shí)候返回。
這種肯定不行。
數(shù)學(xué)的方法：
這些相乘的數(shù)中，含有多少個(gè)因數(shù)5，就有多少個(gè)0，因?yàn)榕紨?shù)比因數(shù)5多的多。比如25，含2個(gè)。125含3個(gè)。
b=n/10結(jié)果為，有多少個(gè)5的倍數(shù)：1,5，、、25、、、100、
b/5結(jié)果為，5的倍數(shù)中，多出的因數(shù)5：25,125
在繼續(xù)，然后把數(shù)值相加。
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. 統(tǒng)計(jì)數(shù)字
計(jì)算數(shù)字k在0到n中的出現(xiàn)的次數(shù)，k可能是0~9的一個(gè)值
貌似目前只能挨個(gè)比較。
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;
}
目前知道的只有這種。
還有一種是按照位來(lái)判斷的。
看原理應(yīng)該是除了第一位以外的其他都相同。
按位分析
4. 丑數(shù) II
設(shè)計(jì)一個(gè)算法，找出只含素因子2，3，5 的第 n 大的數(shù)。
符合條件的數(shù)如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
這個(gè)丑數(shù)也就是，因數(shù)是如上幾個(gè)的都是丑數(shù)。
按照慣例，
- 從1到n，暴力的判斷是否是丑數(shù)，記錄是第幾個(gè)，然后返回。這種顯然不行。
明顯不行啊。應(yīng)該是大于O(3n)？？中間空的多了可能更大。
好像也可以。 - 從1開(kāi)始構(gòu)造整個(gè)丑數(shù)隊(duì)列。
構(gòu)造這個(gè)丑數(shù)數(shù)列：
- 暴力的構(gòu)造
就是從頭到尾挨個(gè)構(gòu)造 - 將構(gòu)造好的丑數(shù)存起來(lái)，然后從中取最小的。
如上的丑數(shù)都有
2^a * 3^b * 5^c的形式。
所以，我們每次講講一個(gè)數(shù)，乘2,3,5分別存在三個(gè)容器中。再?gòu)闹腥∽钚〉牟迦氲綐?gòu)造的丑數(shù)隊(duì)列。
第一次我們將,1*2,1*3,1*5放入q2,q3,q5中，然后再?gòu)闹腥∽钚〉?，放入?gòu)造好的容器中。
取出的元素假設(shè)是m，那么將m*2,m*3,m*5,放入到容器中。
這里存在一個(gè)問(wèn)題：就是會(huì)重復(fù)
如果m從q2中取出，那么分別乘放入三個(gè)容器中
如果從q3中取出，那么只相乘放入q3,q5中即可。
如果從q5中取出，那么只相乘放入q5。
原因在于：
如果我們從q5中取出元素y他應(yīng)該是由5x得來(lái)的。也就是此刻最小的元素是5x,那么之前，我們一定遇到過(guò)2x，也就是一定添加過(guò)2x*5，此時(shí)如果在，添加y*2 = 5x*2，便會(huì)重復(fù)。
#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;
}
}
