发布时间:2023-08-30 19:00
最近在上Java课做练习时遇到一道,比较简单的Java题,暴力破解非常简单,但是出于对速度和性能的要求,我决定花更少的时间,用更少的内存去解决这道题。本博客提供两种解法,暴力破解和算法分析。
算法分析参考了一个大佬用C写的解法:http://zhidao.baidu.com/question/426301104,然后自己改了一下写成Java了。
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
15=1+2+3+4+5
15=4+5+6
15=7+8
请编写程序,根据输入的任何一个正整数,若有符合这种要求的连续正整数序列输出has,否则输出none。
例如:输入15,则输出
has
输入16,则输出
none
以下是两种解法:
①暴力破解:
import java.util.*;
public class NumberSum {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int source = in.nextInt();
int sum = 0;
boolean flag = false;
for(int i=1; i
我觉得这个没什么好说的,就是考虑所有可能性,有一个符合条件直接打破然后输出结果has,否则所有循环完没有符合条件的输出结果none。时间复杂度分析O(n^2)。
②算法分析:
这道题实际上就是一个等差数列求和,如果把数学忘了赶快回去复习一下吧。首先用数学方法分析一下:
首项:a1 = a;
尾项:an = a + (n-1)*d;这里d=1即 an = a + n -1;
等差数列求和:Sn = (a1+an)*n/2 = (2a+n-1)*n/2;(倒序相加法)
由等差数列求和,求得首项a = Sn/n + (1-n)/2;
因为Sn已知(程序输入),所以由项数n计算首项a;然后强转为int类型,若a为整数则其符合条件,标志赋予true,最后输出结果。这里条件n<=(source/2+1),因为本题目条件的原因,所以一个数的连续数字和肯定小于等于它的一半加一,即n<(n/2)+(n/2)+1;然后这里就可以减少循环次数节省时间和空间。时间复杂度分析O(n)。
以下是源代码:
import java.util.*;
public class NumberSum {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
boolean flag = false;
int source = in.nextInt();
for(float n=2; n<=(source/2+1); n++) {
float a = source/n + (float)0.5 - n/2;
if((int)a == a) {
flag = true;
break;
}
}
if(flag == true) {
System.out.println("has");
}else {
System.out.println("none");
}
}
}
有一群200w年薪的朋友是什么感觉?谈一谈入学中国科学院大学的几点感受吧
Cannot connect to the Docker daemon
oracle 消耗资源的语句,Oracle高资源消耗SQL语句定位
Python 项目管理与构建工具:CookieCutter, PyScaffold, PyBuilder, Poetry
记录编译测试LVI-SAM遇到的问题(附测试数据百度云下载链接)
Python:【人工智能】【机器学习】这篇博客带你读懂机器学习
Elasticsearch:使用 Elasticsearch Java client 8.0 来连接带有 HTTPS 的集群
Java 编程问题:七、Java 反射类、接口、构造器、方法和字段