QQ登录

只需一步,快速开始

热门帖子
  • 【修身讲堂·校庆版】重磅来袭!

    【修身讲堂·校庆版】重磅来袭!

    101 人关注

  • 学生单间 哈工大西门 超大阳面卧室

    学生单间 哈工大西门 超大阳面卧室

    19206 人关注

  • 可单间,可整套。

    可单间,可整套。

    407 人关注

热心居民
    查看: 11318|回复: 72

    分享最近做的算法题

    [复制链接]
    发表于 2014-10-27 21:51:06 | 显示全部楼层 |阅读模式
    本帖最后由 木槿不说话 于 2014-10-27 12:39 编辑

    要是关注的人多的话我完全可以一天出一道算法题的~~

    都是我面试的时候遇到的题,大家可以一起讨论呢。

    1, Sort a number of people by their ages


    2,   replace the element with the product ofother elements in the array. 不能用除法.
        比如原始array是这样的: [1,2,3,4,5,6]
        要变成这样:[2*3*4*5*6, 1*3*4*5*6, …]

    我就随便发一下,说说思路就行,brute force也可以嘛,有回复我会讨论的。
     楼主| 发表于 2014-10-28 01:38:02 | 显示全部楼层
    程序员们都去哪里了!不觉得算法好有意思吗。。。

    这些都是面试遇到过的题。还蛮有代表性的。

    再来一道:

    3. 有一个不断变动的list,里面是各种股票,和当前股票的价格。求出当前时刻价格top k的股票分别是什么。
    比如现在:
    A股票 10
    B股票 12
    C股票 2
    D股票 34

    运行程序求topk 当k = 2时刻,返回D股票和B股票
    回复

    使用道具 举报

     楼主| 发表于 2014-10-28 22:31:03 | 显示全部楼层
    卖包子的土鳖 发表于 2014-10-27 23:24
    第二题我想出了一种方法,需要再用两个数组,乘法需要做3N-2次

    用C语言表示,不考虑溢出

    你的思路是对的。

    其实这个思想就是DP dynamic programming

    从前往后DP一次,然后从后往前再DP一次。

    最后把大家都合起来就是题目的解。

    在我的理解里,DP和reversion(递归)是类似思想,都是分治。只是DP把小的解法都存起来了,不用第二次再重复计算了。

    赞动了脑子。
    回复

    使用道具 举报

     楼主| 发表于 2014-10-28 22:35:50 | 显示全部楼层
    失落清夏 发表于 2014-10-27 22:48
    毫无思路。。
    只会这样:
    [a1,a2,...an]

    第二题解法在楼上。

    第一题要问用什么sort方法的话,因为age是有限的。这时候可以问面试官能不能把年龄设定为在0到100之间呢,表示你有考虑。

    我觉得这道题用counting sort是最好的,也就是bucket sort。时间复杂度小。

    但是这里有一个trade off就是,要是人数太少,怎么办。这样的话,counting sort的空间复杂度就不合算了。比如只有6个人,你用了一个0-100的空间去算,人数分布的很稀疏。肯定不合算。所以要是人少的话,就可以用bubble sort之类的,人多就用counting sort
    回复

    使用道具 举报

     楼主| 发表于 2014-10-28 22:38:13 | 显示全部楼层
    本帖最后由 木槿不说话 于 2014-10-28 09:40 编辑
    1. typedef unordered_map<string, int>::iterator mapIter;
    2. struct cmp
    3. {
    4.         bool operator()(mapIter &l , mapIter &r)
    5.         {
    6.                 return l->second > r->second; //小顶堆
    7. //                return l->second < r->second; //大顶堆
    8.         }
    9. };

    10. vector<string> getTopkV1(const vector<string>& strs, int k)
    11. {
    12.         vector<string> res;
    13.         if(k <= 0) return res;
    14.         unordered_map<string, int> mymap;
    15.         for(size_t i = 0; i < strs.size(); i++)
    16.                 mymap[strs[i]]++;

    17.         priority_queue<mapIter, vector<mapIter>, cmp> myQ;

    18.         if(k >= mymap.size())
    19.         {
    20.                 for(mapIter it = mymap.begin(); it != mymap.end(); it++)
    21.                         myQ.push(it);
    22.         }
    23.         else
    24.         {
    25.                 mapIter it = mymap.begin();
    26.                 for(int i = 0; i < k; i++, it++)
    27.                         myQ.push(it);

    28.                 for(; it!= mymap.end(); it++)
    29.                 {
    30.                         myQ.push(it);
    31.                         myQ.pop();
    32.                 }
    33.         }
    34.         while(!myQ.empty())
    35.         {
    36.                 mapIter it = myQ.top();
    37.                 myQ.pop();
    38.                 res.push_back(it->first);
    39.         }
    40.         return res;
    41. }
    复制代码




    这是第三题的c++代码。。。

    木有人回复就不继续这个帖子啦~~

    大家都加油!
    回复

    使用道具 举报

     楼主| 发表于 2014-11-1 21:47:34 | 显示全部楼层
    再来分享一道题,是一道蛮不错的题~

    输入一个字符串比如“1-(3*4+5)”
    写一个方程输出正确结果,返回类型为int

    可以用任意的数据结构,提示:可以用stack哟。(栈)
    回复

    使用道具 举报

     楼主| 发表于 2014-11-8 10:19:47 | 显示全部楼层
    那。。。
    再来一题

    是leetcode的题 但是略有改动

    给一个N*N的grid,里面有字母,用户输入一个单词,判断这个单词在不在里面,单词可横可竖,不能弯折,如果在,给出所有解。
    回复

    使用道具 举报

    发表于 2014-10-27 22:09:34 | 显示全部楼层
    第二个用除法那么简单
    回复

    使用道具 举报

    发表于 2014-10-27 22:27:26 | 显示全部楼层
    虽然我看不懂,但我是来顶帖的

    评分

    参与人数 1金币 +1 收起 理由
    木槿不说话 + 1 赞一个!

    查看全部评分

    回复

    使用道具 举报

    发表于 2014-10-27 22:35:30 | 显示全部楼层
    我的英语水平只看懂了第一题。
    不过还是太模糊,仅仅是把数字排序?
    由于是人的年龄,假设有N多的人(再假设不超过int上限。),这也很好办
    设定一个年龄的数组比如 Ages[120],初始为0,Ages[i]表示年龄为i的人数
    然后开始录入年龄a,对应操作Ages[a]++;
    这样得到的数组Ages[120]从大到小,从小到大怎么输出都无所谓了
    回复

    使用道具 举报

     楼主| 发表于 2014-10-28 01:31:09 | 显示全部楼层
    卖包子的土鳖 发表于 2014-10-27 09:09
    第二个用除法那么简单

    不能。。用除法。。。。
    回复

    使用道具 举报

     楼主| 发表于 2014-10-28 01:33:08 | 显示全部楼层
    失落清夏 发表于 2014-10-27 09:35
    我的英语水平只看懂了第一题。
    不过还是太模糊,仅仅是把数字排序?
    由于是人的年龄,假设有N多的人(再假 ...

    是根据年龄对人进行排序。

    其实是问的用哪一种sort方法比较合适。

    第二题比较有意思啊。。。快做!

    就是一个数组本来是1,2,3,4

    现在第一个元素1用其他元素的乘积代替。
    回复

    使用道具 举报

    发表于 2014-10-28 11:48:53 | 显示全部楼层
    木槿不说话 发表于 2014-10-28 01:33
    是根据年龄对人进行排序。

    其实是问的用哪一种sort方法比较合适。

    毫无思路。。
    只会这样:
    [a1,a2,...an]

    第i个元素:
    (a1*a2*...*ai-1) * (ai+1 * ai+2 * ... * an)
    回复

    使用道具 举报

    发表于 2014-10-28 12:24:27 | 显示全部楼层
    第二题我想出了一种方法,需要再用两个数组,乘法需要做3N-2次

    用C语言表示,不考虑溢出
    1. int a[n],b[n];
    2. int i
    3. a[0]=1;
    4. b[n-1]=1;
    5. for(i=1;i<n;i++)
    6.     a=array[i-1]*a[i-1];
    7. for(i=n-2;i>0;i--)
    8.     a=array[i+1]*a[i+1];
    9. for(i=0;i<n;i++)
    10.     array=a*b;
    复制代码


    我表达能力很差,但是这段代码很简单表的的应该没问题,能看懂吧
    回复

    使用道具 举报

    发表于 2014-10-28 22:36:41 | 显示全部楼层
    木槿不说话 发表于 2014-10-28 22:35
    第二题解法在楼上。

    第一题要问用什么sort方法的话,因为age是有限的。这时候可以问面试官能不能把年龄 ...

    这种问题。。。6个人。。。。我可以说大部分的方法都是木有区别。。。
    回复

    使用道具 举报

    发表于 2014-10-28 22:38:20 | 显示全部楼层
    木槿不说话 发表于 2014-10-28 22:35
    第二题解法在楼上。

    第一题要问用什么sort方法的话,因为age是有限的。这时候可以问面试官能不能把年龄 ...

    第二题的解法代码好像和我说的一样
    回复

    使用道具 举报

    发表于 2014-10-28 22:47:18 来自iphone8 plus 128T 土豪金镶钻版 | 显示全部楼层
    支持一下⊙▽⊙,算法真的很有用
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 加入观海听涛

    本版积分规则

    联系我们

    Powered by Discuz! X3.4 © 2001-2013 Comsenz Inc.

    Archiver|手机版|观海听涛论坛   

    GMT+8, 2020-6-1 03:38 , Processed in 3.030920 second(s), 47 queries , Gzip On, MemCache On.

    快速回复 返回顶部 返回列表