脸家店面

第一题  肆似散 简化版，输入是字符串，输出是压缩以后的字符串。只有一个字符的情况不用特别处理。
第二题  给两个数组，两个数组中的元素都是p

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

,1), (1,1), (9,1), (6,4)]
要求不能展开A和B以后做乘法再压缩。

第二题 Java version

1. import java.util.*;
   
2. 
   
3. public class LocalRun2 {
   
4. //    A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
   
5. //    B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
   
6. //    求A点乘B的结果，以压缩形式的返回。以上面的A，B为例，结果是[(5,1), (1,1), (9,1), (6,4)]
   
7. 
   
8.     public static void main(String[] args) {
   
9.         int[][] a = new int[][] {{1,2}, {3,1}, {2,3}, {3, 1}};
   
10.         int[][] b = new int[][] {{5,1}, {1,1}, {3,4}, {2, 1}};
    
11.         int[][] result = solution(a, b);
    
12.         for (int[] i : result) {
    
13.             System.out.println(Arrays.toString(i));
    
14.         }
    
15.     }
    
16. 
    
17.     public static int[][] solution(int[][] a, int[][] b) {
    
18.         int i = 0;
    
19.         int j = 0;
    
20. 
    
21.         List<int[]> list = new ArrayList<int[]>();
    
22.         while (i < a.length && j < b.length) {
    
23.             int[] currentA = a[i];
    
24.             int[] currentB = b[j];
    
25.             if (currentA[1] == 0) {
    
26.                 i++;
    
27.                 continue;
    
28.             }
    
29.             if (currentB[1] == 0) {
    
30.                 j++;
    
31.                 continue;
    
32.             }
    
33.             int min = Math.min(currentA[1], currentB[1]);
    
34.             currentA[1] -= min;
    
35.             currentB[1] -= min;
    
36.             int current = currentA[0] * currentB[0];
    
37.             if (list.isEmpty()) {
    
38.                 list.add(new int[] {current, min});
    
39.             } else {
    
40.                 int[] prev = list.get(list.size() - 1);
    
41.                 if (prev[0] == current) {
    
42.                     prev[1] = prev[1] + min;
    
43.                 } else {
    
44.                     list.add(new int[] {current, min});
    
45.                 }
    
46.             }
    
47.         }
    
48.         return list.toArray(new int[list.size()][]);
    
49.     }
    
50. }
    
51. 
    

复制代码

第二题

1. /*
   
2. A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
   
3. B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
   
4. 求A点乘B的结果，以压缩形式的返回。以上面的A，B为例，结果是[(5,1), (1,1), (9,1), (6,4)]
   
5. */
   
6. 
   
7. vector<pair<int,int>> dot_product(vector<pair<int,int>> &A, vector<pair<int,int>> &B) {
   
8.     int i = 0, j = 0;
   
9.     vector<pair<int,int>> ans;
   
10. 
    
11.     while (i < (int)A.size() && j < (int)B.size()) {
    
12.         auto &a = A[i];
    
13.         auto &b = B[j];
    
14. 
    
15.         int product = a.first * b.first;
    
16.         int len = min(a.second, b.second);
    
17. 
    
18.         if ((int)ans.size() > 0 && product == ans.back().first)
    
19.             ans.back().second += len;
    
20.         else
    
21.             ans.push_back({product, len});
    
22. 
    
23.         a.second -= len;
    
24.         if (a.second == 0) i++;
    
25.         b.second -= len;
    
26.         if (b.second == 0) j++;
    
27.     }   
    
28. 
    
29.     return ans;
    
30. }
    
31. 
    
32. int main()
    
33. {
    
34.     vector<pair<int,int>> A = {{1,2},{3,1},{2,3},{3,1}};
    
35.     vector<pair<int,int>> B = {{5,1},{1,1},{3,4},{2,1}};
    
36.     vector<pair<int,int>> C = dot_product(A, B);
    
37.     for (auto &p : C)
    
38.         cout << p.first << ", " << p.second << endl;
    
39.     return 0;
    
40. }
    

复制代码

发一个我写的python版本，欢迎指正

1. '''
   
2. A: [(1, 2), (3,1), (2,3), (3, 1)] 表示 {1, 1, 3, 2, 2, 2, 3}
   
3. B: [(5, 1), (1,1), (3,4), (2, 1)] 表示 {5, 1, 3, 3, 3, 3, 2}
   
4. 求A点乘B的结果，以压缩形式的返回。以上面的A，B为例，结果是[(5,1), (1,1), (9,1), (6,4)]
   
5. '''
   
6. 
   
7. def product(A, B):
   
8.     m, n = len(A), len(B)
   
9.     i = j = 0
   
10.     ans = []
    
11.     p = 0
    
12.     len_a = len_b = 0
    
13.     while i < m and j < n:
    
14.         a, b = A[i][0], B[j][0]
    
15.         if len_a == 0:
    
16.             len_a = A[i][1]
    
17.         if len_b == 0:
    
18.             len_b = B[j][1]
    
19.         p = a * b
    
20.         if len_a == len_b:
    
21.             i += 1
    
22.             j += 1
    
23.         elif len_a < len_b:
    
24.             i += 1
    
25.         else:
    
26.             j += 1
    
27.         count = min(len_a, len_b)
    
28.         len_a -= count
    
29.         len_b -= count
    
30.         if not ans or ans[-1][0] != p:
    
31.             ans.append((p, count))
    
32.         else:
    
33.             ans.append((p, ans.pop()[1]+count))
    
34.     return ans
    
35. A = [(1, 2), (3,1), (2,3), (3, 1)]
    
36. B = [(5, 1), (1,1), (3,4), (2, 1)]
    
37. ret = product(A, B)
    
38. print(ret)

复制代码

第二题求思路。。。 谢谢

glad2mu 发表于 2021-3-2 13:36
第二题求思路。。。 谢谢

双指针应该就可以了吧

glad2mu 发表于 2021-3-1 21:36
第二题求思路。。。 谢谢

比较A,B中element的range，重合部分做乘法，on-fly build pair<int, int>，加到结果中类似于find interval overlap。注意边界条件和指针移动。

积分不够 看不到题 TAT

求教 请问什么叫“数组表示压缩后的一串数字”？ 谢谢

sherryhw 发表于 2021-3-22 03:50
求教 请问什么叫“数组表示压缩后的一串数字”？ 谢谢

pair第一个表示数字，第二个表示该数字连续出现的个数。