【面试经验】黑车新鲜OA

Baby2021 发表于 2021-3-7 06:11
2. 给两个String[], 检查是否第二个String[]里所有的String都是第一个String[]里 0 到 某个element的concat ...

有可能的，a中一个或多个

第3题，brute force需要 O((rows * cols)^2)，以下解法O(rows * cols)

1. //Time O(rows * cols)
   
2. vector<int> max_k_submatrix(vector<vector<int>> &matrix, int k)
   
3. {
   
4.     int rows = matrix.size(), cols = matrix[0].size();
   
5.     vector<vector<int>> k_row_sum(rows - k + 1, vector<int>(cols, 0));
   
6. 
   
7.     //滚动算k rows的和，0..k-1, 1..k, 2..k+1 ...., 将二维问题转化为一维问题
   
8.     for (int r = 0; r < k_row_sum.size(); r++) {
   
9.         for (int c = 0; c < cols; c++) {
   
10.             if (r < k)
    
11.                 k_row_sum[0][c] += matrix[r][c];
    
12.             else
    
13.                 k_row_sum[r - k + 1][c] = k_row_sum[r-k][c] + matrix[r][c] - matrix[r-k][c];
    
14.         }   
    
15.     }
    
16. 
    
17.     vector<vector<int>> max_k_sum_index;
    
18. 
    
19.     int max_sum = INT_MIN;
    
20.     for (int r = 0; r < k_row_sum.size(); r++) {   
    
21.         int sum = 0;
    
22.         int s = 0;
    
23.         for (int c = 0; c < cols; c++) {
    
24.             sum += k_row_sum[r][c];
    
25.             if (c - s + 1 > k)
    
26.                 sum -= k_row_sum[r][s++];
    
27.             if (c - s + 1 == k && sum > max_sum) {
    
28.                 max_sum = sum;
    
29.                 max_k_sum_index.clear();
    
30.                 max_k_sum_index.push_back({r, s});
    
31.             } else if (c - s + 1 == k && sum == max_sum) {
    
32.                 max_k_sum_index.push_back({r, s});
    
33.             }   
    
34.         }   
    
35.     }
    
36. 
    
37.     unordered_set<int> distinct_nums;
    
38. 
    
39.     for (auto &index : max_k_sum_index) {
    
40.         int r1 = index[0], c1 = index[1];
    
41.         int r2 = index[0]+k-1, c2 = index[1]+k-1;
    
42. 
    
43.         for (int r = r1; r <= r2; r++) {
    
44.             for (int c = c1; c <= c2; c++) {
    
45.                 distinct_nums.insert(matrix[r][c]);
    
46.             }
    
47.         }
    
48.     }   
    
49. 
    
50.     vector<int> result;
    
51.     for (int num : distinct_nums)
    
52.         result.push_back(num);
    
53. 
    
54.     return result;
    
55. }
    

复制代码

第4题，将数字revert后，接着就是brute force O(N^2)的解法吧，有更优解吗？

cosimo23 发表于 2021-3-6 12:14
请问Q4  是指 int[] num: [12, 34] => 12+43 = 34+21 ?  count =1

i <= j的话 每个数本身都是可以的吧 难道不是3？

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

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