1155 Heap Paths (30分)[堆][DFS][回溯]

By Jalan

知识工具需求

数学

数据结构和算法

• heap
• DFS
• 回溯

语言

题干

你得检查一下是不是堆(最大最小都行)

输入条件

N[1,1000]个树的节点,节点范围在int内,下面给了N个树是层序遍历的结果

输出条件

每行打印每一个根结点到子叶的路径上的节点
最后打印Min Heap/Max Heap/Not Heap

例子

例1

输入

8
98 72 86 60 65 12 23 50

输出

98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap

例2

输入

8
8 38 25 58 52 82 70 60

输出

8 25 70
8 25 82
8 38 52
8 38 58 60
Min Heap

例3

输入

8
10 28 15 12 34 9 8 56

输出

10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

题解

第一次

思路

DFS回溯一下即可

1. 输入
2. 计算子叶节点数
3. 按顺序把所有子叶节点加入leafs数组.
4. 遍历leafs数组向上找直到根节点,把路径录入到route里.输出route,
5. 判断三种类型
6. 输出类型

预期时间复杂度

nlogn

编写用时

90分钟,里面估计有40分钟在debug有30分钟在写怎么判断是哪种.///

代码

CPP

#include <algorithm>
#include <regex>
#include <stdio.h>
#include <vector>

using namespace std;
int n;
vector<int> inputList;
bool isMaxHeap = true;
bool isMinHeap = true;
bool isNotHeap = true;
vector<int> route;

int main(int argc, char const *argv[])
{
    //1
    scanf("%d", &n);
    inputList.resize(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &inputList[i]);
    }
    //2
    int sum = 0;
    int temp = 1;
    int level = 0;
    while (sum < n)
    {
        level++;
        sum += temp;
        temp *= 2;
    }
    int n_1LevelTotal = sum - (sum + 1) / 2;                    //除最下一层外共有这么多节点
    int nLevelCounter = n - n_1LevelTotal;                      //最下一层有这么多节点
    int n_1LevelCounter = (n_1LevelTotal + 1) / 2;              //倒数第二层共有这么多节点
    int leafRouteCounter = nLevelCounter / 2 + n_1LevelCounter; //子叶节点数.
    int n_1LevelLeafCounter = leafRouteCounter - nLevelCounter; //倒数第二层子叶节点数
    //3
    vector<int> leafsIndex;
    int n_1EndIndex = n_1LevelTotal - 1;
    int nEndIndex = n - 1;
    for (int i = 0; i < n_1LevelLeafCounter; i++)
    {
        leafsIndex.push_back(n_1EndIndex - i);
    }
    for (int i = 0; i < nLevelCounter; i++)
    {
        leafsIndex.push_back(nEndIndex - i);
    }
    //4
    vector<int> routeSign;
    for (int p = 0; p < leafsIndex.size(); p++)
    {
        int leafIndex = leafsIndex[p];
        int leafLevel;
        if (leafIndex <= n_1EndIndex)
        {
            leafLevel = level - 1;
        }
        else
        {
            leafLevel = level;
        }
        route.resize(leafLevel);
        int travelIndex = leafIndex;
        for (int i = 0; i < leafLevel; i++)
        {
            route[leafLevel - 1 - i] = inputList[travelIndex];
            if (travelIndex & 1)
            {
                travelIndex = (travelIndex - 1) / 2;
            }
            else
            {
                travelIndex = (travelIndex - 2) / 2;
            }
        }
        for (int i = 0; i < leafLevel; i++)
        {
            printf("%d", route[i]);
            if (i != leafLevel - 1)
            {
                printf(" ");
            }
        }
        printf("\n");
        //排除法2错一对就代表已经定性了,要不就还要遍历判断.
        int Sign = 0;
        if (isMaxHeap)
        {
            ++Sign;
        }
        if (isMinHeap)
        {
            ++Sign;
        }
        if (isNotHeap)
        {
            ++Sign;
        }
        if (Sign == 1)
        {
            continue;
        }
        else
        {
            if (leafLevel > 1)
            {
                int i = 1;
                for (; i < leafLevel; i++)
                {
                    if (route[i] >= route[i - 1])
                    {
                        break;
                    }
                }
                if (i == 1)
                {
                    i = 1;
                    for (; i < leafLevel; i++)
                    {
                        if (route[i] <= route[i - 1])
                        {
                            break;
                        }
                    }
                    if (i == leafLevel)
                    {
                        routeSign.push_back(-1);
                    }
                    else
                    {
                        routeSign.push_back(0);
                    }
                }
                else if (i == leafLevel)
                {
                    routeSign.push_back(1);
                }
                else
                {
                    routeSign.push_back(0);
                }
            }
        }

    }
    bool isMin = false, isMax = false;
        int i = 0;
        for (; i < routeSign.size(); i++)
        {
            if (routeSign[i] == 1)
            {
                continue;
            }
            else
            {
                break;
            }
        }
        if (i == (int)routeSign.size())
        {
            isMax=true;
        }else if (i==0) {
            for (; i < routeSign.size(); i++)
            {
                if (routeSign[i]==-1)
                {
                    continue;
                }else
                {
                    break;
                }


            }
            if (i == (int)routeSign.size())
            {
                isMin=true;
            }
        }
    if (isMin)
    {
        printf("Min Heap");
    }else if (isMax) {
        printf("Max Heap");
    }else
    {
        printf("Not Heap");
    }
    return 0;
}

运行用时

第二次

思路

dfs一下试一试

预期时间复杂度

不知道

编写用时

看了柳神的很多,这里就不统计了

代码

CPP

#include <stdio.h>
#include <vector>
using namespace std;
vector<int> route;
int a[1009], n, isMin = 1, isMax = 1;
//从1开始dfs
void dfs(int index)
{
    //假如左右子树都没了.代表一条路径走完
    if (index * 2 > n && index * 2 + 1 > n)
    {
        if (index <= n)
        //用于在dfs不存在的节点时把他们过滤掉.
        {
            //输出整条路径
            for (int i = 0; i < route.size(); i++)
            {
                printf("%d%s", route[i], i != route.size() - 1 ? " " : "\n");
                //这段搬的柳神的,特别适合用于处理行末不能有多余空格的场景.
            }
        }
        return;
    }
    else
    //左右子树都有或者有其中之一
    //在左右子树只有其中之一的情况会dfs一个不存在的index,这时显然满足(index * 2 > n && index * 2 + 1 > n),但是此时(index>n)会直接return所以无所谓.
    {
        route.push_back(a[index * 2 + 1]); //加右子树
        dfs(index * 2 + 1);                //dfs右子树
        route.pop_back();                  //回溯一位
        route.push_back(a[index * 2]);     //加左子树
        dfs(index * 2);                    //dfs左子树
        route.pop_back();                  //回溯一位
    }
}
int main()
{
    scanf("%d", &n);
    //编号1-1000
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    route.push_back(a[1]);
    dfs(1);
    //搬的柳神的快速判断堆的属性.
    for (int i = 2; i <= n; i++)
    {
        if (a[i / 2] > a[i])
        {
            isMin = 0;
        }
        if (a[i / 2] < a[i])
        {
            isMax = 0;
        }
    }
    if (isMin)
    {
        printf("Min Heap");
    }
    else if (isMax)
    {
        printf("Max Heap");
    }
    else
    {
        printf("Not Heap");
    }
    return 0;
}

运行用时

结尾

看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀@[e-mail]
也欢迎关注我的CSDN账号呀,接下来两个月我应该会按这个格式更新所有的PTA甲级题目

                                        **开心code每一天**