資訊專欄INFORMATION COLUMN
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.
ExampleGiven 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.
兩次排序 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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65500.html
摘要：今日，在第屆神經(jīng)信息處理系統(tǒng)大會(huì)中，百度首席科學(xué)家吳恩達(dá)教授發(fā)表演講利用深度學(xué)習(xí)開(kāi)發(fā)人工智能應(yīng)用的基本要點(diǎn)。為了方便讀者學(xué)習(xí)和收藏，雷鋒網(wǎng)特地把吳恩達(dá)教授的做為中文版。吳恩達(dá)先講述了常見(jiàn)的深度學(xué)習(xí)模型，然后再著分析端到端學(xué)習(xí)的具體應(yīng)用。 今日，在第 30 屆神經(jīng)信息處理系統(tǒng)大會(huì)（NIPS 2016）中，百度首席科學(xué)家吳恩達(dá)教授發(fā)表演講：《利用深度學(xué)習(xí)開(kāi)發(fā)人工智能應(yīng)用的基本要點(diǎn)（Nuts an...
摘要：建立動(dòng)規(guī)數(shù)組，表示從起點(diǎn)處到達(dá)該點(diǎn)的可能性。循環(huán)結(jié)束后，數(shù)組對(duì)所有點(diǎn)作為終點(diǎn)的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時(shí)的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
摘要：整個(gè)過(guò)程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過(guò)一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 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...
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 ...
摘要：如果不在前兩個(gè)循環(huán)之后的話，那么那多余的一行或一列就會(huì)被加入數(shù)組兩次，造成錯(cuò)誤的結(jié)果。解法和一樣，只是簡(jiǎn)化了，甚至可以用一樣的方法去做，只要把也換成。使用，以及最后討論是否為奇數(shù)以判斷中間是否有一個(gè)未循環(huán)的點(diǎn)，是這道題的兩個(gè)有趣的地方。 Spiral Matrix I Problem Given a matrix of m x n elements (m rows, n columns...
閱讀 1582·2021-11-25 09:43
閱讀 4146·2021-11-15 11:37
閱讀 3248·2021-08-17 10:13
閱讀 3554·2019-08-30 14:16
閱讀 3582·2019-08-26 18:37
閱讀 2533·2019-08-26 11:56
閱讀 1195·2019-08-26 10:42
閱讀 685·2019-08-26 10:39
