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.

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

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，代码如下：

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:

Input:
3

Output:
3

Example 2:

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.

代码如下：

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:

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

Example 2:

Input: 3
Output: False

解题思路：使用双指针逼近，代码如下：

#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:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

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

代码如下：

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.

class Solution {
public:
    int trailingZeroes(int n) {
        long result = 0;
        long x = 5;
        while(x<=n){
            result += n/x;
            x *=5;
        }
        return result;
    }
};