当前位置:   article > 正文

华为OD刷题C卷 - 每日刷题 23(提取字符串中的最长表达式,模拟目录管理功能 - 完整实现)

华为OD刷题C卷 - 每日刷题 23(提取字符串中的最长表达式,模拟目录管理功能 - 完整实现)

1、提取字符串中的最长表达式

目标是从一个给定的字符串中提取出最长的合法简单数学表达式,并计算该表达式的值。如果存在多个同样长度的合法表达式,则选择第一个出现的表达式进行计算。

简单数学表达式的规则:
只包含0-9的数字和+、-、*三种运算符。
所有数字的计算结果不超过long类型的最大值。
表达式中操作符不能连续出现,例如"±-+1"是非法的。
如果有多个相同长度的合法表达式,选择第一个出现的表达式。
表达式必须是最长的合法表达式。

2、(模拟目录管理功能 - 完整实现):

这段 Java 代码是模拟目录管理功能的完整实现。它定义了 Main 类和两个辅助类 TreeNode 与 Tree。Tree 类包含了目录树的数据结构和基本操作,如创建目录、切换目录和获取当前路径。

main 方法处理标准输入中的命令序列,并根据命令更新目录树的状态,最终输出最后一条命令的执行结果。

// Hard.java

package OD340;

import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @description 提取字符串中的最长表达式
 * @level 7
 * @score 100
 * @type 双指针、正则表达式、栈
 */


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Hard {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(getMaxMath(str));

    }

    //提取字符串中最长合法表达式并计算值(只包含两个操作数的,且第一个数带正负号),如有多个长度一样,则返回第一个
    public static long getMaxMath(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        //创建正则 匹配 (带正负号0个或1个) 数字1个或多个,然后是 + - * 必须1个 ,然后是 (不带正负号的数字)1个或多个
        //Pattern pattern = Pattern.compile("^([+-]?\\d+)([+*-]{1}\\d+)$");
        //如果匹配不只两个操作数
        Pattern pattern = Pattern.compile("^([+-]?\\d+)(([+*-]\\d+)+)([+*-]\\d+)$");

        int max = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = str.substring(i, j + 1);
                Matcher matcher = pattern.matcher(sub);
                //如果匹配成功,且长度大于当前保存的最长,则更新
                if (matcher.find() && sub.length() > max) {
                    max = sub.length();
                    sum = cal(sub);
                }
            }
        }
        return sum;
    }


    //计算合法且无括号表达式的值:如 1 + 2 * 3 返回 7
    public static long cal(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        //存放操作数
        Stack<Long> stack = new Stack<>();
        //初始化符号和数字
        long number = 0;
        char sign = '+';
        //默认符号为"+" 即使第一位是-1 会+0 再 -1
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            //如果遇到数字,拼数字
            if (c >= '0' && c <= '9') {
                number = number * 10 + (c - '0');
            }
            //没有括号和空格等不合法行为
            //遇到符号或已经到最后一位,将数字入栈、并刷新符号和数字
            if (!Character.isDigit(c) || i == n - 1) {
                if (sign == '+') {
                    //该数字前面符号是“+”直接入栈
                    stack.push(number);
                } else if (sign == '-') {
                    //该数字前面的符号是“-”,变负数后入栈
                    stack.push(-1 * number);
                } else if (sign == '*') {
                    //该数字前面是乘,弹出一个相乘后再入栈
                    stack.push(stack.pop() * number);
                }
                //刷新符号
                sign = c;
                //刷新数字
                number = 0;
            }
        }
        //将栈中的操作数求和
        long sum = 0;
        for (long i : stack) {
            sum += i;
        }
        return sum;
    }
}

// Main.java

package OD340;

import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @description 提取字符串中的最长表达式
 * @level 7
 * @score 100
 * @type 双指针、正则表达式、栈
 */

