当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] PAT1057 Stack (30)(树状数组)

    题意: 模拟一个栈,要求可以输出中位数。 思路: 这题还是有点意思,看题意就知道会卡时间复杂度,想着用multiset试一下发现果然有几个点过不去,后面就没想出来。实际这题应该用树状数组做: Pushx:就update(x,1),就是树状数组的区间更新,c[i]+=1,说明值为i的数出现并更新与其...

    30
    热度
  • [综合] PAT1064 Complete Binary Search Tree (30)(BST)

    题意: 给出一个完全二叉搜索树的键值序列,要求输出层序输出 要点: 完全二叉搜索树的根节点是可以唯一确定的,所以一开始排序一下,再用dfs即可。这题我思路是想到了,但是生成根节点的地方写的有点问题,然后要输出层序是可以用dfs中序遍历再加一个数组直接输出的,这里可以学习一下。 #include<...

    50
    热度
  • [综合] PAT1066 Root of AVL Tree (25)(AVL树)

    题意: 给出一系列要插入平衡搜索二叉树的数,要求输出最后的根节点 思路: 没其他办法,完完全全是AVL树的插入节点模拟,这题就不会写,看别人代码写的。 #include<iostream> #include<algorithm> usingnamespacestd;struc...

    93
    热度
  • [综合] PAT1067 Sort with Swap(0,*) (25)(贪心)

    题意: 给出0~N-1的序列,要求每次只能通过0和其他数交换,最后将所有数排序 思路: 这题还是比较容易想到的,分成两种情况讨论: 0不在0位置,如果0在i位置,那么在i位置的应该是i,所以将i对应的位置与0交换即可 0在第0位且还没排好序,选择还没匹配位置的第一个数与0交换 这题有两个样例卡...

    25
    热度
  • [综合] PAT1068 Find More Coins (30)(DP)

    题意: 给出n枚钱币,要求买价值为m的物品,要求输出具体所用的钱币,如有多种情况输出字典序最小的情况。 思路: 这题就是01背包的变种,状态转移方程很好写:dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+c[i]) 主要难点在于怎么处理多种情况最后输出,基本思路是一开...

    86
    热度
  • [综合] PAT1078 Hashing (25)(hash:二次探测法)

    题意: 给出散列表长和要插入的元素,将这些元素按照读入的顺序插入散列表中,其中散列函数为h(key)=key%TSize,解决冲突采用只向正向增加的二次方探查法。如果题中给出的TSize不是素数,就取第一个比TSize大的素数作为TSize 思路: 这题就是考察一个hash中的处理冲突中的平方探测法...

    51
    热度
  • [综合] PAT1081 Rational Sum(gcd)

    题意: 给出一些分数,要求以分数的形式输出它们的和 思路: 这题就是分别对分子和分母进行处理,中间有个点过不去因为分母过大超过范围,所以中间处理的时候要求出最大公约数,顺便我辗转相除法也忘了,复习一下。 #include<bits/stdc++.h> #defineinf0x3f3f3f...

    9
    热度
  • [综合] PAT1086 Tree Traversals Again (25)(树的遍历)

    题意: 用栈的形式给出一棵树建立的顺序,要求输出后序遍历 思路: push的顺序就是先序遍历,pop出的顺序就是中序遍历,所以直接用二叉树先序和中序遍历转后序即可。主要记录一下模板 #include<bits/stdc++.h> #defineinf0x3f3f3f3f usingnam...

    30
    热度
  • [综合] PAT1087 All Roads Lead to Rome (30)(最短路径+dfs+回溯)

    题意: 有N个城市,M条无向边,从某个给定的起始城市出发,前往名为ROM的城市。每个城市(除了起始城市)都有一个点权(称为幸福值),和边权(每条边所需的花费)。求从起点到ROM所需要的最少花费,并输出其路径。如果路径有多条,给出幸福值最大的那条。如果仍然不唯一,选择路径上的城市平均幸福值最大的那条路...

    22
    热度
  • [综合] PAT1093 Count PAT's (25)(逻辑题)

    题意: 给出一个包含'P','A,'T''三种字符的字符串,问能找到几个PAT子串 思路: 这题是个逻辑题,想到了就很简单,可惜我没想到。基本思路就是找A,A左边的P个数*A右边的T个数累加即可。 #include<algorithm> #include<iostream> ...

    20
    热度
  • [综合] PAT1095 Cars on Campus (30)(模拟)

    题意: 给出n个车牌号、时间点、进出状态的记录,然后查询k个时间点这时校园内的车辆个数。最后还要输出在校园里面呆的时间最长的车的车牌号,以及呆了多久的时间。如果有多辆车就按照它的字母从小到大输出车牌。配对要求是,如果一个车多次进入未出,取最后一个值;如果一个车多次out未进入,取第一个值。 注意:一...

    62
    热度
  • [综合] PAT1145 Hashing - Average Search Time(hash—平方探测法)

    题意: 给定一个序列,用平方探测法解决哈希冲突,然后给出m个数字,如果这个数字不能够被插入就输出”Xcannotbeinserted.”,然后输出这m个数字的平均查找时间 思路: 抽空整套做了一下寒假最新的这套题,感觉还行,大概一个半小时能写完,但是这题就卡住了,前面也出现过这种问题,主要问题在于我...

    17
    热度
  • [综合] PAT1101 Quick Sort (25)(逻辑)

    题意: 快速排序中,我们通常采用某种方法取一个元素作为主元,通过交换,把比主元小的元素放到它的左边,比主元大的元素放到它的右边。给定划分后的N个互不相同的正整数的排列,请问有多少个元素可能是划分前选取的主元?例如给定N=5,排列是1、3、2、4、5。则:1的左边没有元素,右边的元素都比它大,所以它可...

    49
    热度
  • [综合] PAT1104 Sum of Number Segments (20)(数学)

    题意: 给出一个序列的数,要求输出所有连续子集的总和 思路: 这题就是纯粹的数学题,想不到就gg,题意还不明确,给出的序列指的是已经排好序的。基本思路是统计每个数所出现的次数,以该点的位置i,向左有i-1个排序子集,向右有(n-i)个排序子集,左边不能全不用,所以有i种,右边可以全不用也就是到第i个...

    89
    热度
  • [综合] 1110 Complete Binary Tree(完全二叉树)

    题意: 给出一个n表示有n个结点,这n个结点为0~n-1,给出这n个结点的左右孩子,求问这棵树是不是完全二叉树 思路: 这题就是先建树,找出根结点然后层序遍历,我一开始是把每层的结点数存储下来看是否等于2^i,结果有两个案例没过,看别人的代码有更好的方法,就是记录遍历的个数cnt,如果遇到空结点并且...

    11
    热度
  • [综合] PAT1138 Postorder Traversal(树的遍历)

    题意: 给定一棵书的先序遍历和后序遍历,然后找出这棵树后序遍历的第一个元素 思路: 这题的思路很简单,考虑到只要输出第一个元素,所以若有左子树就递归左子树,如果没有左子树,才找右子树。但这题有个点很怪,都是同样的方法我的代码就超时,找了网上别人写的有的能过有的不能过,下面是一个能过的。我看了一下好像...

    19
    热度
  • [综合] PAT1135 Is It A Red-Black Tree(红黑树)

    题意: 给出一棵平衡二叉搜索树的先序序列,要求判断是否为红黑树 思路: 这题一开始我没意识到红黑树都是平衡二叉搜索树,知道后就先按照先序和中序建树,然后按照红黑树的定义,用递归判断每个节点的左右黑节点的个数即可 #include<bits/stdc++.h> usingnamespace...

    91
    热度
  • [综合] PAT1123 Is It a Complete AVL Tree(AVL树完全二叉树)

    题意: 给出一系列数,要求组成AVL树,最后层序输出,并且判断是否为一个完全二叉树 要点: 这题就是一个AVL树的插入和判断完全二叉树,之前分别都有出现过,AVL树的建立需要记忆。 #include<bits/stdc++.h> usingnamespacestd; intcnt=0,n...

    11
    热度
  • [综合] PAT1105 Spiral Matrix(模拟)

    题意: 给出一系列数,要求从大到小螺旋式排列成一个矩阵 思路: 这题看到了一种很好的办法,记录一下,可以先设立一个mapp[m][n]的矩阵并全赋值为-1,这样螺旋时遇到之前插入的值就会停止,这样就可以按行列插入数组。 #include<bits/stdc++.h> usingnames...

    54
    热度
  • [综合] PAT1130 Infix Expression(树的递归)

    题意: 给出一棵符号树,要求加上括号输出正确的序列 思路: 这题一开始没想出来,不知道括号该怎么插入,实际上只要根节点和叶子节点不插入括号,其他的按中序正常插入即可。 #include<bits/stdc++.h> usingnamespacestd;structnode{stringk...

    86
    热度