一、《玩具蛇》
问题描述
算法分析
本题采用的是dfs的思想，基本思路就是遍历每个方格，对每个格子使用dfs进行搜索，若蛇长度为0，则为dfs出口，蛇行方法加一。
代码如下
package dfs;
public class 玩具蛇 {
static int count = 0;
static boolean visited[][];
public static void main(String[] args) {
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
visited = new boolean[4][4];
visited[i][j] = true;
dfs(i,j,15);
visited[i][j] = false;
}
}
System.out.println(count);
}
public static void dfs(int x,int y,int length) {
//判断是否没长度了
if(length == 0) {
//这是一种蛇行方法
count++;
return;
}
//向上
if(x-1>=0&&!visited[x-1][y]) {
visited[x-1][y] = true;
dfs(x-1, y, length-1);
visited[x-1][y] = false;
}
//向下
if(x+1<=3&&!visited[x+1][y]) {
visited[x+1][y] = true;
dfs(x+1, y, length-1);
//为了回退继续深度搜索
visited[x+1][y] = false;
}
//向左
if(y-1>=0&&!visited[x][y-1]) {
visited[x][y-1] = true;
dfs(x, y-1, length-1);
visited[x][y-1] = false;
}
//向右
if(y+1<=3&&!visited[x][y+1]) {
visited[x][y+1] = true;
dfs(x, y+1, length-1);
visited[x][y+1] = false;
}
return;
}
}
二、《小朋友崇拜圈》
问题描述
算法分析
同理，使用dfs搜索。
代码如下
package dfs;
import java.util.Arrays;
import java.util.Scanner;
public class 小朋友崇拜圈 {
static int x;
static boolean[] bs;
static int max;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = scanner.nextInt();
}
bs = new boolean[n];
for(int i=0;i<n;i++){
//记录开头的小朋友
x=i;
dfs(arr, arr[i]-1, 0);
Arrays.fill(bs, false);
}
//输出最大圈的人数
System.out.println(max+1);
}
static void dfs(int[]a,int i,int k) {
if (i == x) {
max = Math.max(max, k);
}
if(!bs[i]) {
bs[i] = true;
dfs(a, a[i]-1, k+1);
}else {
return;
}
}
}
三、《N皇后问题》
问题描述
在 N×N 的方格棋盘放置了 N 个皇后，使得它们不相互攻击（即任意 2 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 角的斜线上。你的任务是，对于给定的 N，求出有多少种合法的放置方法。
输入描述：输入中有一个正整数 N≤10，表示棋盘和皇后的数量。
输出描述：为一个正整数，表示对应输入行的皇后的不同放置数量。
输入：5
输出：8
算法分析
使用dfs进行深度搜索，并添加一个验证函数，用来判断当前位置能否放置皇后。
代码如下
package dfs;
import java.util.Scanner;
public class N皇后 {
static int res = 0;
static int n;
//记录访问（放置皇后）情况，每一步相当于一行（例如n=8占用0-7行）
static int[][] board = new int[20][20];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
dfs(0);
System.out.println(res);
}
public static void dfs(int step) {
//如果步数等于n皇后数量，则刚好放置完所有皇后
//例如n为8:0-7步都能放置，到了8则结束
if(step == n) {
res++;
return;
}
//这里可以理解为：每一步在board记录中相当于一行
for(int i=0;i<n;i++) {
if(isValid(step, i)){
board[step][i]++;
dfs(step+1);
board[step][i]--;
}
}
}
public static boolean isValid(int row,int col) {
//检查列是否有皇后冲突
for(int i=0;i<n;i++) {
if(board[i][col]>0) {
return false;
}
}
//检查左上方是否有皇后冲突
for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {
if(board[i][j]>0) {
return false;
}
}
//检查右上方是否有皇后冲突
for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++) {
if(board[i][j]>0) {
return false;
}
}
return true;
}
}
四、《排列序数》
问题描述
如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
算法分析
本题算法较为简单，找出上述排列的规律公式，即可解决。
代码如下
package lanqiao;
import java.util.Scanner;
public class PermutationOrdinal1111 {
static int jie(int x) {
int sum=1;
for(int i=1;i<=x;i++) {
sum*=i;
}
return sum;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String aString = scanner.nextLine();
int sum = 0;
int n = aString.length();
int[][]arr = new int[n][2];
for(int i=0;i<n;i++) {
arr[i][0]=aString.charAt(i)-97;
//记录比它靠前的字母用了几个
arr[i][1]=0;
for(int j=0;j<i;j++) {
if(arr[j][0]<arr[i][0]) {
arr[i][1]++;
}
}
}
for(int i=0;i<n;i++) {
sum+=(arr[i][0]-arr[i][1])*jie(n-i-1);
}
System.out.println(sum);
}
}
五、《刷题统计》
问题描述
算法分析
本题为简单的枚举题，需要注意的是，评测用例为超过整形等基本数据类型范围的“大数”，因此我们要使用Long类型创建对象来保存“大数”。
代码如下
package yati;
import java.math.BigInteger;
import java.util.Scanner;
public class 刷题统计枚举 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Long aLong = scanner.nextLong();
Long bLong = scanner.nextLong();
Long nLong = scanner.nextLong();
Long[]arr = {aLong,aLong,aLong,aLong,aLong,bLong,bLong};
Long res = new Long(0);
int day = 0;
int i=0;
while(res.longValue()<nLong.longValue()) {
res+=arr[i%7];
i++;
day++;
}
System.out.println(day);
}
}