手机在线建网站,wordpress主题如何开发,广告公司名称创意,织梦网站模板如何安装教程视频题目部分
题目支持优先级的队列难度易题目说明实现一个支持优先级的队列#xff0c;高优先级#xff08;数字越大#xff0c;优先级越高#xff09;先出队列#xff1b;同优先级时先进先出。 如果两个输入数据和优先级都相同#xff0c;则后一个数据不入队列被丢弃。 队…题目部分
题目支持优先级的队列难度易题目说明实现一个支持优先级的队列高优先级数字越大优先级越高先出队列同优先级时先进先出。 如果两个输入数据和优先级都相同则后一个数据不入队列被丢弃。 队列存储的数据内容是一个整数。输入描述一组待存入队列的数据(包含内容和优先级)每组数字内容在前优先级在后。输出描述队列的数据内容(优先级信息输出时不再体现)。补充说明不用考虑输入数据不合法的情况测试数据不超过100个。------------------------------------------------------示例示例1输入(10,1),(20,1),(30,2),(40,3)输出40,30,10,20说明输入样例中向队列写入了 4 个数据每个数据由数据内容和优先级组成。 输入和输出内容都不含空格。 数据 40 的优先级最高所以最先输出其次是 3010 和 20 优先级相同所以按输入顺序输出。示例2输入(10,1),(10,1),(30,2),(40,3)输出40,30,10说明输入样例中向队列写入了4个数据每个数据由数据内容和优先级组成。 输入和输出内容都不含空格。 数据 40 的优先级最高所以最先输出其次是 30两个 10 和 10 构成重复数据被丢弃一个。 解读与分析
题目解读
输入一个字符串把字符串解析成各种队列数据根据优先级输出数据如果优先级相同则按照原顺序输出。
分析与思路
分两步实现。 1. 解析对收入的字符串以 “(” 和 “)” 配对解析成每组数据元素 element包括数据内容element[0]和数据优先级( element[1] )。并把它放到数组 dataArray dataArray 的元素为 element中。 2. 排序对数组中的数据进行排序排序的规则为按照每个元素的 element[1] 大小排序从大到小。 3. 输出对排序的元素逐个输出数据内容element[0]需要注意的是如果前一个输出的数据的内容和优先级与当前即将输出的数据相等则忽略继续下一个。
此算法的时间复杂度和空间复杂度均为 O(n)。 代码实现
Java代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;/*** 支持优先级的队列* * since 2023.10.26* version 0.1* author Frank**/
public class PriorityQueue {public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNext()) {String input sc.nextLine();int[][] elements getElements( input );sort( elements );output( elements );}}private static int[][] getElements( String input ){Listint[] eleList new ArrayList();int indexLeft 0;int indexRight 0;while( indexLeft ! -1){indexLeft input.indexOf( (, indexRight );indexRight input.indexOf( ), indexRight );if( indexLeft -1 ){break;}String eleStr input.substring( indexLeft 1, indexRight );String[] eleArr eleStr.split( , );int[] element new int[2];element[0] Integer.parseInt( eleArr[0] );element[1] Integer.parseInt( eleArr[1] );eleList.add( element );indexRight 1;}int[][] ret new int[eleList.size()][2];for( int i 0; i eleList.size(); i ){ret[i] eleList.get( i );}return ret;}private static void sort( int[][] elements) {Arrays.sort( elements, new Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {return o2[1] - o1[1];}} );}private static void output( int[][] elements ) {StringBuffer sb new StringBuffer();for( int i 0; i elements.length; i ){if( i 0 ( elements[i][0] elements[i - 1][0] ) ( elements[i][1] elements[i - 1][1] ) ) {continue;}sb.append( elements[i][0] , );}String ret sb.toString();ret ret.substring( 0, ret.length() - 1);System.out.println( ret );}
} JavaScript代码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;
void async function() {while (line await readline()) {var elements getElements(line);sort(elements);output(elements);}
}();function getElements(input) {var eleList new Array();var indexLeft 0;var indexRight 0;while (indexLeft ! -1) {indexLeft input.indexOf((, indexRight);indexRight input.indexOf(), indexRight);if (indexLeft -1) {break;}var eleStr input.substring(indexLeft 1, indexRight);var eleArr eleStr.split(,);var element new Array();element[0] parseInt(eleArr[0]);element[1] parseInt(eleArr[1]);eleList.push(element);indexRight 1;}return eleList;
}function sort( elements ) {elements.sort( function( a, b) {return b[1] - a[1];})
}function output( elements ) {var ret ;for( var i 0; i elements.length; i ){if( i 0 ( elements[i][0] elements[i - 1][0] ) ( elements[i][1] elements[i - 1][1] ) ) {continue;}ret ( elements[i][0] , );}ret ret.substring( 0, ret.length - 1);console.log( ret );
} (完)
