微软近期高频面试题分享 + 分析（七）

最近来巨硬面试的小朋友通过概率实在太低了，代码老是写不对，我们组已经十连拒了，不得不感叹，现在出的面试题越来越难了，我决定还是上来地里透透题，说点最近我们组面试常考高频题和解析（毕竟岗位机会也不能都让三锅霸占了对不）。招人艰难，看微软机会的小伙伴，也欢迎LinkedIn勾搭：
https://www.linkedin.com/in/andy-yongjian-deng-212977200/


注意打招呼的时候备注一下，方便识别友军，hhhh。

带娃有压力，尽量保持一周两更，大家海涵。


往期链接：

微软近期高频面试题分享 + 分析（一）

微软近期高频面试题分享 + 分析（二）

微软近期高频面试题分享 + 分析（三）

微软近期高频面试题分享 + 分析（四）

微软近期高频面试题分享 + 分析（五）

微软近期高频面试题分享 + 分析（六）

YankeeDoodle 发表于 2021-6-8 10:17
字符串-兄弟字符串

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配 ...

3、Hashmap
建两个hash数组，分别记录两个字符串，然后比较两个数组的每一项是否相同，有不同的说明不是兄弟字符串

1. #include<iostream>
   
2. #include<stdio.h>
   
3. #include<stdlib.h>
   
4. #include<string.h>
   
5. using namespace std;  
   
6. 
   
7. int main()
   
8. {
   
9.         int hash1[256],hash2[256],i,len1,len2;
   
10.         char str1[100],str2[100];
    
11.        
    
12.         printf("请输入2个字符串：（0结束）\n");
    
13.         while(1)
    
14.         {
    
15.                 //输入
    
16.                 scanf("%s",str1);
    
17.                 if(!strcmp(str1,"0")) break;
    
18.                 scanf("%s",str2);
    
19.                
    
20.                 //比较长度
    
21.                 len1=strlen(str1);
    
22.                 len2=strlen(str2);
    
23.                 if(len1!=len2)
    
24.                 {
    
25.                         printf("%s,%s,二者不是兄弟字符串\n",str1,str2);
    
26.                         continue;
    
27.                 }
    
28.                  
    
29.                 //字符是否相同
    
30.                 memset(hash1,0,sizeof(hash1));
    
31.                 memset(hash2,0,sizeof(hash2));
    
32.                 for(i=0;i<len1;i++)
    
33.                 {
    
34.                         hash1[str1[i]]++;
    
35.                         hash2[str2[i]]++;
    
36.                 }
    
37.                 for(i=0;i<255;i++)
    
38.                 {
    
39.                         if(hash1[i]!=hash2[i])//不同
    
40.                                 break;
    
41.                 }
    
42.                 if(i==255)
    
43.                         printf("%s,%s,二者是兄弟字符串\n",str1,str2);
    
44.                 else
    
45.                         printf("%s,%s,二者不是兄弟字符串\n",str1,str2);
    
46.         }
    
47. }
    
48. /*
    
49. bad abd
    
50. abcd abc
    
51. aabbccdd abcdabcd
    
52. abcdabc aabbccc
    
53. aaa bbb
    
54. ababa babab
    
55. ababa aabba
    
56. 0
    
57. */

复制代码

4、 O（n）到 O（n+m）的素数方法
你可能会这么想：O(n+m)是你能得到的最好的结果了，至少要对每个字母至少访问一次才能完成这项操作，而上一节最后的俩个方案是刚好是对每个字母只访问一次。

给26个字符依次赋予质数。质数是比较特殊的一堆数字，它们只能被1和本身整除。以给a赋值2、给b赋值3、给c赋值5、给d赋值7、给e赋值11、给f赋值13。

加法：两个字符串中的所有字符都赋值了，接着让它们各自相加，如果两个字符串得出的结果是一样的，那它们是兄弟字符串。但是，b+f=3+13=16；c+e=5+11=16，所以有误；

乘法：两个字符串中的所有字符让它们各自相乘，方法是对的，但是会溢出，所以要大整数处理了；用平方和或者立方和：考虑平方和会不会解决加法有误，乘法溢出：b*b+f*f=3*3+13*13=178；c*c+e*e=5*5+11*11=146

然后——轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。

如果是加法，那么使用一个类似于set的数据结构来记录字符串中字母出现的频次即可,但是空间开销会比素数更大（素数法要求分配素数也是需要空间的，虽然是常数级）。代码如下：

1. /*
   
2. 如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，
   
3. 问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。
   
4. */
   
5. #include <iostream>
   
6. using namespace std;
   
7. 
   
8. int isBroStr(char *str1, char *str2)
   
9. {
   
10.     int a[26 * 2] = {0};
    
11.     int i, strLen;
    
12.    
    
13.     if (!str1 && !str2)
    
14.         return 1;
    
15.     else if (!str1 || !str2)
    
16.         return 0;
    
17.     else
    
18.     {
    
19.         if(strlen(str1) != strlen(str2))
    
20.             return 0;
    
21.         strLen = strlen(str1);
    
22.         for(i = 0; i < strLen; i++)
    
23.         {
    
24.             ++a[str1[i] - 'A'];
    
25.             --a[str2[i] - 'A'];
    
26.         }
    
27.         for(i = 0; i < 26 * 2; i++)
    
28.             if (a[i])
    
29.                 return 0;
    
30.         return 1;
    
31.     }        
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.     char *str1 = "asdfaabAAB";
    
37.     char *str2 = "asdfAABaab";
    
38.     if (isBroStr(str1, str2))
    
39.         cout << " String 1 and String 2 are brothers!" << endl;
    
40.     else
    
41.         cout << " String 1 and String 2 are not brothers!" << endl;
    
42.     system("PAUSE");
    
43.     return 0;
    
44. }

