LeetCode刷题打卡
一、（简单题）506.相对名次
二、（中等）264.丑数
三、（困难）23.合并N个升序链表
一、（简单题）506.相对名次
LeetCode原题链接：506.相对名次
题目描述：
给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。
运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2
高，依此类推。运动员的名次决定了他们的获奖情况：
名次第 1 的运动员获金牌 “Gold Medal” 。
名次第 2 的运动员获银牌 “Silver Medal” 。
名次第 3 的运动员获铜牌 “Bronze Medal” 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。
使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。
示例 1：
输入：score = [5,4,3,2,1]
输出：[“Gold Medal”,“Silver Medal”,“BronzeMedal”,“4”,“5”]
解释：名次为 [1st, 2nd, 3rd, 4th, 5th] 。
示例 2：
输入：score = [10,3,8,9,4]
输出：[“GoldMedal”,“5”,“BronzeMedal”,“Silver Medal”,“4”]
解释：名次为 [1st, 5th, 3rd, 2nd, 4th] 。
解题思路：
要求根据得分决定名次，那就可以将所有运动员的得分放入最大堆中，那么从堆中取出来的得分将是由大到小的，给answer[]前三名分别赋值 “Gold Medal”，“Silver Medal"和"Bronze Medal”，余下的直接赋值（名次+“ ”）。
为了让堆中排序好的得分与运动员对应，可以使用有序可重复的集合List来存放得分数组score[]，让堆中取出的得分与集合中元素一比较，就得到了对应运动员的下标。
解题代码：
class Solution { public String[] findRelativeRanks(int[] score) { //创建优先队列对象（默认最小堆），重写比较器，改为最大堆。 PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>(){ public int compare(Integer a,Integer b){ return b.compareTo(a); } }); //创建集合list List list = new ArrayList(); //增强for循环 for(int scores : score){ //得分放入最大堆堆中进行排序 que.offer(scores); //得分放入集合中 list.add(scores); } int num;//表示堆中取出的得分 int index;//表示得分对应的运动员下标 String[] answer = new String[score.length]; for(int i = 0;i <= score.length-1;++i){ num = que.poll(); //从堆中取出得分 index = list.indexOf(num); //通过得分在集合中找到对应下标 if(i == 0){//第一名 answer[index] = "Gold Medal"; }else if(i == 1){//第二名 answer[index] = "Silver Medal"; }else if(i == 2){//第三名 answer[index] = "Bronze Medal"; }else{//名次转化为字符串类型，放入数组中 answer[index] = i+1+""; } } return answer;//返回获奖情况 } }
提交结果：
二、（中等）264.丑数
LeetCode原题链接：264.丑数
题目描述：
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
/
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
/
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
解题思路：
1是丑数，每个丑数与2，3和5相乘，依旧是丑数，我们就可以以此找到前n个丑数，将它们放进Set集合当中，避免重复。
得到的丑数放入最小堆，那么每次取出来的丑数都是最小的，取出n个就是前n个丑数，取出第n个就是第n个丑数。
解题代码：
class Solution { public int nthUglyNumber(int n) { int[] factors = {2,3,5}; Set<Long> set = new HashSet<Long>();//创建集合 //创建优先序列（默认最小堆） PriorityQueue<Long> que = new PriorityQueue<Long>(); int ugly = 0;//表示丑数 set.add(1l);//第一个丑数1放进集合 que.add(1l);//第一个丑数1放进最小堆 //循环取出前n个丑数 for(int i = 0;i < n; ++i){ //从堆中取出当前丑数，赋值给ugly long curr = que.poll(); ugly = (int)curr; //用丑数分别与2，3，5相乘，获得后续丑数 for(int factor : factors){ long next = curr*factor; if(set.add(next)){//放进集合去重 que.offer(next);//放进最小堆 } } } return ugly;//返回第n个丑数 } }
提交结果：
三、（困难）23.合并N个升序链表
做不出来，看了题解之后才完成的.....
LeetCode原题链接：23.合并N个升序链表
题目描述：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
/
示例 1：
输入：lists = [ [1,4,5], [1,3,4], [2,6] ]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下： [
1->4->5,
1->3->4,
2->6 ]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
/
示例 2：
输入：lists = []
输出：[]
/
示例 3：
输入：lists = [[]]
输出：[]
思路：分别将链表数组中，每个链表的首元素放入最小堆，选出最小的元素放入新链表，选出元素的下一个节点进堆，继续排序，重复上述操作，直到堆空为止。
这样就实现了合并后的链表依旧保持升序。
解题代码：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length == 0) return null; ListNode list = new ListNode(0);//创建链表 ListNode curr = list;//将链表第一个值传入 PriorityQueue<ListNode> que = new PriorityQueue<>(new Comparator<ListNode>(){ public int compare(ListNode a,ListNode b){ return a.val-b.val; } });//创建优先队列（最小堆） //将链表数组中，每个链表元素的首元素放入堆 for(ListNode list1 : lists){ if(list1 == null) continue; que.offer(list1); } while(!(que.isEmpty())){//堆不为空时，循环操作 ListNode nextNode = que.poll();//最小的元素出堆 curr.next = nextNode;//链表的下一位指向最小元素 curr = curr.next;//链表指向下一位 if(nextNode.next != null){ que.offer(nextNode.next);//出堆元素的下一位入堆排序 } } return list.next;//跳过头节点，返回链表的下一个元素 } }
提交结果：
贵在坚持…
