Leetcode Weekly Contest 101

這次比賽,網(wǎng)站掛了10多分鐘迅栅。后來終于進(jìn)去了殊校。
我做出來3道,最后一道知道是DP读存,最后一步?jīng)]當(dāng)場分析出來为流。最后排名132/4300

900. RLE Iterator

https://leetcode.com/contest/weekly-contest-101/problems/rle-iterator/
這道題目就是九杂,2個(gè)數(shù)字為一組卧须,告訴你有幾個(gè)幾。
然后NEXT,就根據(jù)翻譯出來的數(shù)來取吴侦。
比如【3,1】就是 【1,1,1】
那么肯定就是維護(hù)一個(gè)REST變量,和一個(gè)指針P酪穿,表明遍歷到目前為止蝴悉,指的這個(gè)數(shù)還剩幾個(gè)沒遍歷。
比如上面的例子锐帜。我調(diào)用next(2) 那就是 P指向1田盈,REST 為1. 還有1和1沒用。

int[] A;
    int p;
    int rest = 0;
    public RLEIterator(int[] A) {
        this.A = A;
        p = -1;
    }
    
    public int next(int n) {
        while(rest - n < 0){
            n -= rest;
            p+=2;
            if(p>=A.length) return -1;
            rest = A[p-1];
        }
        rest -= n;
        if(p>=A.length) return -1;
        return A[p];
    }

901. Online Stock Span

https://leetcode.com/problems/online-stock-span/description/
這是道要維護(hù)前面所有小于等于當(dāng)前值的題缴阎。那么看數(shù)據(jù)規(guī)模還要求O N
果斷允瞧,知道每一步要么是O 1 要么是 Log N。
因?yàn)槭蔷S護(hù)前面連續(xù)的數(shù)蛮拔,所以2分的概率不大瓷式。
一旦一個(gè)數(shù)大于棧頂元素,那么就可以把連續(xù)給斷開语泽。
比如 60,60,70,60. 最后一個(gè)60因?yàn)楸?0阻隔開了贸典,所以只能返回1,而不是3.
根據(jù)這個(gè)性質(zhì)踱卵。我們可以想到單調(diào)棧廊驼。如果一個(gè)數(shù)大于棧頂,其實(shí)那些小于這個(gè)數(shù)就可以POP了惋砂,因?yàn)橐灿貌坏搅恕?/p>

Stack<int[]> st = new Stack<>();
    int idx = 0;
    public StockSpanner() {
        st.push(new int[]{10001,-1});
    }
    
    public int next(int price) {
        while(st.peek()[0]<=price){
            st.pop();
        }
        int res = idx-st.peek()[1];
        st.push(new int[]{price,idx++});
        return res;
    }

902. Numbers At Most N Given Digit Set

https://leetcode.com/problems/numbers-at-most-n-given-digit-set/description/
這道題也不是太難妒挎。我的解法是先用公式把所有位數(shù)比N小的,求掉西饵。
比如1,2,3. 3個(gè)數(shù)酝掩。 N=100,位數(shù)為3. 我們先把位數(shù)為1眷柔,和位數(shù)為2的求了期虾。
位數(shù)為1的是3. 位數(shù)為2的個(gè)數(shù)是33.
再在位數(shù)和N相同的情況下,一位一位求驯嘱。
位數(shù)相同
我們先看第一位能用幾個(gè)镶苞。1,2,3 鞠评; N=200 第一位是2.
我們先把第一位是比2小的數(shù)找到K 找到 然后后面2位茂蚓,就可以隨意了。K
3^(n-1)
下面看這個(gè)2是不是和能用的數(shù)相等。試的話聋涨,我們接著去求下一位晾浴,公式一樣。
如果是1,3,5牍白; N=200脊凰; 我們發(fā)現(xiàn)是3》2; 這個(gè)情況就可以直接跳出循環(huán)了淹朋。

public int atMostNGivenDigitSet(String[] D, int N) {
        N++;
        int l = D.length;
        int nl = (N+"").length();
        //cnt digit number < nl
        int cnt = 0;
        for(int i = 1; i < nl; i++){
            cnt += (int)Math.pow(l,i);
        }
        //cnt digit number = nl
        int k = nl-1;
        for(char c : (N+"").toCharArray()){
            int i = 0;
            for(; i < l && D[i].charAt(0) < c ; i++){}
            cnt += (i*(Math.pow(l,k)));
            if(i<l && D[i].charAt(0) == c){
                k--;
            }else{
                break;
            }
        }
        return cnt;
    }

最后我發(fā)現(xiàn)笙各,如果正好是每一位都相等,那會漏掉完全相等的這個(gè)數(shù)础芍。所以一開始用N++杈抢。
這樣就解決了。

903. Valid Permutations for DI Sequence

https://leetcode.com/problems/valid-permutations-for-di-sequence/description/
這道題的思路是這樣的仑性。
我們先從DI來分析惶楼。
D 勢必為1,0