/**
 * 题目描述
 * 提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0
 * <p>
 * 简单数学表达式只能包含以下内容:
 * <p>
 * 0-9数字,符号+-*
 * 说明:
 * <p>
 * 所有数字,计算结果都不超过long
 * 如果有多个长度一样的,请返回第一个表达式的结果
 * 数学表达式,必须是最长的,合法的
 * 操作符不能连续出现,如 +--+1 是不合法的
 * 输入描述
 * 字符串
 * <p>
 * 输出描述
 * 表达式值
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        System.out.println(getMaxMath(str));

    }

    //提取字符串中最长合法表达式并计算值(只包含两个操作数的,且第一个数带正负号),如有多个长度一样,则返回第一个
    public static long getMaxMath(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        //创建正则 匹配 (带正负号0个或1个) 数字1个或多个,然后是 + - * 必须1个 ,然后是 (不带正负号的数字)1个或多个
        Pattern pattern = Pattern.compile("^([+-]?\\d+)([+*-]{1}\\d+)$");
        //如果匹配不只两个操作数

        int max = 0;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = str.substring(i, j + 1);
                Matcher matcher = pattern.matcher(sub);
                //如果匹配成功,且长度大于当前保存的最长,则更新
                if (matcher.find() && sub.length() > max) {
                    max = sub.length();
                    sum = cal(sub);
                }
            }
        }
        return sum;
    }


    //计算合法且无括号表达式的值:如 1 + 2 * 3 返回 7
    public static long cal(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        //存放操作数
        Stack<Long> stack = new Stack<>();
        //初始化符号和数字
        long number = 0;
        char sign = '+';
        //默认符号为"+" 即使第一位是-1 会+0 再 -1
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            //如果遇到数字,拼数字
            if (c >= '0' && c <= '9') {
                number = number * 10 + (c - '0');
            }
            //没有括号和空格等不合法行为
            //遇到符号或已经到最后一位,将数字入栈、并刷新符号和数字
            if (!Character.isDigit(c) || i == n - 1) {
                if (sign == '+') {
                    //该数字前面符号是“+”直接入栈
                    stack.push(number);
                } else if (sign == '-') {
                    //该数字前面的符号是“-”,变负数后入栈
                    stack.push(-1 * number);
                } else if (sign == '*') {
                    //该数字前面是乘,弹出一个相乘后再入栈
                    stack.push(stack.pop() * number);
                }
                //刷新符号
                sign = c;
                //刷新数字
                number = 0;
            }
        }
        //将栈中的操作数求和
        long sum = 0;
        for (long i : stack) {
            sum += i;
        }
        return sum;
    }
}


// Simple.java

package OD340;

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @description 简单版
 * @level 7
 * @score 100
 * @type 双指针、正则表达式、栈
 */

