Java C++题解 leetcode第k个数实例

目录
  • 题目要求
  • 思路一:小根堆
    • Java
    • C++
  • 思路二:多路归并【多指针】
    • Java
    • C++
    • Rust
  • 总结

题目要求

思路一:小根堆

  • 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x、5x、7x分别也都满足条件。
  • 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆:
    • 弹出x,计算3x、5x、7x并入队;
    • 用一个哈希表记录防止重复入队。
  • 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案。

Java

  • 《学到了》

    • 1L也就是long型的数字1,那么同理1f就是float型,本质上都是相等的1。
    • 还有区分Long型和long型,前者是包装类,有函数可以调用。
class Solution {
    public int getKthMagicNumber(int k) {
        int[] nums = new int[]{3, 5, 7};
        PriorityQueue<Long> que = new PriorityQueue<>();
        Set<Long> set = new HashSet<>();
        que.add(1L);
        set.add(1L);
        while (!que.isEmpty()) {
            long cur = que.poll();
            if (--k == 0)
                return (int) cur;
            for (int x : nums) { // 3、5、7依次
                if (!set.contains(x * cur)) {
                    que.add(x * cur);
                    set.add(x * cur);
                }
            }
        }
        return -1;
    }
}

C++

class Solution {
public:
    int getKthMagicNumber(int k) {
        int nums[3] = {3, 5, 7};
        priority_queue<long, vector<long>, greater<long>> que; // 小根堆
        unordered_set<long> set;
        que.push(1L);
        set.insert(1L);
        while (!que.empty()) {
            long cur = que.top();
            que.pop();
            if (--k == 0)
                return (int)cur;
            for (auto x : nums) { // 3、5、7依次
                if (!set.count(x * cur)) {
                    que.push(x * cur);
                    set.insert(x * cur);
                }
            }
        }
        return -1;
    }
};

思路二:多路归并【多指针】

Java

class Solution {
    public int getKthMagicNumber(int k) {
        int[] res = new int[k + 1];
        res[1] = 1;
        for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) {
            int r3 = res[i3] * 3, r5 = res[i5] * 5, r7 = res[i7] * 7;
            res[idx] = Math.min(r3, Math.min(r5, r7));
            if (res[idx] == r3)
                i3++;
            if (res[idx] == r5)
                i5++;
            if (res[idx] == r7)
                i7++;
        }
        return res[k];
    }
}
  • 时间复杂度:O(k)
  • 空间复杂度:O(k)

C++

class Solution {
public:
    int getKthMagicNumber(int k) {
        int res[k + 1];
        res[1] = 1;
        for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) {
            int r3 = res[i3] * 3, r5 = res[i5] * 5, r7 = res[i7] * 7;
            res[idx] = min(r3, min(r5, r7));
            if (res[idx] == r3)
                i3++;
            if (res[idx] == r5)
                i5++;
            if (res[idx] == r7)
                i7++;
        }
        return res[k];
    }
};
  • 时间复杂度:O(k)
  • 空间复杂度:O(k)

Rust

impl Solution {
    pub fn get_kth_magic_number(k: i32) -> i32 {
        let mut res = vec![0; (k + 1) as usize];
        res[1] = 1;
        let (mut i3, mut i5, mut i7) = (1, 1, 1);
        for idx in 2..(k + 1) as usize {
            let (r3, r5, r7) = (res[i3] * 3, res[i5] * 5, res[i7] * 7);
            res[idx] = r3.min(r5.min(r7));
            if (res[idx] == r3) {
                i3 += 1;
            }
            if (res[idx] == r5) {
                i5 += 1;
            }
            if (res[idx] == r7) {
                i7 += 1;
            }
        }
        res[k as usize]
    }
}
  • 时间复杂度:O(k)
  • 空间复杂度:O(k)

总结

偷懒就不写rust的优先队列了……

是“丑数”的变种题目,题目描述有点问题(力扣日常、去看原文好理解很多),做过就会技巧性并不太强的题目~

以上就是Java C++题解 leetcode第k个数实例的详细内容,更多关于Java C++题解第k个数的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java C++题解leetcode判定是否为字符重排

    目录 题目要求 思路一:排序 Java C++ Rust 思路二:词频统计 Java C++ Rust 总结 题目要求 思路一:排序 Java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; char[] sort1 = s1.toCharArray(); Arrays.sort(sort1); char[]

  • Java C++题解leetcode1598文件夹操作日志搜集器

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 根据日志判断目前在哪一级子文件夹即可,级数就等于返回时的步数,主文件夹级数初始为000: xl:级数+1+1+1: ./:级数不变: ../:级数−1-1−1. Java class Solution { public int minOperations(String[] logs) { int res = 0; for (String l : logs) { if (l.equals("../"))

  • Java C++题解leetcode字符串轮转KMP算法详解

    目录 题目要求 思路一:双指针(模拟) Java C++ 思路二:子串 手写KMP Java dp C++ dp 调API Java C++ 总结 题目要求 思路一:双指针(模拟) Java class Solution { public boolean isFlipedString(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); if (n == 0) retu

  • Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++ 题解leetcode1619删除某些元素后数组均值

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i

  • Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • Python找出最小的K个数实例代码

    题目描述 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,. 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑.以下几种思路当是笔者抛砖引玉,如果读者有兴趣可以自己再使用其他方法一一尝试. 思路1:利用冒泡法 临近的数字两两进行比较,按照从小到大的顺序进行交换,如果前面的值比后面的大,则交换顺序.这样一趟过去后,最小的数字被交换到了第一位:然后是次小的交换到了第二位,...,依次直到第k个数,停

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • JAVA中寻找最大的K个数解法

    这个题拿到之后首先会想到排序,排好序之后在选取选取最大的K个数.排序选择快速排序是个比较好的选择.好了,让我们来进行第一个解法:快速排序代码如下 复制代码 代码如下: public static void quickSort(int[] arr, int start, int end) {  if (start < end) {   int key = arr[start];   int right = start;   int left = end;   while (right < lef

  • Java判断List中相同值元素的个数实例

    如下所示: Map<Object, Integer> map = new TreeMap<Object, Integer>(); for (Object i : listIp) { if (map.get(i) == null) { map.put(i, 1); } else { map.put(i, map.get(i) + 1); } } 以上这篇Java判断List中相同值元素的个数实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

随机推荐