谨以此文巩固算法知识
本来只有六道题的，后来改成26道了，学业繁忙，暂时不写解析了，有时间会补充
题目一：九九乘法表
题目链接：OpenJudge – 001:九九乘法表
思路分析：
分析题目描述可知，共输出9行，每行的列由1至9递增，因此考虑双层嵌套循环
外层循环控制行数，内层循环控制列数
下面分析循环的控制条件
第一行有一列，第二行有二列，即行和列的关系为第n行有n列，即当外层循环到n的时候，内层循环要输出n次
所以只需外层循环从1循环到9，内层循环从1循环到当前外层循环的值即可，下面是代码实现
代码实现：
public class Main {
public static void main(String[] args){
for(int i=1;i<=9;i++){
for (int j=1;j<=i;j++){
System.out.printf(j+"*"+i+"="+j*i+"\t");
}
System.out.println(); //这里是因为行与行间有换行符
}
}
}题目二：斐波那契数列
题目链接：OpenJudge – 002:斐波那契数列
思路分析：
首先需要明确斐波那契数列的定义
如1,3,4,7,11
这种第1,2项为随机值，自第3项开始每项值为前两项之和的数列称为斐波那契数列
公式表示即为
题目给定的输入x,y,n分别为数列的第1,2项以及数列长度
要求的输出为以x第一项，y为第二项，总长度为n的数列
那么我们需要知道该数列的每一项的值
我们现在已知
即我们可以根据此公式求出该数列任一项的值
求法：
定义一个方法int fib(int x,int y,int n),该方法返回以x为第一项,y为第二项的数列的第n项的值
例如输入的n为5
那么有
而f(2)和f(1)的值是已知的，因此可以用递推的方法求出f(5),同理求出f(n),我们代码采用递归形式实现
int fib(int x,int y,int n){
if(n==1)
return x;
if(n==2)
return y;
return fib(x,y,n-1)+fib(x,y,n-2);
}现在我们可以求出该数列的任意一项，因此只需要从1循环至n，循环内调用fib方法即可输出该数列
代码实现：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int n = sc.nextInt();
for (int i = 1; i <= n; i++) {
System.out.print(new Main().fib(x,y,i) + " ");
}
}
public int fib(int x,int y,int n) {
if (n == 1)
return x;
if (n == 2)
return y;
return fib(x,y,n - 1) + fib(x,y,n - 2);
}
}题目三：约瑟夫环问题
题目链接：OpenJudge – 003:约瑟夫问题
思路分析：
下面是我的错误想法，相信也是很多人的想法，不过误打误撞推导出了正确公式，仅供避雷参考
我们假设有7只猴子，数到3的猴子出圈，即n=7,m=3
如上图所示，画圈的编号表示出圈的猴子编号
第一次选出圈猴时，从1开始数，数到3，第二次选出圈猴时，应从4开始数，因此第二次选出圈猴时开头的编号为4，以此类推，最后剩下4为大王
根据上图，我们可以知道，第一次选出圈猴时，开头的编号必然为1，而大王的编号必然是上图中最后一行的开头的编号，因此我们只要找到行与行间编号的映射关系即可知道大王的编号
观察上图画圈的编号，3->6->2->7->5,对应关系为
[f(1)+m]%n=f(2)
[f(2)+m]%n=f(3)
即[f(n)+m]%n=f(n+1) 其中f(n)表示第n行对应的编号
可化为[f(n-1)+m]%n=f(n)
即f(n) = [f(n-1)+m]%n
这个公式是怎么得到的？
我们看第一行，编号3在第一个的第三个位置，下一行的第一个位置必然是(3+1)%7,那么下一行的第三个位置就是(3+1+2)%7,即（3+m）%n
此公式对任一列都适用，我们代入第一列试一试
f(1) = 1
f(2) = [f(1)+3]%7 = 4
f(3) = [f(2)+3]%7 = 0
可以看到，到f(3)这里出现了问题，由于取余符号的特性，7%7,等于0而不是7，这里出现了错误，因此需要修改一下公式，f(n) = [f(n-1)+m-1]%n+1，这样就避免了出现7%7这种情况
至此 我认为该问题已经解决，然而实际上每次出圈总人数都会发生变化，此公式并不适用于求每次出圈的编号即只对f(n)和f(1)适用
下面是明烛大佬给出的数学推导过程 这或许是你能找到的最详细约瑟夫环数学推导！ – 知乎
对于不是单纯搞算法的我们来说，这些数学类知识只需要稍微理解记住即可，不必深究
公式为：f(n) = [f(n-1)+m-1]%n+1
已知f(1)=1,那么f(n)只需要递归即可
代码实现：
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = 1, m = 1;
while (n != 0 && m != 0) {
n = sc.nextInt();
m = sc.nextInt();
if(n==0&&m==0)
break;
System.out.println(new Main().yuesefu(n, m));
}
}
public int yuesefu(int n, int k) {
if (n == 1) {
return 1;
} else {
return (yuesefu(n - 1, k) + k - 1) % n + 1;
}
}
}题目四：全排列
原题链接：OpenJudge – 004:全排列
思路分析：
首先需要知道字母序的定义，用大白话来说，就是先比较第一个字符， 小的排前面，如果第一个字符相同，则比较第二个字符，小的排前面，以此类推
题目要求字符串内所有字符的所有排列，我们首先想到的肯定是暴力循环，但是显然我们并不知道循环的层数，因此采用递归回溯的形式求解（递归实质也是暴力循环，但是可以通过结束条件控制循环层数）
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
static ArrayList<String> array = new ArrayList<String>();
char result[] = new char[7];
int result_index = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
char a[] = str.toCharArray();
new Main().backtrack(a, 0, new boolean[a.length]);
for (int i = 0; i < array.size(); i++) {
System.out.println(array.get(i));
}
}
public void backtrack(char a[], int k, boolean used[]) {
if (k >= a.length) {
if (result_index == a.length) {
String str = new String(result, 0, result_index);
array.add(str);
}
return;
}
for (int i = 0; i < a.length; i++) {
if (!used[i]) {
result[result_index++] = a[i];
used[i] = true;
backtrack(a, k + 1, used);
result_index--;
used[i] = false;
}
}
}
}array是String类型的集合，用于存储所有的排列好的字符串（这里也可以用String数组，但是会造成不必要的空间浪费）
result用于接收每次递归的字符，当达到原字符串的长度时，转成String存储到array中
递归回溯实际上就是对树的遍历
我们假设有a,b,c三个字符，则其树的结构为
由上图可知在result中同一元素会重复，因此使用used数组的boolean值来控制是否添加该元素，元素进入result数组之后，其对应的used数组的值改为true,这样在这一条路径上该元素不会再次进入result数组，在回溯时将该元素的used值设置为false，这样可以在同一层级上的其他路径上再次进入result数组，至于具体代码实现过程，实在繁琐，不再叙述
代码实现：
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
static ArrayList<String> array = new ArrayList<String>();
char result[] = new char[7];
int result_index = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
char a[] = str.toCharArray();
new Main().backtrack(a, 0, new boolean[a.length]);
for (int i = 0; i < array.size(); i++) {
System.out.println(array.get(i));
}
}
public void backtrack(char a[], int k, boolean used[]) {
if (k >= a.length) {
if (result_index == a.length) {
String str = new String(result, 0, result_index);
array.add(str);
}
return;
}
for (int i = 0; i < a.length; i++) {
if (!used[i]) {
result[result_index++] = a[i];
used[i] = true;
backtrack(a, k + 1, used);
result_index--;
used[i] = false;
}
}
}
}题目五：统计质数个数
原题链接：OpenJudge – 005:统计质数个数
思路分析：
首先需要知道质数（素数）的定义，大白话来讲，如果一个数除了可以整除自身外，没有其他可以整除的数，那么这个数就是质数，如2,3,5,7
那么我们要知道一个数是不是素数，只需要知道其除了自身，是否还可以整除其他数
如判断7是不是质数，我们可以从2开始遍历到6，如果之间存在7%i==0，即存在i可以被7整除，那么7就不是质数，如果不存在，则7是质数，显然(7%i!)=0 (i=2,3,4,5,6)，因此7是质数
判断8是不是质数，我们从2遍历到7，显然8%2==0，因此8不是质数
但是此方法时间复杂度较高，可以做适当优化，我们知道，一个数的因数一定是关于其二次根对称的，以16为例，sqrt(16)=4,16=2*8,16=4*4,16=8*2,我们可以观察到，2,8是关于4对称的，那么如果在4之前没有数可以被16整除，则在4-15也不会有数可以被16整除，因此我们只需要遍历到sqrt(n)即可
知道了怎么判断一个数为质数，那么此问题只需要再嵌套一层循环从n遍历到m
即可
代码实现：
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int count = 0;
while (n <= m) {
if (n >= 2) {
int s = 0;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
s++;
break;
}
}
if (s == 0)
count++;
}
n++;
}
System.out.println(count);
}
}题目六：水仙花数
原题链接：OpenJudge – 006:水仙花数（daffodil）
思路分析：
首先明确什么是水仙花数，对于一个三位数abc，如果a^3+b^3+c^3=abc，那么该数就是水仙花数，如153
此题的考点在于对于一个三位数如何单独取出其个位数，十位数，百位数
如153，其个位数为153%10=3,
其十位数为（153/10）%10=5，
其百位数为（153/10/10）%10=1
知道这一点 这道题就基本完成了
代码实现：
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 100; i <= n; i++) {
if ((i % 10) * (i % 10) * (i % 10) + (i / 10 % 10) * (i / 10 % 10) * (i / 10 % 10) + (i / 100 % 10) * (i / 100 % 10) * (i / 100 % 10) == i)
System.out.println(i);
}
}
}题目七：八皇后问题
代码实现：
/**
* @author Sane
* @version 1.0
*/
public class Main {
static int num = 1;
public static void main(String[] args) {
int a[] = new int[8];
new Main().backTrack(a, 0);
}
void backTrack(int a[], int k) {
if (k == 8) {
System.out.println("No. " + num++);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (j == search(a, i))
System.out.print("1 ");
else
System.out.print("0 ");
}
System.out.println();
}
return;
}
for (int i = 0; i < 8; i++) {
if (check(a, i, k)) {
a[k] = i;
backTrack(a, k + 1);
a[k] = 0;
}
}
}
boolean check(int a[], int i, int k) {
for (int j = 0; j < k; j++) {
if (a[j] == i || Math.abs(a[j] - i) == Math.abs(j - k)) {
return false;
}
}
return true;
}
int search(int a[], int i) {
for (int j = 0; j < 8; j++) {
if (a[j] == i)
return j;
}
return 0;
}
}题目八：数字三角形
代码实现：
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] a = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= i; j++) {
a[i][j] = sc.nextInt();
}
}
int[][] dp = new int[N][N];
dp[0][0] = a[0][0];
for (int i = 1; i < N; i++) {
dp[i][0] = dp[i-1][0] + a[i][0];
for (int j = 1; j <= i; j++) {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
}
}
int max = 0;
for (int i = 0; i < N; i++) {
max = Math.max(max, dp[N-1][i]);
}
System.out.println(max);
}
}题目九：放苹果
代码实现：
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int M = sc.nextInt();
int N = sc.nextInt();
System.out.println(countWays(M, N));
}
}
public static long countWays(int M, int N) {
if (M <= 1 || N == 1) {
return 1;
}
if (M < N) {
return countWays(M, M);
}
return countWays(M, N - 1) + countWays(M - N, N);
}
}题目十：鸣人和佐助
代码实现：
import java.util.ArrayDeque;
import java.util.Scanner;
import java.util.Queue;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int hang, lie, chark;
static Queue<xy> que = new ArrayDeque<>();
static char map[][];
static xy mingren;
static boolean visited[][][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
hang = sc.nextInt();
lie = sc.nextInt();
chark = sc.nextInt();
map = new char[hang + 2][lie + 2];
visited = new boolean[hang + 1][lie + 1][chark + 1];
for (int i = 1; i <= hang; i++) {
String str = sc.next();
for (int j = 1; j <= lie; j++) {
map[i][j] = str.charAt(j - 1);
}
}
for (int i = 1; i <= hang; i++) {
for (int j = 1; j <= lie; j++) {
if (map[i][j] == '@') {
mingren = new xy(i, j, chark);
break;
}
}
}
visited[mingren.x][mingren.y][chark] = true;
bfs();
}
static void bfs() {
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
que.add(mingren);
while (!que.isEmpty()) {
xy a = que.poll();
for (int i = 0; i < 4; i++) {
int new_x = a.x + dx[i];
int new_y = a.y + dy[i];
if (new_x > 0 && new_x <= hang && new_y > 0 && new_y <= lie && !visited[new_x][new_y][a.charkla]) {
switch (map[new_x][new_y]) {
case '*':
xy temp = new xy(new_x, new_y, a.charkla);
temp.dist = a.dist + 1;
visited[new_x][new_y][a.charkla] = true;
que.add(temp);
break;
case '+':
System.out.println(a.dist + 1);
return;
case '#':
if (a.charkla != 0) {
xy temp2 = new xy(new_x, new_y, a.charkla - 1);
temp2.dist = a.dist + 1;
visited[new_x][new_y][a.charkla] = true;
que.add(temp2);
}
break;
}
}
}
}
System.out.println("-1");
}
}
class xy {
int x, y, charkla;
int dist;
public xy(int x, int y, int charkla) {
this.x = x;
this.y = y;
this.charkla = charkla;
}
}题目十一：电影节
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int n;
static ArrayList<movie> arrays;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
arrays = new ArrayList<>();
while ((n = sc.nextInt()) != 0) {
while (n-- > 0) {
arrays.add(new movie(sc.nextInt(), sc.nextInt()));
}
Collections.sort(arrays, new Comparator<movie>() {
public int compare(movie m1, movie m2) {
return m1.end - m2.end;
}
});
int last_end = 0;
int count = 0;
for (movie m : arrays) {
int start = m.start;
int end = m.end;
if (start>=last_end) {
count++;
last_end = end;
}
}
System.out.println(count);
arrays.clear();
}
}
}
class movie {
int start;
int end;
public movie(int start, int end) {
this.start = start;
this.end = end;
}
}题目十二：数制转换
代码实现：
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
String str = sc.next();
int b = sc.nextInt();
if (str.equals("0")) {
System.out.println("0");
return;
}
long ten_n = to_ten(str, a);
String s_turn = to_b(ten_n, b);
System.out.print(s_turn);
}
public static long to_ten(String str, int a) {
char num[] = str.toCharArray();
long ten_n = 0;
int count = 0;
for (int i = num.length - 1; i >= 0; i--) {
if (num[i] >= 'A' && num[i] <= 'F')
ten_n += (num[i] - 'A' + 10) * Math.pow(a, count++);
else if (num[i] >= 'a' && num[i] <= 'f')
ten_n += (num[i] - 'a' + 10) * Math.pow(a, count++);
else
ten_n += (num[i] - '0') * Math.pow(a, count++);
}
return ten_n;
}
public static String to_b(long ten_n, int b) {
String s_turn = "";
for (int i = 0; ten_n > 0; i++) {
long temp = ten_n % b;
if (temp >= 0 && temp <= 9) {
s_turn = (temp + "") + s_turn;
} else {
s_turn = (char) ('A' + (temp - 10)) + s_turn;
}
ten_n /= b;
}
return s_turn;
}
}题目十三：胡
代码实现
import java.util.*;
class Main {
static int A[] = new int[10];
static ArrayList<Integer> que = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str;
while (true) {
str = sc.nextLine().replaceAll(" ", "");
if (str.charAt(0) == '0')
break;
for (int i = 0; i < str.length(); i++) {
A[(int) (str.charAt(i) - '0')]++;
}
if ((str.length() - 2) % 3 != 0) {
System.out.println("XIANGGONG");
Arrays.fill(A, 0);
} else {
for (int i = 0; i < 10; i++) {
if (A[i] >= 2)
que.add(i);
}
if (que.isEmpty()) {
System.out.println("BUHU");
Arrays.fill(A, 0);
} else {
boolean s = true;
while (!que.isEmpty()) {
s = true;
int temp = que.remove(0);
int B[] = Arrays.copyOf(A, 10);
B[temp] -= 2;
for (int i = 0; i < 10; i++) {
B[i] %= 3;
}
boolean turn = true;
while (turn) {
int count = 0;
for (int j = 0; j < 10; j++) {
turn = false;
if (B[j] > 0) {
turn = true;
count++;
if (count % 3 == 0) {
B[j - 2]--;
B[j - 1]--;
B[j]--;
count = 0;
} else turn = false;
} else count = 0;
}
}
for (int i = 0; i < 10; i++) {
if (B[i] != 0) {
s = false;
}
}
if (s) {
System.out.println("HU");
Arrays.fill(A, 0);
que.clear();
break;
}
}
if (!s) {
System.out.println("BUHU");
}
}
}
Arrays.fill(A, 0);
que.clear();
}
}
}题目十四：垂直直方图
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static char map[][];
static int counts[] = new int[26];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 4; i++) {
String str = sc.nextLine();
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) >= 'A' && str.charAt(j) <= 'Z')
counts[str.charAt(j) - 'A']++;
}
}
int max = 0;
for (int i = 0; i < 26; i++) {
max = Math.max(max, counts[i]);
}
for (int i = 0; i <= max; i++) {
if (i == max)
for (int j = 0; j < 26; j++) {
System.out.print((char) ('A' + j));
System.out.print(' ');
}
else
for (int j = 0; j < 26; j++) {
if (i >= max - counts[j])
System.out.print("*");
else
System.out.print(' ');
System.out.print(' ');
}
System.out.println();
}
}
}题目十五：算24
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static double a[] = new double[4];
static boolean suc = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
boolean ctn = true;
while (true) {
suc = false;
for (int i = 0; i < 4; i++) {
a[i] = sc.nextDouble();
}
if (a[0] == 0 && a[1] == 0 && a[2] == 0 && a[3] == 0) {
break;
}
dfs(0, a, 0);
System.out.println(suc ? "YES" : "NO");
}
}
static void dfs(int k, double b[], double lastsum) {
if (b.length == 1) {
if (Math.abs(b[0] - 24) < 1e-6)
suc = true;
return;
}
for (int i = 0; i < b.length; i++) {
for (int j = 0; j < b.length; j++) {
if (i != j) {
for (int l = 0; l < 4; l++) {
switch (l) {
case 0:
double temp[] = new double[b.length - 1];
for (int m = 0, p = 0; p < b.length; p++) {
if (p != i && p != j)
temp[m++] = b[p];
}
temp[temp.length - 1] = b[i] + b[j];
dfs(k + 1, temp, b[i] + b[j]);
break;
case 1:
double temp1[] = new double[b.length - 1];
for (int m = 0, p = 0; p < b.length; p++) {
if (p != i && p != j)
temp1[m++] = b[p];
}
temp1[temp1.length - 1] = b[i] - b[j];
dfs(k + 1, temp1, b[i] - b[j]);
break;
case 2:
double temp2[] = new double[b.length - 1];
for (int m = 0, p = 0; p < b.length; p++) {
if (p != i && p != j)
temp2[m++] = b[p];
}
temp2[temp2.length - 1] = b[i] * b[j];
dfs(k + 1, temp2, b[i] * b[j]);
break;
case 3:
if (b[j] != 0) {
double temp3[] = new double[b.length - 1];
for (int m = 0, p = 0; p < b.length; p++) {
if (p != i && p != j)
temp3[m++] = b[p];
}
temp3[temp3.length - 1] = b[i] / b[j];
dfs(k + 1, temp3, b[i] / b[j]);
}
break;
}
}
}
}
}
}
}题目十六：Knight Moves
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int n;
static boolean map[][];
static boolean visited[][];
static ArrayList<xy> que = new ArrayList<>();
static int l;
static int dist[][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
while (n-- > 0) {
l = sc.nextInt();
map = new boolean[l][l];
visited = new boolean[l][l];
dist = new int[l][l];
int startx = sc.nextInt();
int starty = sc.nextInt();
visited[startx][starty] = true;
int endx = sc.nextInt();
int endy = sc.nextInt();
if (startx == endx && starty == endy) {
System.out.println(0);
continue;
}
map[endx][endy] = true;
bfs(startx, starty);
System.out.println(dist[endx][endy]);
que.clear();
}
}
static void bfs(int startx, int starty) {
que.add(new xy(startx, starty));
while (!que.isEmpty()) {
xy temp = que.remove(0);
int x = temp.x;
int y = temp.y;
if (x - 2 >= 0) {
if (y - 1 >= 0 && !visited[x - 2][y - 1]) {
visited[x - 2][y - 1] = true;
dist[x - 2][y - 1] = dist[x][y] + 1;
if (map[x - 2][y - 1]) {
return;
}
que.add(new xy(x - 2, y - 1));
}
if (y + 1 < l && !visited[x - 2][y + 1]) {
visited[x - 2][y + 1] = true;
dist[x - 2][y + 1] = dist[x][y] + 1;
if (map[x - 2][y + 1]) {
return;
}
que.add(new xy(x - 2, y + 1));
}
}
if (x - 1 >= 0) {
if (y - 2 >= 0 && !visited[x - 1][y - 2]) {
visited[x - 1][y - 2] = true;
dist[x - 1][y - 2] = dist[x][y] + 1;
if (map[x - 1][y - 2]) {
return;
}
que.add(new xy(x - 1, y - 2));
}
if (y + 2 < l && !visited[x - 1][y + 2]) {
visited[x - 1][y + 2] = true;
dist[x - 1][y + 2] = dist[x][y] + 1;
if (map[x - 1][y + 2]) {
return;
}
que.add(new xy(x - 1, y + 2));
}
}
if (x + 1 < l) {
if (y - 2 >= 0 && !visited[x + 1][y - 2]) {
visited[x + 1][y - 2] = true;
dist[x + 1][y - 2] = dist[x][y] + 1;
if (map[x + 1][y - 2]) {
return;
}
que.add(new xy(x + 1, y - 2));
}
if (y + 2 < l && !visited[x + 1][y + 2]) {
visited[x + 1][y + 2] = true;
dist[x + 1][y + 2] = dist[x][y] + 1;
if (map[x + 1][y + 2]) {
return;
}
que.add(new xy(x + 1, y + 2));
}
}
if (x + 2 < l) {
if (y - 1 >= 0 && !visited[x + 2][y - 1]) {
visited[x + 2][y - 1] = true;
dist[x + 2][y - 1] = dist[x][y] + 1;
if (map[x + 2][y - 1]) {
return;
}
que.add(new xy(x + 2, y - 1));
}
if (y + 1 < l && !visited[x + 2][y + 1]) {
visited[x + 2][y + 1] = true;
dist[x + 2][y + 1] = dist[x][y] + 1;
if (map[x + 2][y + 1]) {
return;
}
que.add(new xy(x + 2, y + 1));
}
}
}
}
}
class xy {
int x, y;
public xy(int x, int y) {
this.x = x;
this.y = y;
}
}题目十七：末位零
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
while (N-- > 0) {
int count = 0;
int m = sc.nextInt();
while (m > 0) {
count += m / 5;
m /= 5;
}
System.out.println(count);
}
}
}题目十八：二叉树
代码实现
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int m, n;
static int sum = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
m = sc.nextInt();
n = sc.nextInt();
if (m == 0 && n == 0)
break;
sum = 0;
num(m, n, 0);
System.out.println(sum);
}
}
static void num(int m, int n, int hang) {
if (2 * m <= n) {
hang++;
num(2 * m, n, hang);
} else {
if (hang == 0) {
sum = 1;
} else {
int a = 1;
sum = 1;
for (int i = 1; i < hang; i++) {
a *= 2;
sum += a;
}
if (m + 2 * a - 1 >= n)
sum = sum + (n - m) + 1;
else
sum = sum + (m + 2 * a - 1 - m) + 1;
}
}
}
}题目十九：大整数加法
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
ArrayList<Integer> al1 = new ArrayList<>();
ArrayList<Integer> al2 = new ArrayList<>();
boolean i1 = true;
boolean i2 = true;
boolean zero1 = true;
boolean zero2 = true;
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != '0')
zero1 = false;
}
for (int i = 0; i < str2.length(); i++) {
if (str2.charAt(i) != '0')
zero2 = false;
}
if (zero1 && zero2) {
System.out.println(0);
return;
}
for (int i = 0; i < str1.length(); i++) {
if (i1) {
if ((str1.charAt(i) - '0') == 0)
continue;
else
i1 = false;
}
al1.add(str1.charAt(i) - '0');
}
for (int i = 0; i < str2.length(); i++) {
if (i2) {
if ((str2.charAt(i) - '0') == 0)
continue;
else
i2 = false;
}
al2.add(str2.charAt(i) - '0');
}
Collections.reverse(al1);
Collections.reverse(al2);
ArrayList<Integer> al3 = new ArrayList<>();
boolean jinwei = false;
for (int i = 0; i < Math.min(al2.size(), al1.size()); i++) {
int temp = 0;
if (jinwei) {
temp = al1.get(i) + al2.get(i) + 1;
jinwei = false;
} else
temp = al1.get(i) + al2.get(i);
al3.add(temp % 10);
if (temp >= 10) {
jinwei = true;
}
}
if (al1.size() > al2.size()) {
for (int i = al2.size(); i < al1.size(); i++) {
int temp = 0;
if (jinwei) {
temp = al1.get(i) + 1;
jinwei = false;
} else
temp = al1.get(i);
al3.add(temp % 10);
if (temp >= 10) {
jinwei = true;
}
}
} else {
for (int i = al1.size(); i < al2.size(); i++) {
int temp = 0;
if (jinwei) {
temp = al2.get(i) + 1;
jinwei = false;
} else
temp = al2.get(i);
al3.add(temp % 10);
if (temp >= 10) {
jinwei = true;
}
}
}
if (jinwei)
al3.add(1);
Collections.reverse(al3);
for (int i = 0; i < al3.size(); i++) {
System.out.print(al3.get(i));
}
}
}题目二十：显示器
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static boolean shang[] = new boolean[10];
static boolean zhong[] = new boolean[10];
static boolean xia[] = new boolean[10];
static boolean start_shang[] = new boolean[10];
static boolean start_xia[] = new boolean[10];
static boolean end_shang[] = new boolean[10];
static boolean end_xia[] = new boolean[10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int size = sc.nextInt();
int show_num = sc.nextInt();
if (show_num == 0 && size == 0)
break;
shang[1] = true;
shang[4] = true;
zhong[0] = true;
zhong[1] = true;
zhong[7] = true;
xia[1] = true;
xia[4] = true;
xia[7] = true;
start_shang[0] = true;
start_shang[4] = true;
start_shang[5] = true;
start_shang[6] = true;
start_shang[8] = true;
start_shang[9] = true;
start_xia[0] = true;
start_xia[2] = true;
start_xia[6] = true;
start_xia[8] = true;
end_shang[0] = true;
end_shang[1] = true;
end_shang[2] = true;
end_shang[3] = true;
end_shang[4] = true;
end_shang[7] = true;
end_shang[8] = true;
end_shang[9] = true;
end_xia[0] = true;
end_xia[1] = true;
end_xia[3] = true;
end_xia[4] = true;
end_xia[5] = true;
end_xia[6] = true;
end_xia[7] = true;
end_xia[8] = true;
end_xia[9] = true;
String num_str = String.valueOf(show_num);
int len = num_str.length();
for (int i = 0; i < 2 * size + 3; i++) {
for (int k = 0; k < len; k++) {
int temp = num_str.charAt(k) - '0';
if (i == 0 || i == size + 1 || i == 2 * size + 2)
System.out.print(" ");
else {
if (i < size + 1) {
if (start_shang[temp])
System.out.print("|");
else System.out.print(" ");
}
if (i > size + 1) {
if (start_xia[temp])
System.out.print("|");
else System.out.print(" ");
}
}
for (int j = 0; j < size; j++) {
if (i == 0) {
if (shang[temp]) {
System.out.print(" ");
} else System.out.print("-");
} else if (i == size + 1) {
if (zhong[temp]) {
System.out.print(" ");
} else System.out.print("-");
} else if (i == 2 * size + 2) {
if (xia[temp]) {
System.out.print(" ");
} else System.out.print("-");
} else {
System.out.print(" ");
}
}
if (i == 0 || i == size + 1 || i == 2 * size + 2)
System.out.print(" ");
else {
if (i < size + 1) {
if (end_shang[temp])
System.out.print("|");
else System.out.print(" ");
}
if (i > size + 1) {
if (end_xia[temp])
System.out.print("|");
else System.out.print(" ");
}
}
System.out.print(" ");
}
System.out.println();
}
System.out.println();
}
}
}题目二十一：棋盘问题
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int n, k;
static char map[][];
static int count = 0;
static boolean now_map[][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
n = sc.nextInt();
k = sc.nextInt();
if (n == -1 && k == -1) {
break;
}
map = new char[n + 1][n + 1];
now_map = new boolean[n + 1][n + 1];
if (k <= 0 || n <= 0) {
System.out.println(0);
continue;
}
for (int i = 1; i <= n; i++) {
String str = sc.next();
for (int j = 1; j <= n; j++) {
map[i][j] = str.charAt(j - 1);
}
}
dfs(1, 0);
System.out.println(count);
count = 0;
}
}
static void dfs(int ceng, int pulled) {
if (pulled >= k) {
count++;
return;
}
if (ceng > n)
return;
for (int i = 1; i <= n; i++) {
if (map[ceng][i] == '#' && check(ceng, i)) {
now_map[ceng][i] = true;
dfs(ceng + 1, pulled + 1);
now_map[ceng][i] = false;
}
}
dfs(ceng + 1, pulled);
}
static boolean check(int i, int j) {
for (int l = 1; l < i; l++) {
if (now_map[l][j])
return false;
}
return true;
}
}题目二十二：金币
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int day;
static int sum = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
day = sc.nextInt();
if (day == 0)
break;
answer(day);
System.out.println(day + " " + sum);
sum = 0;
}
}
static void answer(int day) {
int jiange = 1;
int last_jiange = jiange;
int gold = 1;
for (int i = 1; i <= day; i++) {
sum += gold;
jiange--;
if (jiange == 0) {
jiange = last_jiange + 1;
last_jiange = jiange;
gold++;
}
}
}
}题目二十三：英语数字转换器
代码实现：
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @author Sane
* @version 1.0
*/
public class Main {
public static void main(String[] args) {
Map<String, Integer> dict = new HashMap<>();
dict.put("negative", -1);
dict.put("zero", 0);
dict.put("one", 1);
dict.put("two", 2);
dict.put("three", 3);
dict.put("four", 4);
dict.put("five", 5);
dict.put("six", 6);
dict.put("seven", 7);
dict.put("eight", 8);
dict.put("nine", 9);
dict.put("ten", 10);
dict.put("eleven", 11);
dict.put("twelve", 12);
dict.put("thirteen", 13);
dict.put("fourteen", 14);
dict.put("fifteen", 15);
dict.put("sixteen", 16);
dict.put("seventeen", 17);
dict.put("eighteen", 18);
dict.put("nineteen", 19);
dict.put("twenty", 20);
dict.put("thirty", 30);
dict.put("forty", 40);
dict.put("fifty", 50);
dict.put("sixty", 60);
dict.put("seventy", 70);
dict.put("eighty", 80);
dict.put("ninety", 90);
dict.put("hundred", 100);
dict.put("thousand", 1000);
dict.put("million", 1000000);
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
if (line.length() == 0) {
break;
}
long ans = 0;
long t = 0;
String[] words = line.split(" ");
for (String word : words) {
if (dict.containsKey(word)) {
int value = dict.get(word);
if (value == -1) {
System.out.print("-");
} else if (value == 100) {
t *= value;
} else if (value == 1000 || value == 1000000) {
t *= value;
ans += t;
t = 0;
} else {
t += value;
}
}
}
ans += t;
System.out.println(ans);
}
}
}题目二十四：重建二叉树
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int index = 0;
static String str1, str2;
static ArrayList<Node> nodes = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
if (!sc.hasNext())
break;
str1 = sc.next();
if (!sc.hasNext())
break;
str2 = sc.next();
digui(str2, 0, null);
bianli(nodes.get(0));
System.out.println();
nodes.clear();
index = 0;
}
}
static void digui(String str2, int dir, Node last_node) {
if (str2.isEmpty())
return;
if (index == str1.length())
return;
char ch = str1.charAt(index);
Node node = new Node(ch);
nodes.add(node);
index++;
if (last_node != null) {
if (dir == 0) {
last_node.left = node;
} else last_node.right = node;
}
String new_array[] = str2.split(String.valueOf(ch));
if (new_array.length > 0) {
digui(new_array[0], 0, node);
}
if (new_array.length > 1)
digui(new_array[1], 1, node);
}
static void bianli(Node node) {
if (node.left != null)
bianli(node.left);
if (node.right != null)
bianli(node.right);
System.out.print(node.data);
}
}
class Node {
char data;
Node left;
Node right;
public Node(char data) {
this.data = data;
}
}题目二十五：汉诺塔问题(Tower of Hanoi)
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int n;
static int a = 1, b = 2, c = 3;
static char ch[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
ch = new char[3];
for (int i = 0; i < 3; i++) {
ch[i] = sc.next().charAt(0);
}
tower(a, b, c, n, n);
}
static void tower(int t1, int t2, int t3, int num, int bianhao) {
if (num == 1) {
char ch1 = 0, ch2 = 0;
switch (t1) {
case 1:
ch1 = ch[0];
break;
case 2:
ch1 = ch[1];
break;
case 3:
ch1 = ch[2];
break;
}
switch (t3) {
case 1:
ch2 = ch[0];
break;
case 2:
ch2 = ch[1];
break;
case 3:
ch2 = ch[2];
break;
}
System.out.println(bianhao + ":" + ch1 + "->" + ch2);
return;
}
tower(t1, t3, t2, num - 1, bianhao - 1);
tower(t1, t2, t3, 1, bianhao);
tower(t2, t1, t3, num - 1, bianhao - 1);
}
}题目二十六：数字方格
代码实现：
import java.util.*;
/**
* @author Sane
* @version 1.0
*/
class Main {
static int a1, a2, a3;
static int n;
static int max;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
if ((i + j) % 2 == 0 && (j + k) % 3 == 0 && (i + j + k) % 5 == 0)
max = Math.max(max, i + j + k);
}
}
}
System.out.println(max);
}
}文章出处登录后可见！
已经登录？立即刷新
