问题
- 比较麻烦的是输入部分，letcode写习惯了，牛客网输入输出还要自己写确实不舒服；
- 全部代码需要手动哈，不像平时在androidstudio中运行好了，再复制进入letcode哈；就连导包都需要自己写；
- 错过一次机会，下次必须间隔六个月才有机会，牛客网会记录你的省份证的，所以准备充分了再去吧；
- 只记得两个了，还有一个题目记不住了，那个更简单，建好对象比较就行了，可能输入的复杂一点；
1.合法最小数
-
输入一组正整数得字符串然后组合出最小值得数并输出;
-
例如输入01 02,组合得最小是102，11 15 00 01组合得11115；
-
使用动态规划
···
import java.util.Scanner;
public class CodeHuaWeiTest {public static void main(String[] args) {
// getMin();
userSetZero();
}
}
//方法也是定义在CodeHuaWeiTest 类里面的；
public static void getMin() {
//定义输入得数据
String[] strings = new String[]{};
//使用java得输入函数
Scanner in = new Scanner(System.in);
//定义分隔
in.useDelimiter("\n");//按回车分隔
//分隔获取输入得数据
strings = in.next().split(" ");if (strings == null || strings.length == 0) System.out.println("");//输入为空 那么返回也为空 //定义dp[i] 表示 i个字符的组成的最小值的string String[] dp = new String[strings.length + 1]; //初始化空字符组成的最小值也是“” dp[0] = ""; //规律: //i个字符组成的最小值，一定是i-1个字符的最小值，然后和最后一个字符再去组合，然后比较 for (int i = 1; i <= strings.length; i++) { String b; String a = dp[i - 1] + strings[i - 1];//a值表示i-1的最小值在前，最后一个字符在后的组合比如 1121 + 01 if (Integer.valueOf(strings[i - 1]) == 0)//如果最后一个字符取值是0，那么它在前的清空就是dp[i-1] b = dp[i - 1]; else b = strings[i - 1] + dp[i - 1]; //如果b为""表示前面的都是0的组合 if (b == "") { if (Integer.valueOf(a) == 0) dp[i] = "";//同时a也是0.没得说继续"" else dp[i] = a;//否则为a } else {//不为"" 那么就需要比较大小来定了 if (Integer.valueOf(a) <= Integer.valueOf(b)) dp[i] = a; else dp[i] = b; } } if (dp[strings.length] == "") System.out.println("0"); else System.out.println(Integer.valueOf(dp[strings.length]));}
··· -
验证截图如下：
屏幕截图 2023-03-14 200254.png
2.开心消消乐
- 输入一个nxm的矩阵，矩阵的值是0或者1，每次点击1，1和它周围的1会变为0，且周围的1变为0的时候它周围的1也会变为0依次类推；
- 求讲矩阵全部变为0所需要点击的最小次数;
- 递归求解比较轻松；
错误或者说不完善的方案
- 第一步是设置输入的矩阵，放入二维数组
- 第二部是递归遍历数组取得它和它周边的1最多的点位（indexI,indexJ）
- 第三步递归将当前选择的点位设置为0，且将它周围的是1的设置为0；递归完成后返回第二部，递归调用方法获取点位，知道所有的都归零，归零完成result++；
- 所有递归完成后，输出result；
static int result = 0;//最终点击次数
static int count = 0;//当前节点附近包括它自己1的总数
static int indexI = 0;
static int indexJ = 0;
static int n, m;
public static void userSetZero() {
int[][] inputs;
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
inputs = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
inputs[i][j] = in.nextInt();
}
}
//new int[][]{{1, 1, 1}, {0, 1, 0}, {0, 1, 0}}
setZero(inputs);
System.out.println("需要点击" + result + "次");
}
//1 1 1
//0 1 0
//0 1 0
public static void setZero(int[][] inputs) {
count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int ij = inputs[i][j];
int countIJ = 0;
if (inputs[i][j] == 1) {//当前点位为1
countIJ++;
//正上
if (i - 1 >= 0 && inputs[i - 1][j] == 1) countIJ++;
//正右
if (j + 1 < m && inputs[i][j + 1] == 1) countIJ++;
//正下
if (i + 1 < n && inputs[i + 1][j] == 1) countIJ++;
//正左
if (j - 1 >= 0 && inputs[i][j - 1] == 1) countIJ++;
//坐上
if (i - 1 >= 0 && j - 1 >= 0 && inputs[i - 1][j - 1] == 1)
countIJ++;
//右上
if (i - 1 >= 0 && j + 1 < m && inputs[i - 1][j + 1] == 1)
countIJ++;
//右下
if (i + 1 < n && j + 1 < m && inputs[i + 1][j + 1] == 1)
countIJ++;
//左下
if (i + 1 < n && j - 1 >= 0 && inputs[i + 1][j - 1] == 1)
countIJ++;
}
if (count < countIJ) {
count = countIJ;
indexI = i;
indexJ = j;
}
}
}
//找到了周围1最多的点，把它和它周围的点都设置为0
if (count != 0) {
setPointZero(indexI, indexJ, inputs);
result++;
}
if (count == 0) return;
setZero(inputs);
}
//递归调用把[x,y]点和它周围和它周围的周围的1设置为0
public static void setPointZero(int x, int y, int[][] inputs) {
inputs[x][y] = 0;
//正上
if (x - 1 >= 0 && inputs[x - 1][y] == 1) setPointZero(x - 1, y, inputs);
//正右
if (y + 1 < m && inputs[x][y + 1] == 1) setPointZero(x, y + 1, inputs);
//正下
if (x + 1 < n && inputs[x + 1][y] == 1) setPointZero(x + 1, y, inputs);
//正左
if (y - 1 >= 0 && inputs[x][y - 1] == 1) setPointZero(x, y - 1, inputs);
//坐上
if (x - 1 >= 0 && y - 1 >= 0 && inputs[x - 1][y - 1] == 1)
setPointZero(x - 1, y - 1, inputs);
//右上
if (x - 1 >= 0 && y + 1 < m && inputs[x - 1][y + 1] == 1)
setPointZero(x - 1, y + 1, inputs);
//右下
if (x + 1 < n && y + 1 < m && inputs[x + 1][y + 1] == 1)
setPointZero(x + 1, y + 1, inputs);
//左下
if (x + 1 < n && y - 1 >= 0 && inputs[x + 1][y - 1] == 1)
setPointZero(x + 1, y - 1, inputs);
}
真正的方案，只要递归调用就好了
- 根本不需要判断哪里的1最多，直接碰到1递归归零，只要是连着的肯定都会归零;然后递归调用;
- 不需要找到1最多的集群，因为每次消除会连带消除，所以直接遍历碰到1就调用递归归零，然后继续遍历就完事儿了；
- 所以我还是想多了哈；
static int result = 0;
static int count = 0;
static int indexI = 0;
static int indexJ = 0;
static int n, m;
public static void userSetZero() {
int[][] inputs;
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
inputs = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
inputs[i][j] = in.nextInt();
}
}
//new int[][]{{1, 1, 1}, {0, 1, 0}, {0, 1, 0}}
// 1 1 1 1
// 0 0 0 1
// 1 1 0 0
// 1 1 0 1
setZero2(inputs);
System.out.println("需要点击" + result + "次");
}
public static void setZero2(int[][] inputs){
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (inputs[i][j] == 1) {
setPointZero(i, j, inputs);
result++;
// setZero(inputs);
}
}
}
}
//递归调用把[x,y]点和它周围和它周围的周围的1设置为0
public static void setPointZero(int x, int y, int[][] inputs) {
inputs[x][y] = 0;
//正上
if (x - 1 >= 0 && inputs[x - 1][y] == 1) setPointZero(x - 1, y, inputs);
//正右
if (y + 1 < m && inputs[x][y + 1] == 1) setPointZero(x, y + 1, inputs);
//正下
if (x + 1 < n && inputs[x + 1][y] == 1) setPointZero(x + 1, y, inputs);
//正左
if (y - 1 >= 0 && inputs[x][y - 1] == 1) setPointZero(x, y - 1, inputs);
//坐上
if (x - 1 >= 0 && y - 1 >= 0 && inputs[x - 1][y - 1] == 1)
setPointZero(x - 1, y - 1, inputs);
//右上
if (x - 1 >= 0 && y + 1 < m && inputs[x - 1][y + 1] == 1)
setPointZero(x - 1, y + 1, inputs);
//右下
if (x + 1 < n && y + 1 < m && inputs[x + 1][y + 1] == 1)
setPointZero(x + 1, y + 1, inputs);
//左下
if (x + 1 < n && y - 1 >= 0 && inputs[x + 1][y - 1] == 1)
setPointZero(x + 1, y - 1, inputs);
}
-
验证截图如图
屏幕截图 2023-03-14 200116.png
总结
- 算法反正就这么几种，最好用的估计就是动态规划和递归了，哈哈哈或者说我用的最熟练的；
- 以后加油；
网友评论