测试次数
快速排序
递增三元组
螺旋折线
日志统计
全球变暖
明码
乘积尾零
砝码称重
杨辉三角
路径
时间显示
直线
货物摆放
空间
卡片
回文日期
子串分值和
七段码
成绩统计
蛇型数组
跑步锻炼
门牌制作
既约分数
最大的公共子串
方格分割
承压计算
后缀表达式
包子凑数
日期问题
等差数列
完全二叉树的权值
分巧克力
等差素数列
特别数的和
迷宫
数列求值
数的分解
七夕礼物
组队
年号字串
-
测试次数
x星球上的居民脾气不好，但幸运的是，他们生气时唯一的异常行为就是摔倒手机。
各大厂商纷纷推出各种防摔手机。x星球质监局规定，手机在允许上市流通之前，必须经过抗跌试验，并对抗跌指数进行评估。x星球上有许多高耸入云的高塔，可用于抗坠落试验。塔的每一层高度都是一样的，与地球略有不同的是，它们的第一层不是地面，而是相当于我们的二楼。如果手机从第七层扔下来没有坏，但是第八层坏了，那么手机的指数就会坏。=7。特别是如果手机从第一层掉下来就坏了，那么耐摔指数=0。如果塔的最高层N层没有损坏，则耐跌指数=n，从各厂家抽样3部手机参加测试，以减少测试次数。
一次测试的塔高为1000层。如果我们总是采取最好的策略，在最坏的运气下，我们需要测试多少次才能确定手机的抗坠落指数？
分析：
- 把M层楼 /N手机的问题转化为函数F(M,N)，其中楼层数M和手机数N函数的两个参数，函数的值是最优解的最大尝试次数
-
第一部手机第一部位置在第一部X(1≤X≤M)层，会有两种情况，第一部手机没有坏，所以剩下的M?X层楼，剩余N手机可以转换为函数：F(M?X,N) 1,1≤X≤M，第一部手机坏了，只剩下1层到X?1层楼需要尝试，剩余的手机数量是N?可转化为函数：F(X?1,N?1) 1,1≤X≤M
public class Main { static int getMinSteps(int num, int floorNum) { if (num < 1 || floorNum < 1) return 0; // 存储num个手机，floorNum层层条件下的最优化尝试次数 int[][] cache = new int[num 1][floorNum 1]; // 每个元素最初化为最大的尝试次数，即只有一部手机 for (int i =1; i <= num; i++)
for (int j = 1; j <= floorNum; j++)
cache[i][j] = j;
for (int n = 2; n <= num; n++)
for (int m = 1; m <= floorNum; m++)
for (int k = 1; k < m; k++)
// 扔手机的楼层从1到m枚举一遍，如果当前算出的尝试次数小于上一次算出的尝试次数，则取代上一次的尝试次数。
cache[n][m] = Math.min(cache[n][m], 1 + Math.max(cache[n - 1][k - 1], cache[n][m - k]));
return cache[num][floorNum];
}
public static void main(String[] args) {
System.out.println(getMinSteps(3, 1000));
}
}-
快速排序
用递归来实现快速排序（quick sort）算法。快速排序算法的基本思路是：假设要对一个数组a进行排序，且a[0] = x。首先对数组中的元素进行调整，使x放在正确的位置上。同时，所有比x小的数都位于它的左边，所有比x大的数都位于它的右边。然后对于左、右两段区域，递归地调用快速排序算法来进行排序。 输入只有一行，包括若干个整数（不超过10个），以0结尾。 输出只有一行，即排序以后的结果（不包括末尾的0）。 5 2 6 1 7 3 4 0 1 2 3 4 5 6 7
分析：
1．先从数列中取出一个数作为基准数。
2．分区过程，
3．再对左右区间重复第二步，直到各区间只有一个数。
import java.util.Scanner;
import java.util.Random;
public class Main{
public static int quickSelect(int a[], int l, int r, int k) {
Random rand = new Random();
int p = rand.nextInt(r - l + 1) + l;
int x = a[p];
int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
int i = l, j = r;
while(i < j) {
while(i < j && a[i] < x) i++;//小于基准值，往左放
if(i < j) {
a[j] = a[i];
j--;
}
while(i < j && a[j] > x) j--;
if(i < j) {
a[i] = a[j];
i++;
}
}
a[i] = x;
p = i;
if(i - l + 1 == k) return a[i];
if(i - l + 1 < k) return quickSelect(a,i+1,r,k-i+l-1); //将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
else return quickSelect(a, l, i - 1, k);
}
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int a[]=new int[110];
for(int i=0;i<n;i++)
{
a[i]=scan.nextInt();
}
System.out.println(quickSelect(a, 0, n-1, 5));
}
}
-
递增三元组
给定三个整数数组 A = [A1, A2, ... AN], B = [B1, B2, ... BN], C = [C1, C2, ... CN]， 请你统计有多少个三元组(i, j, k) 满足：
- 1 <= i, j, k <= N
- Ai < Bj < Ck
第一行包含一个整数N。 第二行包含N个整数A1, A2, ... AN。 第三行包含N个整数B1, B2, ... BN。 第四行包含N个整数C1, C2, ... CN。
对于30%的数据，1 <= N <= 100 对于60%的数据，1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
一个整数表示答案
3 1 1 1 2 2 2 3 3 3
【输出样例】 27
分析：暴力破解即可
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int count = 0;
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int arr1[] = new int[N];
int arr2[] = new int[N];
int arr3[] = new int[N];
for (int i = 0; i < N; i++) {
arr1[i]= sc.nextInt();
}
for (int i = 0; i < N; i++) {
arr2[i]= sc.nextInt();
}
for (int i = 0; i < N; i++) {
arr3[i]= sc.nextInt();
}
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
for (int k = 0; k < arr3.length; k++) {
if (arr1[i] < arr2[j] && arr2[j] < arr3[k]) {
count++;
}
}
}
}
sc.close();
System.out.println(count);
}
}
-
螺旋折线
如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？
X和Y
对于40%的数据，-1000 <= X, Y <= 1000 对于70%的数据，-100000 <= X， Y <= 100000 对于100%的数据, -1000000000 <= X, Y <= 1000000000
输出dis(X, Y)
0 1
3
分析：
- 由图可得，主要分析各个象限的拐点即可
第一象限的拐点坐标——dx = max(abs(x), abs(y))，dy = dx 第二象限的拐点坐标——dx = -max(abs(x), abs(y))，dy = -dx 第三象限的拐点坐标——dx = -max(abs(x), abs(y))，dy = dx - 1 第四象限的拐点坐标——dx = max(abs(x), abs(y))，dy = -dx
- 由图可得，距离与拐点的关系
第一象限(abs(dx)+abs(dy))^2 第二象限(abs(dx)+abs(dy)) * (abs(dx)+abs(dy) - 1) 第三象限(abs(dx)+abs(dy))^2 第四象限(abs(dx)+abs(dy)) * (abs(dx)+abs(dy) + 1)
import java.util.Scanner;
public class Main {
static int x, y;
static int df = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
x = in.nextInt();
y = in.nextInt();
if (x > 0 && y >= 0) {//第一象限
int dx = Math.max(x, y);
int dy = dx;//拐点坐标
df = (dx + dy) * (dx + dy);//拐点
if (x < dx) {
df -= (dx - x);
}
if (y < dy) {
df += (dy - y);
}
} else if (x >= 0 && y < 0) {
int dx = Math.max(Math.abs(x), Math.abs(y));
int dy = -dx;
df = (dx + Math.abs(dy)) * (dx + Math.abs(dy) + 1);
if (x < dx) {
df += (dx - x);
}
if (y > dy) {
df -= (y - dy);
}
} else if (x < 0 && y <= 0) {
int dx = -Math.max(Math.abs(x), Math.abs(y));
int dy = dx + 1;
df = (Math.abs(dx) + Math.abs(dy)) * (Math.abs(dx) + Math.abs(dy));
if (x > dx) {
df -= (x - dx);
}
if (y > dy) {
df += (y - dy);
}
} else if (x <= 0 && y > 0) {
int dx = -Math.max(Math.abs(x), Math.abs(y));
int dy = -dx;
df = (Math.abs(dx) + Math.abs(dy)) * (Math.abs(dx) + Math.abs(dy) - 1);
if (x > dx) {
df += (x - dx);
}
if (y < dy) {
df -= (y - dy);
}
}
System.out.println(df);
}
}-
日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
ts id
表示在ts时刻编号id的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
第一行包含三个整数N、D和K。 以下N行每行一条日志，包含两个整数ts和id。
对于50%的数据，1 <= K <= N <= 1000 对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
按从小到大的顺序输出热帖id。每个id一行。
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
1
3
解析：主要采用
1.[ T ,T+D )是一个“窗口”，随着时间T的增长，窗口不断往后滑动，符合尺取法的通向扫描
2.尺取法的思路：按时间从小到大处理每一个帖子，当处理到T时刻的帖子时，窗口[T-D,T）之前的帖子已经失效了，对当前窗口的统计没有效果
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
int n, d, k;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
d = sc.nextInt();
k = sc.nextInt();
resou arr[] = new resou[n];
for (int i = 0; i < n; i++) {
int time = sc.nextInt();
int id = sc.nextInt();
arr[i] = new resou(time, id);
}
Arrays.sort(arr); // 对其进行排序
int ID = arr[0].id;
boolean flag =false;
for (int i = 0; i < n; i++) {
if (i + k - 1 < n && arr[i + k - 1].id == ID && arr[i + k - 1].ts - arr[i].ts < d && !flag )
{
System.out.println(ID);
flag = true;
} else if (arr[i].id != ID)
{
ID = arr[i].id;
flag = false;
i = i - 1;
}
}
}
}
class resou implements Comparable<resou> //创建resou类，继承Comparable排序类
{
int ts, id;
resou(int ts, int id)
{
this.ts = ts;
this.id = id;
}
@Override
public int compareTo(resou com) {//自定义对象同样需要继承Comparable接口，并重写compareTo方法
if (id == com.id) // 先对id做比较其次id相同对ts做比较
return ts - com.ts;
else
return id - com.id;
}
}
-
全球变暖
你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。 由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
一个整数表示答案。
1
分析：
- 用dfs找出总共的岛屿数目，对于dfs方法中，首先需判断i,j是否超出矩阵边界，避免下标越界情况出现。之后将该字符处的访问标志为置1表示已访问过，然后依次判断该字符上右下左四个方向是否存在陆地且未曾访问过，如果存在则把找到的符合条件的字符作为当前字符，继续深搜，这样属于同一个岛屿的陆地访问标志都变成了1，且岛屿数只加过1次。
- 用两个for循环淹没岛屿（四面一面邻海就要被淹没） ，利用一个数组来表示淹没还是陆地
- 再用dfs找出淹没后还有多少个岛屿，前后相减就是被淹没的岛屿数
import java.util.Scanner;
public class Main {
static int n;
static int[][] dfs_vis;
static int dir[][] = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
dfs_vis = new int[n][n];
char[][] map = new char[n][n];
for (int i = 0; i < n; i++) {
String s = sc.nextLine();
map[i] = s.toCharArray();
}
//找岛屿
int start = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '#' && dfs_vis[i][j] == 0) {
dfs_vis[i][j] = 1;
dfs(i, j, map);
start++;
}
}
}
//淹没
int vis[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '#') {
vis[i][j] = 1;
for (int k = 0; k < 4; k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
if (check(nx, ny, n) && map[nx][ny] == '.' && vis[nx][ny] == 0) {
//vis[nx][ny] = 1;
map[i][j] = '.';
break;
}
}
}
}
}
//找淹没后剩余的岛屿
dfs_vis = new int[n][n];
int end = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '#' && dfs_vis[i][j] == 0) {
dfs_vis[i][j] = 1;
dfs(i, j, map);
end++;
}
}
}
System.out.println(start);
System.out.println(end);
System.out.println(start - end);
}
private static void dfs(int i, int j, char[][] map) {
for (int k = 0; k < 4; k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
if (check(nx, ny, map.length) && map[nx][ny] == '#' && dfs_vis[nx][ny] == 0) {
dfs_vis[nx][ny] = 1;
dfs(nx, ny, map);
}
}
}
private static boolean check(int nx, int ny, int n) {
return nx >= 0 && nx < n && ny >= 0 && ny < n;
}
}-
明码
汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节，一共16行，布局是： 第1字节，第2字节 第3字节，第4字节 .... 第31字节, 第32字节 这道题目是给你一段多个汉字组成的信息，每个汉字用32个字节表示，这里给出了字节作为有符号整数的值。题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形，从中看出题目的要求，并根据要求填写答案。 这段信息是（一共10个汉字）：
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16 4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0 0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4 4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64 16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128 0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0 2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0 1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0 0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0
思路：
- 每两个为一组，十进制转化为2进制
toBinaryString(int i)- 负数用补码表示
- str＝str.substring(int beginIndex);截取掉str从首字母起长度为beginIndex的字符串，将剩余字符串赋值给str；
public class Main {
public static void main(String[] args) {
int array[] = new int[] {4, 0, 4, 0 ,4 ,0 ,4, 32, -1, -16, 4, 32, 4, 32, 4,
32, 4, 32, 4, 32, 8, 32, 8, 32, 16, 34, 16, 34, 32, 30, -64, 0,
16, 64, 16, 64, 34 ,68 ,127, 126 ,66 ,-124, 67, 4, 66, 4 ,66 ,-124,
126 ,100 ,66 ,36, 66, 4, 66, 4, 66, 4, 126, 4, 66, 40, 0 ,16,4,0,4,
0,4,0,4,32,-1,-16,4,32,4,32,4,32,4,32,4,32,8,32,8,32,16,34,16,34,32,
30,-64,0,0,-128,64,-128,48,-128,17,8,1,-4,2,8,8,80,16,64,32,64,-32,
64,32,-96,32,-96,33,16,34,8,36,14,40,4,4,0,3,0,1,0,0,4,-1,-2,4,0,4,
16,7,-8,4,16,4,16,4,16,8,16,8,16,16,16,32,-96,64,64,16,64,20,72,62,
-4,73,32,5,16,1,0,63,-8,1,0,-1,-2,0,64,0,80,63,-8,8,64,4,64,1,64,0,
-128,0,16,63,-8,1,0,1,0,1,0,1,4,-1,-2,1,0,1,0,1,0,1,0,1,0,1,0,1,0,5,
0,2,0,2,0,2,0,7,-16,8,32,24,64,37,-128,2,-128,12,-128,113,-4,2,8,12,
16,18,32,33,-64,1,0,14,0,112,0,1,0,1,0,1,0,9,32,9,16,17,12,17,4,33,
16,65,16,1,32,1,64,0,-128,1,0,2,0,12,0,112,0,0,0,0,0,7,-16,24,24,48,
12,56,12,0,56,0,-32,0,-64,0,-128,0,0,0,0,1,-128,3,-64,1,-128,0,0 };
for(int i=0; i < array.length; i++) {
if(array[i] < 0) {
String bin1 = Integer.toBinaryString(array[i]).replace("0", " ");
String bin2 = bin1.substring(24).replace("0", " ");
if(i % 2 != 0) {//两个字节为一组
System.out.println(bin2);
}else {
System.out.print(bin2);
}
}else {
String bin3 = Integer.toBinaryString(array[i]).replace("0", " ");
String ary[] = new String[] {" "," "," "," "," "," "," ",""};
if(i % 2 != 0) {
System.out.println(ary[bin3.length()-1]+bin3);
}else {
System.out.print(ary[bin3.length()-1]+bin3);
}
}
}
}
}-
乘积尾零
如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？ 5650 4542 3554 473 946 4114 3871 9073 90 4329 2758 7949 6113 5659 5245 7432 3051 4434 6704 3594 9937 1173 6866 3397 4759 7557 3070 2287 1453 9899 1486 5722 3135 1170 4014 5510 5120 729 2880 9019 2049 698 4582 4346 4427 646 9742 7340 1230 7683 5693 7015 6887 7381 4172 4341 2909 2027 7355 5649 6701 6645 1671 5978 2704 9926 295 3125 3878 6785 2066 4247 4800 1578 6652 4616 1113 6205 3264 2915 3966 5291 2904 1285 2193 1428 2265 8730 9436 7074 689 5510 8243 6114 337 4096 8199 7313 3685 211 注意：需要提交的是一个整数，表示末尾零的个数。不要填写任何多余内容。
分析：
暴力破解，
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num [] = new int [100];
int cnt = 0;
for (int i = 0; i < 100; i++) {
num[i] = sc.nextInt();
}
for (int i = 1; i < num.length; i++) {
num[i] *= num[i-1];
while(num[i] % 10 == 0)
{
cnt++;
num[i] /= 10;
}
num[i] %= 1000;//为防止越界，每次保留后三位，只有为0时，才会出现
}
System.out.println(cnt);
}
}-
砝码称重
分析:
例如：我们输入3个砝码，分别是1,4,6
当输入第一个砝码(1)时，可以称出重量为：1
再输入第二个砝码(4)时，可以称出的重量为：1,(4 - 1),(4 + 1),4
当前可以称出的重量有：1,3,4,5
再输入第三个砝码(6)时，可以称出的重量为：1,3,4,5,(6 - 1),(6 + 1),(6 - 3),(6 + 3),(6 - 4),(6 + 4),(6 - 5),(6 + 5),6
当前可以称出的重量有：1,2,3,4,5,6,7,9,10,11
import java.util.Scanner;
public class Main1{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[n][n];
for(int i=0;i<n;i++){//每一行第一个均为1
nums[i][0] = 1;
}
nums[1][1] = 1;//第二行也是一
if(n>2){
for(int i=2;i<n;i++){
for(int j=1;j<=i;j++){
nums[i][j] = nums[i-1][j]+nums[i-1][j-1];//每个数字都是上面两个数字的和
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
System.out.print(nums[i][j]+" ");
}
System.out.println();
}
}
}
方法二:
import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[n][n];
for(int i=0;i<n;i++){
Long number = (long) 1;
for(int j=0;j<=i;j++){
System.out.print(number+" ");
// number = number*(i-j)/(j+1)是重点
//数据过大可能溢出，用Long型
number = (Long)number * (i-j)/(j+1);
}
System.out.println();
}
}
}-
路径
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。 小蓝的图由 2021 个结点组成，依次编号 1 至 2021。对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
思路：
- 使用邻接矩阵将图存储
- 最小公倍数—>最大公约数—>辗转相除法
-
弗洛伊德算法
public class Main {
public static void main(String[] args) {
int len = 2021;
int maxValue=1000000000;
int[][] matrix = new int[len][len];
for (int i = 0; i < len; i++) {//构造邻接矩阵
for (int j = i + 1; j < len; j++) {
if (j <= 21 + i) {
matrix[i][j] = lcm(j + 1, i + 1);
matrix[j][i]=lcm(j + 1, i + 1);
}else{
matrix[i][j]=maxValue;
matrix[j][i]=maxValue;
}
}
}
floyd(matrix);
System.out.println(matrix[1-1][len-1]);
}
public static void floyd(int[][] dis){
int length;
for (int k = 0; k <dis.length ; k++) {
for (int i = 0; i < dis.length; i++) {
for (int j = 0; j < dis.length; j++) {
length=dis[i][k]+dis[k][j];
if(length < dis[i][j]){
dis[i][j]=length;//更新路径
}
}
}
}
}
//最大公约数
public static int gcd(int m, int n) {
return n == 0 ? m : gcd(n, m % n);
}
//最小公倍数
public static int lcm(int m, int n) {
return m * n / gcd(m, n);
}
}-
时间显示
小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970年 11 月 11 日 00:00:00 到当前时刻经过的毫秒数。现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
分析:
-
时=n/1000/60/60%24
-
分=n/1000/60%60
-
秒=n/1000%60
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long time = scanner.nextLong();
//获取时分秒
long hours = time / 1000 / 60 / 60 % 24;
long minutes = time / 1000 / 60 % 60;
long seconds = time / 1000 % 60;
//按照输出格式完成输出
if(hours < 10) {
System.out.print("0" + hours + ":");
}else {
System.out.print(hours + ":");
}
if(minutes < 10) {
System.out.print("0" + minutes + ":");
}else {
System.out.print(minutes + ":");
}
if(seconds < 10) {
System.out.print("0" + seconds);
}else {
System.out.print(seconds);
}
}
}
-
直线
在平面直角坐标系中，两点可以确定一条直线。给定平面上 20 × 21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横坐标是 0到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之 间的整数的点。 请问这些点一共确定了多少条不同的直线?
- 斜率不存在的直线要另外考虑
- 将直线存入集合中，重复数据只保留一个
- k和b可能是小数，而小数在计算机中是有精度的，直接存小数，哪怕用double型也可能不准确。所以我们用分数存储k和b,且要用最简分数表示，否则不好比较是否相同
- 把坐标存入容器ArrayList中，形式是x*100+y（一个int型的数据）这个数对除以100就是横坐标，对100取余就是纵坐标。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class Main {
public static void main(String[] args) {
HashSet<String> kb=new HashSet<String>();//存放截距与斜率
int x=0;//横坐标
int y=0;//纵坐标
//把坐标以x*100+y的形式存入ArrayList
HashSet<Integer> al=new HashSet<>();
for(x=0;x<20;x++){
for(y=0;y<21;y++){
al.add(x*100+y);
}
}
List<Integer> arr = new ArrayList<>(al);
//用i遍历形成的每一条直线，利用点斜式唯一标识一条直线
for(int i=0;i<x*y;i++){
int x1=arr.get(i)/100;//点一横坐标
int y1=arr.get(i)%100;//点一纵坐标
for(int j=i+1;j<x*y;j++){
int x2=arr.get(j)/100;//点二横坐标
int y2=arr.get(j)%100;//点二纵坐标
/*计算斜率（用分数（kup/kdown）表示）*/
int kup=y1-y2;
int kdown=x1-x2;
if(kdown==0){
//kdown=0说明斜率不存在
String s="y="+x1;
kb.add(s);
}else{
int kgcd=gcd(kup,kdown);//分子分母最大公约数
kup=kup/kgcd;
kdown=kdown/kgcd;//得到最简分数
//计算截距（用分数（bup/bdown）表示）
int bup=y1*kdown-kup*x1;
int bdown=kdown;
int bgcd=gcd(bup,bdown);//分子分母最大公约数
bup=bup/bgcd;
bdown=bdown/bgcd;//得到最简分数
//以kup+" "+Kdown+" "+bup+" "+bdown的形式存储一条直线
String s=kup+" "+kdown+" "+bup+" "+bdown;
kb.add(s);
}
}
}
//kb中的元素是不重复的，有重复也只会存储其中一个，因此kb的大小就是直线的个数
System.out.println(kb.size());
}
//辗转相除求最大公约数
static int gcd(int a, int b) {
if(b==0){
return a;
}
return gcd(b,a%b);
}
}
-
货物摆放
小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有 n箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n =L×W×H。给定 n，请问有多少种堆放货物的方案满足要求。
例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
请问，当 n=2021041820210418 （注意有 16 位数字）时，总共有多少种方案？
分析：
- a、b、c均为n的因数，只需找出n的所有因数，进行枚举
- 特别注意n为长整型
- 存入集合去重
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
long n = 2021041820210418l;
long t = n;
Set<Long> set = new HashSet<>();
for (long i = 1;i <= t;i++){
if (n%i==0){//表示i是n的因数
t = n / i;//t*i=n 依据这个每次缩小遍历的上限，减少时间
set.add(i);
set.add(t);
}
}
ArrayList<Long> list = new ArrayList<>(set);
//利用列表枚举集合中的元素
int cnt = 0;
for (int i = 0;i<list.size();i++){
long a = list.get(i);
for (int j = 0;j< list.size();j++){
long b = list.get(j);
if (a*b>n) continue;//若大于，则不需要第三个，此处可以减少第三重的遍历
for (int k =0;k< list.size();k++){
long c = list.get(k);
if (a*b*c==n) cnt++;
}
}
}
System.out.println(cnt);
}
}-
空间
【问题描述】
小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？
分析：
-
卡片
【问题描述】 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝有很多数字卡片，每张卡片上都是数字0到9。小蓝准备用这些卡片来拼一些数，他想从1开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从1拼到多少。例如，当小蓝有30张卡片，其中0到9各3张，则小蓝可以拼出1到10,但是拼11时卡片1已经只有一张了，不够拼出11。现在小蓝手里有0到9的卡片各2021张，共2021张，请问小蓝可以从1拼到多少?
解析：
- 用长度为10的数组，来模拟数值为0～9的卡片，每一张都有2021张
- 暴力遍历
- 利用取模，取出每一位数字进行判断
public class Main {
public static void main(String[] args) {
int []num = new int[10];
for (int k = 0;k < 10;k++){//表示卡片的数量
num[k] = 2021;
}
int t;
int m;
int flag = 0;
int i;
for (i = 1;;i++){
t = i;
while (t > 0){//取位数
m = t % 10;
if (num[m]==0){
flag = 1;//卡片数量为0
break;
}
num[m]--;
t/=10;
}
if (flag == 1) break;
}
System.out.println(i-1);
}
}-
回文日期
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。
输入包含一个八位整数 NN，表示日期。
对于所有评测用例，10000101 \leq N \leq 8999123110000101≤N≤89991231，保证 NN 是一个合法日期的 8 位数表示。
输出两个日期类型的回文数ABCDDCBA和ABABBABA
分析：主要思路
- 判断日期的合法性（年、月、日）
- 将数字变换成字符串进行回文数比较
substring() 方法返回字符串的子字符串。
parseInt() 解析一个字符串并返回一个整数import java.util.Scanner;
public class Main {
public static String str="";
public static boolean isLeap(int year){//判断闰年，用于日期校验
return (year%4==0&&year%100!=0)||year%400==0;
}
public static boolean check(int a,int b,int c){
//月份效验
if(b<1||b>12) return false;
if(c<1||c>31) return false;
//日效验
switch (b){//日期校验
case 2:if(isLeap(a)&&c>29) return false;
if(!isLeap(a)&&c>28) return false;
break;
case 4:
case 6:
case 9:
case 11:
if(c>30) return false;
break;
default:
break;
}
if(str.charAt(0)==str.charAt(2)//将数字化为字符串进行回文数判断
&&str.charAt(2)==str.charAt(5)
&&str.charAt(5)==str.charAt(7)&&
str.charAt(1)==str.charAt(3)
&&str.charAt(3)==str.charAt(4)&&
str.charAt(4)==str.charAt(6))
{
return true;
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int cur = scanner.nextInt();
int sum=0;
for (int i = cur; i <= 89991231; i++) {
str="";
str+=i;
if(check(Integer.parseInt(str.substring(0,4)),//将某个字符串返回的整数传入检查函数进行判断回文数
Integer.parseInt(str.substring(4,6)),
Integer.parseInt(str.substring(6,8)))){
sum++;
System.out.println(i);
if(sum==2){//找到两个即停止
break;
}
}
}
}
}
-
子串分值和
【问题描述】 对于一个字符串 S，我们定义 S 的分值 f(S) 为 S 中出现的不同的字符个 数。例如 f(”aba”) = 2，f(”abc”) = 3, f(”aaa”) = 1。 现在给定一个字符串 S[0…n−1]（长度为 n），请你计算对于所有 S 的非空 子串 S[i…j](0≤i≤ j < n)，f(S[i…j]) 的和是多少。
【输入格式】 输入一行包含一个由小写字母组成的字符串 S。
【输出格式】 输出一个整数表示答案。
【样例输入】 ababc
【样例输出】 28
思路:
- 求出所有非空子串
- 对于每一个非空子串，求出不同字符的个数
- 求和
HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
HashSet 允许有 null 值。
HashSet 是无序的，即不会记录插入的顺序。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
Set<Character> set = new HashSet<>();
int sum=0;
for (int i = 0; i < str.length(); i++) {
for (int j = 0; j < str.length() - i; j++) {//非空子串的最大长度为原子串的长度
set.clear();
for (int k = i; k <= i + j; k++) {
set.add(str.charAt(k));//依次取字符串，加入到集合中
}
sum+=set.size();
}
}
System.out.println(sum);
}
}-
七段码
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。 例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
思路：
把所有相邻并且发光的二极管
public class Main {
public static int N=10;
public static int e[][]=new int[N][N];//存储二极管相邻的信息
public static int f[]=new int[N];//并查集
public static int ans=0;//记录亮的路径数，为1时符合题目要求
public static boolean st[]=new boolean[N];//存储二极管的发光情况，true表示发光
public static void creat(){
e[1][2]=e[1][6]=1;//表示相邻
e[2][1]=e[2][7]=e[2][3]=1;
e[3][2]=e[3][7]=e[3][4]=1;
e[4][3]=e[4][5]=1;
e[5][7]=e[5][6]=e[5][4]=1;
e[6][5]=e[6][7]=e[6][1]=1;
e[7][2]=e[7][3]=e[7][5]=e[7][6]=1;
}
public static int find(int u){//找出某一条路径的根二极管
if(f[u]==u) return u;
f[u]=find(f[u]);
return f[u];
}
public static void dfs(int d){
if(d>7){//所有二极管都检查了一遍，终止条件
for(int i=1;i<=7;i++){//并查集初始化
f[i]=i;
}
for(int i=1;i<=7;i++){
for(int j=1;j<=7;j++){
if(e[i][j]==1&&st[i]==true&&st[j]==true){//把所有发光且相邻的二极管合并
int fx=find(i),fy=find(j);//找出二极管所在路径的根二极管
if(fx!=fy){
f[fx]=fy;//若两个二极管的根二极管不同，则合并形成一个集合
}
}
}
}
int k=0;//表示产生的集合的个数
for(int i=1;i<=7;i++){
if(st[i] &&f[i]==i)k++;//记录成功的路径数，即产生的集合的个数
}
if(k==1) ans++;//只产生一个集合，说明所有的发光二极管是连成一片的
return;
}
st[d]=true;
dfs(d+1);
st[d]=false;
dfs(d+1);
}
public static void main(String[] args) {
creat();
dfs(1);
System.out.println(ans);
}
}
-
成绩统计
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。
输入的第一行包含一个整数 n (1≤n≤104)n\ (1 \leq n \leq 10^4)n (1≤n≤104)，表示考试人数。
接下来 n行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。
good = (int)((jg / n) * 100 + 0.5);
nice = (int)((yx / n) * 100 + 0.5);public class Main {
public static void main(String[] args) {
double jg = 0,yx = 0;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int []stu = new int[n];
for (int i = 0;i < n;i++){
stu[i] = sc.nextInt();
if (stu[i] >= 60 && stu[i] <= 100){
jg++;
if (stu[i] >= 85) yx++;
}
}
int good = 0,nice = 0;
good = (int)((jg / n) * 100 + 0.5);
nice = (int)((yx / n) * 100 + 0.5);
System.out.println(good + "%");
System.out.println(nice + "%");
}
}
-
蛇型数组
分析：
public class Main {
public static void main(String[] args) {
int MAX = 100;
int [][] arr = new int[MAX][MAX];
arr[0][0] = 1;
arr[0][1] = 2;
arr[1][0] = 3;
int i = 1,j = 0;//从第一行第0列开始
int flag = 0;
while(i < MAX-1 & j < MAX-1){
if(i == 0){//到达第一行，下一个数在原数据的右侧
arr[0][j+1] = arr[0][j] + 1;
j++;//同时保证数据的列移动
flag = 1;
}
if(j == 0){//到达第一列，下一个数在原数据的下面
arr[i+1][0] = arr[i][0] + 1;
i++;同时保证数据的行移动
flag = 0;
}
if(flag == 0){//表示到达最左边，下一个数向右上方移动
arr[i-1][j+1] = arr[i][j] + 1;
i = i - 1;
j = j + 1;
}
if(flag == 1){//表示到达最上面，下一个数向左下方移动
arr[i+1][j-1] = arr[i][j] + 1;
i = i + 1;
j = j - 1;
}
}
for (i = 0;i < MAX;i++){
for(j = 0;j < MAX;j++){
System.out.print(arr[i][j] + "\t");
}
System.out.println();
}
}
}
-
跑步锻炼
题目描述 小蓝每天都锻炼身体。正常情况下，小蓝每天跑1千米。如果某天是周一或者月初（1日），为了激励自己，小蓝要跑2千米。如果同时是周一或月初，小蓝也是跑2千米。小蓝跑步已经坚持了很长时间，从2000年1月1日周六（含）到2020年10月1日周四（含）。请问这段时间小蓝总共跑步多少千米？
分析：
public class Main {
public static void main(String[] args) {
int day = 0;
int sum = 0;
for(int year = 2000;year < 2020;year++){
for(int month = 1;month <= 12;month++){
for(int k = 1; k <= day(year,month); k++){
int weekday = (day + 6) % 7;
if( k == 1 || weekday == 1) sum += 2;
else sum++;
day++;
}
}
}
for(int month = 1;month <10;month++){
for(int k = 1; k <= day(2020,month); k++){
int weekday = (day + 6) % 7;
if( k == 1 || weekday == 1) sum += 2;
else sum++;
day++;
}
}
System.out.println(sum+2);
}
public static boolean year(int year){
if(((year % 4 == 0)&&(year % 100 != 0))||(year % 400 ==0)) return true;
return false;
}
public static int day(int year,int month){
if(month == 1 || month == 3 ||month == 5 ||month == 7 ||month == 8 ||month == 10 ||month == 12)return 31;
if(month == 4 || month == 6 ||month == 9 ||month == 11)return 30;
if(year(year)) return 29;
if (!year(year)) return 28;
return 0;
}
public static boolean chu1(int day,int temp){
if((day - temp == 31) ||(day - temp == 30)||(day - temp == 28)||(day - temp == 29)) return true;
return false;
}
}
-
门牌制作
【问题描述】 小蓝要为一条街的住户制作门牌号。 这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。 小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字 符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7，即需要 1 个 字符 0，2 个字符 1，1 个字符 7。 请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？
分析：
public class Main {
public static void main(String[] args) {
int cnt = 0;
for(int i = 1;i <= 2020;i++){//遍历
int m = i;
while (m > 0){
if(m % 10 == 2){//取模
cnt++;
}
m/=10;
}
}
System.out.println(cnt);
}
}
-
既约分数
【问题描述】
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。例如，3/4 , 5/2 , 1/8 , 7/1都是既约分数。请问，有多少个既约分数，分子和分母都是1 到2020 之间的整数（包括1和2020）？
分析：
：以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
public class Main {
public static void main(String[] args) {
int cnt = 0;
for (int i = 1;i <= 2020;i++){
for (int j = 1;j <= 2020;j++){
if (gcd(i,j)==1) cnt++;
}
}
System.out.println(cnt);
}
public static int gcd(int i,int j){
if(i % j == 0) return j;//当余数为 0 时，取当前算式除数为最大公约数
return gcd(j, i % j);//当余数不为 0 时，取除数为下一个式子的被除数，取余数为下一个式子的除数
}
}-
最大公共子串
求两个串的所有子串中能够匹配上的最大长度是多少。 比如："abcdkkk" 和 "baabcdadabc"， 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
分析：
int[][] a = new int[c1.length+1][c2.length+1];//作为判断两个字符串数组是否匹配
//若对应位置匹配成功，则对应的二维矩阵值变化int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) {
a[i][j] = a[i-1][j-1]+1;
if(a[i][j] > max) max = a[i][j];
}
}
}
"abcdkkk"
"baabcdadabc"
A12=A01+1 A13=A02+1 ...
A21=A10+1 A24=A13+1 ...public class Main
{
static int f(String s1, String s2)
{
char[] c1 = s1.toCharArray();//将字符串转换为字符串数组
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length+1][c2.length+1];//作为判断两个字符串数组是否匹配
//若对应位置匹配成功，则对应的二维矩阵值变化
int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) {
a[i][j] = a[i-1][j-1]+1;
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
public static void main(String[] args){
int n = f("abcdkkk", "baabcdadabc");
System.out.println(n);
System.out.println(f("aaakkkabababa", "baabababcdadabc"));
System.out.println(f("abccbaacbcca", "ccccbbbbbaaaa"));
System.out.println(f("abcd", "xyz"));
System.out.println(f("ab", "ab"));
}
}-
方格分割