1 .A + B 問題
給出兩個整數(shù)a和b, 求他們的和, 但不能使用 + 等數(shù)學(xué)運算符弱卡。
加減法在底層是使用二進制來進行運算的烛缔。
加法荧库，
位運算
- 按位求反
~
運來為1汁果，變?yōu)?，0變?yōu)?疼电；~1010=0101 - 與運算
&
兩個對應(yīng)位置都為1嚼锄，則為1，否則為0蔽豺。1010 & 1011=·1010 - 或運算
|
兩個對應(yīng)位置都為0区丑，則為0，否則為1修陡。1010 | 1011 = 1011 - 異或運算
^
兩個對應(yīng)位置只有一個為1沧侥，則為1，否則為0魄鸦。1010 ^ 1011 = 0001
加法分為兩部分宴杀，某一位相加，和產(chǎn)生進位拾因。
不考慮進位的情況下旺罢，二進制：1+1=0斯棒，0+1=1。這符合異或運算主经。
然后再加上這一位產(chǎn)生的進位。如果兩個對應(yīng)為上都為1庭惜，那么應(yīng)該產(chǎn)生進位1 & 1 = 1罩驻，1 & 0 = 0，這符合與運算护赊。
如果當(dāng)前應(yīng)該進位惠遏，那么下一位應(yīng)該加1，也就是本位進位骏啰，下一位加1节吮，所以應(yīng)該使用移位運算，進行左移一位1&1<<1
所以加法是：異或運算進行相加判耕，而與運算進行進位透绩。
a + b = a^b + (a&b)<<1
題目要求不能使用加法，所以壁熄，是個遞歸a+b = add(a^b,(a&b)<<1)
當(dāng)帚豪，其中任意一個為0時（通常是不產(chǎn)生進位，第二個參數(shù)為0）草丧，那么結(jié)束狸臣，第一個參數(shù)也就是最終的值。
代碼
int add(a,b)
{
if(a == 0)
{
return b;//通常因為起始輸出的a就是0
}
if(b == 0)
{
return a;//通常因為昌执，在遞歸中不產(chǎn)生進位烛亦。
}
return add(a^b,(a&b)<<1);
}
拓展
如果是減法那？
相減使用的是還是異或運算懂拾，借位使用的仍然是與運算煤禽。但是，1-0和0-1委粉，并不一定是否要借位啊呜师。
減去一個數(shù)等于加上這個數(shù)的相反數(shù)。而按位求反贾节，正式求一個數(shù)的相反數(shù)(不考慮進位)汁汗。
但是這又涉及到第一位的問題。
暫時無解栗涂。
2. 階乘結(jié)果尾部的0
設(shè)計一個算法知牌，計算出n階乘中尾部零的個數(shù)
先計算出階乘結(jié)果，然后再不斷的%10斤程，記錄次數(shù)角寸，當(dāng)不是0的時候返回菩混。
這種肯定不行。
數(shù)學(xué)的方法：
這些相乘的數(shù)中扁藕，含有多少個因數(shù)5覆劈，就有多少個0，因為偶數(shù)比因數(shù)5多的多萍鲸。比如25肮柜，含2個。125含3個望薄。
b=n/10結(jié)果為疟游，有多少個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)計數(shù)字
計算數(shù)字k在0到n中的出現(xiàn)的次數(shù)干签，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;
}
目前知道的只有這種拆撼。
還有一種是按照位來判斷的容劳。
看原理應(yīng)該是除了第一位以外的其他都相同。
按位分析
4. 丑數(shù) II
設(shè)計一個算法闸度，找出只含素因子2竭贩，3，5 的第 n 大的數(shù)莺禁。
符合條件的數(shù)如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
這個丑數(shù)也就是留量，因數(shù)是如上幾個的都是丑數(shù)。
按照慣例哟冬，
- 從1到n楼熄，暴力的判斷是否是丑數(shù)，記錄是第幾個浩峡，然后返回可岂。這種顯然不行。
明顯不行啊翰灾。應(yīng)該是大于O(3n)缕粹？稚茅？中間空的多了可能更大。
好像也可以平斩。 - 從1開始構(gòu)造整個丑數(shù)隊列亚享。
構(gòu)造這個丑數(shù)數(shù)列：
- 暴力的構(gòu)造
就是從頭到尾挨個構(gòu)造 - 將構(gòu)造好的丑數(shù)存起來，然后從中取最小的绘面。
如上的丑數(shù)都有
2^a * 3^b * 5^c的形式虹蒋。
所以，我們每次講講一個數(shù)飒货，乘2,3,5分別存在三個容器中。再從中取最小的插入到構(gòu)造的丑數(shù)隊列峭竣。
第一次我們將,1*2,1*3,1*5放入q2,q3,q5中塘辅，然后再從中取最小的，放入構(gòu)造好的容器中皆撩。
取出的元素假設(shè)是m扣墩，那么將m*2,m*3,m*5,放入到容器中。
這里存在一個問題：就是會重復(fù)
如果m從q2中取出扛吞，那么分別乘放入三個容器中
如果從q3中取出呻惕，那么只相乘放入q3,q5中即可。
如果從q5中取出滥比，那么只相乘放入q5亚脆。
原因在于：
如果我們從q5中取出元素y他應(yīng)該是由5x得來的。也就是此刻最小的元素是5x,那么之前盲泛，我們一定遇到過2x濒持，也就是一定添加過2x*5，此時如果在寺滚，添加y*2 = 5x*2柑营，便會重復(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;
}
}