如果之后是I。我們可以列舉以J為結(jié)尾的上升時(shí)什么诊杆。 首先以0為結(jié)尾是不可能的歼捐。
其次,以1為結(jié)尾是可以的201. 以2為結(jié)尾也是可以的 是102
我們不妨定義(DP I J) 就是 I個(gè)數(shù)字的全排列里晨汹,符合到PATTERN.substring(0,i-1)的最后一個(gè)數(shù)字為J的個(gè)數(shù)有幾個(gè)豹储。
根據(jù)題目的例子
DID 的情況
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
dp[4][0] = 2
dp[4][1] = 2
dp[4][2] = 1
dp[4][3] = 0
dp[4][4] = 0
如果我們要在DID 后面多加一個(gè)D,會怎么轉(zhuǎn)變呢
如果要符合條件淘这,dp[5][0] = {(2+1, 1+1, 3+1, 0+1,0)剥扣,(2+1, 1+1, 3+1, 0+1,0)}(這里可以得知dp[5][0] = 0+dp[4][0])
dp[5][0] = {(2+1, 0+1, 3+1, 1+1,0),(3+1, 0+1, 2+1, 1+1,0)} (這里可以得知dp[5][0] = dp[4][0]+dp[4][1])
dp[5][0] = {(1, 0+1, 3+1, 2+1,0)} (這里可以得知dp[5][0] =dp[4][0]+dp[4][1]+dp[4][2])
那么當(dāng)D的時(shí)候铝穷,dp[i][j] 可以從 dp[i-1][k] (k from j ... i-1)
同樣可以發(fā)現(xiàn)dp[i][j] 在最后一個(gè)是字母是I的時(shí)候钠怯,我們可以從dp[i-1][k](k from 0...j-1)
那么比如DIDI的情況
dp[5][0] = 0 因?yàn)镴-1《0
dp[5][1] = {(2+1, 1+1, 3+1, 0,1),(3+1, 1+1, 2+1, 0,1)} dp[5][1] = dp[4][0]
dp[5][2] = {(2+1, 1, 3+1, 0,2),(3+1, 1, 2+1, 0,2)} + {(2+1, 0, 3+1, 1,2),(2+1, 0, 3+1, 1,2)} dp[5][2] = dp[4][0]+dp[4][1]
綜上

public int numPermsDISequence(String s) {
        int n = s.length()+1;
        long[][] dp = new long[n][n];
        dp[0][0] = 1;
        int M = 1000000007;
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(s.charAt(i-1) == 'D'){
                    for(int k = j; k < i; k++)
                        dp[i][j] = (dp[i][j]+dp[i-1][k])%M;
                }else{
                    for(int k = 0; k < j; k++)
                        dp[i][j] = (dp[i][j]+dp[i-1][k])%M;
                }
            }
        }
        long ans = 0;
        for(int i = 0; i < n; i++) ans = (ans+dp[n-1][i])%M;
        return (int) ans;
    }

下面我們思考可不可以優(yōu)化,因?yàn)槲铱吹阶詈笊纱鸢赣幸粋€(gè)累加的操作曙聂。我就思考了這么一個(gè)問題晦炊,我可以不可以讓DP狀態(tài)就表示為(DP I J) 就是 I個(gè)數(shù)字的全排列里,符合到PATTERN.substring(0,i-1)的最后一個(gè)數(shù)字至多為J的個(gè)數(shù)有幾個(gè)宁脊。
這樣我最后就可以直接范圍DP[N-1][N-1]就是解了断国。

隨后我依然把這個(gè)解給擺出來。
DI 的情況有
(2,0,1)dp[3][1] = 1
(1,0,2)dp[3][2] = dp[3][1]+1 = 2;
dp[3][3] = dp[3][2]+0=2;
如果后面接了D
dp[4][0] 當(dāng)最后一個(gè)數(shù)是0的話朦佩,那么就意味著并思,之前3,3的所有可能都可以組成新的解。因?yàn)橹灰?的位置语稠,所有的解,最后補(bǔ)上0,前面+1仙畦,都是WORK的输涕。
dp[4][1] ,肯定是包含DP[4][0]的,如果最后一位需要是1. (3,0,2,1)(2,0,3,1)也是可以的
目前還看不出規(guī)律慨畸。
dp[4][2] = dp[4][1] + 最后一位需要是2的莱坎,這時(shí)我們會發(fā)現(xiàn) (2,0,1,2) 是沒法通過加1,使得最后一位是2寸士,同時(shí)保持下降的檐什。
所以我們需要排除dp[3][1]這個(gè)解,而這個(gè)1弱卡,是比當(dāng)前的2小1 的乃正。
我們猜想公式為dp[i][j] = dp[i][j-1]+dp[i-1][i-1]-dp[i-1][j-1]
這個(gè)遞推公式的含義就是,少這個(gè)位數(shù)婶博,如果要讓最后一位是J瓮具,必須前一位至少也需要是J,所以J-1的都不行凡人。

