LeetCode-math类总结(会持续更新...)

本文主要是对leetcode中的math类算法的总结,包含了各题的solution和常用的解决方法。

相关源码:code

204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

解题思路:本题利用了素数的概念和打表法 ,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int countPrimes(int n) {
vector<bool> check(n);
//bool []check = new bool[n];
int count = 0;
for(int i=2; i<n; i++){
if(check[i]==false){
count++;
for(int j=2;i*j<n;j++){
check[j*i]=true;
}
}
}

return count;
}
};

263. Ugly Number

Description:Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

解题思路:直接除以2,3,5,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool isUgly(int num) {
while(num > 1){
if(num%2 == 0){
num /= 2;
}else if(num%3 == 0){
num /= 3;
}else if(num%5 == 0){
num /= 5;
}else{
break;
}
}

return num==1;
}
};

400. Nth Digit

Description:Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

1
2
3
4
5
6
Input:
3

Output:
3

Example 2:

1
2
3
4
5
6
7
8
Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int findNthDigit(int n) {

long base = 9;
long digits = 1;
while(n-base*digits > 0){
n -= base*digits;
base *=10;
digits++;
}

int index = n%digits;
if(index == 0){
index=digits;
}
int num = 1;
for(int i=1; i<digits; i++){
num *= 10;
}

num += (index==digits) ? n/digits - 1 : n/digits;
for(int i=index; i<digits; i++){
num /= 10;
}

return num%10;

}
};

633. Sum of Square Numbers

Description:Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.

Example 1:

1
2
3
4
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

1
2
Input: 3
Output: False

解题思路:使用双指针逼近,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <math.h>

using namespace std;

class Solution{
public:
bool judgeSquareSum(int c) {
if(c < 0) return false;
int l = 0;
int r = (int)sqrt(c);
while(l<=r){
temp = l*l + r*r;
if(temp < c){
l++;
}else if(temp > c){
r--;
}else{
return true;
}
}
return false;
}
};

367. Valid Perfect Square

Description:

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

1
2
3
Input: 16
Returns: True

Example 2:

1
2
3
Input: 14
Returns: False

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
bool isPerfectSquare(int num) {
for(int i=1; num>0; i+=2){
num -= i;
}
return num==0;
}

bool isPerfectSquare2(int num){
int left = 1;
int right = num;
while(left<=right){
int mid = left + (right - left)/2;
int temp = mid*mid;
if(temp < num){
left=mid+1;
}else if(temp > num){
right = mid-1;
}else{
return true;
}
}
return false;
}
};

172. Factorial Trailing Zeroes

Description:

Given an integer n, return the number of trailing zeroes in n!.

**Note: **Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int trailingZeroes(int n) {
long result = 0;
long x = 5;
while(x<=n){
result += n/x;
x *=5;
}
return result;
}
};