考试情况： 时间：19：00---21：00 平台：赛码 选择题：30道，涉及计算机网络、Linux基础（大量）、mysql数据库、数据结构（连通图……）读程序 算法题：2道，可以在本地IDE调试，难度适中。
1、超大整数转字符串处理问题
小A随手写出了一个正整数n。他可以对这个数字做出如下操作： 1、 把这个数字除以一个数，且保证结果是大于1的正整数； 2、 把这个数字减去1。 小A想知道通过如上操作把这个数变成1的最小操作次数。 输入：第一行有1个正整数T，表示数据的组数； 接下来T行，每行有1个正整数n，含义如题。 1 ≤ T ≤ 10000，1 ≤ n ≤ 10的18次方。 输出：输出T行，每行1个整数，表示题目所求的最小操作次数。 输入：2 1 4 输出：0 2
思路1：开始采用动态规划思想，但是只能通过36%，问题出现在对于每次输入的n要自底向上逐个值进行计算，我最初分析可能是时间复杂度过高，改用思路2递归求解。
public class First {
public static final int INT_MAX=0X7FFFFFFA;
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int t=cin.nextInt();
int n;
while (t-->0){
n=cin.nextInt();
int[]res=new int[n+1];
res[1]=0;
if(n==1){
System.out.println(0);
}
else{
res[2]=1;
for(int i=3;i<=n;i++){
int yueshu=yueshu(i);
if(yueshu>=INT_MAX){
res[i]=res[i-1]+1;
}
else{
res[i]=Math.min(res[i-1],res[i/yueshu])+1;
}
}
}
for(int j=1;j<=n;j++){
System.out.println("j="+j+" 值："+res[j]);
}
}
}
private static int yueshu(int n) {
for(int i=n-1;i>1;i--)
{
if(n%i==0&&n/i>1)
{
return i;
}
}
return INT_MAX;
}
} 思路2：对于输入的n，只需要递归去算n,n/(最大约数)，根据奇偶最多也就2次或3次即可得到结果，相比于上面计算n次有了大大的提升，但是结果还是通过36%。认真分析后采用了思路3 public class second {
public static final int INT_MAX=0X7FFFFFFA;
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int t=cin.nextInt();
int n;
while (t-->0){
n=cin.nextInt();
int res=getnum(n);
System.out.println(res);
}
}
private static int getnum(int n){
if(n<=1)
return 0;
if(n==2)
return 1;
if(yueshu(n)>=INT_MAX){
return getnum(n-1)+1;
}
else{
return Math.min(getnum(n-1),getnum(n/yueshu(n)))+1;
}
}
private static int yueshu(int n) {
for(int i=n-1;i>1;i--)
{
if(n%i==0)
{
return i;
}
}
return INT_MAX;
}
} 思路3：通过思路2 的尝试我们发现结果有一定的规律性，对于奇数n我们需要计算3次（n=n-1,n除以约束降到2，2-1）对于偶数n只需要执行后面2步即可，所以对于前面特殊情况特殊处理外，后面只需要判断奇偶数进行输出3、2就可以了。因为时间原因，代码比较粗糙，匆匆的改了下，交上去100%，就去做了第二题，但是基本的思想已经在里面了，后面可以自己优化。 核心思想：
1 ≤ n ≤ 10的18次方 对于超长的输入采用字符串进行读取处理 ，取最后以为判断奇偶进行输出，如果有其它处理大数方法请多多指教。 public class four {
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int t=cin.nextInt();
int n;
String str;
while (t-->0){
str=cin.next();
int res;
if(str.length()<2){
n=Integer.parseInt(str);
if(n==1)
res=0;
else if(n==2)
res=1;
else if(n==3)
res=2;
else if(n==4)
res=2;
else{
if(n%2==0)
{
res=2;
}
else {
res=3;
}
}
}
else{
int len=str.length();
char c=str.charAt(len-1);
if(c=='2'||c=='0'||c=='4'||c=='6'||c=='8'){
res=2;
}
else{
res=3;
}
}
System.out.println(res);
}
}
} 题目2： 在长度为n的数组上进行查找连续长度为k的区间内和的最大值，最后返回最大值区间的中间位置下标 输入：10 3 5 5 5 10 10 10 5 10 10 10 代表n=10 k=3,后面是输入的n个数 输出：5 代表下标为4 5 6 三个元素的和最大为30（注意题目要求若符合区域有多个，取较前的），中间下标=5
因为时间问题，采用暴力搜索的策略
public class NOtwo {
public static void main(String[] args) {
int n,k;
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
k=cin.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<n;i++){
list.add(cin.nextInt());
}
int maxsum=0;
int index=0;
for(int i=0;i+k<=n;i++){
int sum=0;
int j;
for(j=0;j<k;j++){
sum+=list.get(i+j);
}
if(sum>maxsum)
{
index=i+(j/2)+1;
maxsum=sum;
}
}
System.out.println(index);
}
}
最后过了78%，请大佬指教……
全部评论
(1) 回帖