[关闭]
@yexiaoqi 2022-05-21T01:07:56.000000Z 字数 1052 阅读 388

HJ70. 矩阵乘法计算量估算

刷题


题目:矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如:A是一个50×10的矩阵,B是10×20的矩阵,C是20×5的矩阵。计算A*B*C有两种顺序:((AB)C)或者(A(BC)),前者需要计算15000次乘法,后者只需要3500次。编写程序计算不同的计算顺序需要进行的乘法次数。

数据范围:矩阵个数:1≤n≤15,行列数:1≤rowi,coli≤100,保证给出的字符串表示的计算顺序唯一。
进阶:时间复杂度:O(n),空间复杂度:O(n)

输入描述:输入多行,先输入要计算乘法的矩阵个数n,每个矩阵的行数,列数,总共2n的数,最后输入要计算的法则。计算的法则为一个字符串,仅由左右括号和大写字母('A'~'Z')组成,保证括号是匹配的且输入合法!
输出描述:输出需要进行的乘法次数
链接https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b


栈相关的需要画图,图画出来就明白了

  1. public class Main {
  2. public static void main(String[] args){
  3. Scanner sc = new Scanner(System.in);
  4. while(sc.hasNext()){
  5. int n = sc.nextInt();
  6. int[][] nums = new int[n][2];
  7. for(int i=0; i<n; i++){
  8. nums[i][0] = sc.nextInt();
  9. nums[i][1] = sc.nextInt();
  10. }
  11. String s = sc.next();
  12. Stack<Integer> stack = new Stack<>();
  13. int count=0;
  14. for(int i=s.length()-1,j=n-1; i>=0; i--){
  15. char c=s.charAt(i);
  16. if(c>='A' && c<='Z'){
  17. stack.push(nums[j][0]);//行
  18. stack.push(nums[j][1]);//列
  19. j--;
  20. } else if (c=='('){
  21. //倒序遍历+行先入栈,所以先出来的是y
  22. Integer y=stack.pop();
  23. Integer x=stack.pop();
  24. Integer z=stack.pop();
  25. stack.pop();//出栈的是 y
  26. //计算量
  27. count+=x*y*z;
  28. //再把x,z加进去
  29. stack.push(x);
  30. stack.push(z);
  31. }
  32. }
  33. System.out.println(count);
  34. }
  35. }
  36. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注