请问有没有网站兑换quarter的？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

请问有没有网站兑换quarter的？

请问有没有网站兑换quarter的？# Money - 海外理财

a*y2013-12-19 08:12

1 楼

sorted array with repeated elements
for given element, find out its range.
e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
binary search的变种
我感觉这个不是O（logn）啊
code是发现repeat次数的
int binarySearch(char* charset, int start, int end, char target)
{
if (charset == NULL) return 0;
if (start == end)
{
if (charset[start] == target) return 1;
else return 0;
}
int mid = start + (end-start)/2;

int left = 0, right = 0;
left = binarySearch(charset,start,mid-1,target);
right = binarySearch(charset, mid+1, end, target);
return (charset[mid] == target ? left+right+1 : left + right);

}

e*n2013-12-19 08:12

2 楼

不想总去银行换，请问有没有网站兑换的？多谢了

d*n2013-12-19 08:12

3 楼

size_t left, right, found;
size_t found=bsearch(array, start, end, target );
left=right=found;
while (array[left--]==target) left=found;
while (array[right++]==target) right=found;
return left, right

z*82013-12-19 08:12

4 楼

洗衣店造币厂

S*I2013-12-19 08:12

5 楼

http://www.cplusplus.com/reference/algorithm/equal_range/

【在 a*******y 的大作中提到】

: sorted array with repeated elements
: for given element, find out its range.
: e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6]
: binary search的变种
: 我感觉这个不是O（logn）啊
: code是发现repeat次数的
: int binarySearch(char* charset, int start, int end, char target)
: {
: if (charset == NULL) return 0;
: if (start == end)

a*y2013-12-19 08:12

6 楼

No , worst case is O(n) for this

【在 d****n 的大作中提到】

: size_t left, right, found;
: size_t found=bsearch(array, start, end, target );
: left=right=found;
: while (array[left--]==target) left=found;
: while (array[right++]==target) right=found;
: return left, right

d*n2013-12-19 08:12

7 楼

你也没说要求啊

【在 a*******y 的大作中提到】

: No , worst case is O(n) for this

a*y2013-12-19 08:12

8 楼

要log（n)的

f*n2013-12-19 08:12

9 楼

Functions to find the left and right bounds, both log(n):
// left bound, inclusive
int binarySearch_left(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low < high) {
mid = (low + high) / 2;
if (arr[mid] >= value)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
// right bound, inclusive
int binarySearch_right(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return low - 1;
}

f*n2013-12-19 08:12

10 楼

那个code是O(n)

【在 a*******y 的大作中提到】

S*I2013-12-19 08:12

11 楼

Read the source code of equal_range in a C++ implementation. In both VC and
GCC, implementation of equal_range is based on lower_bound and upper_bound,
both of which have log(n) complexity if the range to be searched is a sorted
array. So equal_range has complexity 2log(n).

【在 a*******y 的大作中提到】

: 要log（n)的

l*c2013-12-19 08:12

12 楼

you lost one more step in each function. Think about "ABBC". Your approach
will find 0 as the left edge.
Try to add this before return in:
if (array[low]else return low;

【在 f*******n 的大作中提到】

: Functions to find the left and right bounds, both log(n):
: // left bound, inclusive
: int binarySearch_left(char* arr, int len, char value) {
: int low = 0, high = len-1, mid;
: while (low < high) {
: mid = (low + high) / 2;
: if (arr[mid] >= value)
: high = mid - 1;
: else
: low = mid + 1;

a*y2013-12-19 08:12

13 楼

我觉得他应该把第一个那个“<=”改成< 就行了

【在 l****c 的大作中提到】

:
: you lost one more step in each function. Think about "ABBC". Your approach
: will find 0 as the left edge.
: Try to add this before return in:
: if (array[low]: else return low;

a*y2013-12-19 08:12

14 楼

吧这个 if (arr[mid] >= value) 中的大于等于改成《
第二个function return hi
我来贴两个吧，test过了
int binarySearchLower(int A[], int l, int h, int k) {
int lo = l;
int hi = h;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
if (A[mid] < k)
lo = mid+1;
else
hi = mid-1;
}

return lo;
}
int binarySearchUpper(int A[], int low, int high, int k)
{
int lo = low;
int hi = high;
while (lo <=hi)
{
int mid = lo + (hi-lo)/2;
if (A[mid] > k)
hi = mid - 1;
else
lo = mid + 1;
}
return hi;
}

【在 f*******n 的大作中提到】

f*n2013-12-19 08:12

15 楼

Copying mistake
// left bound, inclusive
int binarySearch_left(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] >= value)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
// right bound, inclusive
int binarySearch_right(char* arr, int len, char value) {
int low = 0, high = len-1, mid;
while (low < high) {
mid = (low + high) / 2;
if (arr[mid] > value)
high = mid - 1;
else
low = mid + 1;
}
return low - 1;
}