亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

901-股票價(jià)格跨度

用戶83 / 961人閱讀

摘要:前言的第二道題目,同樣是分值分且中等難度的題目股票價(jià)格跨度編寫一個(gè)類,它收集某些股票的每日?qǐng)?bào)價(jià),并返回該股票當(dāng)日價(jià)格的跨度。第二版股票價(jià)格跨度存儲(chǔ)一個(gè)遞增數(shù)列的實(shí)體最低位最高位在當(dāng)前股價(jià)區(qū)間內(nèi)最高位大于當(dāng)前股價(jià),生成一個(gè)新的

前言

Weekly Contest 101的第二道題目,同樣是分值4分且中等難度的題目股票價(jià)格跨度:

編寫一個(gè)StockSpanner類,它收集某些股票的每日?qǐng)?bào)價(jià),并返回該股票當(dāng)日價(jià)格的跨度。

今天股票價(jià)格的跨度被定義為股票價(jià)格小于或等于今天價(jià)格的最大連續(xù)日數(shù)(從今天開始往回?cái)?shù),包括今天)。

例如,如果未來7天股票的價(jià)格是[100, 80, 60, 70, 60, 75, 85],那么股票跨度將是 [1, 1, 1, 2, 1, 4, 6]

示例:

輸入:["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
輸出:[null,1,1,1,2,1,4,6]
解釋:
首先,初始化 S = StockSpanner(),然后:
S.next(100) 被調(diào)用并返回 1,
S.next(80) 被調(diào)用并返回 1,
S.next(60) 被調(diào)用并返回 1,
S.next(70) 被調(diào)用并返回 2,
S.next(60) 被調(diào)用并返回 1,
S.next(75) 被調(diào)用并返回 4,
S.next(85) 被調(diào)用并返回 6。

注意 (例如) S.next(75) 返回 4,因?yàn)榻刂两裉斓淖詈?4 個(gè)價(jià)格
(包括今天的價(jià)格 75) 小于或等于今天的價(jià)格。

提示:

調(diào)用StockSpanner.next(int price) 時(shí),將有1 <= price <= 10^5。

每個(gè)測(cè)試用例最多可以調(diào)用10000StockSpanner.next。

在所有測(cè)試用例中,最多調(diào)用150000StockSpanner.next。

此問題的總時(shí)間限制減少了50%

解題思路

這道題目其實(shí)如果只是實(shí)現(xiàn)題目的功能要求的話是一道很簡(jiǎn)單的題目。只是不斷獲取一個(gè)數(shù)組從最后一個(gè)元素開始單調(diào)遞增數(shù)列的長(zhǎng)度。

但是有由于在提示內(nèi)容中已經(jīng)提到了執(zhí)行時(shí)間限制的問題,就可以知道這個(gè)題目需要進(jìn)行執(zhí)行時(shí)間相關(guān)方面的優(yōu)化。最終我決定使用的優(yōu)化方案是參考跳表這種數(shù)據(jù)結(jié)構(gòu),利用空間換取時(shí)間。思路大致如下,詳細(xì)內(nèi)容可以參考實(shí)現(xiàn)代碼的第二版:

定義一個(gè)存儲(chǔ)遞增數(shù)列的實(shí)體StockPrices,該實(shí)體還會(huì)記錄最高位(第一個(gè)元素)和最低位(最后一個(gè)元素)

StockSpanner中存儲(chǔ)的是StockPrices的數(shù)組

每當(dāng)有新股價(jià)進(jìn)入,逆序(從最后一個(gè)元素開始)遍歷StockSpannerStockPrices數(shù)組。然后根據(jù)是否在當(dāng)前的遞增數(shù)列的范圍進(jìn)行處理。

以示例作為例子:
初始化后

pricesList:[
    {
        left:0
        right:0
        prices:[]
    }

next(100)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    }
return 1

next(80)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    }]
return 1

next(60)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    }
    {
        left:60
        right:60
        prices:[60]
    }]
    
return 1  

next(70)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    }]
    
return 2 

next(60)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    },
    {
        left:60
        right:60
        prices:[60]
    }]
   
return 1 

next(75)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    },
    {
        left:60
        right:75
        prices:[60,75]
    }]
   
return 4 

next(85)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    },
    {
        left:60
        right:85
        prices:[60,75,85]
    }]
   
return 6
實(shí)現(xiàn)代碼 第一版

這個(gè)版本是只實(shí)現(xiàn)功能的版本,所以提交上去基本都是執(zhí)行超時(shí)的結(jié)果。但是可以作為第二版的參考。

class StockSpanner {

    private List prices;

    public StockSpanner() {
        prices=new ArrayList();
    }

    public int next(int price) {
        int result=1;
        prices.add(price);
        int days=prices.size();
        if(days>1){
            int todayPrice=price;
            for(int i=days-2;i>=0;i--){
                if(todayPrice>=prices.get(i)){
                    ++result;
                }else{
                    break;
                }
            }
        }
        return result;
    }
}
第二版
/**
 * 股票價(jià)格跨度
 * @author RJH
 * create at 2018/9/9
 */
public class StockSpanner {

    private List pricesList;

