📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: 孤笑客
跳转到指定楼层
上一主题 下一主题
收起左侧

请教4道题目的最优做法(G家真题)

🔗
Linzertorte 2015-10-30 03:04:22 | 只看该作者
全局:
线段树,BIT,平衡树,大家都好厉害。我要是面试官看到你们写这些,我就哭 了,(我准备的第二题看来是没时间问了)
回复

使用道具 举报

🔗
ryancooper 2015-10-30 04:46:05 | 只看该作者
全局:
ryancooper 发表于 2015-10-30 01:01
对于第4题,要是全部输入的都是正整数的话,应该有个线性的算法

说错了,原来的没说是sort的,所以应该是nlogn。
  1. def solve(nums, N):
  2.         nums.sort()
  3.         leastNumNotRepresentsByAnySubsequenceOfNums = 1
  4.         res = 0
  5.         for num in nums:
  6.                 if num > leastNumNotRepresentsByAnySubsequenceOfNums:
  7.                         res += 1
  8.                         leastNumNotRepresentsByAnySubsequenceOfNums <<= 1
  9.                 else:
  10.                         leastNumNotRepresentsByAnySubsequenceOfNums += num
  11.                 if leastNumNotRepresentsByAnySubsequenceOfNums >= N + 1:
  12.                         break
  13.         tmp = N + 1 - leastNumNotRepresentsByAnySubsequenceOfNums
  14.         tmp = tmp / leastNumNotRepresentsByAnySubsequenceOfNums + (0 if tmp % leastNumNotRepresentsByAnySubsequenceOfNums == 0 else 1)
  15.         return res if leastNumNotRepresentsByAnySubsequenceOfNums >= N + 1 else res + tmp
复制代码
变量名起得太长,不过为了表达我的意思,就这样吧
回复

使用道具 举报

🔗
oaknova 2015-10-30 09:43:36 | 只看该作者
全局:
第二题用stack:
  1. package leetcode;
  2. import java.util.*;

  3. public class Leetcode {
  4.         public static void main(String[] args){
  5.                 String str = "dsfsdctaceat";
  6.                 String result;
  7.                
  8.                 int[] count = new int[26];
  9.                 for(int i=0; i<str.length(); i++){
  10.                         count[str.charAt(i)-'a']++;
  11.                 }
  12.                
  13.                 StringBuffer sb = new StringBuffer();
  14.                 LinkedList<Character> stack = new LinkedList<>();
  15.                 int start = 0;
  16.                 for(int i=0; i<str.length(); i++){
  17.                         if(count[str.charAt(i)-'a'] == 0)
  18.                                 continue;
  19.                         while(!stack.isEmpty() && count[stack.peek()-'a']>1 && stack.peek()>str.charAt(i)){
  20.                                 count[stack.peek()-'a']--;
  21.                                 stack.pop();
  22.                         }
  23.                         stack.push(str.charAt(i));
  24.                         if(count[stack.peek()-'a'] == 1){
  25.                                 while(!stack.isEmpty()){
  26.                                         char top = stack.pop();
  27.                                         count[top-'a'] = 0;
  28.                                         sb.insert(start, top);
  29.                                 }
  30.                                 start = sb.length();
  31.                         }
  32.                 }
  33.                 while(!stack.isEmpty()){
  34.                         char top = stack.pop();
  35.                         count[top-'a'] = 0;
  36.                         sb.insert(0, top);
  37.                 }
  38.                
  39.                 result = sb.toString();
  40.                 System.out.print(result);
  41.         }
  42. }
复制代码
测试结果:
"dsfsdctaceat":dfsacet
"agazcabcab":agzbc
"aaaa":a
"aaaabb":ab
回复

使用道具 举报

🔗
 楼主| 孤笑客 2015-10-30 10:09:06 | 只看该作者
全局:
第三题应该增加一个条件,C越小越好。(你懂的。不然太简单了。)
回复

使用道具 举报

🔗
hj867955629 2015-10-30 12:33:52 | 只看该作者
全局:
oaknova 发表于 2015-10-30 09:43
第二题用stack:测试结果:
"dsfsdctaceat":dfsacet
"agazcabcab":agzbc

结果不对。。试试前面那个case: acbdefafedcb
回复

使用道具 举报

🔗
hj867955629 2015-10-30 12:43:08 | 只看该作者
全局:
第三题就先找一个比B最高位小的最大的数,剩下的从大到小排列,使得初始A的值尽量接近B,然后一直next permutation直到大于B?
回复

使用道具 举报

🔗
hj867955629 2015-10-30 13:37:05 | 只看该作者
全局:
z928czzc 发表于 2015-10-30 00:59
第一题只是排序的某种变形。Partial heap sort就能解决。

第二题比较interesting,想了几分钟,答案如下 ...

第四题没看到比较好的解法呀这上面。。
回复

使用道具 举报

🔗
z928czzc 2015-10-30 22:52:32 | 只看该作者
全局:
hj867955629 发表于 2015-10-30 13:37
第四题没看到比较好的解法呀这上面。。

第四题是codeforce problem。讨论见
http://www.careercup.com/question?id=5717521992777728

第一个解法就是正确解法。
回复

使用道具 举报

全局:
stellari 发表于 2015-10-30 00:00
比如第1题你可以这样:从后向前扫,每扫一个元素p就将其插入一个平衡二叉树T中,同时找到此时它在T中的位置 ...

请问楼主,BST的话你打算如何实现呢?以及如何将元素在树中的位置和比他大的元素个数联系起来呢?谢谢
回复

使用道具 举报

🔗
ryancooper 2015-10-31 01:48:54 | 只看该作者
全局:
hj867955629 发表于 2015-10-30 13:37
第四题没看到比较好的解法呀这上面。。

我看了下,我的思想和楼下那个人提到的答案类似。我在遍历的过程中maitain最小的不能够被当前任何子序列(非连续)之和表示的数。如果遍历的当前数比该数要大,证明我们现在需要补充数了。写代码的时候犯了个错,第九行的else不需要,第十行保留。不过还是有点小问题,好像有些输入会多1个出来
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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