一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3811|回复: 9
收起左侧

[数组] 请教这道 Lintcode 的 Nuts & Bolts problem

[复制链接] |试试Instant~ |关注本帖
mnmunknown 发表于 2015-7-28 22:34:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

http://www.lintcode.com/en/problem/nuts-bolts-problem/#

基本思路很简单,由于compare规定只能按(nut, bolt)的顺序放, 先从nut里选一个做pivot,按此pivot与bolts array进行比较并且进行partition; 而后返回pivot element的index,代表对应原先选择的nut的bolt,并且以此元素回到nuts array里面进行partition; 最后递归处理左右两边。

但是这题在第六个test case总挂,测试了好多遍也不清楚为什么,向论坛里各位请教下,谢谢!
  1. /**
  2. * public class NBCompare {
  3. *     public int cmp(String a, String b);
  4. * }
  5. * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
  6. * if "a" is bigger than "b", it will return 1, else if they are equal,
  7. * it will return 0, else if "a" is smaller than "b", it will return -1.
  8. * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
  9. */
  10. public class Solution {
  11.     /**
  12.      * @param nuts: an array of integers
  13.      * @param bolts: an array of integers
  14.      * @param compare: a instance of Comparator
  15.      * @return: nothing
  16.      */
  17.     public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
  18.         /*
  19.         if(nuts[0].equals("ab")){
  20.             for(String nut : nuts){
  21.                 for(String bolt : bolts){
  22.                     if(compare.cmp(nut, bolt) == 0)
  23.                         System.out.println(nut + " matches " + bolt);
  24.                 }
  25.             }
  26.         }
  27.         */
  28.         sortSubArray(nuts, bolts, 0, nuts.length - 1, compare);
  29.     }
  30.    
  31.     private void sortSubArray(String[] nuts, String[] bolts, int start, int end, NBComparator compare){
  32.         if(start >= end) return;
  33.         
  34.         int pivot = sortBolts(nuts[start], bolts, start, end, compare);
  35.      
  36.         sortNuts(nuts, bolts[pivot], start, end, compare);
  37.         
  38.         sortSubArray(nuts, bolts, start, pivot - 1, compare);
  39.         sortSubArray(nuts, bolts, pivot + 1, end, compare);
  40.         
  41.         return;
  42.     }
  43.    
  44.     private int sortBolts(String nut, String[] bolts, int start, int end, NBComparator compare){
  45.         
  46.         int left = start;
  47.         int right = end;
  48.         
  49.         while(left < right){
  50.             while(left < right && compare.cmp(nut, bolts[left]) < 0){
  51.                 left++;
  52.             }
  53.             while(left < right && compare.cmp(nut, bolts[right]) > 0){
  54.                 right--;
  55.             }
  56.             
  57.             if(left < right) swap(bolts, left, right);
  58.         }
  59.         
  60.         /*
  61.         System.out.println("Current Bolts: ");
  62.         for(String bolt : bolts){
  63.             System.out.print(bolt + " ");
  64.         }
  65.         for(String bolt : bolts){
  66.             System.out.print(compare.cmp(nut, bolt) + " ");
  67.         }
  68.         System.out.println("Given nut: " + nut);
  69.         System.out.println("Pivot index: " + left);
  70.         */
  71.         for(int i = start; i <= end; i++ ){
  72.             if(compare.cmp(nut, bolts[i]) == 0) left = i;
  73.         }
  74.         return left;
  75.     }
  76.    
  77.     private void sortNuts(String[] nuts, String bolt, int start, int end, NBComparator compare){
  78.         int left = start;
  79.         int right = end;
  80.         
  81.         while(left < right){
  82.             while(left < right && compare.cmp(nuts[left], bolt) > 0){
  83.                 left ++;
  84.             }
  85.             while(left < right && compare.cmp(nuts[right], bolt) < 0){
  86.                 right --;
  87.             }
  88.             if(left < right) swap(nuts, left, right);
  89.         }
  90.         
  91.         /*
  92.         System.out.println("Current Bolts: ");
  93.         for(String nut : nuts){
  94.             System.out.print(nut + " ");
  95.         }
  96.         for(String nut : nuts){
  97.             System.out.print(compare.cmp(nut, bolt) + " ");
  98.         }
  99.         System.out.println("Given bolt: " + bolt);
  100.         System.out.println("Pivot index: " + left);
  101.         */
  102.         
  103.         
  104.         return;
  105.     }
  106.    
  107.     private void swap(String[] array, int a, int b){
  108.         String temp = array[a];
  109.         array[a] = array[b];
  110.         array[b] = temp;
  111.     }
  112. };
复制代码
 楼主| mnmunknown 发表于 2015-7-28 22:36:22 | 显示全部楼层
第 71 - 73 行原先没有,我在测试的时候加了进去想看看是不是返回的index有问题,实际跑的时候请拿掉
回复 支持 反对

使用道具 举报

