最小(大)栈、求最大公约数、判断一个数是否为2的整数次幂

2.最小(大)栈问题

题目

实现一个栈，该栈带有出栈(pop)，入栈(push)，取最小元素(getMin)3个方法。且要保证这3个方法的时间复杂度都是O(1)。

思路

1.设原有的栈为main栈，此时创建一个额外的min栈，用于辅助main栈。

2.当第1个元素，进main栈时，让该元素，也进入min栈，这个唯一的元素也是main栈的min值。

3.之后，每当最小元素进入main栈时，比较新元素和main栈当前最小值的大小，如果小于main栈的最小值，则让新元素也进入min栈，此时min栈的栈顶元素就是main栈的最小值。

4.每当main栈有元素出栈时，如果出栈元素是main栈当前最小值，则让min栈的栈顶元素也出栈。此时min栈余下的栈顶元素所指向的，是main栈中，除最小值外的最小值元素，代替刚出栈的元素成为main栈的当前最小值。

5.当调用getMin方法时，返回min栈的栈顶所存储的值，这也就是栈A的最小值。

此解法中，进栈，出栈，取最小值的时间复杂度都是O(1).

最大栈，同理。

代码

import java.util.Stack;

public class MinStack {

    private final Stack<Integer> mainStack = new Stack<>();
    private final Stack<Integer> minStack = new Stack<>();
    private final Stack<Integer> maxStack = new Stack<>();

    /**
     * 入栈
     * @param element 元素
     */
    public void push(int element){
        mainStack.push(element);
        //注意判断是否为空条件，要在短路或的左边。因为要先向空栈添加元素，才能返回栈顶元素进行判断。否则报stack is empty异常。
        if(minStack.isEmpty() || element <= minStack.peek())
            minStack.push(element);//记录主栈中的历史最小值
        if(maxStack.isEmpty() || element >= maxStack.peek())
            maxStack.push(element);//记录主栈中的历史最大值
    }

    /**
     * 出栈操作
     */
    public Integer pop(){
        if(mainStack.peek().equals(maxStack.peek()))
            maxStack.pop();//如果出栈的是主栈中的最大值，则辅助栈也出栈
        if(mainStack.peek().equals(minStack.peek()))
            minStack.pop();//如果出栈的是主栈中的最小值，则辅助栈也出栈
        return mainStack.pop();
    }

    /**
     * 获取栈的最大值
     */
    public int getMax() throws Exception{
        if(mainStack.isEmpty())
            throw new RuntimeException("stack is empty");
        return maxStack.peek();//返回辅助栈中的栈顶元素就是主栈中的最大值
    }

    /**
     * 获取栈的最小值
     */
    public int getMin() throws Exception{
        if(mainStack.isEmpty())
            throw new RuntimeException("stack is empty");
        return minStack.peek();//返回辅助栈中的栈顶元素就是主栈中的最小值
    }

    public static void main(String[] args) throws Exception {
        MinStack stack = new MinStack();
        stack.push(4);
        stack.push(9);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);
        System.out.println(stack.getMin());
        System.out.println(stack.getMax());
        stack.pop();
        stack.pop();
        stack.pop();
        System.out.println(stack.getMin());
        System.out.println(stack.getMax());
    }
}

3.如何求出最大公约数

题目

写一段代码，求出两个最大整数的最大公约数，尽量优化算法的性能。

//GreatestCommonDivisor gcd
public static int gcd1(int a,int b){
    int big = Math.max(a, b);
    int small = Math.min(a, b);
    if (big % small == 0)
        return small;
    for(int i = small / 2;i > 1;i--){
        if(small%i==0 && big % i == 0)
            return i;
    }
    return 1;
}

存在的问题，如果传入的整数是10000和10001，用你的方法就需要循环10000/2-1=4999次，更别说其他更大的数了。

思路

辗转相除法，也叫欧几里得算法(Eucliden algorithm)，该算法的目的是求出两个正整数的最大公约数。

这条算法基于一个定理：两个正整数a和b(a > b)，它们的最大公约数，等于a除b的余数，c和b之间的最大公约数。

例如，10和45，45除以10商4余5，那么10和45最大公约数，等于10和5的最大公约数。