下面再看I的情況名党,我們可以得知,最后一位是0挠轴,是不可能存在I的传睹。那么DP[4][1]。我們就可以加上DP[3][0]的那些解岸晦,最后補(bǔ)上1. 同理DP[4][2] 所有DP[3][1]的解都可以再最后補(bǔ)上2.
我們猜想公式為dp[i][j] = dp[i][j-1]+dp[i-1][j-1]

最后處理下邊界情況欧啤。得到代碼如下,時(shí)間復(fù)雜度被優(yōu)化到N ^2

public int numPermsDISequence(String s) {
        int l = s.length()+1;
        int[][] dp = new int[l][l];
        dp[0][0] = 1;
        int M = 1000000007;
        for(int i = 1; i < l; i++){
            for(int j = 0; j <= i; j++){
                if(s.charAt(i-1) == 'D'){
                    if(j!=0){
                        dp[i][j] = (dp[i][j-1]-dp[i-1][j-1]+M)%M;
                    }
                    dp[i][j] = (dp[i][j]+dp[i-1][i-1])%M;
                    
                }else{
                    if(j!=0){
                        dp[i][j] = (dp[i][j-1]+dp[i-1][j-1])%M;
                    }
                }
            }
        }
        return dp[l-1][l-1];
    }
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末委煤,一起剝皮案震驚了整個(gè)濱河市堂油,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌碧绞,老刑警劉巖府框,帶你破解...
    沈念sama閱讀 219,366評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異讥邻,居然都是意外死亡迫靖,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,521評論 3 395
  • 文/潘曉璐 我一進(jìn)店門兴使,熙熙樓的掌柜王于貴愁眉苦臉地迎上來系宜,“玉大人,你說我怎么就攤上這事发魄№锬粒” “怎么了俩垃?”我有些...
    開封第一講書人閱讀 165,689評論 0 356
  • 文/不壞的土叔 我叫張陵,是天一觀的道長汰寓。 經(jīng)常有香客問我口柳,道長,這世上最難降的妖魔是什么有滑? 我笑而不...
    開封第一講書人閱讀 58,925評論 1 295
  • 正文 為了忘掉前任跃闹,我火速辦了婚禮,結(jié)果婚禮上毛好,老公的妹妹穿的比我還像新娘望艺。我一直安慰自己,他們只是感情好肌访,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,942評論 6 392
  • 文/花漫 我一把揭開白布找默。 她就那樣靜靜地躺著,像睡著了一般场靴。 火紅的嫁衣襯著肌膚如雪啡莉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,727評論 1 305
  • 那天旨剥,我揣著相機(jī)與錄音咧欣,去河邊找鬼。 笑死轨帜,一個(gè)胖子當(dāng)著我的面吹牛魄咕,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播蚌父,決...
    沈念sama閱讀 40,447評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼哮兰,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了苟弛?” 一聲冷哼從身側(cè)響起喝滞,我...
    開封第一講書人閱讀 39,349評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎膏秫,沒想到半個(gè)月后右遭,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,820評論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡缤削,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,990評論 3 337
  • 正文 我和宋清朗相戀三年窘哈,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片亭敢。...
    茶點(diǎn)故事閱讀 40,127評論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡滚婉,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出帅刀,到底是詐尸還是另有隱情让腹,我是刑警寧澤远剩,帶...
    沈念sama閱讀 35,812評論 5 346
  • 正文 年R本政府宣布,位于F島的核電站哨鸭,受9級特大地震影響民宿,放射性物質(zhì)發(fā)生泄漏娇妓。R本人自食惡果不足惜像鸡,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,471評論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望哈恰。 院中可真熱鬧只估,春花似錦、人聲如沸着绷。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,017評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽荠医。三九已至吁脱,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間彬向,已是汗流浹背兼贡。 一陣腳步聲響...
    開封第一講書人閱讀 33,142評論 1 272
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留娃胆,地道東北人遍希。 一個(gè)月前我還...
    沈念sama閱讀 48,388評論 3 373
  • 正文 我出身青樓,卻偏偏與公主長得像里烦,于是被迫代替她去往敵國和親凿蒜。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,066評論 2 355

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)胁黑。 張土汪:刷leetcod...
    土汪閱讀 12,747評論 0 33
  • <center>#1 Two Sum</center> link Description:Given an arr...
    鐺鐺鐺clark閱讀 2,155評論 0 3
  • 1.Sort Colors[Sort Colors]https://leetcode.com/problems/s...
    Zake_Wang閱讀 423評論 0 1
  • 廈門回來那天就發(fā)現(xiàn)小倉鼠死了废封。試著把他救活,我以為救活了丧蘸,然而最終還是沒有漂洋。 和籠子一起扔到垃圾桶。 都過去三天了...
    lichangan閱讀 375評論 0 0
  • 受傷的射手像今夜的戈壁——在黑暗中盼望仙人掌開出金黃的花朵触趴。 碩大的花蕊變成他的弓箭氮发,甘甜的漿果變成他的酒杯。 天...
    他是鬼徹閱讀 199評論 0 2