【数据结构与算法分析第三版------》算法分析】

古城微笑少年丶 2023-09-26 15:51 135阅读 0赞

import lombok.extern.slf4j.Slf4j;
    import org.apache.commons.lang3.time.StopWatch;
    import org.junit.Test;
    
    /**
     * 数据结构与算法分析第三版-》算法分析
     * 1、最大子序列和
     * 2、折半查找法（二分法）
     * 3、最大公因数的欧几里得
     * 4、高效率的幂运算
     *
     * @author lfsun
     */
    @Slf4j
    public class Chapter02 {
        
    
        private static final int[] a = {
        -3, 4, 3, -1, -2, -1, 2, 9, -2};
    
        /**
         * 1、最大子序列和
         *
         * @param a
         * @return
         */
        public int maxSubSum(int[] a) {
        
            int max = 0, thisSum = 0;
            for (int i = 0; i < a.length; i++) {
        
                thisSum += a[i];
                if (thisSum > max) {
        
                    max = thisSum;
                } else if (thisSum < 0) {
        
                    thisSum = 0;
                }
            }
            return max;
        }
    
        @Test
        public void testMaxSubSum() {
        
            log.info("{}", maxSubSum(a));
        }
    
    
        /**
         * 2、折半查找法（二分法）
         */
        public int binarySearch(int[] a, int found) {
        
            int left = 0, right = a.length - 1;
            while (left <= right) {
        
                int mid = (left + right) / 2;
                if (a[mid] - found < 0) {
        
                    left = mid + 1;
                } else if (a[mid] - found > 0) {
        
                    right = mid - 1;
                } else {
        
                    return mid;
                }
            }
            return -1;
        }
    
        @Test
        public void testBinarySearch() {
        
            log.info("{}", binarySearch(a, 0));
            log.info("{}", binarySearch(a, -2));
            log.info("{}", binarySearch(a, 4));
        }
    
    
        /**
         * 3、最大公因数的欧几里得
         */
        public long gcd(long m, long n) {
        
            while (n != 0) {
        
                long mod = m % n;
                m = n;
                n = mod;
            }
            return m;
        }
    
        @Test
        public void testGcd() {
        
            log.info("{}", gcd(50, 20));
            log.info("{}", gcd(300, 21));
            log.info("{}", gcd(1989, 1590));
        }
    
        public long pow(long m, int n) {
        
            return (long) Math.pow(m, n);
        }
    
        /**
         * 4、高效率的幂运算(与lang包下 Math的 public static double pow(double a, double b) 旗鼓相当)
         */
        public long powH(long x, int n) {
        
            if (n == 0) {
        
                return 1;
            }
            if (n == 1) {
        
                return x;
            }
            // if (MathUtil.isEven(n)) {
        
            // if (n % 2 == 0) {
        
            if ((n & 0x1) == 0) {
        
                // 判断是否偶数
                return powH(x * x, n / 2);
            } else {
        
                return powH(x * x, n / 2) * x;
            }
        }
    
        @Test
        public void testPow() {
        
            // 创建一个 StopWatch 实例并开始计时
            StopWatch sw = StopWatch.createStarted();
            log.info("{}", powH(4, 11));
            log.info("{}", powH(5, 11));
            log.info("{}", powH(6, 11));
            log.info("{}", powH(7, 11));
            // 获取计时时间
            log.info("{}", sw.getTime());
            // 计时重置
            sw.reset();
            // 开始计时
            sw.start();
            log.info("{}", pow(4, 11));
            log.info("{}", pow(5, 11));
            log.info("{}", pow(6, 11));
            log.info("{}", pow(7, 11));
            log.info("{}", sw.getTime());
    
        }
    }