rambless

矩阵乘法计算量估算

https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            List<Point> list = new ArrayList<>(n);
            Point p;
            for (int i = 0; i < n; i++) {
                p = new Point(in.nextInt(), in.nextInt());
                list.add(p);
            }
            in.nextLine();
            String str = in.nextLine();
            String s = str.replace("(", "").replace(")", "");
            Point temp = cal(str, s, list);
            System.out.println(temp.z);
        }
    }

    //利用栈的特性实现运算顺序
    private static Point cal(String str, String s, List<Point> list) {
        Point p;
        Deque<Point> stack = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            //如果是括号则递归算括号里边的
            if (str.charAt(i) == '(') {
                int count = 1;
                int j = i + 1;
                while (count > 0 && j < str.length()) {
                    if (str.charAt(j) == ')') {
                        count--;
                    } else if (str.charAt(j) == '(') {
                        count++;
                    }
                    j++;
                }
                stack.push(cal(str.substring(i + 1, j - 1), s, list));
                //回溯
                i = j;
            }

            if (i < str.length()) {
                //由于括号后边可能还有括号,需继续括号逻辑
                if (str.charAt(i) == '(') {
                    int num = 1;
                    int m = i + 1;
                    while (num > 0 && m < str.length()) {
                        if (str.charAt(m) == ')') {
                            num--;
                        } else if (str.charAt(m) == '(') {
                            num++;
                        }
                        m++;
                    }
                    stack.push(cal(str.substring(i + 1, m - 1), s, list));
                    //回溯
                    i = m;
                } else if (str.charAt(i) == ')') {
                    //输入合法时不存在此情况
                } else {
                    //矩阵时直接压栈
                    p = list.get(s.indexOf(str.substring(i, i + 1)));
                    stack.push(p);
                }
            }

        }

        Point pre = stack.pop();
        Point temp;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            int num = temp.x * temp.y * pre.y + pre.z + temp.z;
            pre = new Point(temp.x, pre.y, num);
        }
        return pre;
    }

    static class Point {
        int x;
        int y;
        int z = 0;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

}

全部评论

相关推荐

05-21 15:47
门头沟学院 Java
浪漫主义的虹夏:项目有亮点吗,第一个不是纯玩具项目吗,项目亮点里类似ThreadLocal,Redis储存说难听点是花几十分钟绝大部分人都能学会,第二个轮子项目也没体现出设计和技术,想实习先沉淀,好高骛远的自嗨只会害了自己
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务