Monthly Archives: June 2014
单向链表倒转递归解法
我的解法:
struct node *revert_recursive(struct node *n, struct node **head)
{
struct node *tail;
struct node *tmp;
if (!n->next) {
tail = n;
*head = n;
return tail;
}
tail = revert_recursive(n->next, &tmp);
*head = tmp;
tail->next = n;
n->next = NULL;
return n; /* n is new tail */
}
我的思路是递归过程中要记录new head和tail.
但实际上当解决最小问题的时候知道head了,然后递归返回的时候也就传给父问题了: “return nh”
更妙的是tail不需要保存, head->next就是tail:这点很关键,我想不到。
别人的更漂亮的解法:
struct node *revert_recursive_2(struct node *head)
{
struct node *nh;
if (head == NULL || !head->next)
return head;
nh = revert_recursive_2(head->next);
head->next->next = head; /* head->next is tail */
head->next = NULL;
return nh;
}
target no.
check faxes: 866-225-7041 -> 3
debit card: 888-480-8232
约瑟夫环问题
看解二,妙。
http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html
妙处在于如何找到子问题,并且找出子问题和原问题的关联。
1, 2, 3, … , k, k+1, k+2, … , n
子问题f(n-1)是:
1, 2, 3, … , k, k+1, … , n-1
但如何得到这个子问题呢?
我的错误想法是将k+1变为k, k+2变为k-1, … , n变为n-1
正确的子问题是这样得到的:
k+1, k+2, … , n, 1, 2, … , k-2, k-1
然后做变换:
x -> x`
k+1 -> 1
k+2 -> 2
…
n -> k
…
k-2 -> n-2
k-1 -> n-1
变换公式是:x` = (x-k+n)%n
变回来的公式是:x = (x`+ k)%n
所以有递归式:f(n) = (f(n-1)+k)%n, f(1)=1