/**
 * 题目描述
 * 提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0
 * <p>
 * 简单数学表达式只能包含以下内容:
 * <p>
 * 0-9数字,符号+-*
 * 说明:
 * <p>
 * 所有数字,计算结果都不超过long
 * 如果有多个长度一样的,请返回第一个表达式的结果
 * 数学表达式,必须是最长的,合法的
 * 操作符不能连续出现,如 +--+1 是不合法的
 * 输入描述
 * 字符串
 * <p>
 * 输出描述
 * 表达式值
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Simple {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        //简单合法表达式为只有两个操作数 如 1+1 -1+1 +1+1都是合法的
        //正则包含三部分:开头^(含有0个或1个符号的数字1个到多个) (操作符+-*) (数字1个到多个)$结尾
        Pattern pattern = Pattern.compile("^([+-]?\\d+)([+*-])(\\d+)$");
        int maxLength = 0;
        long sum = 0;
        //遍历
        for (int i = 0; i < str.length(); i++) {
            for (int j = i; j < str.length(); j++) {
                String sub = str.substring(i, j + 1);
                Matcher matcher = pattern.matcher(sub);
                //如果匹配到且长度大于当前保存的长度,则更新
                if (matcher.find() && sub.length() > maxLength) {
                    maxLength = sub.length();
                    //求解 使用matcher.group(1)和matcher.group(3)分别获取两个数字
                    long num1 = Long.parseLong(matcher.group(1));
                    long num2 = Long.parseLong(matcher.group(3));
                    //操作符
                    String sign = matcher.group(2);
                    switch (sign) {
                        case "+":
                            sum = num1 + num2;
                            break;
                        case "-":
                            sum = num1 - num2;
                            break;
                        case "*":
                            sum = num1 * num2;
                            break;
                    }

                }
            }
        }
        System.out.println(sum);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
package OD341;

import java.util.HashMap;
import java.util.Scanner;

/**
 * @description 模拟目录管理功能
 * @level 6
 * @score 200
 * @url https://hydro.ac/d/HWOD2023/p/OD341
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //初始化目录树
        Tree tree = new Tree();

        //记录最后一条命令的输出 除了pwd有输出,其他都输出空
        //输出为空时要输出根目录"/" 才能百分百解法
        String command_output = "/";

        outer:
        while (sc.hasNextLine()) {
            String line = sc.nextLine();

            String[] tmp = line.split(" ");

            //命令 mkdir cd pwd
            String cmd_key = tmp[0];
            //参数
            //String cmd_val =  tmp[1];//pwd没有参数,可能会越界
            //常量在前面,防止空指针异常
            if ("pwd".equals(cmd_key)) {
                //pwd不需要参数,有参数的错误输入什么都不需要干
                if (tmp.length != 1) continue;
                //否则,就将当前命令的输出结果保存
                command_output = tree.pwd();
            } else if ("mkdir".equals(cmd_key) || "cd".equals(cmd_key)) {
                //参数只能有1个
                if (tmp.length != 2) continue;

                //目录名
                String cmd_val = tmp[1];

                //除了 cd .. 不需要检测 其他都需要检测文件名是否合法
                if (!(cmd_key.equals("cd") && cmd_val.equals(".."))) {
                    for (int i = 0; i < cmd_val.length(); i++) {
                        char c = cmd_val.charAt(i);
                        //不合法,直接跳到下一个命令
                        if (c < 'a' || c > 'z') continue outer;
                    }
                }

                //实现操作
                if ("mkdir".equals(cmd_key)) {
                    tree.mkdir(cmd_val);
                    //mkdir操作没有输出,清空当前保存的最后输出
                    command_output = "/";
                } else {
                    //cd
                    tree.cd(cmd_val);
                    //清空
                    command_output = "/";
                }
            }
        }
        //输出最后一条命令的输入,如果是mkdir cd 则没有输出
        System.out.println(command_output);
    }

    //节点 包含父目录 子目录<>
    static class TreeNode {
        //目录名
        String curDicName;
        //父目录
        TreeNode fa;
        //子目录:<子目录名,子目录对象>
        HashMap<String, TreeNode> ch;

        //构造方法 新建一个节点<节点名,父目录>
        public TreeNode(String curDicName, TreeNode fa) {
            this.curDicName = curDicName;
            this.fa = fa;
            this.ch = new HashMap<>();
        }
    }

    //目录树
    static class Tree {
        //根节点
        TreeNode root;
        //当前层
        TreeNode cur;

        //默认无参构造方法
        public Tree() {
            //根节点 视为名称为/
            this.root = new TreeNode("/", null);
            this.cur = root;
        }

        //新建目录
        public void mkdir(String dicName) {
            //如果有同名子目录,则不做任务操作
            //子目录名,子目录对象(名称+"/",该子目录的父目录)
            this.cur.ch.putIfAbsent(dicName, new TreeNode(dicName + "/", this.cur));
        }

        //进入目录
        public void cd(String dicName) {
            //cd .. 防止空指针异常
            if ("..".equals(dicName)) {
                //如果上层不为空,则进入上层
                if (this.cur.fa != null) {
                    this.cur = this.cur.fa;
                }
                //如果为空,不进行任何操作
            } else {
                //cd dicName
                //有同名子目录才进入
                if (this.cur.ch.containsKey(dicName)) {
                    //进入
                    this.cur = this.cur.ch.get(dicName);
                }
                //没有同名子目录则不做任何操作
            }
        }

        //pwd
        public String pwd() {
            StringBuilder sb = new StringBuilder();

            //从当前层遍历到root,每次插入到头部,即倒序
            TreeNode cur = this.cur;
            while (cur != null) {
                // c/ -> b/c/ -> a/b/c/ -> /a/b/c/
                sb.insert(0, cur.curDicName);
                cur = cur.fa;
            }
            return sb.toString();
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/708969
推荐阅读
相关标签
  

闽ICP备14008679号