栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode—<排序专项>剑指 Offer 40、41、45、61

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode—<排序专项>剑指 Offer 40、41、45、61

剑指 Offer 40. 最小的k个数、41. 数据流中的中位数、45. 把数组排成最小的数、61. 扑克牌中的顺子

题目描述:
[40]
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
[41]
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
[45]
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
[61]
从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

考察重点:
第40题 golang中,先排序,后取前k项切片。
第41题使用一个大顶堆一个小顶堆实现中位数求解,元素先进入大顶堆后进入小顶堆,且始终保证小顶堆元素个数小于大顶堆元素个数,最终二者的堆顶平均值或者大顶堆堆顶即是中位数。
第45题先将整个int数组转化为String数组,重写排序规则,按照A+B 第61题顺子表示大小王可以构成任意数字,如“1,4,0,0,5” 可以表示为“1,2,3,4,5”。只需要排序数组并求得0的数量,再判断0的个数是否可以填补顺序数组元素间的差值。

第40题

func getLeastNumbers(arr []int, k int) []int {
    sort.Ints(arr)
    return arr[:k]
}

第41题

class MedianFinder {
    PriorityQueue smallque;
    PriorityQueue bigque;
    
    public MedianFinder() {
        bigque = new PriorityQueue(new Comparator(){
            @Override
            public int compare(Integer a1, Integer a2){
                return a2 - a1;
            }
        });
        smallque = new PriorityQueue();
    }
    
    public void addNum(int num) {
        bigque.add(num);
        smallque.add(bigque.remove());
        if(bigque.size() < smallque.size()){
            bigque.add(smallque.remove());
        }
    }
    
    public double findMedian() {
        if(smallque.size() == bigque.size()){
            return (bigque.peek() + smallque.peek()) / 2.00000;
        }
        return bigque.peek();
    }
}

第45题

    public String minNumber(int[] nums) {
        String[] nums2 = new String[nums.length];
        for(int i = 0;i < nums.length;i ++){
            nums2[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(nums2, new Comparator(){
            @Override
            public int compare(String o1, String o2) {
                return (o1+o2).compareTo(o2+o1);
            }
        });
        return String.join("", nums2);
    }

第61题

    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int markZero = 0;
        int oldNum = 0;
        int i = 0;
        for(;i < nums.length;i ++){
            if(nums[i] != 0){
                break;
            }
            markZero ++;
        }
        oldNum = i < nums.length ? nums[i] : 0;
        for(i = i + 1;i < nums.length;i ++){
            int a = Math.abs(nums[i] - oldNum) - 1;
            if(a > markZero || nums[i] == oldNum){
                return false;
            }else{
                markZero = markZero - a;
            }
            oldNum = nums[i];
        }
        return true;
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/969776.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号