题目：
将杨辉三角的数按从上到下、从左到右的顺序排成一列。给定一个正整数N，请输出数列中第一次出现N是在第几个数？
对20%的测试用例，1<=N<=10；对所有的测试用例，1<=N<=1000000000
思路1：(该思路适合N较小的时候，如1<=N<=10)
用二维数组构造杨辉三角，停止构造条件是当
arr[i][j]==N
相应题解如下：（是参照基础题 “类型4：二维数组”的代码改过来的）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int N=s.nextInt()+1;// 最多 构建一个长度为N的二维数组，下标为N-1
int [][] arr=new int [N][N];
arr[0][1]=0;
for (int i = 0; i 不出所料，只拿了二十分。因为剩下的测试样例的N 太大，生成二维数组时内存超限了。。
思路2：参照CSDN上一位c++大佬的解法，做了一点笔记，并且自己用java写了一遍
大佬的文章链接如下：
https://blog.csdn.net/njuptACMcxk/article/details/116426985
思路：找规律（只看下半部分）
行列 0 1 2 3 01 111 2121 31331 41464 5151010 6161520 ……………
规律：设行下标为i，列下标为j
对应的数字为
C
i
j
C_{i}^{j}
Cij
矩阵的每一行和每一列，都是递增的，而对角线上的数，恰是矩阵中每一列的首个数字，对称轴上的数可表示为
C
2
j
j
C_{2j}^{j}
C2jj
当j>16时，
C
2
j
j
C_{2j}^{j}
C2jj>10^9。所以可以将循环范围缩减至16“递增”——>已排序，便于查找——>二分法查找第j列上>=N的数——>从大到小找效率更高（N可以很大）找到了数，它是第几个数？——>个数求和。
如目标数字在第i行，第j列，前i-1行的数有
i
(
i
+
1
)
2
frac{i(i+1)}{2}
2i(i+1)
个，j从0起算，所以总数要在这个基础上加j+1,结果为
i
(
i
+
1
)
2
+
j
+
1
frac{i(i+1)}{2}+j+1
2i(i+1)+j+1
题解：
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static long N;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
N = s.nextInt();
for (int i = 16; ; i--) {
if(hasFind(i)) break;
}
}
public static boolean hasFind(int j) {
long l = 2 * j, r = Math.max(l, N);
//二分法
while (l < r) {
long mid = l + r >> 1;//右移一位，相当于除以2取整
if (C(mid, j) >= N) r = mid;
else l = mid + 1;
}
if (C(r, j) != N) return false;
else System.out.println(r * (r + 1) / 2 + j + 1);
return true;
}
public static long C(long a, long b) {//求解Cmn
long c = 1;
for (long i = a, j = 1; j <= b; i--, j++) {
c = c * i / j;
if (c > N) return c;
}
return c;
}
}
心得体悟：程序员学好数据结构与算法真的是很必要的；掌握多种解决方法也是很必要的。因为数据量小的时候怎么舒服怎么来，但是数据量一大就是考验功底的时候了。暴力只能解决极小部分问题。
时间显示
这题的原型可归为：类型10：打印输出找规律 中的类题1
package pra;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n=s.nextInt();
System.out.print((n/60-n/60%60)/60);//h
System.out.print(":");
System.out.print(n/60%60);//m
System.out.print(":");
System.out.print(n%60);//s
}
}
那题的题解如上。
注意这题有两处不同，一是数据范围。 二是输出格式：有前置0。
解题过程：（注：过程嘛，说明前几步都是错的，赶时间的小伙伴建议直接下拉至最后一步）
在这题扩大了数据范围的情况下，我发现我之前的代码通用性不强，初步猜测是只适用于24 * 60 *60 的评测数据，因为在仅仅把数据类型由int换为long之后，我发现输入46800999，输出为13000:16:39，但答案是13:00:00……。
后面我在输出之前加了一行语句，希望把时间减到一天之内
n%=(24*60*60);
但发现还是不对劲。输入46800999，输出了16:16:39。
于是我又看了看题目，发现自己漏了一个关键信息**:给定的输入是毫秒**。（认真读题！不能心急！）
这就简单了，在上面那条语句之前再加上一句：
n/=1000;
另外，对于时的计算，其实还有更简便的写法：
n/3600
写基础题的时候没想起来，写了长长的一串……
最终通过评测的代码如下：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
long n=s.nextLong();
n/=1000;
n%=(24*60*60);
System.out.printf("%02d",n/3600);//h
System.out.print(":");
System.out.printf("%02d",n/60%60);//m
System.out.print(":");
System.out.printf("%02d",n%60);//s
}
}
双向排序
题目：
题解：不用测都知道以下写法最多只能过60%的测试样例，因为new Integer[len]里的len数据类型只能是int，不能是long；对数组进行切割排序的时候也有这个问题。输入数据最大可达10万，直接溢出。
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int len = s.nextInt();//序列长度
Integer[] arr = new Integer[len];
for (int i = 0; i < len; i++) {
arr[i] = i + 1;
}
long count = s.nextInt();//操作次数
for (long i = 1; i <= count; i++) {
int flag = s.nextInt();//0 对0到edge-1号元素降序;1 对edge到len-1号元素升序
int edge = s.nextInt();//
if (flag == 0) {
Integer[] tmp = new Integer[edge];
System.arraycopy(arr, 0, tmp, 0, edge);
Arrays.sort(tmp, Collections.reverseOrder());
System.arraycopy(tmp, 0, arr, 0, edge);
}
if (flag == 1) {
//Arrays.sort(arr);
Integer[] tmp = new Integer[len - edge + 1];
System.arraycopy(arr, edge - 1, tmp, 0, len - edge + 1);
Arrays.sort(tmp);
System.arraycopy(tmp, 0, arr, edge - 1, len - edge + 1);
}
}
for (int i = 0; i < len; i++) {
System.out.print(arr[i] + " ");
}
}
}
害，在网上找到了很多c++的题解，思路看懂了一些，之后有机会再补充？感觉有些数据结构没法和java的对应上，我也不知道能用什么代替……我承认我这算法学习还停留在了浅层阶段，被具体语言限制……
特别数的和
题目：小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到
40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。请问，在 1 到 n 中，所有这样的数的和是多少？
题解：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
String n=s.next();
int N=Integer.valueOf(n);
int sum=0;
for (int i = 0; i <=N ; i++) {
String tmp=String.valueOf(i);
for (int j = 0; j < tmp.length(); j++) {
if((tmp.charAt(j)=='2'||tmp.charAt(j)=='9'||tmp.charAt(j)=='1'||tmp.charAt(j)=='0')&&(tmp.charAt(0)!='0')){
sum+=i;
break;
}
}
}
System.out.println(sum);
}
}
其实这里面以字符串形式读入再转换成整数是画蛇添足了。不过一开始这样转换还因为我在循环里面也在用这个n，结果输出结果不对劲。现在保留这段多余代码也算是给自己提个醒
。
等差数列
题目：
问题描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A₁, A₂, · · · , AN。(注意 A₁ ∼ AN 并不一定是按等差数列中的顺序给出)
题解：
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int N=s.nextInt();
ArrayList arr=new ArrayList<>();
for (int i = 0; i < N; i++) {
arr.add(s.nextInt());
}
Collections.sort(arr);
int odd=arr.get(1)-arr.get(0);
for (int i = 1; i < N-1; i++) {
if((arr.get(i+1)-arr.get(i))<=odd){
odd=arr.get(i+1)-arr.get(i);
}
}
int max=arr.get(N-1);int min=arr.get(0);
//special situation
if(odd==0) System.out.println(N);
else System.out.println((max-min)/odd+1);
}
}
注意：
N才十万，不是很大，存进数组然后暴力循环遍历就能通过全部测试样例
给定数据不按顺序，要排序
用等差数列的公式：
a
n
=
a
1
+
(
n
−
1
)
d
an=a1+(n-1)d
an=a1+(n−1)d
差为0的很特殊，另外输出
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）