这样，就可以递归的方法把问题逐步简化。首先，计算出a和b的余数c，问题就转化为了b和c的最大公约数，然后计算出b和c的余数d，问题转化为c和d的最大公约数，以此类推，逐渐把两个较大整数之间的运算，简化为两个较小整数之间的运算，直到两个数可以整除，或者其中一个数减小到1结束。

//getGreatestCommonDivisor
public static int gcd2(int a, int b) {
    int big = Math.max(a, b);
    int small = Math.min(a, b);
    if (big % small == 0)
        return small;
    return gcd2(big % small, small);
}

但是也有问题，当两个整数较大时，a%b取模运算的性能会比较差。(a % b)= a - (a/b)*b。

还有算法，更相减损术，出自中国古代《九章算术》，也是一种求最大公约数的算法。

原理：两个正整数a和b(a>b)，它们的最大公约数，等于a-b的差值c和较小数b的最大公约数。

例如，10和45，45-10=35，那么10和45最大公约数，等于10和35的最大公约数。

这样，就可以递归的方法把问题逐步简化。首先，计算出a和b的差值c，问题就转化为了b和c的最大公约数，然后计算出b和c的差值d，问题转化为b和d的最大公约数，以此类推，逐渐把两个较大整数之间的运算，简化为两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的连个数的值。

public static int gcd3(int a,int b){
    if(a == b)
        return a;
    int big = Math.max(a,b);
    int small = Math.min(a,b);
    return gcd3(big-small,small);
}

存在问题，如果两个数的差值较大如，10000和2，该方法递归的深度也会很大，要递归9998次，才结束。

在计算机中，位运算的性能是非常高的。对于给出的正整数a和b。

当a和b均为偶数时，gcd(a,b) = 2*gcd(a/2,b/2) = 2 * gcd(a>>1,b>>1)

当a为偶数，b为奇数时，gcd(a,b) = gcd(a/2,b) = gcd(a>>1,b)

当a为奇数，b为偶数时，gcd(a,b) = gcd(a,b/2) = gcd(a,b>>1)

当a和b均为奇数时，先利用更相减损术运算一次，gcd(a,b) = gcd(b,a-b)，此 时a-b必然是偶数，然后又可以继续进行移位运算。

这种方式在两数都比较小时，可能看不出计算次数的优势；当两数越大时，计算次数的减少就会越明显。

final code

	/**
     * @param a 正整数
     * @param b 正整数
     * @return 最大公约数
     */
    public static int gcd(int a, int b) {
        if (a == b)
            return a;
        if ((a & 1) == 0 && (b & 1) == 0)//正整数的偶数的最低位一定是0，和1进行算术&操作，一定是0
            return gcd(a >> 1, b >> 1) << 1;
        else if ((a & 1) == 0 && (b & 1) != 0)
            return gcd(a >> 1, b);
        else if ((a & 1) != 0 && (b & 1) == 0)
            return gcd(a, b >> 1);
        else {
            int big = Math.max(a, b);
            int small = Math.min(a, b);
            return gcd(big - small, small);
        }
    }

4.如何判断一个数是否为2的整数次幂

题目

如何判断一个正整数是否为2的正整数幂，比如1、2、4、8、16…，要求性能尽可能高。

思路

这里直接给出O(1)的思路，不再给出其他思路。我觉得学习算法的意义就是，学习别人高效的思路。

这里，用到一个数学知识，2^n - 1= 2^(n-1) + 2 ^(n-2) + .... + 2^0。n为自然数。

而2^n(n为自然数)的特征是，在32位补码中，只有表示其值的位是1，其余位都是0。而2^n-1，就是2^(n-1) + 2 ^(n-2) + .... + 2^0，等于被判断的数num-1，如果num是2的整数次幂，则在num-1的特征是，在num表示其值的位后面的位都是1。

例如，16 = 2^4， 2^4 - 1 = 2^3 + 2^2 + 2^1 + 2^0，(int)16的后8位，00010000，(int)15的后8位00001111，

这样16 & 15 的结果就是0，以此，可以得出判断一个数是否是2的整数次幂的思路。

代码

    //2^n - 1 = 2^(n-1) + 2^(n-2) + ... + 2^0;(n为>=0的正整数)
    /**
     * @param num 自然数
     */
    public static boolean isPowerOf2(int num){
        return (num & num - 1) == 0;
    }

来源链接：https://www.cnblogs.com/changming06/p/18612136