专栏首页营琪的小记录算法:递归和分治-实战

算法:递归和分治-实战

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_43126117/article/details/99105076


leetcode:50实现 pow(x, n) ,即计算 x 的 n 次幂函数。

方法一、直接调用库函数

我猜运行时间是最快的

public double myPow(double x, int n) {
      return Math.pow(x, n);
    }

方法二、暴力

public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        for (long i = 0; i < N; i++)
            ans = ans * x;
        return ans;
    }

方法三、递归分治的做法

class Solution {
    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }
};

leetcode:169求众数。

题目解析:本质就是求数组,相同元素出现次数,返回的结果就是次数最多对应的元素。

方法一:暴力

    public int majorityElement1(int[] nums) {
        int n = nums.length;
        for (int x : nums) {
            int count = 0;
            for (int j : nums) {
                if (x == j) count++;
            }
            if (count > n / 2) return x;
        }
        return 0;
    }

方法二:哈希表 ,元素出现次数存入map中

public int majorityElement2(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap();
        for (int x : nums) {
            Integer num = map.get(x);
            if (num == null) num = 0;
            map.put(x, num + 1);
            if (num + 1 > n / 2) return x;
        }
        return 0;
    }

方法三:分治

class Solution11 {
        private int countInRange(int[] nums, int num, int lo, int hi) {
            //计算两边次数
            int count = 0;
            for (int i = lo; i <= hi; i++) {
                if (nums[i] == num) {
                    count++;
                }
            }
            return count;
        }

        private int majority(int[] nums, int lo, int hi) {
            if (lo == hi) {         //递归出口
                return nums[lo];
            }
            //数据准备
            int mid = (hi-lo)/2 + lo;
            //对子问题进行递归处理
            int left = majority(nums, lo, mid);
            int right = majority(nums, mid+1, hi);

            //子结果数据合并判断 
            if (left == right) {           
                return left;
            }
            
            //left!=right时,根据次数判断
            int leftCount = countInRange(nums, left, lo, hi);
            int rightCount = countInRange(nums, right, lo, hi);

            return leftCount > rightCount ? left : right;
        }

        public int majorityElement(int[] nums) {
            return majority(nums, 0, nums.length-1);
        }
    }

方法四:扩展 Boyer-Moore 投票算法

假设众数为当前值记为+1,其余数记为-1,并且相加,当等于零时,重新开始,假设下一个为众数,直到最后,结果肯定大于0,那么最后一个假设众数为真。

   public int majorityElement(int[] nums) {
       int count = 0;
       Integer candidate = null;

       for (int num : nums) {
           if (count == 0) {
               candidate = num;
           }
           count += (num == candidate) ? 1 : -1;
       }

       return candidate;
   }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java的基础程序设计结构(Java学习-1)

    注释就是方便自己或者别人阅读代码,绝大多数的程序语言都有注释这个功能,大部分的注释命令都是相同的或者想通的,

    营琪
  • 复习:GoF的23种设计模式之iterator模式(行为型)

    就如java集合中的iterator类似,是一种最简单也是最常用的设计模式。它可以让用户通过的特定接口轮询容器中的每一个元素,而不需要了解底层实现。

    营琪
  • 算法:HashTable、List、Map、Set-实战

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    营琪
  • top100习题

    根据每日 气温 列表,请重新生成一个列表,对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

    黑白格
  • 【Leet Code】1. Two Sum

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 查找算法

    查找,作为应用最为广泛和最基础的算法思想之一,几乎在所有应用程序之中都有它的思想身影。往细一点说:查找可以有 顺序查找、二分查找、散列表查找,下面依次来看一下这...

    指点
  • 适合数据分析面试笔试入门的编程题

    1.在输入ai1的时候,因为是每颗果树的第一个输入,代表刚开始果树的苹果含量,所以可以写在第二个循环的前面和第一个循环的里面,所以第二个循环就要从1开始。

    开心鸭
  • codeforces415D. Glad to see you!

    交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$

    attack
  • 算法学习记录

    MiChong
  • cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

    答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案

    attack

扫码关注云+社区

领取腾讯云代金券