算法-数据结构 关于算法-数据结构:PAT甲级1085-Perfect-Sequence 从N个正整数中抉择若干个数字组成一个序列,最大值为M,最小值为m,那么该序列中的数字,也就是从m到M的数字肯定是原序列中的间断序列,因为不然就会存在一个数字大于m小于M不在抉择的序列中,而后将其退出到该序列使其长度变大并且合乎题意,那么原来选出的序列就不是最长的了。所以咱们肯定是在一个有序序列中选出一个…
算法-数据结构 关于算法-数据结构:PAT甲级1038-Recover-the-Smallest-Number 这个题要求一堆数字串拼接取得最小的数字,那么对于其部分问题就是有2个数字串,如何拼接使其最小,答案就是先将其2种可能拼接进去比拟其大小即可,而数字的大小其实和转化为字符串的大小比拟是统一的,而且对于拼接操作指的基本上就是字符串操作。那么也即是对于这样一堆数字串转为字符串,而后对于任意2个字符串a和b的…
算法-数据结构 关于算法-数据结构:PAT甲级1067-Sort-with-Swap0-i 依据题目给出的替换例子,仔细观察能够晓得其替换策略为:如果数字0以后在i号位,则找到数字i以后所处的地位,而后把0与i进行替换。然而认真思考发现如果数字0在0地位就无奈继续执行上来,所以对于该策略,须要对于数字0在地位0上进行特判,将数字0与序列中任意一个不在本位上的数字进行替换,这样策略就能够持续进行下…
算法-数据结构 关于算法-数据结构:PAT甲级1037-Magic-Coupon 很直观的感触就是将2个汇合中负数大的顺次相乘,正数小的顺次相乘而后再相加。对这2个汇合都从小到大进行排序,那么从左往右将雷同地位的正数进行相乘,而后从右往左将雷同地位的负数进行相乘,并且将其问题累加就是最终后果。
算法-数据结构 关于算法-数据结构:PAT甲级1033-To-Fill-or-Not-to-Fill 已知终点与起点的间隔为D,油箱的最大油量为Cmax,单位汽油可能反对后退Davg。给定N个加油站的单位油价和离终点的间隔C所有加油站都在一条线上),汽车初始时刻处于终点地位,油箱为空,且能够在任意加油站购买任意量的汽油(前提是不超过油箱容量),求从终点到起点的最小破费。如果无奈达到起点,则输入可能行驶的最远距离。
算法-数据结构 关于算法-数据结构:PAT甲级1070-Mooncake 此题是应用贪婪的思维来求解,个别为了取得最大收益,会首先将售价最高的月饼尽可能多的销售进来,因为在需求量肯定的状况下,单价高的月饼总售价也会更高,所以咱们对所有的月饼依照其单价从高到低进行排序,而后顺次遍历所有的月饼,如果以后月饼的数量小于等于需求量,那么就全副售出并计算收益和更新需求量,否则就…
算法-数据结构 关于算法-数据结构:PAT甲级1048-Find-Coins 应用hash散列的思维来解决每一个输出的数字,nums来记录每一个数字呈现的次数,下标为数字,其值为呈现次数。那么咱们从0开始遍历始终到1000,对于每一个数字j,首先得判断j和M-j呈现的次数是否都不为0,如果是,对于所有j!=M-j(两数字不相等)或者j==M-j并且nums[j]>1(两数字相等然而呈现了至多2次),就输入j和M-j,并…
算法-数据结构 关于算法-数据结构:PAT甲级1050-String-Subtraction s1和s2别离记录第一和第二个字符串,应用table记录所有在s2中呈现过的字符,在遍历s1的过程中,只有以后字符在table中没有被记录就输入即可。
算法-数据结构 关于算法-数据结构:PAT甲级1092-To-Buy-or-Not-to-Buy 给出两串珠子中每颗珠子的色彩,问第一串中是否有第二串中的所有珠子,即对每种色彩来说,第一串中该色彩珠子的个数必须不小于第二串中该色彩珠子的个数。如果是,输入“Yes””,并输入第一串中除了用来和第二串珠子进行匹配以外,还剩多少珠子:如果不是,则输入“No”,并输入第串中还少多少个珠子,能力让第一串领有第二串…
算法-数据结构 关于算法-数据结构:PAT甲级1084-Broken-Keyboard 咱们能够应用notBroken记录哪些字符是好的键,在输出s1和s2的时候,首先变量s2,将s2的字符全副记录为好键,notBroken[s2[i]] = true,而后遍历s1,对于在notBroken中显示s1的字符不是好键的就进行输入,然而因为只输入一次,所以在输入结束后,就将其记录为好键。