[LintCode] Nuts & Bolts Problem

tuomao 发布于2019-08-14 15:15 / 2711人阅读

Problem

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

We will give you a compare function to compare nut with bolt.

Example

Given nuts = ["ab","bc","dd","gg"], bolts = ["AB","GG", "DD", "BC"].
Your code should find the matching bolts and nuts.

one of the possible return:

nuts = ["ab","bc","dd","gg"], bolts = ["AB","BC","DD","GG"].

we will tell you the match compare function. If we give you another compare function.
the possible return is the following:

nuts = ["ab","bc","dd","gg"], bolts = ["BC","AA","DD","GG"].

So you must use the compare function that we give to do the sorting.
The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.

Solution

两次排序 O(n^2)

public class Solution {  
    public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {  
        // write your code here  
         for(int i=0;i
Quick Sort
    public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
        // write your code here
        sort(nuts,bolts,0,nuts.length-1, compare);
    }
    public void sort(String[] nuts, String[] bolts, int l, int h, NBComparator compare) {
        if(l < h){
            int p = partition(nuts, l,h, bolts[h], compare);
            partition(bolts, l,h,nuts[p], compare);
            sort(nuts, bolts, l, p-1,compare);
            sort(nuts, bolts, p+1, h,compare);
        }
    }
    public int partition(String[] strs, int l, int w, String pivot, NBComparator compare) {
        int j = l-1;
        for (int i = l; i < w; i++) {
            if (compare.cmp(strs[i], pivot) == -1 || compare.cmp(pivot, strs[i]) == 1) {
                j++;
                swap(strs, i, j);
            } else if (compare.cmp(strs[i], pivot) == 0 ||compare.cmp(pivot, strs[i]) == 0) {
                swap(strs, i, w);
                i--;
            }
        }
        j++;
        swap(strs, j,w);
        return j;
    }
    private void swap(String[] a, int i, int j) {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

专线服务私有云 Nuts problem Bolts LintCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65500.html

吴恩达 NIPS 2016唯一的中文版PPT

摘要：今日，在第届神经信息处理系统大会中，百度首席科学家吴恩达教授发表演讲利用深度学习开发人工智能应用的基本要点。为了方便读者学习和收藏，雷锋网特地把吴恩达教授的做为中文版。吴恩达先讲述了常见的深度学习模型，然后再着分析端到端学习的具体应用。今日，在第 30 届神经信息处理系统大会（NIPS 2016）中，百度首席科学家吴恩达教授发表演讲：《利用深度学习开发人工智能应用的基本要点（Nuts an...

yunhao 2019-04-25 18:06 评论0 收藏0
[LintCode/LeetCode] Jump Game I &amp; II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0
[LintCode/LeetCode] Single Number I &amp; II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Subsets &amp; Subsets II

Subsets Problem Given a set of distinct integers, return all possible subsets. Notice Elements in a subset must be in non-descending order.The solution set must not contain duplicate subsets. Example ...

tracy 2019-08-14 14:26 评论0 收藏0
[LintCode] Spiral Matrix I &amp; Spiral Matrix II

摘要：如果不在前两个循环之后的话，那么那多余的一行或一列就会被加入数组两次，造成错误的结果。解法和一样，只是简化了，甚至可以用一样的方法去做，只要把也换成。使用，以及最后讨论是否为奇数以判断中间是否有一个未循环的点，是这道题的两个有趣的地方。 Spiral Matrix I Problem Given a matrix of m x n elements (m rows, n columns...

tuantuan 2019-08-14 15:19 评论0 收藏0