1.小美的外卖订单【简单题】
题意理解：
这道题是简单题，主要是一个逻辑实现和判断的问题。但是简单题一般喜欢加一点小障碍，所以读题的时候就要比较注意一些约束条件。就比如这道题：过了15/20个测试用例，出现error, 当时没明白到底哪里校验有问题，最后发现： 原价、折扣、满减都是正实数。所谓正实数：没有0！！！
正实数：是实数（real numbers）中的一个重要概念，它们是大于0的所有实数。正实数包括正整数、正分数（即正小数）以及正无理数。
还涉及一些边边角角的考核： 小数点保留两位
解题思路：
1.计算每道菜的折扣价 原价-折扣价，注意约束条件判断：原价>=折扣价>0
2.统计所有菜原价sum1
3.统计所有菜折扣价sum2
4.判断原价是否满足满减 sum1>=满减>0,并返回满减后的价格给sum1
5.返回最优惠min(sum1,sum2)
1.题目实现
import java.text.DecimalFormat;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
double[][] prices = new double[n][2];
for (int i = 0; i < n; i++) {
prices[i][0] = in.nextDouble();
prices[i][1] = in.nextDouble();
}
double x = in.nextDouble();
double y = in.nextDouble();
System.out.println(main.compute(prices, x, y));
}
public String compute(double[][] prices, double x, double y) {
if (x==0||y==0||x < y|| y<0) return "error";
double cost1 = 0.0;
double cost2 = 0.0;
for (int i = 0; i < prices.length; i++) {
if(prices[i][0]==0||prices[i][0]==0) return "error";
if (prices[i][0] >= prices[i][1]&&prices[i][1]>0) {
cost1 += prices[i][0];
cost2 += prices[i][1];
} else {
return "error";
}
}
double minCost = cost2;
//满减否
if (cost1 >= x) { //满足满减条件
minCost = Math.min(minCost, cost1 - y);
}
DecimalFormat df = new DecimalFormat("#.00");
return df.format(minCost);
}
}2.复杂度分析
时间复杂度：O(n) 遍历菜的时间损耗
空间复杂度：O(n) 存储菜的空间损耗
2.小美的字符串匹配度【不难，但题看错了气死！】
题意理解：
这道题想复杂了，原因是题没读明白，所以读题真的太重要了！！！
这题给定两个字符串，从头开始往后匹配
对于字符串可以操作一次两个元素换位置，最多操作一次，可以不操作
最终，我们能获得的最大匹配是多少？
解题思路：
实现：借鉴大佬思路
遍历s和t,将对应位置上匹配到的元素剔除，删除后，上下元素坐标一致且值不同
如："abacd"和"aabdd“ 操作完 ”bca“ 和”abd“
bac和abd中，遍历s: bac ，若取到b,i=0；
在t:abd中找可以匹配的b ,如j=1时，匹配
此时有个需要额外注意的点：
s[i]=b == t[j]==b 将t串，i|j位置互换，在i位置上获得一个匹配，+1
额外的判断： s[j]==t[i] 交换后，对应的j位置是否能再次获得一个匹配呢？
1.题目实现
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String s1 = in.nextLine();
String s2 = in.nextLine();
System.out.println(main.compute(s1, s2));
}
public int compute(String s1, String s2) {
int pairs = 0;
int len = s1.length(); //s1和s2等长
StringBuilder sb1 = new StringBuilder(s1);
StringBuilder sb2 = new StringBuilder(s2);
//在s2中找s1的匹配
for (int i = 0; i < len; i++) {
if (sb1.charAt(i) == sb2.charAt(i)) {
sb1.deleteCharAt(i);
sb2.deleteCharAt(i);
i--;//第i个被删除后，回溯到前一个
len--;
pairs++;
}
}
len = sb1.length();
int changePairs = 0;
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if (sb1.charAt(i) == sb2.charAt(j) || sb1.charAt(i) == sb2.charAt(j)) {
changePairs = Math.max(1, changePairs);
}
if (sb1.charAt(i) == sb2.charAt(j) && sb1.charAt(j) == sb2.charAt(i)) {
changePairs = 2;
break;//最多增加两个匹配，不会再多了，所以可以退出了
}
}
}
return pairs+changePairs;
}
}2.复杂度分析
时间复杂度：O(n^2) 双for时间损耗
空间复杂度：O(2n) 两字符串长度空间损耗
3.小美的树上染色【有难度，但是很大原因是题看错了】
题意理解：
按照要求对节点染色，要求染色的节点最多。
相邻为染色且和为平方数的两节点染色。
这道题目是：一定要染红嘛？想复杂了，如果可以染色，一定要染。然后这道题变成了简单题。一定要仔细看题看题。
看了大佬解题思路有个地方不明白，为什么要从后往前遍历边呢？
反着测试用例过不去，不理解！有懂得大佬能给我讲讲嘛~
解题思路：
1.遍历所有的边，判断两节点是否满足染色要求：相邻为染色且和为平方数的两节点染色。
2.符合条件：两节点染色，sum+=2
1.题目实现
import java.util.*;
public class Main {
public static void main(String[] args) {
Main solution=new Main();
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int[][] node=new int[n][2];
for(int i=0;i<n;i++){
node[i][0]=in.nextInt();
node[i][1]=0;
}
int[][] lines=new int[n-1][2];
for(int i=0;i<n-1;i++){
lines[i][0]=in.nextInt()-1;
lines[i][1]=in.nextInt()-1;
}
System.out.println(solution.compute(n,node,lines));
}
/**
* 计算染色节点
* @param n 节点个数
* @param node 0是权值，1是颜色；（0白色1红色）
* @param lines 边关系
* @return
*/
public int compute(int n,int[][] node,int[][] lines){
int result=0;
for(int i=lines.length-1;i>=0;i--){
//两个相邻白色节点
if(node[lines[i][0]][1]==0&&node[lines[i][1]][1]==0){
//是平方数
float product=node[lines[i][0]][0]*node[lines[i][1]][0];
if(Math.sqrt(product)-(int)Math.sqrt(product)==0){
node[lines[i][0]][1]=1;
node[lines[i][1]][1]=1;
result+=2;
}
}
}
return result;
}
}
2.复杂度分析
时间复杂度: O(n)遍历边
空间复杂度：O(n^2) 边、节点的存储
4.小美的排列询问【简单题】
题意理解：
遍历数组，查看给出的元素是否相邻即可
解题思路：
1.遍历数组，找到其中一个元素
2.查看另一个元素是否在该元素的左|右
3.若在Yes
4.不在则下一个，遍历完都找不到，No
1.题目实现
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
int x = in.nextInt();
int y = in.nextInt();
System.out.println(main.compute(nums, x, y));
}
public String compute(int[] nums, int x, int y) {
int a = Math.min(x, y);
int b = Math.max(x, y);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == a && ((i + 1) < nums.length && nums[i + 1] == b || i - 1 >= 0 &&
nums[i - 1] == b)) return "Yes";
else if (nums[i] == a && !((i + 1) < nums.length && nums[i + 1] == b ||
i - 1 >= 0 && nums[i - 1] == b)) return "No";
}
return "No";
}
}2.复杂度分析
时间复杂度：O(n) 遍历数组的时间损耗
空间复杂度：O(n) 数组存储的空间损耗
5.小美的排列构造【这也是道简单题】
题意理解：
首先明确：数组权值：对相邻两项求和，其中最大值和最小值的差值
为了绕让权值尽可能的小
就要使相临两数之间的和差不多的大。
一个思路是：首先对数组进行排序。
从数组末尾取数据，往数组前面的元素间插入，总是一个小值，一个大值的。
但是测试没过，不知道哪里的问题。——错在了，奇数个元素时，漏了一个元素
解题思路：
1.题目实现
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(main.compute(n));
}
public String compute(int n){
StringBuilder sb=new StringBuilder();
for(int i=1;i<=n/2;i++){
sb.append(i+" "+(n-i+1)+" ");
}
if(n%2!=0){
sb.append((n+1)/2);
}
return sb.toString();
}
}2.复杂度分析
特别有意思的一点：【记录一下】
用String result+""拼接字符串，超时了
但是用StringBulider是可以的
时间复杂度：O(n/2)遍历一半数据的时间损耗
空间复杂度：O(n)存储数据的空间损耗
6.小美走公路【简单题】
题意理解：
由于是环形公路，所有从x到y站无非两种方式：顺时针|逆时针
可以统计全程sum，和x到y的顺时针长度len1,则逆时针sum-len1
解题思路：
1.遍历所有的站点到下一站距离
2.统计全程长度sum
3.当遍历到x站点开始统计长度len1,到站点y结束
4.返回min（sum-le1,len1）
1.题目实现
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main=new Main();
Scanner in = new Scanner(System.in);
int n=in.nextInt();
long[] a=new long[n];
for(int i=0;i<n;i++){
a[i]=in.nextLong();
}
long x=in.nextLong();
long y=in.nextLong();
System.out.println(main.compute(a,x,y));
}
public long compute(long[] a,long x,long y){
long start=Math.min(x,y);
long end=Math.max(x,y);
long sum=0;//整圈
long left=0;//从start->end
for(int i=0;i<a.length;i++){
if(i>=start-1&&i<end-1) left+=a[i];
sum+=a[i];
}
return Math.min(left,sum-left);
}
}2.复杂度分析
时间复杂度分析：O(n) 遍历站点的时间损耗
空间复杂度分析：O(n) 站点存储的时间损耗
7.小美的好矩阵【感觉自己思路没错，但是测试用例没过】
题意理解：
在n*m的矩阵中找到一个符合好矩阵的条件矩阵。有多少个？
解题思路：
row[i][j]:第i行，第j个位置，构造一个行，是否满足好矩阵一个行的条件：true|false
思路是这样的，首先对每行的每个位置开始，构造一个行，判断其是否符合好矩阵的行。
contains[i][j][k]:第i行，第j个位置，构造一个行，包含ABC的个数:k=0:A,k=1:B,k=3:C
col[i][j]:第i列，第j个位置，构造一个列，是否满足好矩阵一个列的条件：true|false
对每列的每个位置开始，构造一个列，判断其是否符合好矩阵的列。
1.题目实现
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main=new Main();
Scanner in = new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
in.nextLine();
char[][] map=new char[n][m];
for(int i=0;i<n;i++){
map[i]=in.nextLine().toCharArray();
}
System.out.println(main.compute(map,n,m));
}
public int compute(char[][] map,int n,int m) {
boolean[][] row = new boolean[n][m];
boolean[][] col = new boolean[n][m];
boolean[][][] contains=new boolean[n][m][3];
Deque<int[]> queue = new LinkedList<>();
//初始化:行检测
for (int i = 0; i < n; i++) {//行检测
for (int j = 0; j < m; j++) {
if (queue.size() == 3) {
queue.pollFirst();
}
if ("ABC".contains(Character.toString(map[i][j]))) {
if(!queue.isEmpty()){
int pre_i = queue.peekLast()[0], pre_j = queue.peekLast()[1];
if (map[pre_i][pre_j] == map[i][j]) {//与前一个重复，丢弃前面的
queue.clear();
}
}
queue.offerLast(new int[]{i, j});//加入最新元素
if (queue.size() == 3) {
row[i][j] = true;//当前及前两个构成一个结果
if(map[i][j]=='A'||map[i][j-1]=='A'||map[i][j-2]=='A') contains[i][j][0]=true;
if(map[i][j]=='B'||map[i][j-1]=='B'||map[i][j-2]=='B') contains[i][j][1]=true;
if(map[i][j]=='C'||map[i][j-1]=='C'||map[i][j-2]=='C') contains[i][j][2]=true;
}
} else {
queue.clear();
}
}
queue.clear();
}
queue.clear();
//初始化:列检测
for (int j = 0; j < m; j++) { //列检测
for (int i = 0; i < n; i++) {
if (queue.size() == 3) {
queue.pollFirst();
}
if ("ABC".contains(Character.toString(map[i][j]))) {
if(!queue.isEmpty()){
int pre_i = queue.peekLast()[0], pre_j = queue.peekLast()[1];
if (map[pre_i][pre_j] == map[i][j]) {//与前一个重复，丢弃前面的
queue.clear();
}
}
queue.offerLast(new int[]{i, j});//加入最新元素
if (queue.size() == 3) {
col[i][j] = true;//当前及前两个构成一个结果
}
} else {
queue.clear();
}
}
queue.clear();
}
//九宫格检查
int result = 0;
for (int i = 2; i < n; i++) {
for (int j = 2; j < m; j++) {
//矩阵里有没有ABC:查三行元素
//containsC[i][j]||containsC[i-1][j]||containsC[i-2][j])
//三行检测:倒着数三行
//row[i][j]&&row[i-1][j]&&row[i-2][j]
//三列检测:倒着数三行
//col[i][j]&&col[i][j-1]&&col[i][j-2]
if ((contains[i][j][0]||contains[i-1][j][0]||contains[i-2][j][0])&&//有A
(contains[i][j][1]||contains[i-1][j][1]||contains[i-2][j][1])&&//有B
(contains[i][j][2]||contains[i-1][j][2]||contains[i-2][j][2])&&//有C
row[i][j] && row[i - 1][j] && row[i - 2][j] &&
col[i][j] && col[i][j - 1] && col[i][j - 2]) {
result++;
}
}
}
return result;
}
}2.复杂度分析
时间复杂度：O(n*m) 双for的时间损耗
空间复杂度：O(n*m*3) contains的空间损耗
这道题主要难在了判断和分析上，要做到准确且不漏
8.小美的蛋糕切割【简单题】
题意理解：
切蛋糕，这里把蛋糕看成n*m个小格子组成的整体，不能把小格子切开，所以切蛋糕的位置就是（n+m），切开之后，美味度是每部分小格子权值和
解题思路：
1.遍历横切n个位置，求每次的最小美味度差值
2.遍历竖切m个位置，求每次的最小美味度差值
3.返回最小美味度差值（此处差值求绝对值）
1.题目实现
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Main main=new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] cake=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cake[i][j]=in.nextInt();
}
}
System.out.println(main.compute(cake,n,m));
}
public int compute(int[][] cake,int n,int m){
long[] row=new long[n];
long[] col=new long[m];
long sum=0;
long minResult=Integer.MAX_VALUE;
//行计数+总和计数
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
row[i]+=cake[i][j];
}
sum+=row[i];
}
//列计数
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
col[j]+=cake[i][j];
}
}
//遍历横刀切
long cake1=0,cake2=0;
for(int i=0;i<=n-1;i++){
cake1+=row[i];
cake2=sum-cake1;
minResult=Math.min(minResult,Math.abs(cake1-cake2));
}
//遍历横刀切
cake1=0;cake2=0;
for(int j=0;j<=m-1;j++){
cake1+=col[j];
cake2=sum-cake1;
minResult=Math.min(minResult,Math.abs(cake1-cake2));
}
return (int)minResult;
}
}2.复杂度分析
时间复杂度：O(n^2) 双for循环损耗
空间复杂度：O(n^2) cake数组空间损耗
9.小美的字符串变换【困难：图相关的没复习】
题意理解：
看大佬的做法，这是dfs，深度遍历，但是emmmm，图论没有好好复习哎。
借鉴了下大佬思路，其实不难。就是递归遍历图，和遍历树是一样的。只是这里借助一个uesd存储访问状态。
解题思路：
将字符串n铺成一个矩阵
该矩阵的权值：连通块数
欲求最小的连通块数。
1.遍历所有可能的矩阵组合，即n%i==0
2.在每一个可能的矩阵组合中，统计联通图个数。
3.统计连通图个数用count来维护，dfs(map, used, x, y, ++count);
每找到一个连通图，count++(同一块，count相同)
如：矩阵：aababbabb used中的count: [1, 1, 2, 3, 4, 4, 5, 6, 6]
1.解题思路
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String input = in.nextLine();
Main main = new Main();
System.out.println(main.compute(n, input));
}
public int compute(int n, String s) {
int res = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) {
if (n % i == 0) { //摆阵
char[][] map = new char[i][n / i];
int[][] used = new int[i][n / i];
//赋值
int index = 0;
for (int x = 0; x < i; x++) {
for (int y = 0; y < n / i; y++) {
map[x][y] = s.charAt(index++);
}
}
//dfs计算联通图树
//赋值
int count = 0;
for (int x = 0; x < i; x++) {
for (int y = 0; y < n / i; y++) {
//寻找每一个
if (used[x][y] == 0) {
dfs(map, used, x, y, ++count);
}
}
}
res = Math.min(res, count);
}
}
return res;
}
public void dfs(char[][] map, int[][] used, int i, int j, int count) {
/**
* i,j越界或该位置已被访问过
*/
if (i < 0 || j < 0 || i > map.length - 1 || j > map[0].length - 1 ||
used[i][j] != 0) return;
used[i][j] = count;
/**
* 像四个位置尝试扩展
*/
if (i > 0 && map[i][j] == map[i - 1][j]) {
dfs(map, used, i - 1, j, count);
}
if (i < map.length - 1 && map[i][j] == map[i + 1][j]) {
dfs(map, used, i + 1, j, count);
}
if (j > 0 && map[i][j] == map[i][j - 1]) {
dfs(map, used, i, j - 1, count);
}
if (j < map[0].length - 1 && map[i][j] == map[i][j + 1]) {
dfs(map, used, i, j + 1, count);
}
}
}2.复杂度分析
时间复杂度：O(n^3) 矩阵构建的时间耗费（O(n^2)）*dfs的时间耗费（dfs，查联通分量每个节点访问一次，总的是O（n））
空间复杂度：O(n^2) uesd及map的空间耗费
![[伴学笔记]02-应用视角的操作系统 [南京大学2024操作系统]](https://img-blog.csdnimg.cn/direct/2430961b70ed4d66bc05823d1d46e012.png)
