https://github.com/allaboutjst/airbnb/blob/master/README.md
17. Round Prices: 每个数统一向下取整,然后判断其sum与原近似值sum差值多少来决定有多少数需要向上取整,然后根据小数部分排序,拥有较小的小数部分的数向下取整,其他的向上取整
https://github.com/allaboutjst/airbnb/blob/master/src/main/java/round_prices/RoundPrices.java
https://discuss.leetcode.com/topic/246/round-numbers
先将所有floor(x)加起来统计出如果所有都floor的话还差多少,按照ceil以后需要加的价格排序,贪心取最小的补齐即可。
public static int[] round(double[] nums) {
// calculate the round sum, and then sort the nums with the difference between ceiling
// and then make those close to ceil be ceiling, close to floor be floor
NumWithDiff[] diffNums = new NumWithDiff[nums.length];
double sum = 0.0;
int floorSum = 0;
for(int i = 0; i < nums.length; i++) {
double num = nums[i];
int floor = (int) num;
int ceil = floor;
if(floor < num) {
ceil++;
}
floorSum += floor;
sum += num;
diffNums[i] = new NumWithDiff(ceil, ceil - num);
}
// sort the diffNums
Arrays.sort(diffNums, new Comparator<NumWithDiff>() {
public int compare(NumWithDiff n1, NumWithDiff n2) {
if(n1.diff <= n2.diff) {
return -1;
}
return 1;
}
});
int roundSum = (int)Math.round(sum);
int toCeilNum = roundSum - floorSum;
int[] results = new int[nums.length];
int i = 0;
while(i < toCeilNum) {
results[i] = diffNums[i].num;
i++;
}
while(i < nums.length) {
results[i] = diffNums[i].num - 1;
i++;
}
return results;
}
https://github.com/gabhi/leetcode-1/blob/master/b/Rounding.java
public int[] round(Double[] input) {
if(input == null || input.length == 0) return new int[0];
Queue<Double> minCeil = new PriorityQueue<Double>(input.length, new Comparator<Double>() {
public int compare(Double x, Double y) {
return Double.compare(Math.ceil(x) - x, Math.ceil(y) - y);
}
});
// Get offset
Double sum = 0.0;
int floorSum = 0;
int[] res = new int[input.length];
for(int i = 0; i < input.length; i++) {
sum += input[i];
int floor = (int) Math.floor(input[i]);
floorSum += floor;
res[i] = floor;
minCeil.add(input[i]);
}
// Numbers contributing to larger
int offset = (int) Math.round(sum) - floorSum;
Set<Double> mins = new HashSet<>();
for(int i = 0; i < offset; i++) {
mins.add(minCeil.poll());
}
for(int i = 0; i < res.length && offset > 0; i++) {
if(mins.contains(input[i])) {
res[i]++;
offset--;
}
}
return res;
}
https://stackoverflow.com/questions/792460/how-to-round-floats-to-integers-while-preserving-their-sum
http://www.1point3acres.com/bbs/thread-161001-1-1.html
float也行。然后还要考虑正负。
http://www.1point3acres.com/bbs/thread-156061-1-1.html
像LC里的text justification, regular expression matching在他家都算是热身题,感觉大部分题自己都不能独立做出来,比如csv parser, 之类
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=146539
他们公司list价格分成好几个部分,但是都是整数,如果在美金是整数,到了欧洲的网页显示汇率转换之后就变成了floating point,然后要round成整数,但是全部加起来round,和单独round再加起来,结果会不一样
# base price 100 => 131.13 => 131
# cleaning fee 20 => 26.23 => 26
# service fee 10 => 13.54 => 14
# tax 5 => 6.5 => 7
# => 177.4E => 178E
# sum 135$ => 178.93E => 179E
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
那么问题就来了,给个input list of floating points, 要求output list of integers, 满足以下两个constraint, 就是和跟Round(x1+x2+... +xn)的结果一样,但是minimize output 和input的绝对值差之和
#Input: A = [x1, x2, ..., xn]
# Sum T = Round(x1+x2+... +xn) ; 178.93E => 179
# Output: B = [y1, y2, ...., yn]
# Constraint #1: y1+y2+...+yn = T
# Constraint #2: minimize sum(abs(diff(xi - yi)))
举例. visit 1point3acres.com for more.
# A = [1.2, 2.3, 3.4]
# Round(1.2 + 2.3 + 3.4) = 6.9 => 7
# 1 + 2 + 3 => 6
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
# 1 + 3 + 3 => 7. 鍥磋鎴戜滑@1point 3 acres
# 0.2 + 0.7 + 0.4 = 1.3
# 1 + 2 + 4 => 7
# 0.2 + 0.3 + 0.6 = 1.1
所以[1,2,4]比[1,3,3]要好
Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn). We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where yi = Floor(xi) or Ceil(xi), ceiling or floor of xi.
We also want to minimize sum |x_i-y_i|
17. Round Prices: 每个数统一向下取整,然后判断其sum与原近似值sum差值多少来决定有多少数需要向上取整,然后根据小数部分排序,拥有较小的小数部分的数向下取整,其他的向上取整
https://github.com/allaboutjst/airbnb/blob/master/src/main/java/round_prices/RoundPrices.java
public int[] roundUp(double[] arr) {
int n = arr.length;
NumWithDiff[] arrWithDiff = new NumWithDiff[n];
double sum = 0.0;
int floorSum = 0;
for (int i = 0; i < n; i++) {
int floor = (int) arr[i];
int ceil = floor;
if (floor < arr[i]) ceil++;
floorSum += floor;
sum += arr[i];
arrWithDiff[i] = new NumWithDiff(ceil, ceil - arr[i]);
}
int num = (int) Math.round(sum);
int diff = num - floorSum;
Arrays.sort(arrWithDiff, new Comparator<NumWithDiff>() {
@Override
public int compare(NumWithDiff n1, NumWithDiff n2) {
if (n1.diffWithCeil <= n2.diffWithCeil) return -1;
else return 1;
}
});
// Arrays.sort(arrWithDiff, (a, b) -> (Double.compare(b.diffWithCeil, a.diffWithCeil)));
int[] res = new int[n];
int i = 0;
for (; i < diff; i++) {
res[i] = arrWithDiff[i].num; // 这些放ceil
}
for (; i < n; i++) {
res[i] = arrWithDiff[i].num - 1; // 剩下的只放floor
}
return res;
}
class NumWithDiff {
int num;
double diffWithCeil;
public NumWithDiff(int n, double c) {
this.num = n;
this.diffWithCeil = c;
}
}
public int[] roundUp(double[] prices) {
if (prices == null || prices.length == 0) {
return new int[0];
}
int[] res = new int[prices.length];
double sum = 0;
int roundSum = 0;
Number[] numbers = new Number[prices.length];
for (int i = 0; i < prices.length; i++) {
numbers[i] = new Number(prices[i], i);
sum += prices[i];
roundSum += (int) Math.round(prices[i]);
res[i] = (int) Math.round(prices[i]);
}
int sumRound = (int) Math.round(sum);
if (sumRound == roundSum) {
return res;
} else if (sumRound > roundSum) {
Arrays.sort(numbers, (a, b) -> (Double.compare(b.frac, a.frac)));
int count = sumRound - roundSum;
for (int i = 0; i < prices.length; i++) {
Number num = numbers[i];
if (num.frac < 0.5 && count > 0) {
res[num.index] = (int) Math.ceil(num.val);
count--;
} else {
res[num.index] = (int) Math.round(num.val);
}
}
} else {
Arrays.sort(numbers, (a, b) -> (Double.compare(a.frac, b.frac)));
int count = roundSum - sumRound;
for (int i = 0; i < prices.length; i++) {
Number num = numbers[i];
if (num.frac >= 0.5 && count > 0) {
res[num.index] = (int) Math.floor(num.val);
count--;
} else {
res[num.index] = (int) Math.round(num.val);
}
}
}
return res;
}
class Number {
double val;
double frac;
int index;
Number(double val, int index) {
this.val = val;
this.frac = val - Math.floor(val);
this.index = index;
}
}
When you book on airbnb the total price is:
Total price = base price + service fee + cleaning fee + ...
input : array of decimals ~ X
output : array of int ~ Y
output : array of int ~ Y
But they need to satisfy the condition:
- sum(Y) = round(sum(x))
- minmize (|y1-x1| + |y2-x2| + ... + |yn-xn|)
Example1:
input = 30.3, 2.4, 3.5
output = 30 2 4
input = 30.3, 2.4, 3.5
output = 30 2 4
Example2:
input = 30.9, 2.4, 3.9
output = 31 2 4
airbnb面试题汇总input = 30.9, 2.4, 3.9
output = 31 2 4
先将所有floor(x)加起来统计出如果所有都floor的话还差多少,按照ceil以后需要加的价格排序,贪心取最小的补齐即可。
def roundNum(self, input):
output = map(lambda x: floor(x), input)
remain = int(round(sum(input)) - sum(output))
it = sorted(enumerate(input), key=lambda x: x[1] - floor(x[1]))
for _ in xrange(remain):
output[it.pop()[0]] += 1
return output
//c++
vector<int> roundNumber(vector<double>& prices) {
vector<int> ans;
int got = 0;
double all = 0.0;
vector<pair<double, int> > s_prices;
for (int i = 0; i < prices.size(); ++i) {
double price = prices[i];
int tmp = int(floor(price));
got += tmp;
ans.push_back(tmp);
all += price;
s_prices.push_back(make_pair(price, i));
}
sort (s_prices.begin(), s_prices.end(),
[](pair<double, int> a, pair<double, int> b)
{ return a.first - floor(a.first) > b.first - floor(b.first);});
for (int i = 0; i < int(round(all)) - got; ++i) {
ans[s_prices[i].second]++;
}
return ans;
}
from math import floor
def roundNumbers(input):
output = map(lambda x: floor(x), input)
remain = round(sum(input) - sum(output))
it = sorted(enumerate(input), key=lambda i: i[1] - floor(i[1]))
for _ in range(remain):
output[it.pop()[0]] += 1
return output
https://github.com/joseph5wu/LeetCode/blob/master/src/airbnb/roundsSum/Solution.javapublic static int[] round(double[] nums) {
// calculate the round sum, and then sort the nums with the difference between ceiling
// and then make those close to ceil be ceiling, close to floor be floor
NumWithDiff[] diffNums = new NumWithDiff[nums.length];
double sum = 0.0;
int floorSum = 0;
for(int i = 0; i < nums.length; i++) {
double num = nums[i];
int floor = (int) num;
int ceil = floor;
if(floor < num) {
ceil++;
}
floorSum += floor;
sum += num;
diffNums[i] = new NumWithDiff(ceil, ceil - num);
}
// sort the diffNums
Arrays.sort(diffNums, new Comparator<NumWithDiff>() {
public int compare(NumWithDiff n1, NumWithDiff n2) {
if(n1.diff <= n2.diff) {
return -1;
}
return 1;
}
});
int roundSum = (int)Math.round(sum);
int toCeilNum = roundSum - floorSum;
int[] results = new int[nums.length];
int i = 0;
while(i < toCeilNum) {
results[i] = diffNums[i].num;
i++;
}
while(i < nums.length) {
results[i] = diffNums[i].num - 1;
i++;
}
return results;
}
https://github.com/gabhi/leetcode-1/blob/master/b/Rounding.java
public int[] round(Double[] input) {
if(input == null || input.length == 0) return new int[0];
Queue<Double> minCeil = new PriorityQueue<Double>(input.length, new Comparator<Double>() {
public int compare(Double x, Double y) {
return Double.compare(Math.ceil(x) - x, Math.ceil(y) - y);
}
});
// Get offset
Double sum = 0.0;
int floorSum = 0;
int[] res = new int[input.length];
for(int i = 0; i < input.length; i++) {
sum += input[i];
int floor = (int) Math.floor(input[i]);
floorSum += floor;
res[i] = floor;
minCeil.add(input[i]);
}
// Numbers contributing to larger
int offset = (int) Math.round(sum) - floorSum;
Set<Double> mins = new HashSet<>();
for(int i = 0; i < offset; i++) {
mins.add(minCeil.poll());
}
for(int i = 0; i < res.length && offset > 0; i++) {
if(mins.contains(input[i])) {
res[i]++;
offset--;
}
}
return res;
}
https://stackoverflow.com/questions/792460/how-to-round-floats-to-integers-while-preserving-their-sum
http://www.1point3acres.com/bbs/thread-161001-1-1.html
Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn).
We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where yi = Floor(xi) or Ceil(xi), ceiling or floor of xi.
We also want to minimize sum |x_i-y_i|
float也行。然后还要考虑正负。
http://www.1point3acres.com/bbs/thread-156061-1-1.html
像LC里的text justification, regular expression matching在他家都算是热身题,感觉大部分题自己都不能独立做出来,比如csv parser, 之类
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=146539
他们公司list价格分成好几个部分,但是都是整数,如果在美金是整数,到了欧洲的网页显示汇率转换之后就变成了floating point,然后要round成整数,但是全部加起来round,和单独round再加起来,结果会不一样
# base price 100 => 131.13 => 131
# cleaning fee 20 => 26.23 => 26
# service fee 10 => 13.54 => 14
# tax 5 => 6.5 => 7
# => 177.4E => 178E
# sum 135$ => 178.93E => 179E
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
那么问题就来了,给个input list of floating points, 要求output list of integers, 满足以下两个constraint, 就是和跟Round(x1+x2+... +xn)的结果一样,但是minimize output 和input的绝对值差之和
#Input: A = [x1, x2, ..., xn]
# Sum T = Round(x1+x2+... +xn) ; 178.93E => 179
# Output: B = [y1, y2, ...., yn]
# Constraint #1: y1+y2+...+yn = T
# Constraint #2: minimize sum(abs(diff(xi - yi)))
举例. visit 1point3acres.com for more.
# A = [1.2, 2.3, 3.4]
# Round(1.2 + 2.3 + 3.4) = 6.9 => 7
# 1 + 2 + 3 => 6
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
# 1 + 3 + 3 => 7. 鍥磋鎴戜滑@1point 3 acres
# 0.2 + 0.7 + 0.4 = 1.3
# 1 + 2 + 4 => 7
# 0.2 + 0.3 + 0.6 = 1.1
所以[1,2,4]比[1,3,3]要好
- // 思路就是先把所有floor加起来,然后看差多少,然后把多少个floor转成ceil
- // 转的时候按照num本身与ceil的距离排序
- public static int[] getNearlyArrayWithSameSum(double[] arr) {
- NumWithDiff[] arrWithDiff = new NumWithDiff[arr.length];
- double sum = 0.0;
- int floorSum = 0;
- for (int i = 0; i < arr.length; i++) {
- int floor = (int)arr[i];
- int ceil = floor;
- if (floor < arr[i]) ceil++; // 查是不是4.0这种floor/ceil都是本身的
- floorSum += floor;
- sum += arr[i];. 1point3acres.com/bbs
- arrWithDiff[i] = new NumWithDiff(ceil, ceil - arr[i]); // 把ceil都放在数组里面进行比较
- }
- int num = (int) Math.round(sum);
- int diff = num - floorSum;
- Arrays.sort(arrWithDiff, new Comparator<NumWithDiff>() {
- public int compare(NumWithDiff n1, NumWithDiff n2) {. from: 1point3acres.com/bbs
- if (n1.diffWithCeil <= n2.diffWithCeil) return -1;
- else return 1;
- }
- });. from: 1point3acres.com/bbs
- int[] res = new int[arr.length];
- int i = 0;. From 1point 3acres bbs
- for (; i < diff; i++) {. 1point3acres.com/bbs
- res[i] = arrWithDiff[i].num; // 这些放ceil
- }
- for (; i < arr.length; i++) {
- res[i] = arrWithDiff[i].num - 1; // 剩下的只放floor
- }
- return res;
- }