billryan 发表于 2015-7-30 22:10:45 | 显示全部楼层
我的思路和你类似,但是我的在第5个挂掉,感觉可能是 lintcode 方面的问题?
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2015-7-30 23:53:25 | 显示全部楼层
billryan 发表于 2015-7-30 22:10
我的思路和你类似,但是我的在第5个挂掉,感觉可能是 lintcode 方面的问题?

因为test case很大而且不是按照字面字母对应,在那个test case上具体哪里出了问题我也不清楚。

不过试了好几种不同的partition写法依然在同一个test case上挂让人想不通啊。
回复 支持 反对

使用道具 举报

billryan 发表于 2015-7-31 08:55:20 | 显示全部楼层
mnmunknown 发表于 2015-7-30 23:53
因为test case很大而且不是按照字面字母对应,在那个test case上具体哪里出了问题我也不清楚。

不过试 ...

同样的思路我用 Python 和 C++写的过了,见 https://github.com/billryan/algo ... nd_bolts_problem.md
回复 支持 反对

使用道具 举报

chenjunren0406 发表于 2015-8-4 13:53:30 | 显示全部楼层
不知道楼主ac木有啊? 我也卡在这里了。
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2015-8-4 21:47:47 | 显示全部楼层
chenjunren0406 发表于 2015-8-4 13:53
不知道楼主ac木有啊? 我也卡在这里了。

没,我现在倾向于认为这题的java test case有问题。。。等待哪位java ac的消息
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2015-8-11 10:11:35 | 显示全部楼层
chenjunren0406 发表于 2015-8-4 13:53
不知道楼主ac木有啊? 我也卡在这里了。

一行代码没改,前两天再跑就ac了,看来是test case有问题
回复 支持 反对

使用道具 举报

chenjunren0406 发表于 2015-8-20 12:57:17 | 显示全部楼层
感谢楼组提醒,我刚刚去提交了,也ac了。
回复 支持 反对

使用道具 举报

timeinphl 发表于 2016-7-30 22:13:41 | 显示全部楼层
本帖最后由 timeinphl 于 2016-7-30 22:15 编辑

我做这道题的时候也是有时可以通过,有时说超时,用的是c++。

  1. class Solution {
  2. public:
  3.     using CompareResult = enum { SMALLER = -1, EQUAL = 0,
  4.                                  BIGGER = 1, REVERSED = 2 };
  5.     void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare)
  6.     {
  7.         if (nuts.size() != bolts.size() || nuts.empty() || bolts.empty())
  8.         {
  9.             return;
  10.         }
  11.         quick_sort(nuts, bolts, 0, bolts.size() - 1, compare);
  12.     }
  13.    
  14.     int partition(string pivot_other, vector<string> &targets, int l, int r, Comparator compare)
  15.     {
  16.         
  17.         for (int i = l; i <= r; i++)
  18.         {
  19.             if (compare.cmp(pivot_other, targets) == 0 || compare.cmp(targets, pivot_other) == 0)
  20.             {
  21.                 swap(targets, targets[l]);
  22.                
  23.                 break;
  24.             }
  25.         }
  26.         string pivot = targets[l];

  27.         while (l < r)
  28.         {
  29.             while
  30.             (
  31.                 l < r &&
  32.                 (compare.cmp(pivot_other, targets[r]) == BIGGER ||
  33.                  (compare.cmp(pivot_other, targets[r]) == REVERSED &&
  34.                   compare.cmp(targets[r], pivot_other) == SMALLER)
  35.                  )
  36.             )
  37.             {
  38.                 r--;
  39.             }
  40.             targets[l] = targets[r];

  41.             while
  42.             (
  43.                 l < r &&
  44.                 (compare.cmp(pivot_other, targets[l]) == SMALLER ||
  45.                 (compare.cmp(pivot_other, targets[l]) == REVERSED &&
  46.                  compare.cmp(targets[l], pivot_other) == BIGGER)
  47.                 )
  48.             )
  49.             {
  50.                 l++;
  51.             }
  52.             targets[r] = targets[l];
  53.         }
  54.         targets[l] = pivot;
  55.         return l;
  56.     }
  57.    
  58.     void quick_sort(vector<string> &nuts, vector<string> &bolts, int l, int r, Comparator compare)
  59.     {
  60.         if (l >= r)
  61.         {
  62.             return;
  63.         }
  64.         string pivot_from_bolts = bolts[l];
  65.         int idx = partition(pivot_from_bolts, nuts, l, r, compare);
  66.         
  67.         string pivot_from_nuts = nuts[idx];
  68.         partition(pivot_from_nuts, bolts, l, r, compare);
  69.         
  70.         quick_sort(nuts, bolts, l, idx - 1, compare);
  71.         quick_sort(nuts, bolts, idx + 1, r, compare);
  72.     }
  73. };
复制代码
// reference: https://github.com/kamyu104/LintCode/blob/master/C++/nuts-bolts-problem.cpp
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 13:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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