    /**
     * 存儲(chǔ)一個(gè)遞增數(shù)列的實(shí)體
     */
    class StockPrices{
        /**
         * 最低位
         */
        int left;
        /**
         * 最高位
         */
        int right;
        /**
         *
         */
        List prices=new ArrayList<>();
    }


    public StockSpanner() {
        pricesList=new ArrayList<>();
        StockPrices stockPrices=new StockPrices();
        pricesList.add(stockPrices);
    }

    public int next(int price) {
        int result=0;
        StockPrices stockPrices=pricesList.get(pricesList.size()-1);
        List prices=stockPrices.prices;
        if(prices.size()==0){
            stockPrices.left=price;
            stockPrices.right=price;
            prices.add(price);
            result+=prices.size();
            return result;
        }
        if(stockPrices.right<=price){//在當(dāng)前股價(jià)區(qū)間內(nèi)
            prices.add(price);
            stockPrices.right=price;
            result+=prices.size();
        }else{//最高位大于當(dāng)前股價(jià),生成一個(gè)新的StockPrices
            StockPrices newStockPrices=new StockPrices();
            newStockPrices.prices=new ArrayList<>();
            newStockPrices.prices.add(price);
            newStockPrices.left=price;
            newStockPrices.right=price;
            result+=newStockPrices.prices.size();
            pricesList.add(newStockPrices);
        }
        for(int i=pricesList.size()-2;i>=0;i--){
            StockPrices sp=pricesList.get(i);
            if(sp.right>price){
                break;
            }else if(sp.left>price){
                for(int j=sp.prices.size()-1;j>=0;j--){
                    if(price<=sp.prices.get(j)){
                        ++result;
                    }
                }
            }else if(sp.left<=price){
                result+=sp.prices.size();
            }
        }
        return result;
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://www.ezyhdfw.cn/yun/77053.html

相關(guān)文章

  • [Leetcode] Best Time to Buy and Sell Stock 買賣股票的最佳

    摘要:雙指針法復(fù)雜度時(shí)間空間思路根據(jù)買賣股票的特性,我們必須先低價(jià)買,再高價(jià)賣,這個(gè)找最大收益的過程實(shí)際上是找到目前為之的最低價(jià)。我們可以利用這個(gè)之前計(jì)算的結(jié)果降低時(shí)間復(fù)雜度不過代價(jià)是額外空間,所以需要把到的最大收益存在數(shù)組中。 Best Time to Buy and Sell Stock I Say you have an array for which the ith element...

    nanchen2251 評(píng)論0 收藏0
  • 【刷算法】LeetCode.150-買賣股票的最佳時(shí)機(jī) II

    摘要:題目描述給定一個(gè)數(shù)組,它的第個(gè)元素是一支給定股票第天的價(jià)格。設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易多次買賣一支股票。隨后,在第天股票價(jià)格的時(shí)候買入,在第天股票價(jià)格的時(shí)候賣出這筆交易所能獲得利潤(rùn)。 題目描述 給定一個(gè)數(shù)組,它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。 設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易(多次買賣一支股票...

    Vultr 評(píng)論0 收藏0
  • 【LeetCode】貪心算法--買賣股票的最佳時(shí)機(jī) II(122)

    摘要:貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法,總是做出在當(dāng)前看來是最好的選擇,不從整體最優(yōu)上加以考慮,也就是說,只關(guān)心當(dāng)前最優(yōu)解,按照貪心策略,不關(guān)心以后,我們只關(guān)心當(dāng)前利益。 一、寫在前面 為什么要在LeetCode刷題?大家都知道不管是校招還是社招算法題是必考題,而這一部分恰巧是大多數(shù)人的短板,所以刷題首先是為了提高自身的編程能力,能夠在算法面試中...

    xbynet 評(píng)論0 收藏0
  • 金融套利策略:理解統(tǒng)計(jì)套利的工作原理

    摘要:后一種方法被稱之為多因子統(tǒng)計(jì)套利模型。套利套利可以被稱為交叉資產(chǎn)套利的一種形式,它可以識(shí)別的價(jià)值與其相關(guān)資產(chǎn)之間的差異。目前,統(tǒng)計(jì)套利策略已經(jīng)成為了對(duì)沖基金和投資銀行的主要力量。 作者:chen_h微信號(hào) & QQ:862251340微信公眾號(hào):coderpai簡(jiǎn)書地址:https://www.jianshu.com/p/ea2... 1. 什么是定量交易 定量交易是通過統(tǒng)計(jì)技術(shù)(或...

    whataa 評(píng)論0 收藏0
  • AJAX應(yīng)用【股票案例、驗(yàn)證碼校驗(yàn)】

    摘要:當(dāng)然了,和具體股票對(duì)象應(yīng)該是全局的變量這樣才能夠在別的方法中用到二驗(yàn)證碼校驗(yàn)對(duì)于驗(yàn)證碼檢查我們并不會(huì)陌生,我們?cè)趯W(xué)習(xí)的時(shí)候已經(jīng)使用過了驗(yàn)證碼檢查了。 一、股票案例 我們要做的是股票的案例,它能夠無刷新地更新股票的數(shù)據(jù)。當(dāng)鼠標(biāo)移動(dòng)到具體的股票中,它會(huì)顯示具體的信息。 我們首先來看一下要做出來的效果: showImg(https://segmentfault.com/img/remote/...

    阿羅 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<