【Day 01】力扣(LeetCode)每日一刷[506.相对名次][264.丑数][23.合并N个升序链表]

简介: 每日一刷[506.相对名次][264.丑数][23.合并N个升序链表]。

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;//返回获奖情况
        }
    }

提交结果:

微信图片_20221029000534.png


二、(中等)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个丑数
    }
}


提交结果:

微信图片_20221029000547.png


三、(困难)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;//跳过头节点,返回链表的下一个元素
    }
}

提交结果:

微信图片_20221029000558.png


贵在坚持…

微信图片_20221028221827.jpg




目录
相关文章
|
2月前
【bug记录】旋转链表与力扣报错:member access within null pointer of type ‘struct ListNode‘
【bug记录】旋转链表与力扣报错:member access within null pointer of type ‘struct ListNode‘
|
2月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
30 0
|
2月前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表
解决LeetCode "K 个一组翻转链表" 问题的三种方法:使用栈、尾插法和虚拟节点顺序法,并提供了每种方法的Python实现代码。
27 0
|
2月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
2月前
|
存储 算法
LeetCode第86题分隔链表
文章介绍了LeetCode第86题"分隔链表"的解法,通过创建两个新链表分别存储小于和大于等于给定值x的节点,然后合并这两个链表来解决问题,提供了一种简单易懂且操作原链表的解决方案。
LeetCode第86题分隔链表
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
算法
LeetCode第23题合并 K 个升序链表
这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法,使用分而治之的思想,通过递归合并链表的方式解决了这个难题。
LeetCode第23题合并 K 个升序链表
|
2月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
23 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
2月前
|
C++ 索引
leetcode 707.设计链表
本文提供了解决LeetCode 707题"设计链表"的C++实现,包括单链表的节点定义和类方法实现,如添加节点、获取节点值、删除节点等。
|
2月前
|
算法
LeetCode第92题反转链表 II
文章分享了LeetCode第92题"反转链表 II"的解法,通过使用四个指针来记录和更新反转链表段的头部、尾部以及前一个和后一个节点,提供了一种清晰且易于理解的解决方案。
LeetCode第92题反转链表 II