【微信事业群】趣味面试算法题

向右看齐 2022-04-24 08:18 214阅读 0赞

今天和大家分享博主在腾讯二面期间遇到的两道比较有意思的算法题，由Excel引出的两道面试算法题，可以点开上面的音乐，边听边看~。博主当时面的是微信事业群，截图如下：

![1240][]

二面主要是项目为主，其次就是算法。算法和项目大概各占了一半的时间，二面期间有两道比较有意思的算法题。这两道题面试官是以Excel为切入点引入的。到底是怎么一回事呢，先看下面的Excel截图：

![1240 1][]

上面是一个新建的Excel的截图，大家关注一下用红色方框标注的部分，我们把鼠标继续往右边继续拖动，依次可以得到下面两张图：

![1240 2][]

![1240 3][]

由上面可以看出：Excel中第一列用A表示：

A -> 第1列

B -> 第2列

C -> 第3列

…

Z -> 第26列

AA -> 第27列

AB -> 第28列

基于上面这些事实，面试官引入了两道面试算法题。严格意义上讲，两道算法题都不难，但是其中一道有点绕，不太好处理，很容易出错。下面我们先从简单的那道题开始：

第一题比较容易，没有任何坑，题目如下：

在上面介绍的基础上，函数的输入是下图左边的列，期望的输出是下图右边的列：

![1240 4][]

举例而言，如果函数输入是：AB，那么算法就该输出当前输入在Excel中是第几列：28。

题目应该很清楚了，看到这的小伙伴可以停下来想想思路。问题不难，但是有些细节需要注意。在继续往下看前，一定要有自己的思考哦~

题目考察点很明确，属于:进制的转化问题。输入是Excel中用26个字母表示的列，输出的是对应列的十进制。所以呢，这道题本质是把26进制转换为10进制。但是，又有不一样的地方？

传统的26进制A对应的应该是十进制的0,；B应该对应的是十进制的1，到这里你可能发现了，它们之间存在一个1的差值。在进行进制转换时，注意处理这个差值就好。相对第二道题，这道比较好处理。第一道题唯一需要注意的地方就是那个差值的处理，代码如下：

解法一：

public int numberConvert(String s) { 
        //存储最后转换的结果
        int res = 0;
    
        //进制转换的底数
        int base = 1;
    
        //charAt(0)是最高位！！！！！
        //这里我们从最低位开始处理
        for(int i=s.length()-1;i>=0;i--){ 
            //比正宗的26进制大一，处理差值1
            res += (s.charAt(i)-'A'+1)*base;
            base *= 26;//底数
        }
        return res;
    }

解法二：

public int numberConvert(String s) {
        int res = 0;
        int base = 1;
    
        //charAt(0)是最高位！！！！！
        //这里我们从高位开始处理
        for(int i=0;i<s.length();i++){
            res=res*26+(s.charAt(i)-'A'+1);
        }
        return res;
    }

两种解法本质是一样的，只是具体的实现细节不一样，关于本题的更多**吐槽**、**看法**和**建议，欢迎小伙伴们评论留言**~

微信事业群 面试官在第一道题之后，又给出了第二道相关的题。博主的二面面试一共有四道算法题。第一道就是上面那道，开胃算法一般比较简单，第二道相对第一道处理起来更绕一些 ，但也不难。题目如下：

![1240 5][]

也就是现在输入变成了：十进制的数字；输出的是Excel中字母表示的列。例如，输入28，算法需要输出第28列在Excel中是怎么表示的，即应该输出：AB。

这个问题其实有点绕，可能不是像看上去的那么好写代码，看到这的小伙伴可以停下来想想看，这个题的难点在哪，又该怎么处理呢？

就像上面提到的，这个题不是正宗的进制转换，正宗的26进制：A -> 0；B -> 1，而在本题中：   A -> 1;B - >2,本题的26进制与正宗的26进制相差了1。这个相差1提了很多遍，因为它是解题的关键。

本题的26进制比正宗的26进制相差1，所以在进行转换的时候，我们可以先把待转换的十进制数减一，减完之后再按照正常的26进制进行转换就可以了。实现代码如下：

public String convertToSequence(int num) { 
        //处理上面说的：相差1问题
        //之后就是:正常的十进制转26进制啦
        num -= 1;
        if(num<0) return "";
    
        String res = new String();
    
        //先转换最低位,余数
        int remain = num % 26;
        res=(char)('A'+remain)+res;
    
        //最低位之外剩余要转换的数
        int cur = num / 26;
    
        if(cur>0 && cur<=26)//直接转换
            res=(char)('A'+(cur-1))+res;
        else if(cur>26){ 
            //剩余带转换的数>26则需要下次循环
            res = convertToSequence(cur)+res; 
               }
            
        return res;
    }

思路可能有点绕，大家可以停下来在草稿纸上试试看，转换的关键几个案例是：1 ->A；26-> Z； 27 -> AA；比如说，输入是27：

先转换最低位：(27-1)%26=0，所以最低位是‘A‘+0=‘A’；其余位相当于是把十进制的(27-1)/26=1转换为本题中的26进制，剩余位为(1-1)/26=0，对应本题中的26进制为：‘A’+0=‘A’,所以27转换之后为：AA。

非递归实现版本如下：

public String convertToTitle(int num) {
        String res = "";
        while(num != 0) {
            num -= 1;
    
            int remain = num % 26;
            res=(char)('A'+remain)+res;
    
            num = num / 26;
        }
        return res;
    }

题目有点绕，主要是处理：相差1的问题。

**微信事业群**的这两道面试算法题，你有什么看法呢?欢迎小伙伴们评论区留言分享**疑问**、**吐槽**和**建议~**

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：公众号后台回复“**csdn**”即可免费领取【csdn】和【百度文库】下载服务；公众号后台回复“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240 6]

**推荐阅读**

[2108全网java面试题汇总(含答案)][2108_java]

[2018全网java面试题汇总(下)  ][2018_java]

[1240]: /images/20220217/4fd48c8adfbb49bb80c7908bb2596fd9.png
[1240 1]: /images/20220217/8b92c75e816342878c9f05cfcdd99563.png
[1240 2]: /images/20220217/2b397fa751b04a99970d959a12686438.png
[1240 3]: /images/20220217/2f9975b55c924b679c7ebd8e530ea720.png
[1240 4]: /images/20220217/cfe8a0ba210c4977a66c17ea9c6f48de.png
[1240 5]: /images/20220217/53d6bd58c2c041308335f1bb4da93e93.png
[1240 6]: /images/20220217/a25eec95b5534ca8abe10cd0d98ec56a.png
[2108_java]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247484619&idx=1&sn=eade64b3192ebbdf745113ef4a07b325&chksm=eb51273fdc26ae29e81d1d0efd0ade6397733009a7f6ecf5068dd7b6d5798619f60a3a73d706&scene=21#wechat_redirect
[2018_java]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247484619&idx=2&sn=188b0cd7e617842dd9a5abc06493b23e&chksm=eb51273fdc26ae2910ad67ca7d8cafbdaf519dcfe7e351701332b9a14005718924bebfd0b710&scene=21#wechat_redirect