第二题  给两个数组，两个数组中的元素都是pair<int, int>，数组表示压缩后的一串数字

A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}

B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}

求A点乘B的结果，以压缩形式的返回。以上面的A，B为例，结果是[(5,1), (1,1), (9,1), (6,4)]

要求不能展开A和B以后做乘法再压缩。

 

 1 class Solution {
 2     public static void main(String[] args) {
 3         // A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
 4         // B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
 5         // 求A点乘B的结果，以压缩形式的返回。以上面的A，B为例，结果是[(5,1), (1,1), (9,1), (6,4)]
 6 
 7         Pair pair1 = new Pair(1, 2);
 8         Pair pair2 = new Pair(3, 1);
 9         Pair pair3 = new Pair(2, 3);
10         Pair pair4 = new Pair(3, 1);
11         Pair pair5 = new Pair(5, 1);
12         Pair pair6 = new Pair(1, 1);
13         Pair pair7 = new Pair(3, 4);
14         Pair pair8 = new Pair(2, 1);
15 
16         List<Pair> list1 = Arrays.asList(pair1, pair2, pair3, pair4);
17         List<Pair> list2 = Arrays.asList(pair5, pair6, pair7, pair8);
18 
19         Solution s = new Solution();
20         List<Pair> result = s.compressedVectorMultiplication(list1, list2);
21         System.out.println(result);
22     }
23 
24     public List<Pair> compressedVectorMultiplication(List<Pair> list1, List<Pair> list2) {
25         List<Pair> result = new ArrayList<>();
26         int idx1 = 0, idx2 = 0;
27 
28         while (idx1 < list1.size() && idx2 < list2.size()) {
29             Pair p1 = list1.get(idx1);
30             Pair p2 = list2.get(idx2);
31 
32             int value = p1.val * p2.val;
33             int count = Math.min(p1.count, p2.count);
34 
35             if (result.isEmpty() || result.get(result.size() - 1).val != value) {
36                 result.add(new Pair(value, count));
37             } else {
38                 result.get(result.size() - 1).count += count;
39             }
40 
41             p1.count -= count;
42             p2.count -= count;
43 
44             if (p1.count == 0) {
45                 idx1++;
46             }
47 
48             if (p2.count == 0) {
49                 idx2++;
50             }
51         }
52         return result;
53     }
54 }
55 
56 class Pair {
57     int val;
58     int count;
59 
60     public Pair(int val, int count) {
61         this.val = val;
62         this.count = count;
63     }
64 
65     public String toString() {
66         return "(" + val + "," + count + ")";
67     }
68 }