算法刷题-求素数、数据流的中位数、不同的二叉搜索树
2023-03-07 09:06:10 时间
求素数、数据流的中位数、不同的二叉搜索树
求素数
求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 进阶:
- 如果数据流中所有整数都在 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];
}
}
本文内容到此结束了, 如有收获欢迎点赞?收藏?关注✔️,您的鼓励是我最大的动力。 如有错误❌疑问?欢迎各位指出。 主页:共饮一杯无的博客汇总?? 保持热爱,奔赴下一场山海。???
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的