跳石板
这一题其实很简单，首先利用分解因数的一部分知识，找到n到m之间所有数字的约数，然后通过bfs进行搜索。当然直接进行bfs肯定会炸的，直接用set进行状态保留。为什么这里我用map是我误以为可能还要比较路径优劣，但既然用了bfs就不用费这个力了。（不用状态保留，提前剪枝会超时）
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
Map<Integer, ArrayList<Integer>> init_array = new HashMap<>();
for (int i = 2; i <= m; i++){
init_array.put(i, new ArrayList<>());
}
for (int i = 2; i <= m; i++){
int j = 2;
while(i * j <= m){
init_array.get(i * j).add(i);
j++;
}
}
int path = bfs(init_array, n, m);
System.out.println(path);
}
private static int bfs(Map<Integer,ArrayList<Integer>> init_array, int n, int m) {
Queue<Integer> pos_queue = new LinkedList<>();
pos_queue.offer(n);
int paths = -1;
Map<Integer, Integer> state_map = new HashMap<>();
state_map.put(n, 0);
while (!pos_queue.isEmpty()){
paths++;
int len = pos_queue.size();
for (int i = 0; i < len; i++){
int pos = pos_queue.poll();
if (pos > m){
continue;
}else if (pos == m){
return paths;
}
List<Integer> list = init_array.get(pos);
int k = list.size();
for (int j = 0; j < k; j++){
//如果这个节点已经被访问过了，continue
if (state_map.get(pos + list.get(k - 1 - j)) != null){
continue;
}else {
state_map.put(pos + list.get(k - 1 - j), paths);
pos_queue.offer(pos + list.get(k - 1 - j));
}
}
}
}
return -1;
}
}
优雅点
思路：一个圆有四个部分，但问题在于如何将原切割成等价的四分，那就是四个左开右闭区间，可以无重合的覆盖整一个圆。
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
double r = Math.sqrt(n);
int max_len = (int) r;
int result = 0;
for (int i = 1; i <= max_len; i++){
int tmp_y = (int)Math.sqrt(n - i * i);
if ((tmp_y * tmp_y + i * i) == n){
result++;
}
}
System.out.println(4 * result);
}
}
小易喜欢的单词
本题的难点就是规则二——子字符串不可以出现ABAB的形式，思路就是将其简化为当前字符可供的选择就是加字符或者不加。然后如果加了字符，是否已经在前面字串中选取了两个，是的话就搜索后半部分字串中是否有这个字串；如果只是选取了一个的话就直接入队（这里还可以验证一下是否相同字符已经入队），继续循环。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String word = scanner.next();
String[] results = {"Dislikes", "Likes"};
System.out.println(results[isLiked(word)]);
}
private static int isLiked(String word) {
Queue<String> queue = new LinkedList<>();
queue.offer("");
char[] wordA = word.toCharArray();
int len = wordA.length;
for (int i = 0; i < len; i++){
if (!(wordA[i] >= 'A' && wordA[i] <= 'Z')){
return 0;
}
if (i < len - 1 && wordA[i] == wordA[i + 1]){
return 0;
}
int size = queue.size();
for (int j = 0; j < size; j++){
String tmp = queue.poll();
switch (tmp.length()){
case 0:
//字符串可以添加或者不添加，入队
queue.offer("");
queue.offer(tmp + wordA[i]);
break;
case 1:
//字符串可以添加成为两个字符
queue.offer(tmp);
char A = tmp.charAt(0);
char B = wordA[i];
int indexA = word.substring(i).indexOf(A);
if (indexA == -1){
break;
}
int indexB = word.substring(i).substring(indexA).indexOf(B);
// System.out.println(indexA + " : " + indexB);
if (indexB == -1 || indexB == 0){
break;
}else {
return 0;
}
default:
;
}
}
}
return 1;
}
}
两种排序方法
水题，直接有String.compareTo(String)可以调用。
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String[] strings = new String[n];
int index = 0;
while (index < n){
strings[index++] = scanner.next();
}
String[] result = {"none", "lexicographically", "lengths", "both"};
int i = 0;
if (isLexOrder(strings)){
i = 1;
}
if (isLenOrder(strings)){
i = i + 2;
}
System.out.println(result[i]);
}
private static boolean isLenOrder(String[] strings) {
if (strings.length <= 1){
return true;
}
for (int i = 0; i < strings.length - 1; i++) {
if (strings[i].length() > strings[i + 1].length()) {
return false;
}
}
return true;
}
private static boolean isLexOrder(String[] strings) {
if (strings.length <= 1){
return true;
}
for (int i = 0; i < strings.length - 1; i++) {
if (strings[i].compareTo(strings[i + 1]) > 0) {
return false;
}
}
return true;
}
}
