• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            [LeetCode]Jump Game [& II]-2014.01.11

            Posted on 2014-01-11 01:43 Uriel 閱讀(172) 評論(0)  編輯 收藏 引用 所屬分類: LeetCode
            這題昨天攜程網(wǎng)絡(luò)賽有原題,于是今天來做了一下,不過自己還是太挫,只想到裸O(n^2)的dp,據(jù)說會超時,但是又想不出優(yōu)化,于是瞟了一眼解題報告,瞬間恍然大悟...
            第二重循環(huán)不需要從頭開始再掃一遍,只需要從目前能到達的最遠點開始即可!
            兩題方法完全一樣~

            Jump Game

             1 class Solution {
             2 public:
             3     bool canJump(int A[], int n) {
             4         int dp[1000010], mx = 0;
             5         memset(dp, 0, sizeof(dp));
             6         for(int i = 0; i < n; ++i) {
             7             for(int j = mx - i + 1; j <= A[i] && i + j < n; ++j) {
             8                 if(!i || dp[i])
             9                     dp[i + j] = dp[i] + 1;
            10             }
            11             mx = max(mx, A[i] + i);
            12         }
            13         if(dp[n - 1] || n == 1) return true;
            14         return false;
            15     }
            16 };

            Jump Game II

             1 class Solution {
             2 public:
             3     int jump(int A[], int n) {
             4         int dp[1000010], mx = 0;
             5         memset(dp, 0, sizeof(dp));
             6         for(int i = 0; i < n; ++i) {
             7             for(int j = mx - i + 1; j <= A[i] && i + j < n; ++j) {
             8                 dp[i + j] = dp[i] + 1;
             9             }
            10             mx = max(mx, A[i] + i);
            11         }
            12         return dp[n - 1];
            13     }
            14 };
            国色天香久久久久久久小说| 国产综合久久久久| 久久国产精品-久久精品| 蜜桃麻豆www久久| 无码人妻久久一区二区三区蜜桃| 99精品国产在热久久无毒不卡| 亚洲国产精品无码久久一区二区| 2020久久精品亚洲热综合一本| 久久国产AVJUST麻豆| 狠狠综合久久AV一区二区三区| 色8久久人人97超碰香蕉987| 久久精品一区二区国产| 久久亚洲AV永久无码精品| 久久久久亚洲精品日久生情 | 伊人久久大香线蕉精品不卡 | 五月丁香综合激情六月久久| 国产V综合V亚洲欧美久久| 国产亚洲美女精品久久久| 99精品久久久久久久婷婷| 久久久精品午夜免费不卡| 污污内射久久一区二区欧美日韩| 久久精品国产影库免费看| 久久免费视频1| 久久国产精品二国产精品| 精品国产乱码久久久久久1区2区| 国产—久久香蕉国产线看观看| 色青青草原桃花久久综合| 久久成人精品视频| 国产精品美女久久久久| 国内精品久久久久影院薰衣草| 久久国产成人午夜AV影院| 久久精品国产精品亚洲毛片| 新狼窝色AV性久久久久久| 国产精品久久久久久五月尺| 精品无码人妻久久久久久| 欧美日韩中文字幕久久伊人| 国产亚洲精久久久久久无码| 久久久久久亚洲精品成人 | 一个色综合久久| 久久国产一片免费观看| 久久久99精品成人片中文字幕|