算法:小记两道牛客的算法题

问题

• 比较麻烦的是输入部分，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

总结

• 算法反正就这么几种，最好用的估计就是动态规划和递归了，哈哈哈或者说我用的最熟练的；
• 以后加油；