A. 组队 490
手动算吧,不麻烦。但是要注意一个队员只能选中一次。
B. 不同子串 100
只要没有重复的,都用set做,很舒服。
注意 i 和 j 位置要写对。犯了好几次错误导致死循环了,我反思。
import java.util.HashSet;
public class Main {
static String str = "0100110001010001";
static HashSet<String> hs = new HashSet<String>();
public static void main(String[] args) {
for (int i = 0; i < str.length(); i++)
for (int j = i; j < str.length(); j++)
{
hs.add(str.substring(i, j + 1)); //substring会截到第二个参数-1
}
System.out.println(hs.size());
}
}
C. 数列求值 4659
注意运算过程只和每个数的后四位有关系,所以要取模,不然long都会爆。
public class Main {
static long[] num = new long[30000000];
static long[] num2 = new long[30000000];
//法二:递归,但递归不了一万以上层。
static long f(int i)
{
if(num2[i] != 0) return num2[i];
if(i <= 3) return 1;
else return num2[i] = (f(i - 1) % 10000 + f(i - 2) % 10000 + f(i - 3) % 10000) % 10000;
}
public static void main(String[] args)
{
//法一:递推
num[1] = num[2] = num[3] = 1;
for(int i = 4; i <= 20190324; i++)
{
num[i] = num[i - 1] + num[i - 2] + num[i - 3];
num[i] %= 10000; //必须取模,不然不够存
}
System.out.println(num[20190324]);
//System.out.println(f(20193024));
}
}
D. 数的分解
用indexof()
做,就很舒服。
但要注意,因为取到的数字“各不相同”,而且顺序不影响,所以这三个数各自的范围要注意。
public class Main {
public static void main(String[] args) {
int res = 0;
for (int i = 1; i <= 2019; i++)
for (int j = i + 1; j <= 2019; j++)
{
int k = 2019 - i - j;
if(k <= j) continue; //还有等于的情况也不能要,切记
int sumi = String.valueOf(i).indexOf('2') + String.valueOf(i).indexOf('4');
int sumj = String.valueOf(j).indexOf('2') + String.valueOf(j).indexOf('4');
int sumk = String.valueOf(k).indexOf('2') + String.valueOf(k).indexOf('4');
if(sumi + sumj + sumk == -6) res++;
}
System.out.println(res);
}
}
E. 迷宫 答案太长了
和 走迷宫 这道题大同小异。
注意:因为BFS迷宫是逆序找通路的,最后输出的答案也必须逆序输出。
DLRU的遍历顺序不能变,还有题干输入也有些刁钻,需要注意。
另外,分享一下在网上看到的 Excel大法
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Pair
{
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int N = 52;
static int n, m;
static int[][] map = new int[N][N];
static int[][] d = new int[N][N];
static Pair[][] pre= new Pair[N][N];
static Queue<Pair> q = new LinkedList<Pair>();
static int dx[] = {1, 0, 0, -1};
static int dy[] = {0, -1, 1, 0};
static int idx;
static char[] ans = new char[1510];
static void bfs()
{
q.offer(new Pair(0, 0));
while(q.size() >0)
{
Pair now = q.poll();
for (int i = 0; i < 4; i++)
{
int x = now.x + dx[i], y = now.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m) continue;
if(map[x][y] == 1 || d[x][y] != 0) continue;
d[x][y] = d[now.x][now.y] + 1;
pre[x][y] = new Pair(now.x, now.y);
q.offer(new Pair(x, y));
}
}
int x = n - 1, y = m - 1;
/*
D 1,0
L 0,-1
R 0,1
U -1,0
*/
while(x != 0 || y != 0) //不是并且
{
Pair temp = pre[x][y];
int prex = pre[x][y].x, prey = pre[x][y].y;
if(x - prex == 1) ans[idx] = 'D';
else if (x - prex == -1) ans[idx] = 'U';
else if(y - prey == -1) ans[idx] = 'L';
else if(y - prey == 1) ans[idx] ='R';
idx ++;
x = prex; //别忘了回溯
y = prey;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
for (int i = 0; i < n; i++)
{
input = br.readLine().split(" ");
for (int j = 0; j < input[0].length(); j++) map[i][j] = input[0].charAt(j) - '0'; //char转int
}
bfs();
for(int i = idx -1; i >=0; i--) System.out.print(ans[i]);
}
}