最小(大)栈、求最大公约数、判定一个数是否为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).
最大栈，同理。
代码

1. import java.util.Stack;
3. public class MinStack {
5.     private final Stack<Integer> mainStack = new Stack<>();
6.     private final Stack<Integer> minStack = new Stack<>();
7.     private final Stack<Integer> maxStack = new Stack<>();
9.     /**
10.      * 入栈
11.      * @param element 元素
12.      */
13.     public void push(int element){
14.         mainStack.push(element);
15.         //注意判断是否为空条件，要在短路或的左边。因为要先向空栈添加元素，才能返回栈顶元素进行判断。否则报stack is empty异常。
16.         if(minStack.isEmpty() || element <= minStack.peek())
17.             minStack.push(element);//记录主栈中的历史最小值
18.         if(maxStack.isEmpty() || element >= maxStack.peek())
19.             maxStack.push(element);//记录主栈中的历史最大值
20.     }
22.     /**
23.      * 出栈操作
24.      */
25.     public Integer pop(){
26.         if(mainStack.peek().equals(maxStack.peek()))
27.             maxStack.pop();//如果出栈的是主栈中的最大值，则辅助栈也出栈
28.         if(mainStack.peek().equals(minStack.peek()))
29.             minStack.pop();//如果出栈的是主栈中的最小值，则辅助栈也出栈
30.         return mainStack.pop();
31.     }
33.     /**
34.      * 获取栈的最大值
35.      */
36.     public int getMax() throws Exception{
37.         if(mainStack.isEmpty())
38.             throw new RuntimeException("stack is empty");
39.         return maxStack.peek();//返回辅助栈中的栈顶元素就是主栈中的最大值
40.     }
42.     /**
43.      * 获取栈的最小值
44.      */
45.     public int getMin() throws Exception{
46.         if(mainStack.isEmpty())
47.             throw new RuntimeException("stack is empty");
48.         return minStack.peek();//返回辅助栈中的栈顶元素就是主栈中的最小值
49.     }
51.     public static void main(String[] args) throws Exception {
52.         MinStack stack = new MinStack();
53.         stack.push(4);
54.         stack.push(9);
55.         stack.push(7);
56.         stack.push(3);
57.         stack.push(8);
58.         stack.push(5);
59.         System.out.println(stack.getMin());
60.         System.out.println(stack.getMax());
61.         stack.pop();
62.         stack.pop();
63.         stack.pop();
64.         System.out.println(stack.getMin());
65.         System.out.println(stack.getMax());
66.     }
67. }

复制代码

3.如何求出最大公约数

题目

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

1. //GreatestCommonDivisor gcd
2. public static int gcd1(int a,int b){
3.     int big = Math.max(a, b);
4.     int small = Math.min(a, b);
5.     if (big % small == 0)
6.         return small;
7.     for(int i = small / 2;i > 1;i--){
8.         if(small%i==0 && big % i == 0)
9.             return i;
10.     }
11.     return 1;
12. }

复制代码

存在的问题，假如传入的整数是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竣事。

1. //getGreatestCommonDivisor
2. public static int gcd2(int a, int b) {
3.     int big = Math.max(a, b);
4.     int small = Math.min(a, b);
5.     if (big % small == 0)
6.         return small;
7.     return gcd2(big % small, small);
8. }

复制代码

但是也有问题，当两个整数较大时，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的最大公约数，以此类推，逐渐把两个较大整数之间的运算，简化为两个较小整数之间的运算，直到两个数可以相等为止，最大公约数就是最终相等的连个数的值。

1. public static int gcd3(int a,int b){
2.     if(a == b)
3.         return a;
4.     int big = Math.max(a,b);
5.     int small = Math.min(a,b);
6.     return gcd3(big-small,small);
7. }

复制代码

存在问题，假如两个数的差值较大如，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

1.         /**
2.      * @param a 正整数
3.      * @param b 正整数
4.      * @return 最大公约数
5.      */
6.     public static int gcd(int a, int b) {
7.         if (a == b)
8.             return a;
9.         if ((a & 1) == 0 && (b & 1) == 0)//正整数的偶数的最低位一定是0，和1进行算术&操作，一定是0
10.             return gcd(a >> 1, b >> 1) << 1;
11.         else if ((a & 1) == 0 && (b & 1) != 0)
12.             return gcd(a >> 1, b);
13.         else if ((a & 1) != 0 && (b & 1) == 0)
14.             return gcd(a, b >> 1);
15.         else {
16.             int big = Math.max(a, b);
17.             int small = Math.min(a, b);
18.             return gcd(big - small, small);
19.         }
20.     }

复制代码

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的整数次幂的思路。
代码

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

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。