特辣的海藻10
特辣的海藻！10
基础知识点
1.清除换行符
scan.nextInt()要加scan.nextLine()清楚换行符。
2.Map.Entry<K, V>
Map.Entry是Map接口的嵌套接口，表示一个键值对（Key-Value）
常用方法：
entry.getKey()：获取键
entry.getValue()：获取值
entry.setValue(V value)：修改值，不常用
3.list.get(i)
从用列表list中获取第i个元素
4.entrySet()
返回Map中所有键值对的集合，类型为Set<Map.Entry<K, V»
若Map包含{1: 2, 3: 4}，则entrySet()返回两个Map.Entry对象。
5.HashSet
核心特性
- 唯一性：不允许存储重复元素
- 无序性：不保证元素的存储或访问顺序
- 允许null：可包含一个null元素
- 非线程安全：多线程环境下需要外部同步
- 基于哈希表：底层有HashMap实现，键位元素，值为固定虚拟对象
相关方法的使用
- add(E e)：添加元素，成功返回true，重复返回false
- remove(Object o)：删除元素，存在则返回true
- contais(Object o)：检查元素是否存在
- size()：返回元素数量
- isEmpty()：判断集合是否为空
- iterator()：返回迭代器，支持遍历操作
6.Character.getNumericValue()
属于Character类，这是一个静态方法，用来获取给定字符的数字值，对于大多数字符，特别是非数字字符，这个方法返回-1。
7.charAt(int indddx)
这是String类的一个实例方法，用于返回指定索引处的字符。字符串在Java中被视为一个字符序列，而charAt()方法允许你访问这个序列中的任意字符。
8.ArrayList
创建
ArrayList<String> list = new ArrayList<>();
// 指定初始容量
ArrayList<String> list2 = new ArrayList<>(10);
// 使用另一个集合初始化
ArrayList<String> list3 = new ArrayList<>(list);
- add(int index, E e)：在指定位置添加元素，如果没有index就直接添加在后面
- get(int index)：访问特定位置元素
- set(int index, E element)：替换指定位置元素
- size()：返回列表中元素的数量
- isEmpty()：判断列表是否为空
- clear()：清空列表中的所有元素
- contains(Object o)：检查列表是否包含某个特定元素
- indexOf(Object o) 和 lastIndexOf(Object o)：分别返回元素首次和最后一次出现的位置
9.Integer与int的区别
int：Java的基本数据类型，直接存储数值
Integer：int的包装类，是一个对象，存储在堆内存中
Array.sort()方法要求传入的数组是对象数组（如Integer[]），而不是基本类型数组（如int[]）
list.toArray()返回的是Object[ ]，无法直接转换为int[ ]
对于Integer, == 比较的是对象的引用，而不是值。由于Integer的缓存机制（-128到127），某些小整数的 == 比较可能正确，但大整数会出错。所以对于Integer对象，必须用equals()比较，==也可以但需要手动拆箱。
题
1.
import java.util.*;
public class Main {
private static int N;
private static boolean[][] vis;
private static char[][] grid;
private static int[] dx = {-1, 0, 1, 0};
private static int[] dy = {0, 1, 0, -1};
public static boolean bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
boolean hasInland = false;
vis[x][y] = true;
while(!queue.isEmpty()) {
int[] pos = queue.poll();
int i = pos[0], j = pos[1];
boolean isInner = true;
for(int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || nx >= N || ny < 0 || ny >= N || grid[nx][ny] != '#') {
isInner = false;
break;
}
}
if(isInner)
hasInland = true;
for(int k = 0; k < 4; k++){
int nx = i + dx[k];
int ny = j + dy[k];
if(nx >= 0 && nx < N && ny >= 0 && ny < N
&& grid[nx][ny] == '#' && !vis[nx][ny]) {
vis[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
return hasInland;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
N = scan.nextInt();
scan.nextLine();
grid = new char[N][N];
vis = new boolean[N][N];
for(int i = 0; i < N; i++) {
grid[i] = scan.nextLine().toCharArray();
}
int ans = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(grid[i][j] == '#' && !vis[i][j]) {
boolean isInland = bfs(i, j);
if(!isInland) {
ans++;
}
}
}
}
System.out.print(ans);
scan.close();
}
}这个题目是酱紫的。哎呀烦死了！让AI帮我上学工作赚钱算了！！！ 鲧！！（）
核心思路：
- 岛屿定义：由相邻（上下左右）的陆地（#）组成的连通区域
- 淹没规则：如果一个陆地块的四周存在海洋(.)或边界，它会被淹没。
- 存货条件：若岛屿中存在至少一个内部快（四周全是陆地），则岛屿存活；否则完全被淹没
实现流程
1.遍历所有陆地块：使用双重循环遍历网格中的每个单元格。如果遇到未被访问的陆地，启动bfs遍历改岛屿。
2.bfs遍历岛屿：将其起始陆地块加入队列，并标记为已访问。
3.在这个队列遍历过程中，从队列中取出一个陆地块（i, j)，检查这个陆地块是否是内部块；若该块是内部块，标记为hasInland = true。怎么判断内部块，若任意一个方向是海洋或者越界，则当前块不是内部块。仅当四个方向均为陆地时，当前块是内部块。
4.若四周未被访问的陆地块加入队列，继续遍历。
2.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str = scan.next();
int n = str.length();
int[][] dp = new int[n][n];
// 初始化长度为1的最长回文子字符串
for(int i = 0; i < n; i++)
dp[i][i] = 1;
for(int len = 2; len <= n; len++) {
for(int i = 0; i <= n-len; i++) {
int j = i + len - 1;
if(str.charAt(i) == str.charAt(j))
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
int maxLen = dp[0][n-1];
System.out.print(n - maxLen);
scan.close();
}
}找到一个最长回文子字符串，然后用原字符串的长度减去这个子字符串的长度。这是一个动态规划的问题。dp[i][j]是代表着从 i 到 j 最长的回文子字符串。
外循环遍历回文字符串所有可能的长度，len=2起始是因为回文字符串的长度最少是2；内循环遍历从下标0开始所有可能的起点。
当长度为2，起点i为0，终点j为1…
当长度为2，起点i为1，终点j为2…
当长度为2，起点i为2，终点j为3…
当长度为3，起点i为0，终点j为2…
当长度为3，起点i为1，终点j为3…
状态转移方程：
情况1：两端字符相同，如果str[i] == str[j]，则这两个字符可以加入回文子序列，dp[i][j]的值等于去掉两端后的字串str[i+1…j-1]的最长回文子串加2（因为新增了两个字符）
情况2：两端字符不同，如果str[i] != str[j]，最长回文子序列要么不包含str[i]（对应dp[i+1][j]），要么不包含s[j]（对应dp[i][j-1]）取两者最大值作为当前子串的LPS长度。
最终可以得到整个字符串的最长回文子序列长度。原问题的答案（最少脱落的种子数）即为字符串总长度减去最长回文子序列长度。
3.
题挺简单的，就是加瓦的一些相关用法不熟。。。。。
import java.util.*;
import static java.util.Collection.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// 输入n
int n = scan.nextInt();
// 吸收换行符
scan.nextLine();
// 动态数组list
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++) {
// 每一行以字符串来存储
String str = scan.nextLine();
// 字符串中的一个个字符转换成整型
for(String s : str.split(" ")) {
list.add(Integer.valueOf(s));
}
}
// 创建整型包数组
Integer[] nums = new Integer[list.size()];
// 将上述的list转为数组
nums = list.toArray(nums);
Arrays.sort(nums);
//
// for(Integer num : nums)
// System.out.print(num + " ");
int repeat = 0, jump = 0;
for(int i = 1; i < nums.length; i++) {
if(nums[i] - nums[i-1] > 1)
repeat = nums[i]-1;
if(nums[i].equals(nums[i-1]))
jump = nums[i];
}
System.out.print(repeat + " " + jump);
scan.close();
}
}还有两道简单题做过的重新写了一遍就不放了。
4.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = nnew Scanner(System.in);
int n = scan.nextInt();
int[] admire = new int[n+1];
for(int i = 1; i <= n; i++) {
admire[i] = scan.nextInt();
}
boolean[] vis = new int[n+1];
int maxCircle = 0;
for(int i = 0; i < n; i++) {
if(!vis[i]) {
int count = 0;
int cur = i;
while(!vis[cur]) {
vis[cur] = true;
cur = admire[cur];
count++;
}
if(cur == i)
maxCircle = Math.max(maxCircle, count);
}
}
System.out.print(maxCircle);
scan.close();
}
}这道题说难也不难的。。而且很熟悉的感觉。。。怎么我做不出
首先看懂题目
它的思路就是，按照数组顺序一个一个来，如果这个小朋友i没有被遍历过，那就对它进行以下操作：沿着崇拜关系遍历，用cur指针不断更新它崇拜的小朋友，同时用count记录这个崇拜圈的长度。如果cur最终回到起点 i，说明这是一个环，然后更新最大的崇拜圈长度。就这么简单！