題目匯總https://leetcode-cn.com/tag/math/
223. 矩形面積中等[?]
224. 基本計(jì)算器（沒(méi)做）
231. 2的冪簡(jiǎn)單[?]
233. 數(shù)字 1 的個(gè)數(shù)困難（不會(huì)做侣监，看題解）
258. 各位相加簡(jiǎn)單[?]
263. 丑數(shù)簡(jiǎn)單[?]
264. 丑數(shù) II中等[?]
223. 矩形面積中等
在二維平面上計(jì)算出兩個(gè)由直線構(gòu)成的矩形重疊后形成的總面積。
每個(gè)矩形由其左下頂點(diǎn)和右上頂點(diǎn)坐標(biāo)表示臣淤，如圖所示橄霉。
示例:
輸入: -3, 0, 3, 4, 0, -1, 9, 2
輸出: 45
思路：總面積-折疊面積
//2020.07.20
class Solution {//執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了98.13%的用戶
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int area1 = (C - A) * (D - B);
int area2 = (G - E) * (H - F);
if(C <= E || A >= G || B >= H || D <= F){
return area1 + area2;//無(wú)重疊
}
int leftX = Math.max(A, E);//左下交點(diǎn)
int leftY = Math.max(B, F);//左下交點(diǎn)
int rightX = Math.min(C, G);//右上交點(diǎn)
int rightY = Math.min(D, H);//右上交點(diǎn)
return area1 + area2 - (rightX - leftX) * (rightY - leftY);
}
}
231. 2的冪簡(jiǎn)單
給定一個(gè)整數(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 2 的冪次方邑蒋。
示例 1:
輸入: 1姓蜂，輸出: true
解釋: 20 = 1
示例 2:
輸入: 16，輸出: true
解釋: 24 = 16
示例 3:
輸入: 218医吊，輸出: false
思路：
根據(jù)二進(jìn)制的性質(zhì)钱慢，若
n為2的冪，則n & (n - 1) = 0
class Solution {//執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶
public boolean isPowerOfTwo(int n) {
if(n < 1)
return false;
//報(bào)錯(cuò)bad operand types for binary operator '&'
//是因?yàn)?'==' 的優(yōu)先級(jí)比 '&' 大卿堂，需要加括號(hào)
return (n & (n - 1)) == 0;
}
}
233. 數(shù)字 1 的個(gè)數(shù)困難
給定一個(gè)整數(shù) n束莫，計(jì)算所有小于等于 n 的非負(fù)整數(shù)中數(shù)字 1 出現(xiàn)的個(gè)數(shù)。
示例:
輸入: 13
輸出: 6
解釋: 數(shù)字 1 出現(xiàn)在以下數(shù)字中: 1, 10, 11, 12, 13 草描。
思路：
258. 各位相加簡(jiǎn)單
給定一個(gè)非負(fù)整數(shù)
num麦箍，反復(fù)將各個(gè)位上的數(shù)字相加，直到結(jié)果為一位數(shù)陶珠。
示例:
輸入:38
輸出: 2
解釋: 各位相加的過(guò)程為：3 + 8 = 11,1 + 1 = 2挟裂。 由于2是一位數(shù)，所以返回 2揍诽。
進(jìn)階:
你可以不使用循環(huán)或者遞歸诀蓉，且在 O(1) 時(shí)間復(fù)雜度內(nèi)解決這個(gè)問(wèn)題嗎？
思路一：我的直觀做法遞歸
class Solution {//執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶
public int addDigits(int num) {
if(num < 10)
return num;
int sum = 0;
while(num != 0){
int digit = num % 10;
sum += digit;//計(jì)算每位數(shù)字之和
num /= 10;
}
return addDigits(sum);
}
}
思路二：題解區(qū)的優(yōu)秀做法
其中有推導(dǎo)過(guò)程https://leetcode-cn.com/problems/add-digits/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-7/#comment
n 是 0 暑脆，數(shù)根就是 0渠啤。
n 不是 9 的倍數(shù)，數(shù)根就是 n 對(duì) 9 取余添吗，即 n mod 9沥曹。
n 是 9 的倍數(shù)，數(shù)根就是 9。
同樣的妓美，我們可以通過(guò) (n-1) mod 9 + 1 這個(gè)式子把上邊的幾種情況統(tǒng)一起來(lái)僵腺。
class Solution {//執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
}
263. 丑數(shù)簡(jiǎn)單
編寫(xiě)一個(gè)程序判斷給定的數(shù)是否為丑數(shù)。
丑數(shù)就是只包含質(zhì)因數(shù)2, 3, 5的正整數(shù)壶栋。
示例 1:
輸入: 6
輸出: true
解釋: 6 = 2 × 3
思路：
如果一個(gè)數(shù)能夠被2整除辰如，那么讓他繼續(xù)除以2；
如果一個(gè)數(shù)能夠被3整除贵试，那么讓他繼續(xù)除以3琉兜；
如果一個(gè)數(shù)能夠被5整除，那么讓他繼續(xù)除以5毙玻；
如果最后這個(gè)數(shù)變?yōu)?豌蟋，那么這個(gè)數(shù)就是丑數(shù)，否則不是桑滩。
class Solution {
public boolean isUgly(int num) {
while(num % 2 == 0)
num /= 2;
while(num % 3 == 0)
num /= 3;
while(num % 5 == 0)
num /= 5;
return num == 1;
}
}
264. 丑數(shù) II中等
編寫(xiě)一個(gè)程序梧疲，找出第
n個(gè)丑數(shù)。
丑數(shù)就是質(zhì)因數(shù)只包含2, 3, 5的正整數(shù)施符。
示例:
輸入: n = 10
輸出: 12
解釋:1, 2, 3, 4, 5, 6, 8, 9, 10, 12是前 10 個(gè)丑數(shù)。
**說(shuō)明: **
1是丑數(shù)擂找。n不超過(guò)1690戳吝。
思路：三指針+動(dòng)態(tài)規(guī)劃
利用三個(gè)指針，每次找到三組中最小的元素贯涎，然后指針后移
//2020.06.11
class Solution {//執(zhí)行用時(shí) :3 ms, 在所有 Java 提交中擊敗了84.88%的用戶
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1; //丑數(shù)序列听哭， 第 1 個(gè)丑數(shù)是 1
int p_2 = 0;
int p_3 = 0;
int p_5 = 0;
for (int i = 1; i < n; ++i)
{
dp[i] = Math.min(Math.min(2 * dp[p_2], 3 * dp[p_3]), 5 * dp[p_5]);
if(dp[i] == 2 * dp[p_2])
++p_2;
if(dp[i] == 3 * dp[p_3])
++p_3;
if(dp[i] == 5 * dp[p_5])
++p_5;
}
return dp[n - 1];//找出第 n 個(gè)丑數(shù)
}
}
