求素数、数据流的中位数、不同的二叉搜索树
- 求素数
- 数据流的中位数
- 不同的二叉搜索树
求素数
求1-100内的素数：
代码语言：javascript复制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 进阶:
- 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
- 如果数据流中 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];
}
}本文内容到此结束了， 如有收获欢迎点赞
