欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?C++題解?leetcode第k個(gè)數(shù)實(shí)例

 更新時(shí)間:2022年09月29日 15:19:29   作者:AnjaVon  
這篇文章主要為大家介紹了Java?C++題解?leetcode第k個(gè)數(shù)實(shí)例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

題目要求

思路一:小根堆

  • 中文題目描述不太清晰,但其實(shí)由題目可以發(fā)現(xiàn),當(dāng)x滿足條件時(shí),3x、5x、7x分別也都滿足條件。
  • 將滿足條件的數(shù)依次放入優(yōu)先隊(duì)列存放用于后續(xù)計(jì)算,由于每次要取待計(jì)算隊(duì)列中最小的數(shù)x,所以定義小根堆:
    • 彈出x,計(jì)算3x、5x、7x并入隊(duì);
    • 用一個(gè)哈希表記錄防止重復(fù)入隊(duì)。
  • 每次取數(shù)(pop)時(shí)進(jìn)行計(jì)數(shù),到第k次結(jié)束,當(dāng)前隊(duì)首即為答案。

Java

  • 《學(xué)到了》
    • 1L也就是long型的數(shù)字1,那么同理1f就是float型,本質(zhì)上都是相等的1。
    • 還有區(qū)分Long型和long型,前者是包裝類,有函數(shù)可以調(diào)用。
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];
    }
}
  • 時(shí)間復(fù)雜度:O(k)
  • 空間復(fù)雜度: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];
    }
};
  • 時(shí)間復(fù)雜度:O(k)
  • 空間復(fù)雜度: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]
    }
}
  • 時(shí)間復(fù)雜度:O(k)
  • 空間復(fù)雜度:O(k)

總結(jié)

偷懶就不寫rust的優(yōu)先隊(duì)列了……

是“丑數(shù)”的變種題目,題目描述有點(diǎn)問(wèn)題(力扣日常、去看原文好理解很多),做過(guò)就會(huì)技巧性并不太強(qiáng)的題目~

以上就是Java C++題解 leetcode第k個(gè)數(shù)實(shí)例的詳細(xì)內(nèi)容,更多關(guān)于Java C++題解第k個(gè)數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • c++實(shí)現(xiàn)加載so動(dòng)態(tài)庫(kù)中的資源

    c++實(shí)現(xiàn)加載so動(dòng)態(tài)庫(kù)中的資源

    下面小編就為大家?guī)?lái)一篇c++實(shí)現(xiàn)加載so動(dòng)態(tài)庫(kù)中的資源。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2016-12-12
  • OpenCV提取圖像中圓線上的數(shù)據(jù)具體流程

    OpenCV提取圖像中圓線上的數(shù)據(jù)具體流程

    在對(duì)圖像進(jìn)行處理時(shí),經(jīng)常會(huì)要提取出圖像中某條直線、圓線或者ROI區(qū)域內(nèi)的感興趣數(shù)據(jù),進(jìn)行重點(diǎn)關(guān)注。本文主要介紹了利用OpenCV獲取圖像中圓線上的數(shù)據(jù),需要的可以參考一下
    2021-11-11
  • C語(yǔ)言使用stdlib.h庫(kù)函數(shù)的二分查找和快速排序的實(shí)現(xiàn)代碼

    C語(yǔ)言使用stdlib.h庫(kù)函數(shù)的二分查找和快速排序的實(shí)現(xiàn)代碼

    以下是對(duì)C語(yǔ)言使用stdlib.h庫(kù)函數(shù)的二分查找和快速排序的實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的介紹,需要的朋友可以過(guò)來(lái)參考下。希望對(duì)大家有所幫助
    2013-10-10
  • C語(yǔ)言實(shí)現(xiàn)數(shù)組元素排序方法詳解

    C語(yǔ)言實(shí)現(xiàn)數(shù)組元素排序方法詳解

    這篇文章主要為大家介紹了C語(yǔ)言算法練習(xí)中數(shù)組元素排序的實(shí)現(xiàn)方法,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)C語(yǔ)言有一定幫助,需要的可以參考一下
    2023-02-02
  • 你只用do-while來(lái)實(shí)現(xiàn)循環(huán)?太浪費(fèi)了

    你只用do-while來(lái)實(shí)現(xiàn)循環(huán)?太浪費(fèi)了

    這篇文章主要介紹了你只用do-while來(lái)實(shí)現(xiàn)循環(huán)?太浪費(fèi)了,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-12-12
  • 詳解C++的模板中typename關(guān)鍵字的用法

    詳解C++的模板中typename關(guān)鍵字的用法

    在C++的Template中我們經(jīng)??梢砸?jiàn)到使用typename來(lái)定義類型名稱,更加具體的我們就在接下來(lái)為大家詳解C++的模板中typename關(guān)鍵字的用法,需要的朋友可以參考下:
    2016-06-06
  • ShellExecute函數(shù)用法的實(shí)例代碼

    ShellExecute函數(shù)用法的實(shí)例代碼

    ShellExecute函數(shù)用法的實(shí)例代碼,需要的朋友可以參考一下
    2013-03-03
  • C++中的最小生成樹(shù)算法超詳細(xì)教程

    C++中的最小生成樹(shù)算法超詳細(xì)教程

    這篇文章主要介紹了C++中的最小生成樹(shù)算法超詳細(xì)教程,最小生成樹(shù)的最著名的算法有兩個(gè), 一個(gè)是Prim算法, 另一個(gè)當(dāng)然就是Kruskal算法, 接下來(lái), 我將盡我所能的介紹這兩個(gè)算法, 也算是對(duì)自己學(xué)習(xí)的一個(gè)回顧吧,需要的朋友可以參考下
    2023-08-08
  • C語(yǔ)言實(shí)現(xiàn)掃雷游戲源代碼

    C語(yǔ)言實(shí)現(xiàn)掃雷游戲源代碼

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷游戲源代碼,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-03-03
  • C++中宏的使用問(wèn)題詳解

    C++中宏的使用問(wèn)題詳解

    宏替換是C/C++系列語(yǔ)言的技術(shù)特色,C/C++語(yǔ)言提供了強(qiáng)大的宏替換功能,源代碼在進(jìn)入編譯器之前,要先經(jīng)過(guò)一個(gè)稱為“預(yù)處理器”的模塊,這個(gè)模塊將宏根據(jù)編譯參數(shù)和實(shí)際編碼進(jìn)行展開(kāi),展開(kāi)后的代碼才正式進(jìn)入編譯器,進(jìn)行詞法分析、語(yǔ)法分析等等。
    2016-05-05

最新評(píng)論