[LintCode] Nuts & Bolts Problem

tuomao 發布于2019-08-14 15:15 / 2978人閱讀

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;
    }

GPU云服務器云服務器 Nuts problem Bolts LintCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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