• 【leetcode周赛】301场中国银联

    0、关于集合知识的温故知新

    集合知识宏观比较不涉及源码，但是对比很详细

    TreeSet常见方法讲解，涉及各个方法的源码

    TreeSet add源码分析：

    package collection;

import java.util.Comparator;
import java.util.TreeSet;

/*
 * @author lzy
 * @version 1.0
 * */
public class TreeSet_ {
    public static void main(String[] args) {
        //无参构造treeset方法，打印出的元素依旧是无序的。
        //添加的元素，按照字符串大小来排序
        //3. 使用treeSet提供的构造器可以传入一个比较器(匿名内部类 并指定排序规则
        /*public TreeSet(Comparator comparator) {
        this(new TreeMap<>( comparator));
            }       */
        /*
        public interface Comparator {
        int compare(T o1, T o2);
        * */
        TreeSet treeSet=new TreeSet();
        /*TreeSet treeSet=new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).compareTo((String)o2);
              //  return ((String)o1).length()-((String)o2).length(); 长度
            }
        });*/
        //1. 构造器：将传入的比较器，赋给了TreeMap底层的comparator属性
        /* public TreeSet(Comparator comparator) {
        this(new TreeMap<>(comparator));
    }*/
        //2.底层源码：cpr这就是传入的底层的匿名内部类比较器 底层思想就是 比较然后选择应该找树的左边还是右边，然后更新parent，然后循环遍历整棵树，最后将key-value-parent传入构造新的树节点
        /*
        *  Comparator cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);//动态绑定道匿名内部类(对象)所实现的接口方法。
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);//如果相等则key加不进去
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable k = (Comparable) key;//这里是将Key进行一个向上转型，方便调用父类接口的方法
                * //原因就是这里key是一个String类型，但是String类型源码中是实现了Comparable接口的所以可以转型，不行你去看String源码
                * //https://blog.csdn.net/weixin_43971252/article/details/119396327 从如果传入不实现Comparable的类，我们也有解决方法
                * //1. 实现Comparable接口  2. 传入Comparable匿名内部类
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        * */
        /*
        * public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }
        * */
       // treeSet.add("hbm");
       // treeSet.add("hlm");
       // treeSet.add("xbm");
        treeSet.add(1231231312);
        treeSet.add(12312321);
        System.out.println(treeSet);
        //
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103

    一、2335. 装满杯子需要的最短总时长

    题目描述：

    现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。

    给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。

    输入：amount = [5,4,4]
    输出：7
    解释：下面给出一种方案：
    第 1 秒：装满一杯冷水和一杯热水。
    第 2 秒：装满一杯冷水和一杯温水。
    第 3 秒：装满一杯冷水和一杯温水。
    第 4 秒：装满一杯温水和一杯热水。
    第 5 秒：装满一杯冷水和一杯热水。
    第 6 秒：装满一杯冷水和一杯温水。
    第 7 秒：装满一杯热水。

    代码思路：

    贪心，每次贪心的选取两杯水来喝，如果发现杯数最多的水，比其他两杯总数加起来还多，那么返回杯数最多的水的数量。

    代码题解:

    class Solution {
	//数字数量少了，用冒泡速度很快。
    private int[] bubbleSort(int[] amount) {
        for(int i = 0; i < amount.length - 1; i++) {
            for(int j = i + 1; j < amount.length; j++) {
                if(amount[j - 1] > amount[j]) {
                    int temp = amount[j];
                    amount[j] = amount[j - 1];
                    amount[j - 1] = temp;
                }
            }
        }
        return amount;
    }
    public int fillCups(int[] amount) {
        //4 4 3 ,3 3 3,2 2 3, 2 1 2,1 1 1,0 0 1,1
        if(amount.length == 0) return 0;
        int res = 0;
        bubbleSort(amount);
        while(amount[2] > 0){
           if(amount[0] + amount[1] <= amount[2]) {
                return res + amount[2];   
           }else {
               amount[2]--;
               amount[1]--;
               res++;
           }
            bubbleSort(amount);
        }
        
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    二、2336. 无限集中的最小数字

    现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, …] 。

    实现 SmallestInfiniteSet 类：

    SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
    int popSmallest() 移除 并返回该无限集中的最小整数。

    void addBack(int num) 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中。

    输入
    [“SmallestInfiniteSet”, “addBack”, “popSmallest”, “popSmallest”, “popSmallest”, “addBack”, “popSmallest”, “popSmallest”, “popSmallest”]
    [[], [2], [], [], [], [1], [], [], []]
    输出
    [null, null, 1, 2, 3, null, 1, 4, 5]
    解释
    SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
    smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。
    smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
    smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
    smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
    smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。
    smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
    // 且 1 是最小的整数，并将其从集合中移除。
    smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
    smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

    代码思路：

    1. 由于题目数据量只有1000个，所以手动添加1000个数模拟无限集合。
    2. 根据题目的要求：
      • 需要返回最小整数(表示我的集合得有序)。
      • 同时进行添加操作，添加数字之后，也要保证有序。
      • 无需添加null值(TreeSet 底层代码不让加null值)
    3. 根据上述题目的要求，TreeSet比较符合，但是如果使用HashMap的话，由于是按照递增数字来添加的，所以，通过hashCode加入指定位置元素，碰巧也是有序的，所以用HashMap也可以。

    代码题解：

    package leetcode;

import java.util.TreeSet;

/*
 * @author lzy
 * @version 1.0
 * */
public class SmallestInfiniteSet {
    public static void main(String[] args) {
        new SmallestInfiniteSet();
    }
    private TreeSet<Integer> treeSet;

    public SmallestInfiniteSet() {
        this.treeSet = new TreeSet();
        for (int i = 1; i < 1001; i++) {
            treeSet.add(i);
        }
    }

    public int popSmallest() {
        int res = treeSet.first();
        treeSet.remove(treeSet.first());
        return res;
    }

    public void addBack(int num) {
        if (treeSet.contains(num)) {
            return;
        } else {
            treeSet.add(num);
        }
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    时间复杂度： O(NLOGN)

    主要时间开销来自于对二叉树的排序，以及底层红黑树的维护。

    三、2337. 移动片段得到字符串

    没做 (饿的一批，有时间看大佬题解吧)

    四、2338. 统计理想数组的数目

    hard难度，劝退 (饿的一批，有时间看大佬题解吧)

  • 相关阅读:
    boomYouth
    专利说明书怎么写？
    “通胀噩梦：恶梦继续还是即将终结？经济前景备受关注！“
    Ubuntu 20.04.05安装ceres-1.14.0
    QT笔记——QT类反射机制简单学习
    Pytorch：模块（Module类）
    python3
    在visual studio里配置Qt插件并运行Qt工程
    这份华为以太网接口配置命令太真香了！
    基于SSM的房屋租售网站
  • 原文地址：https://blog.csdn.net/weixin_44627672/article/details/126459099