算法刷题-求素数、数据流的中位数、不同的二叉搜索树

求素数

求1-100内的素数：

public static void main(String[] args){
        for(int i=0;i<100;i++) {
            checkPrime(i);
        }
    }
    private static void checkPrime(int x){
        boolean isPrime = true;
        if(x ==1 || x %2 ==0 && x !=2 )
        {
            isPrime = false;
        }
        else
        {
            for( int i =3; i< Math.sqrt(x); i+=2)
            {
                if( x % i == 0)
                {
                    isPrime = false;
                    break;
                }
            }
        }
        if( isPrime)
        {
            System.out.println(x +"是素数");
        }
        else
        {
            System.out.println(x+ "不是素数");
        }
    }

数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

示例： addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 进阶:

1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

class MedianFinder {
    PriorityQueue<Integer> min;
    PriorityQueue<Integer> max;
    /** initialize your data structure here. */
    public MedianFinder() {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
    }
    public void addNum(int num) {
        max.add(num);
        min.add(max.remove());
        if (min.size() > max.size())
            max.add(min.remove());
    }
    public double findMedian() {
        if (max.size() == min.size())
            return (max.peek() + min.peek()) / 2.0;
        else
            return max.peek();
    }
}
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1： 输入：n = 3 输出：5 示例 2： 输入：n = 1 输出：1

提示：

• 1 <= n <= 19

class Solution {
    public int numTrees(int n) {
        if (n < 2) {
            return 1;
        }
        int[] count = new int[n + 1];
        count[0] = 1;
        count[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = 0;
            for (int root = 1; root <= i; root++) {
                sum = sum + count[root - 1] * count[i - root];
            }
            count[i] = sum;
        }
        return count[n];
    }
}

本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????‍????

保持热爱，奔赴下一场山海。????????????