110.字符串接龙
题目：110. 字符串接龙 (kamacoder.com)
思路：没有思路
答案
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String beginStr = scanner.next();
String endStr = scanner.next();
Set<String> strSet = new HashSet<>();
for (int i = 0; i < n; i++) {
strSet.add(scanner.next());
}
System.out.println(findShortestTransformation(beginStr, endStr, strSet));
}
private static int findShortestTransformation(String beginStr, String endStr, Set<String> strSet) {
// 记录strSet里的字符串是否被访问过，同时记录路径长度
Map<String, Integer> visitMap = new HashMap<>();
// 初始化队列
Queue<String> queue = new LinkedList<>();
queue.add(beginStr);
// 初始化visitMap
visitMap.put(beginStr, 1);
while (!queue.isEmpty()) {
String word = queue.poll();
int pathLength = visitMap.get(word); // 这个字符串在路径中的长度
// 开始在这个str中，挨个字符去替换
for (int i = 0; i < word.length(); i++) {
char[] newWordArray = word.toCharArray();
// 遍历26个字母
for (char j = 'a'; j <= 'z'; j++) {
newWordArray[i] = j;
String newWord = new String(newWordArray);
if (newWord.equals(endStr)) { // 发现替换字母后，字符串与终点字符串相同
return pathLength + 1; // 找到了路径
}
// 字符串集合里出现了newWord，并且newWord没有被访问过
if (strSet.contains(newWord) && !visitMap.containsKey(newWord)) {
// 添加访问信息，并将新字符串放到队列中
visitMap.put(newWord, pathLength + 1);
queue.add(newWord);
}
}
}
}
// 没找到输出0
return 0;
}
}
小结
- 使用 Set<String> 存储字符串
- 使用 Map<String, Integer> 记录是否访问过,以及路径长度
- 通过queue来存储遍历过的字符串,从beginStr开始,每次替换一个字符,要是替换后的字符串存在于set中,就将该字符串记录为已访问,并将字符串放入到queue中
105.有向图的完全可达性
题目：105. 有向图的完全可达性 (kamacoder.com)
思路：从1出发,进行深搜,走完所有路径,看是否能够到达所有节点
尝试(运行出错）
import java.util.*;
public class Main {
private static List<List<Integer>> adjList;
private static List<List<Integer>> allPaths;
private static int target;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
adjList = new ArrayList<>();
for (int i = 0; i < n + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
adjList.get(s).add(t);
}
for(int i =2; i<=n; i++){
target = i;
allPaths = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
currentPath.add(1);
findAllPaths(1, currentPath);
if(allPaths.isEmpty()){
System.out.println("-1");
}
}
System.out.println("1");
scanner.close();
}
private static void findAllPaths(int currentNode, List<Integer> currentPath) {
if (currentNode == target) {
allPaths.add(new ArrayList<>(currentPath));
return;
}
for (int nextNode : adjList.get(currentNode)) {
currentPath.add(nextNode);
findAllPaths(nextNode, currentPath);
currentPath.remove(currentPath.size() - 1);
}
}
}答案
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(); // 边的数量
// 节点编号从1到n，所以申请 n+1 这么大的数组
List<List<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 读取边的信息并构建邻接表
for (int i = 0; i < m; i++) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph.get(s).add(t);
}
// 初始化访问数组
boolean[] visited = new boolean[n + 1];
dfs(graph, 1, visited);
// 检查是否所有节点都被访问到了
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
System.out.println(-1);
return;
}
}
System.out.println(1);
}
private static void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
if (visited[node]) {
return;
}
visited[node] = true;
for (int neighbor : graph.get(node)) {
dfs(graph, neighbor, visited);
}
}
}
小结
通过递归, 把所有路径跑一遍, 之后再检查是否所有的节点都有被访问到, 此处不需要回溯
106.岛屿的周长
题目：106. 岛屿的周长 (kamacoder.com)
思路：逐个遍历1，计算每个1跟临近的0所形成的边界，加起来，就是周长
尝试（示例输出正确，提交后输出错误）
import java.util.*;
class Main{
public static int n;
public static int m;
public static int[][] grid;
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
grid = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
grid[i][j] = scanner.nextInt();
}
}
int maxArea = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
maxArea+=count(i,j);
}
}
System.out.println(maxArea);
}
public static int count(int i,int j){
if(grid[i][j]!=1) return 0;
int len = 0;
if(grid[i-1][j]==0){
len++;
}
if(grid[i+1][j]==0){
len++;
}
if(grid[i][j-1]==0){
len++;
}
if(grid[i][j+1]==0){
len++;
}
return len;
}
}答案
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 行数
int m = scanner.nextInt(); // 列数
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = scanner.nextInt();
}
}
int landCount = 0; // 陆地数量
int neighborCount = 0; // 相邻陆地的数量
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
landCount++; // 统计总的陆地数量
// 统计上边相邻陆地
if (i - 1 >= 0 && grid[i - 1][j] == 1) neighborCount++;
// 统计左边相邻陆地
if (j - 1 >= 0 && grid[i][j - 1] == 1) neighborCount++;
// 下边和右边的相邻陆地不统计是为了避免重复计算
}
}
}
// 计算岛屿的周长
int perimeter = landCount * 4 - neighborCount * 2;
System.out.println(perimeter);
}
}
小结
注意每次只统计上边和左边的相邻陆地
