記錄 LeetCode 刷題中遇到的數(shù)學(xué)相關(guān)題目
質(zhì)數(shù)是數(shù)論中很重要的一部分，應(yīng)該也是大多數(shù)人剛接觸數(shù)論時(shí)接觸到第一個(gè)知識(shí)點(diǎn)。下面根據(jù)官方題解總結(jié)一下幾種判斷質(zhì)數(shù)或者篩質(zhì)數(shù)的方法：
下面是線性篩的做法：
重慶分公司
重慶分公司
public int countPrimes(int n) {Listprimes = new ArrayList(); //質(zhì)數(shù)集合
int[] isPrime = new int[n]; //標(biāo)記質(zhì)數(shù)
Arrays.fill(isPrime, 1);
for (int i = 2; i< n; ++i) {if (isPrime[i] == 1) {primes.add(i);
}
//注意如果 i * primes.get(j) >= n 直接跳出循環(huán)
for (int j = 0; j< primes.size() && i * primes.get(j)< n; ++j) {isPrime[i * primes.get(j)] = 0;
//遇到能整除的質(zhì)數(shù)結(jié)束標(biāo)記過(guò)程
if (i % primes.get(j) == 0) {break;
}
}
}
return primes.size();
} 根據(jù)數(shù)據(jù)范圍，n 不大于 231- 1 的大取值為 319= 1162261467，那么如果 n 是 3 的冪，即 n = 3x，那么一定滿足 n * 3k= 319，其中 0<= k<= 19，亦即 319% n = 0，所以只需判斷這個(gè)等式是否成立即可。還要判斷 n 是否大于 0：
public boolean isPowerOfThree(int n) {return n >0 && 1162261467 % n == 0;
}remain 數(shù)組中，remain[0] 記錄被遍歷過(guò)的元素中，被三除后余 0 的元素大和；remain[[1] 記錄被三除后余 1 的元素大和；remain[2] 記錄被三除后余 2 的元素大和。當(dāng)把所有元素遍歷完后，remain[0] 就是本題答案
public int maxSumDivThree(int[] nums) {int len = nums.length;
int[] remain = new int[3];
int a,b,c;
for(int i = 0; i< len; i++){a = remain[0] + nums[i];
b = remain[1] + nums[i];
c = remain[2] + nums[i];
remain[a % 3] = Math.max(remain[a % 3], a);
remain[b % 3] = Math.max(remain[b % 3], b);
remain[c % 3] = Math.max(remain[c % 3], c);
}
return remain[0];
}字符串轉(zhuǎn)化為數(shù)字，相當(dāng)于 26 進(jìn)制轉(zhuǎn)化為十進(jìn)制。
但十進(jìn)制中沒(méi)有 0，‘A’ 對(duì)應(yīng)的是 1 而不是 0，所以將字母轉(zhuǎn)化為數(shù)字時(shí)還需要加一，即 字母 - ‘A’ + 1 而不是 字母 - ‘A’
public int titleToNumber(String columnTitle) {int len = columnTitle.length();
int ans = 0;
for(int i = 0; i< len; i++){ans = ans * 26 + (columnTitle.charAt(i) - 'A' + 1);
}
return ans;
}171 題的思路逆過(guò)來(lái)即可。一開(kāi)始是沒(méi)做 171 題先做了 168 題，對(duì)這個(gè) “cn–” 語(yǔ)句不能理解。然后就先做了 171 題，171 中的 “columnTitle.charAt(i) - ‘A’ + 1” 還是挺好理解的
cn 每次減一后對(duì) 26 取余得到的就是 171 中 " columnTitle.charAt(i) - ‘A’ "，所以再加 ‘A’ 得到的就是對(duì)應(yīng)位上的字母。以此類(lèi)推，將所有字母使用 StringBuilder 連接起來(lái)。連接的順序是從低位到高位， reverse 成高位到低位即可
public String convertToTitle(int cn) {StringBuilder sb = new StringBuilder();
while (cn >0) {cn--;
sb.append((char)(cn % 26 + 'A'));
cn /= 26;
}
return sb.reverse().toString();
}如果輪到我的時(shí)候剩下 0 個(gè)石頭，那我必輸；如果剩下 1 個(gè)，那我可以拿 1 個(gè)，輪到對(duì)面沒(méi)有石頭拿，對(duì)面必輸；如果剩下 2 個(gè)，那我可以拿 2 個(gè)，輪到對(duì)面沒(méi)有石頭拿，對(duì)面必輸；如果剩下 3 個(gè)，那我可以拿 3 個(gè)，輪到對(duì)面沒(méi)有石頭拿，對(duì)面必輸；如果剩下 4 個(gè)，那我不管拿 1 個(gè)還是 2 個(gè)還是 3 個(gè)，剩下的石頭對(duì)面都可以一次性拿完，再次輪到我沒(méi)有石頭拿，我必輸；如果剩下 5 個(gè)，我可以只拿 1 個(gè)，剩下 4 個(gè)給對(duì)面，跟剩下 4 個(gè)給我一樣，對(duì)面必輸…可以發(fā)現(xiàn)規(guī)律，如果 n 取余 4 為 0，那么我必輸
public boolean canWinNim(int n) {return n % 4 != 0;
}randX() 可以得到 [1,X]，那么 randX() - 1 為 [0,X - 1]，(randX() - 1) * Y 為 [0,(X - 1)Y]，那么 (randX() - 1) * Y + randY() 即為 [1,X*Y]
故已有 randX()，randY()，可以通過(guò) (randX() - 1) * Y + randY() 得到 randX*Y
所以對(duì)于這道題，一開(kāi)始已有 rand7,可以得到 rand49，如果結(jié)果在 [1,40] 中，就可以取余 10 然后加 1 得到 rand10。如果結(jié)果在 [41,49]，就可以減去 40，得到 [1,9]，即 rand9，可以跟 rand7 得到 rand63。同理如果結(jié)果在 [1,60] 可以得到 rand10，否則就是得到 rand3，可以跟 rand7 得到 rand21。此時(shí)如果結(jié)果在 [1,20] 可以得到 rand10，否則只剩下 1 這一個(gè)結(jié)果，無(wú)法繼續(xù)得到新的 rand，只能從頭開(kāi)始循環(huán)
public int rand10() {while(true) {int rand7_1 = rand7();
int rand7_2 = rand7();
int r1 = (rand7_1 - 1) * 7 + rand7_2; //rand 49
if(r1<= 40) return r1 % 10 + 1; //rand 10
r1 -= 40; //rand 9
int rand7_3 = rand7();
int r2 = (r1 - 1) * 7 + rand7_3; //rand 63
if(r2<= 60) return r2 % 10 + 1; //rand 10
r2 -= 10; //rand 3
int rand7_4 = rand7();
int r3 = (r2 - 1) * 7 + rand7_4; //rand 21
if(r3<= 20) return r3 % 10 + 1;
//此時(shí)r3 - 20是1，說(shuō)明后續(xù)無(wú)法繼續(xù)去找rand X*Y了，只能重新開(kāi)始循環(huán)
}
}計(jì)算 xn，如果是按照 n 個(gè) x 相乘的思路，復(fù)雜度為 O(n)；而快速冪基于分治的思想，xn會(huì)等于 xn/2的平方，因此可以先計(jì)算出 xn/2然后進(jìn)行一次平方運(yùn)算得到 xn，同理，xn/2又等于 xn/4，因此可以先計(jì)算出 xn/4然后進(jìn)行一次平方運(yùn)算得到 xn/2，以此類(lèi)推，因此總的復(fù)雜度為 O(logn)，從而減少運(yùn)算時(shí)間
要注意的是，如果 n 為奇數(shù)，那么 xn應(yīng)該等于 xn/2* xn/2* x，因此需要判斷進(jìn)行平方根的平方運(yùn)算時(shí)需不需要多乘一個(gè) x
class Solution {public double myPow(double x, int n) {return n >= 0 ? quickPow(x, n) : 1.0 / quickPow(x, -n);
}
public double quickPow(double x, long n) {if (n == 0) {return 1.0;
}
//計(jì)算平方根
double tmp = quickPow(x,n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
}約瑟夫環(huán)。參考題解。
我們知道最后剩下的數(shù)字在最后一個(gè)數(shù)組中下標(biāo)肯定為 0，由于在上一輪要?jiǎng)h除第 m 個(gè)數(shù)，而且不是最后剩下這個(gè)數(shù)，所以最后剩下這個(gè)數(shù)在上一輪，也就是倒數(shù)第二個(gè)數(shù)組中的前面一定有 m 個(gè)數(shù)，它才不會(huì)被刪掉，所以它在倒數(shù)第二個(gè)數(shù)組中的下標(biāo)就是 (0 + m) % 2，0 + m 表示前面有 m 個(gè)數(shù)，但由于前面不一定有 m 個(gè)數(shù)，所以我們要把數(shù)組看成循環(huán)數(shù)組，所以求下標(biāo)時(shí)要取余數(shù)組大小，倒數(shù)第二個(gè)數(shù)組的大小為 2 ，所以取余 2。得到的就是最后剩下的這個(gè)數(shù)在倒數(shù)第二個(gè)數(shù)組中的下標(biāo)，以此類(lèi)推，推算到第一個(gè)數(shù)組，也即原數(shù)組，就能得到最后剩下的數(shù)字在原數(shù)組中的下標(biāo)，從而找到這個(gè)數(shù)
public int lastRemaining(int n, int m) {int res = 0;
for(int i = 2;i<= n;i++){res = (res + m) % i;
}
return res;
}你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
