數(shù)字與數(shù)學(xué)基礎(chǔ)問(wèn)題

1、數(shù)字統(tǒng)計(jì)

1.1、符號(hào)統(tǒng)計(jì)

LeetCode1822. 給定一個(gè)數(shù)組，求所有元素的乘積的符號(hào)，如果最終答案是負(fù)的返回-1，如果最終答案是正的返回1，如果答案是0返回0.

這題其實(shí)只用看數(shù)組中0和負(fù)數(shù)的個(gè)數(shù)就好了，數(shù)組中有0的話，最后的結(jié)果肯定是0，數(shù)組中負(fù)數(shù)的個(gè)數(shù)是奇數(shù)的話，最終結(jié)果就是負(fù)的，偶數(shù)個(gè)的話結(jié)果就是正的。代碼如下：

public int arraySign(int[] nums) {int prod = 1;for (int i = 0; i < nums.length; i++) {if (nums[i] == 0) {return 0;} else if (nums[i] < 0) {//直接交替就好了，很好的處理技巧prod = -prod;}}return prod;
}

1.2、階乘結(jié)果中末尾0的個(gè)數(shù)

設(shè)計(jì)一個(gè)算法，算出n階乘后有多少個(gè)尾隨0。

這題如果硬算的話肯定會(huì)花費(fèi)很多時(shí)間，我們可以換個(gè)角度思考，如果一個(gè)數(shù)的末尾有0，肯定是乘過(guò)10的，而10是由 2 * 5得來(lái)的，所以只用統(tǒng)計(jì)2和5一起出現(xiàn)多少對(duì)，不過(guò)因?yàn)?出現(xiàn)的次數(shù)一定大于5出現(xiàn)的次數(shù)，因此我們只需要統(tǒng)計(jì)5出現(xiàn)的次數(shù)就好了。在統(tǒng)計(jì)的過(guò)程中，我們只需要統(tǒng)計(jì)5、10、15、…… $5^n$這樣5的整數(shù)倍就好了，最后累加起來(lái)，就是多少個(gè)0。代碼如下：

public int trailingZeroes(int n) {int cnt = 0;for (long num = 5; n / num > 0; num *= 5) {cnt += n / num;}return cnt;
}

這里num * 5 是因?yàn)?n / num 首先計(jì)算的是從1到n數(shù)中包含1個(gè)5的個(gè)數(shù)，比如1 * 5 = 5，2 * 5 = 10，然后計(jì)算的是包含2個(gè)5的個(gè)數(shù)，比如5 * 5 = 25，5 * 5 * 2 = 50，以此類推，加起來(lái)就是最終結(jié)果中含5的個(gè)數(shù)。

2、溢出問(wèn)題

2.1、整數(shù)反轉(zhuǎn)

LeetCode7. 給你一個(gè)32位的有符號(hào)整數(shù)x，返回將x中的數(shù)字部分反轉(zhuǎn)后的結(jié)果。如果反轉(zhuǎn)后整數(shù)超過(guò)32位的有符號(hào)整數(shù)的范圍[-2^31 , 2^31 - 1]，就返回0.假設(shè)環(huán)境不允許存儲(chǔ)64位整數(shù)（有符號(hào)或無(wú)符號(hào)）。

這題需要考慮溢出的問(wèn)題，比如1147483649這個(gè)數(shù)字，它是小于最大的32位整數(shù)2147483647的，但是將這個(gè)數(shù)字反轉(zhuǎn)過(guò)來(lái)后就變成了9463847411，這就比最大的32位整數(shù)還要大了，這樣的數(shù)字是沒(méi)法存到int中的，所以就溢出了。

取得一個(gè)數(shù)中的各個(gè)位上的數(shù)字很簡(jiǎn)單，循環(huán)取模即可，例如取得12345的各個(gè)數(shù)位上的數(shù)字，首先將12345 % 10 = 5，就得到個(gè)位數(shù)上的數(shù)字5，然后將12345 / 10 = 1234，這樣再繼續(xù)模10就好了，如下圖所示：

這是正數(shù)的情況，如果再考慮負(fù)數(shù)的話，可以將循環(huán)設(shè)置為while(x != 0)。因?yàn)闊o(wú)論是正數(shù)還是負(fù)數(shù)，按照上面不斷的/10操作，最后都會(huì)變?yōu)?，所以判斷終止條件就是 != 0。

再就是怎么去處理溢出的問(wèn)題，我們需要從倒數(shù)第二位開(kāi)始判斷是否溢出，因?yàn)槿绻苯颖容^最終的結(jié)果的話，像上面所講到的，一旦數(shù)溢出的話int是存不下的，所以得提前判斷。而32位最大整數(shù)MAX=2147483647，它的倒數(shù)第二位是4，所以就要分析結(jié)果的倒數(shù)第二位和4的大小關(guān)系，如下所示：

• 如果res > 214748364，那最后一位要接上的數(shù)就不用看了，肯定溢出了
• 如果res = 214748364，就需要跟最大數(shù)的最后一個(gè)數(shù)字相比，如果比7大，那就說(shuō)明溢出了
• 如果res < 214748364，繼續(xù)處理即可，不會(huì)溢出

對(duì)于負(fù)數(shù)同理，代碼如下：

public int reverse(int x) {int res = 0;while(x != 0) {//獲得末尾數(shù)字int temp = x % 10;//判斷是否大于最大的32位整數(shù)if (res > Integer.MAX / 10 || (res == Integer.MAX / 10 && temp > 7)) {return 0;}//判斷是否小于最小的32位整數(shù)if (res < Integer.MIN / 10 || (res == Integer.MIN / 10 && temp < -8)) {return 0;}res = res * 10 + temp;x /= 10;}return res;
}

3、進(jìn)制專題

3.1、進(jìn)制轉(zhuǎn)換

給定一個(gè)十進(jìn)制數(shù)M，以及需要轉(zhuǎn)換的進(jìn)制數(shù)N，將十進(jìn)制數(shù)M轉(zhuǎn)化位N進(jìn)制數(shù)。M是32位整數(shù)，2<=N<=16.

對(duì)于這個(gè)問(wèn)題，需要處理以下的幾個(gè)點(diǎn)：

• 超過(guò)進(jìn)制最大范圍后需要映射到其他進(jìn)制，比如用ABCDEF去表示數(shù)
• 需要對(duì)結(jié)果進(jìn)行轉(zhuǎn)置
• 需要判斷符號(hào)

用以下三個(gè)措施可以比較方便的去處理這個(gè)問(wèn)題：

• 定義大小位16的數(shù)組F，保存的是2到16的各個(gè)進(jìn)制的值對(duì)應(yīng)的標(biāo)記，這樣賦值時(shí)只計(jì)算下標(biāo)，不必考慮不同進(jìn)制的轉(zhuǎn)換關(guān)系
• 使用StringBuffer完成數(shù)組轉(zhuǎn)置等功能
• 通過(guò)一個(gè)flag來(lái)判斷正數(shù)還是負(fù)數(shù)

//要考慮到余數(shù)>9的情況，2 <= N <= 16
public static final String[] F = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"};//將十進(jìn)制數(shù)M轉(zhuǎn)化位N進(jìn)制數(shù)
public String convert(int M, int N) {if (M < 0) {flag = true;M * -1;}StringBuffer sb = new StringBuffer();int temp;while(M != 0){temp = M % N;sb.append(F[temp]);M = M / N;}sb.reverse();return (flag ? "-" : "") + sb.toString();
}