一刀也不切,提出一定不要死记硬背

作者:澳门娱乐

  链表的逆置常作为应届生面试题,主要考察求职者对链表的理解,还有思维能力。逆置的思路主要是保存几个临时的指针变量,其实好多面试题都可以通过保存临时变量的方式来解决。对于此类问题,建议一定不要死记硬背,因为死记硬背一定会随着时间的推移而忘记,建议按照pPrev,pNode,pNext依次向后推移的思路理解的基础上记住。

Pizza pieces

  以下C++代码给出了两种实现,一种是循环,一种是递归。注意递归的时候要采用尾递归的形式。因为普通递归在调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,因此递归次数过多容易造成栈溢出。尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。

Description

In her trip to Italy, Elizabeth Gilbert made it her duty to eat perfect pizza. One day, she ordered one for dinner. And then some Italian friends appeared at her room.

The problem is that there were many people who ask for a piece of pizza at that moment. And she had a knife that only cuts straight.

Given a number K (K<=45000), help her get the maximum of pieces possible (not necessarily of equal size) with Kcuts. If K is a negative number, the result must be -1 (or Nothing in Haskell).

  尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈,而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可,之前的可优化删去。

Examples

maxPizza(0) == 1
maxPizza(1) == 2
maxPizza(3) == 7

 

4刀,可以分成11块

澳门娱乐6165,是11块, 
这个数有规律: 
一刀也不切,切0刀:还是1快 
切1刀:1+1=2块 
切2刀:2+2=4 
切3刀:3+4=7 
切4刀:4+7=11 
切5刀:5+11=16 
当前下刀能切成的块数=现在是第几刀的数+前一刀已经切成的块数 
公式:Xn=(n+1)*n/2+1,Xn是切成的块数,n是切割的次数. 

 

使用递归处理,需要注意使用尾递归

顾名思义,尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。

  尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈,而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可,之前的可优化删去。

public class Pizza
{

    public static int  maxPizza(int cut) {
        //TODO : Code goes here
      if (cut < 0)
            {
                return -1;
            }
            else if (cut == 0)
            {
                return 1;
            }
            else
            {
                return maxPizza(cut - 1) + cut;
            }
  }
}

 

其他人的解法:

使用for循环的,当然了这个for循环可以使用Linq来简化

return cut < 0 ? -1 : Enumerable.Range(1, cut).Aggregate(1, (x, y) => x + y);

public class Pizza
{

    public static int  maxPizza(int cut) {

    if(cut < 0)
    {
      return -1;
    }

    if(cut == 0)
    {
      return 1;
    }

    int result = 0;

    for(int i = 1; i <= cut; i++)
    {
      result = result + i;
    }

    return result + 1;
  }
}

 

#include "stdafx.h"

struct ListNode
{
    int m_nData;
    ListNode* m_pNext;
};

// pPrev    pNode    pNext
// 正常实现
ListNode* ReverseList(ListNode *pHead)
{
    ListNode* pNode = pHead;
    ListNode* pReversedHead = NULL;
    ListNode* pPrev = NULL;
    while(NULL != pNode)
    {
        ListNode* pNext = pNode->m_pNext;// 保存当前节点的下一个节点
        if (NULL == pNext)
            pReversedHead = pNode;// 如果下一节点为NULL,则当前节点为反转后的头节点,记录

        pNode->m_pNext = pPrev;// 将当前节点的下一个节点指向已经记录的前一个节点,因为要反转嘛
        pPrev = pNode;// 现在要向右错位了,前一个节点成为了当前节点
        pNode = pNext;// 当前节点成为了当前节点的下一个节点
    }
    return pReversedHead;
}
// 递归实现
ListNode* ReverseSingle(ListNode* pNode, ListNode* pPrev)
{
    if (NULL == pNode)
    {
        return pPrev;
    }

    ListNode* pNext = pNode->m_pNext;// 保存当前节点的下一个节点
    pNode->m_pNext = pPrev;

    return ReverseSingle(pNext, pNode);
}

ListNode* ReverseListRecursive(ListNode *pHead)
{
    ListNode* pNode = pHead;
    ListNode* pPrev = NULL;

    return ReverseSingle(pNode, pPrev);
}

int _tmain(int argc, _TCHAR* argv[])
{
    int len = 10;
    ListNode *pHead = new ListNode;
    pHead->m_nData = 10;
    pHead->m_pNext = NULL;
    ListNode *pPrev = pHead;

    for (int i=0; i<len; i++)
    {
        ListNode *p = new ListNode;
        p->m_nData = i; 
        p->m_pNext = NULL;
        if (NULL != pPrev)
        {
            pPrev->m_pNext = p;
        }
        pPrev = p;
    }

    //ListNode *pReversedHead = ReverseList(pHead);
    ListNode* pReversedHead = ReverseListRecursive(pHead);

    return 0;
}

   尾递归可以参考:递归与尾递归总结。

本文由澳门娱乐6165发布,转载请注明来源

关键词: