Prepaid mastercard 丢了，怎么办 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

Prepaid mastercard 丢了，怎么办

Prepaid mastercard 丢了，怎么办# Money - 海外理财

s*s2015-03-27 07:03

1 楼

1. merger sort a single linked list
2. find minimum k from two sorted array
我写得又长又臭，求短小精悍，清晰易懂的C++ codes.

s*r2015-03-27 07:03

2 楼

好几个月几个月以前买的master prepaid debit card，后来用了一次，当时以为用掉
了，就扔了，最近发现那个transaction被
declined, 所以钱还在那张卡里
我知道在哪里买的卡，也知道卡的后四位，这怎么处理啊，谢谢
能挂失吗？

a*n2015-03-27 07:03

3 楼

第二题
int findKthSmallest(int A[], int m, int B[], int n, int k) {
if (m>n) return findKthSmallest(B,n,A,m,k);
if (m==0) return B[k-1];
if (k==1) return min(A[0], B[0]);
int i = min(m-1,k/2);
int j = k-1-i;
int Ai_1 = (i==0)?INT_MIN:A[i-1];
int Bj_1 = (j==0)?INT_MIN:B[j-1];
int Ai = (i==m)?INT_MAX:A[i];
int Bj = (j==n)?INT_MAX:B[j];
if(Ai_1if(Bj_1if(Ai==Bj) return Ai;
if (Aireturn findKthSmallest(A,i,B+j+1, n-j-1, k-j-1);
}

d*02015-03-27 07:03

4 楼

不知道能否挂失

e*s2015-03-27 07:03

5 楼

有没有对空间要求？只能用原来的list?

j*x2015-03-27 07:03

6 楼

https://github.com/justicezyx/puzzles/blob/master/list_merge_sort.cpp
https://github.com/justicezyx/puzzles/blob/master/find_kth_of_two_sorted_
arrays.cpp
又臭又长的给你增加点信心

b*72015-03-27 07:03

7 楼

1. merger sort a single linked list
template
ListNode * mergeHelper(ListNode * left, ListNode * right)
{
assert(left != NULL && right != NULL);
ListNode * head = NULL;
if(left->val < right->val)
{
head = left;
left = left->next;
}
else
{
head = right;
right = right->next;
}
while( left != NULL && right != NULL)
{
if(left->val < right->val)
{
head->next = left;
left = left->next;
}
else
{
head->next = right;
right = right->next;
}
head = head->next;
}
head->next = (left != NULL) ? left : right;
return head;
}
template
pair *, ListNode *> partitionHelper(ListNode * head)
{
assert(head != NULL && head->next != NULL);
ListNode * slow = head;
ListNode * fast = head;
while(fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return make_pair(head, slow);
}
template
ListNode * mergeSort(ListNode * head)
{
if(head == NULL || head->next == NULL)
return head;
auto r = partitionHelper(head);
ListNode * left = mergeSort(r.first);
ListNode * right = mergeSort(r.second);
return mergeHelper(left, right);
}
2. find minimum k from two sorted array
template
T findkthElem(T A[], int len1, T B[], int len2, int k)
{
assert(k> 0 && k <=len1+len2 && len1 >= 0 && len2 >= 0);
if(len1 == 0) return B[k-1];
if(len2 == 0) return A[k-1];
if(k == 1) return min(A[0], B[0]);
int k1 = k/2;
int k2 = k - k1;
if(k1 > len1)
{
k1 = len1;
k2 = k - k1;
}
if(k2 > len2)
{
k2 = len2;
k1 = k - k2;
}
if(A[k1-1] < B[k2-1])
{
return findkthElem(A+k1, len1 - k1, B, len2, k2);
}
else
{
return findkthElem(A,len1, B+k2, len2-k2, k1);
}
}

s*s2015-03-27 07:03

8 楼

多谢楼上的几位。

s*s2015-03-27 07:03

9 楼

学习重写了一遍。不太理解 partitionHelper为什么要返回head in the pair?在
mergeSort()里,
ListNode *left = mergeSort(head);
就可以了吧？
另外，这个megersort的复杂度是O(NlgN)?

【在 b******7 的大作中提到】

: 1. merger sort a single linked list
: template
: ListNode * mergeHelper(ListNode * left, ListNode * right)
: {
: assert(left != NULL && right != NULL);
: ListNode * head = NULL;
: if(left->val < right->val)
: {
: head = left;
: left = left->next;