基础知识点
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);// 输入nint n = scan.nextInt();// 吸收换行符scan.nextLine();// 动态数组listArrayList<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,说明这是一个环,然后更新最大的崇拜圈长度。就这么简单!