【面试算法题总结16】数学相关算法

快速幂
n=-2147483648这个用例决定了要用long变量b。
下面(b % 2) == 1可以变成(b & 1) == 1；b /=2;可以变成b >>= 1;

class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0){
            if((b % 2) == 1){
                res *= x;
            }
            x *= x;
            b /=2;
        }
        return res;
    }
}

每个运算都%mod，而且还要防止一个大数-小数，但只有大数被%mod了，还要再+mod，最后再%mod。

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int T=in.nextInt();
        for(int i=0;i 
 
 
例题3：确定比例，求最大乘积 
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        long A=in.nextLong();
        long B=in.nextLong();
        long a=in.nextLong();
        long b=in.nextLong();

        //逻辑开始
        //找到a和b的最大公约数(让a和b同比变小)
        long c=f(a,b);
        long minX=a/c;
        long minY=b/c;
        
        long resultX=0,resultY=0;
        for(int k=1;k*minX<=A&&k*minY<=B;++k){
            long x=k*minX;
            long y=k*minY;
            resultX=x;
            resultY=y;
        }
        System.out.println(resultX+" "+resultY);
    }

    //找到a和b的最大公约数
    static long f(long a,long b){
        long c=0;
        while(b!=0){
            c=a%b;
            a=b;
            b=c;
        }
        return a;
    }
}
 
 
 
例题4：修水渠 
import java.util.*;

public class T12{
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        int[] house=new int[n];
        for(int i=0;i 
 
 
例题5：安排一下座位，达到邻座之间的差异之和最大 
import java.util.*;

public class T13{
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        int[] nums=new int[n];
        for(int i=0;i0) reslutSum = reslutSum + Math.abs(resultArr[i]-resultArr[i-1]);
        }
        //计算最后一位与第一位的差值
        reslutSum = reslutSum + Math.abs(resultArr[n-1]-resultArr[0]);

        //输出结果
        System.out.println(reslutSum);
        for (long result : resultArr) {
            System.out.print(result + " ");
        }
    }
}
 
 
 
例题6：正n边形的等腰锐角三角形数量 
画了一个正n边形，他想知道多边形中等腰锐角三角形的数量。（三角形的顶点要在多边形的顶点上）
 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        //计算没有减去钝角前每个角能构成的等腰三角形个数p
        long p=(n-1)/2;
        //p减去其中的钝角个数
        p=(p+1)/2;
        //计算减去钝角后的结果sum
        long sum=n*p;
        //sum减去直角的个数
        if(n%4==0)sum-=n;
        //sum减去重复的锐角的个数
        if(n%3==0)sum-=n/3*2;
        System.out.println(sum);
    }
}