复制代码

YankeeDoodle 发表于 2021-6-18 09:56
橘子问题

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

2、贪心策略+记忆化
我们再次观察一下，当 n > 0，
1）假如路径全是由 -1 组成的 => 这种情况下到 0 的距离为 n
2）假如某条路径不只是由 -1 组成的，经过了 k 次 -1 然后出现了 /3。此时 (n-k) 一定是 3 的倍数。这条路径从 n 到 (n-k)/3 经过了 (k+1) 条边。我们证明以下结论： 如果 k >= 3，那么这条路径一定不是最优的。 可以替换为路径：我们先进行 (k-3) 次 -1，再进行 1 次 /3，再进行 1 次 -1，同样得到 (n-k)/3。但是只用了 (k-1) 条边。 于是如果最优路径是 -1 再 /3，那么 -1 的次数必然 < 3: 当 n % 3 == 0 时，k 可以为 0,3,6,9,... 我们只用考虑 k == 0 的路径 当 n % 3 == 1 时，k 可以为 1,4,7,10,... 我们只用考虑 k == 1 的路径 当 n % 3 == 2 时，k 可以为 2,5,8,11,... 我们只用考虑 k == 2 的路径
3）同理 2，假如某条路径不只是由 -1 组成的，经过了 k 次 -1 然后出现了 /2。 此时 (n-k) 一定是 2 的倍数。这条路径从 n 到 (n-k)/2 经过了 (k+1) 条边。我们证明以下结论： 如果 k >= 2，那么这条路径一定不是最优的。 可以替换为路径：我们先进行 (k-2) 次 -1，再进行 1 次 /2'，再进行 1 次 -1，同样得到 (n-k)/2。 但是只用了 k 条边。 于是如果最优路径是 -1 再 /2，那么 '-1' 的次数必然 < 2。 当 n % 2 == 0 时，k 可以为 0,2,4,6,... 我们只用考虑 k == 0 的路径 当 n % 2 == 1 时，k 可以为 1,3,5,7,... 我们只用考虑 k == 1 的路径
所以，以上的结论可以辅助我们做出一个决定，一个个吃必然没有2个、3个吃更加有效。转移方程就变为$f(n) = 1+min(f(n/2)+n%2, f(n/3)+n%3)$

1. class Solution {
   
2. public:
   
3.     map<int,int>mp;
   
4.     int dfs(int i){
   
5.         if(i==0)return 0;
   
6.         if(i==1)return 1;
   
7.         if(mp.count(i))return mp[i];
   
8.         return mp[i]=min(dfs(i/2)+i%2+1,dfs(i/3)+i%3+1);
   
9.     }
   
10.     int minDays(int n) {
    
11.         mp.clear();
    
12.         return dfs(n);
    
13.     }
    
14. 
    
15. };

复制代码

为什么要加上记忆化呢？没有加上记忆化的结构如下,少了很多重复递归的节点，直接map就可以完成。

而加上了记忆化的结构如下：

复杂度分析：
时间复杂度为$T(n)=T(n/2)+T(n/3)+O(1)$，加上记忆化，深度为$log(n)$，于是要遍历的节点数为$O(log^2n)$
空间复杂度：$O(log^2 n)$，即为需要存储的 $f(i)$ 的个数。

字符串-兄弟字符串

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）

YankeeDoodle 发表于 2021-6-8 10:17
字符串-兄弟字符串

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配 ...

1、O（n*m）的轮询方法

判断string2中的字符是否在string1中： String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPO

判断一个字符串是否在另一个字符串中，最直观也是最简单的思路是，针对第二个字符串string2中每一个字符，与第一个字符串string1中每个字符依次轮询比较，看它是否在第一个字符串string1中。

YankeeDoodle 发表于 2021-6-8 10:17
字符串-兄弟字符串

如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配 ...

2、 O(mlogm)+O(nlogn)+O(m+n)的排序方法

一个稍微好一点的方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(mlogm) + O(nlogn)次操作，之后的线性扫描需要O(m+n)次操作。

步骤如下： 1、判断两个字符串的长度是否一样,如果不一样则退出。 2、每个字符串按字符排序，如acb排序之后是abc,如果是兄弟字符串的话，排序之后是一样的。

好人一生平安

wow楼主好人一生平安啊~

攒👍🏻

橘子问题

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。 每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。

1. 示例 1：
   
2. 输入：n = 10
   
3. 输出：4
   
4. 解释：你总共有 10 个橘子。
   
5. 第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。
   
6. 第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除）
   
7. 第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
   
8. 第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。
   
9. 你需要至少 4 天吃掉 10 个橘子。
   
10. 
    
11. 示例 2：
    
12. 输入：n = 6
    
13. 输出：3
    
14. 解释：你总共有 6 个橘子。
    
15. 第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除）
    
16. 第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除）
    
17. 第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。
    
18. 你至少需要 3 天吃掉 6 个橘子。
    
19. 
    
20. 示例 3：
    
21. 输入：n = 1
    
22. 输出：1
    
23. 
    
24. 示例 4：
    
25. 输入：n = 56
    
26. 输出：6

复制代码