LeetCode刷题打卡

一、（简单题）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] 。

解题思路：
题目给定我们一个长度为n的数组score，数组中每一个元素代表着对应运动员的得分，我们需要做的就是输出一个长度为n的数组answer，answer数组中的元素对应的是score数组中每位运动员得分所得到名次。

得分排列前三的运动员，在answer数组中元素值为 “Gold Medal” 、“Silver Medal"和"Bronze Medal”，剩下的运动员在answer数组中的元素值就是其得分做得到的名次（4 ~ n）了。

要求根据得分决定名次，那就可以将所有运动员的得分放入最大堆中，那么从堆顶中取出来的得分是当前最高得分，也就是说取出的元素将是由大到小排列的，给answer[]前三名，也就是堆中取出的前三个元素分别赋值 “Gold Medal”，“Silver Medal"和"Bronze Medal”，余下的直接赋值（名次+“ ”）即可。

但是这时候就出现了问题，经过最大堆排序后，取出的得分顺序以及被打乱，我们就无法将answer数组中的名次与score数组中的得分对应起来了。

为了让堆中排序好的得分与运动员对应，需要使用有序可重复的集合List来存放得分数组score[]，每次在最大堆的堆顶取出得分元素时，让该得分与list集合中的得分元素一比较，就得到了当前得分在数组score中的位置，接下来将当前得分的对应名次赋值给answer数组中与数组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;//跳过头节点，返回链表的下一个元素
    }
}

提交结果：