[心得]面接問題の分析と整理3

この書き方では、1つのブログに4つのテーマが書かれています
9.段差問題f(0)=0;f(1)=1; f(2)=1+1=2; 繰返し式:f(n)=f(n-1)+f(n-2)+f(n-3)
面接金典第221ページ原題.

#include 
using namespace std;

int count_steps(int n, int *map);

int main()
{
    const int N=10;
    int map[N];
    for(int i=0;imap[i]=-1;
    }

    for(int i =0; icout<"\t"<map)<return 0;
}

int count_steps(int n, int *map)
{
    if(n<0) return 0;
    else if(!n) return 1;
    else if(map[n]>=0)  return map[n];
    else
    {
        map[n] = count_steps(n-1, map) + count_steps(n-2, map) + count_steps(n-3, map);
        return map[n];
    }
}

ダイナミックプランニングアルゴリズムは、サブ問題ごとに1回のみ解き、その結果を保存し、サブ問題が発生するたびに答えを再計算することを回避します.ここでは再帰も使われています
10.10進数から2進数すべての表示方法数を求める例えば1->1 2->10,02 3->11 4->100,020,012 5->101,021 6->110022102 F(0)=0 F(1)=1 F(2)=2 F(3)=1=F(1)F(4)=3=F(1)+F(2)F(5)=2=F(2)F(6)=F(2)+F 9(3)=1+2=3
式をまとめると、F(0)=0 F(1)=1 F(2)=2 F(n)=F((n-1)/2)if nis odd F(n)=F(n/2)+F((n-2)/2)if nis even
コード略も再帰解法です
11.インクリメント数列の各項目を3^i*5^j*7^k(i,j,k>=0)と表すことができます.

#include 
#include 
#include 
using namespace std;

int getMagicNumber(int n);
int getNextNum(queue<int> &q3, queue<int> &q5, queue<int> &q7, int *nextQ);

int main()
{
    for(int i=0;i<11;++i)
        cout<":\t"<return 0;
}

int getMagicNumber(int n)
{
    if(n<=0)    return 0;
    queue<int> q3,q5,q7;
    stack<int> s;

    int cnt=0;
    int nextNum, nextQ;
    while(cntreturn s.top();
}

int getNextNum(queue<int> &q3, queue<int> &q5, queue<int> &q7, int *nextQ)
{
    int min;
    if(q3.empty())
    {
        min=1;
        *nextQ=3;
    }else
    {
        if(q3.front()3;
        }else if(q5.front()5;
        }else{
            min = q7.front();
            q7.pop();
            *nextQ=7;
        }

        switch(*nextQ)
        {
            case 3: q3.push(min*3);
            case 5: q5.push(min*5);
            default:q7.push(min*7);
        }
        return min;
    }
}

最適化できる点:stackはback関数のみで末尾要素を取得するのでqueueに置き換えることができ、同時に関数のインタフェースを3つのパラメータに簡略化することができる.
このテーマではstlのqueueやstackなどのモジュールの使い方も示しています
12.ツリーの右隣のノードを探すために再帰と非再帰の両方を要求するこの問題の非再帰は、各層にわたって右隣のノードを出力する層順ループを行うことができる.

#include 
#include 
using namespace std;

typedef struct Node* NodePointer;

struct Node
{
    int data;
    int depth;
    NodePointer lChild;
    NodePointer rChild;
    NodePointer rBrother;
};

struct myQueue{};

void findRBrother(NodePointer root);
void addToQueue(NodePointer root, myQueue q);
void findRBrotherRecursive(NodePointer root);

int main()
{
    NodePointer root=0;
    findRBrother(root);
    findRBrotherRecursive(root);
    return 0;
}

void findRBrother(NodePointer root)
{
    if(!root)   return;
    root->depth = 0;
    queue q;
    NodePointer last=0, next;
    while(!q.empty())
    {
        next = q.front();
        q.pop();

        q.push(next->lChild);
        q.push(next->rChild);

        if(last->depth == next->depth)
        {
            last->rBrother = next;
        }
        last = next;
    }
}

void findRBrotherRecursive(NodePointer root)
{
    int front=0,rear=0;
    NodePointer left,right;
    left = root;
    right = root->lChild;
    queue q;
    if(!root)   return;
    if(root->lChild)
        q.push(root->lChild);
    if(root->rChild)
        q.push(root->rChild);

    while(right)
    {
        left->rBrother = right;
        left = right;
        right=right->lChild;

        if(left->lChild)
            q.push(left->lChild);
        if(left->rChild)
            q.push(left->rChild);
    }
    if(q.empty())   return;
    left = q.front();
    q.pop();
    findRBrotherRecursive(left);
}

このコードはデータ構造の拡張能力を体現している.
ここでは、上位レベルのコードを添付して印象を深めます.

void levelOrder(NodePointer root)
{
    int front=0, rear = 0;
    queue q;
    if(!root)   return;
    q.push(root);
    while(1)
    {
        root = q.front();
        q.pop();
        if(!root)   break;
        cout<data<if(root->lChild)
            q.push(root->lChild);
        if(root->rChild)
            q.push(root->rChild);
    }
}