LeetCode刷題總結（10）

2020-07-25

Z 字形變換

AC代碼

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int n = s.size();
        string temp[numRows];
        int t_numRows = 0;
        int p = 0;
        while(p < n) {
            while(p < n && t_numRows < numRows) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows++;
            }
            t_numRows = numRows -2;
            while (p < n && t_numRows > 0) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows--;
            }
        }
        string res;
        for(int i = 0 ; i < numRows; i++) {
            res = res + temp[i];
        }
        return res;
    }
};

優(yōu)化思路

  1. 兩層while循環(huán)多次判斷p<n,效率底下虱而，實際上只需要當t_numRows==0或t_numRows==numRows-1時改變方向即可

  2. 實際上需要的string數(shù)組長度是min(n, numRows)

    優(yōu)化代碼

    class Solution {
public:
 string convert(string s, int numRows) {
     if (numRows <= 1) {
         return s;
     }
     int n = int(s.size());
     int len = min(numRows, n);
     vector<string> temp(len);
     int t_numRows = 0;
     bool goingDown = false;
     for(int i = 0; i < n; i++) {
         temp[t_numRows] += s[i];
         if (t_numRows == 0 || t_numRows == numRows-1) {
             goingDown = !goingDown;
         }
         t_numRows += goingDown ? 1 :-1;
     }
     string res;
     for (int i = 0; i < len; i++) res += temp[i];
     return res;
 }
};

    再次優(yōu)化

    可以直接找新舊數(shù)列的數(shù)字關系，直接計算

    優(yōu)化代碼

    class Solution {
public:
 string convert(string s, int numRows) {
     if (numRows <= 1) {
         return s;
     }
     int len_s = int(s.size());
     int unit =(2*numRows-2);
     int n = len_s/unit;
     int remain = len_s%unit;
     string res(len_s, 0);
     for (int i = 0; i < len_s; i++) {
         int p = 0;
         if (i%unit == 0) {
             p = i/unit+1;
         } else {
             int r = i%unit + 1,c = i/unit+1;
             if (r > numRows) {
                 r = unit-r+2;
                 p = 1;
             } else if (r == numRows) {
                 p = 1-c;
             }
             p += n + (n*2)*(r-2) + 2*(c-1) + min(r-1, remain)+1;
             if (remain > numRows) {
                 p += max(r-(unit-remain+2),0);
             }
         }
         res[p-1] = s[i];
     }
     return res;
 }
};

    最終成績

    執(zhí)行用時：8 ms, 在所有 C++ 提交中擊敗了98.89%的用戶

    內(nèi)存消耗：7.7 MB, 在所有 C++ 提交中擊敗了100.00%的用戶

## 75. 顏色分類

AC代碼 計數(shù)

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n[3] = {0};
        for(int i : nums) {
            n[i]++;
        }
        int x = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < n[i]; j++) {
                nums[j+x] = i;
            }
            x += n[i];
        }
    }
};

優(yōu)化 三指針法

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int f,t = int(nums.size())-1,m;
        f = m = 0;
        while (m <= t) {
            if (nums[m] == 0) {
                swap(nums[m++], nums[f++]);
            } else if (nums[m] == 2) {
                swap(nums[m], nums[t--]);
            } else {
                m++;
            }
        }
    }
    void xchg(int& a, int& b) {
        a = a+b;
        b = a-b;
        a = a-b;
    }
};

129. 求根到葉子節(jié)點數(shù)字之和

AC代碼

class Solution {
public:
    int sum = 0;
    void go(TreeNode* root, int num) {
        if (root->left == NULL && root->right == NULL) {
            sum += num*10+root->val;
            return;
        }
        if (root->left != NULL) {
            go(root->left, num*10+root->val);
        }
        if (root->right != NULL) {
            go(root->right, num*10+root->val);
        }
    }
    int sumNumbers(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        go(root, 0);
        return sum;
    }
};

29. 兩數(shù)相除

AC代碼

class Solution {
public:
    unsigned int i2ui(int n) {
        return (n<0&&n != -2147483648)?-n:((n == -2147483648) ? 2147483648 : n);
    }
    int divide(int dividend, int divisor) {
        bool neg = (dividend<0)^(divisor<0);
        unsigned int a = i2ui(dividend), b = i2ui(divisor);
        unsigned int res = 0;
        unsigned int tb = b;
        unsigned int add = 1;
        while((tb & 0x80000000)==0) {
            tb <<= 1;
            add <<= 1;
        }
        while (a >= b) {
            if (a >= tb) {
                res += add;
                a -= tb;
            }
            add >>=1;
            tb >>= 1;
        }
        res =  (res > 2147483647 && !neg) ? INT_MAX : res;
        int ires = neg ? ((res>2147483648)?INT_MAX:-res) : res;
        return ires;
    }
};

思路

利用最基本的列豎式法开泽，先轉(zhuǎn)成正數(shù)牡拇，再計算

優(yōu)化

  1. 不滿足題目的假設我們的環(huán)境只能存儲 32 位有符號整數(shù)的條件

  2. 類似上面的算法，把所有數(shù)轉(zhuǎn)化為負數(shù)穆律，再對divisor=0x80000000時特判

優(yōu)化代碼

class Solution {
public:
    int nabs(int n) {
        return (n > 0)? -n : n;
    }
    int divide(int dividend, int divisor) {
        int neg = ((dividend<0)^(divisor<0));
        dividend = nabs(dividend);
        divisor = nabs(divisor);
        int sub = 1;
        if (divisor==INT_MIN) {
            return (dividend == INT_MIN) ? 1 : 0;
        }
        int t_divisor = -divisor;
        while((t_divisor & 0x40000000)==0) {
            t_divisor <<= 1;
            sub <<= 1;
        }
        int res = 0;
//        cout << t_divisor << " " << sub << endl;
        while (dividend <= divisor && sub != 0) {

            if (dividend <= -t_divisor) {
                dividend += t_divisor;
                res -= sub;
            }

            sub >>= 1;
            t_divisor >>= 1;

        }
        if (dividend <= divisor) {
            res = (res == INT_MIN)? res : res-1;
//            cout << res << endl;
        }
        res = !neg ? ((res==-2147483648)?INT_MAX:-res) : res;
        return res;
    }
};

最終成績

執(zhí)行用時：0 ms, 在所有 C++ 提交中擊敗了100.00%的用戶

內(nèi)存消耗：6 MB, 在所有 C++ 提交中擊敗了100.00%的用戶

36. 有效的數(shù)獨

AC代碼

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            int r[9] = {0};
            int c[9] = {0};
            int s[9] = {0};
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    r[board[i][j]-'1']++;
                }
                if (board[j][i] != '.') {
                    c[board[j][i]-'1']++;
                }
            }
            int a = i/3;
            int b = i%3;
            for (int ii = 3*a; ii < 3*(a+1); ii++) {
                for (int ij = 3*b; ij < 3*(b+1); ij++) {
                    if (board[ii][ij] != '.') {
                        s[board[ii][ij]-'1']++;
                    }
                }
            }
            for (int j = 0; j < 9; j++) {
                if (r[j] > 1 || c[j] > 1 || s[j] > 1) {
                    return false;
                }
            }

        }
        return true;
    }
};

5. 最長回文子串

AC代碼

class Solution {
public:
    map<int ,int, greater<int>> m;
    int rb=0,re=0;
    string longestPalindrome(string s) {
        int n = int(s.size());
        if (n <= 0) {
            return "";
        }

        go(s, 0, n);
        for (int off = 1; off < n; off++) {
            go(s, off, n);
            go(s, 0, n-off);
        }
        while (!m.empty()) {
            int sub = m.begin()->first;
            int sum = m.begin()->second;
            int beg = (sum-sub)/2;
            int end = (sum+sub)/2;
            if(go(s, beg,end) && ((re-rb) > (end-beg))) break;
        }
        return s.substr(rb, re-rb);
    }
    bool go(string& s,int beg, int end) {
        int pos = isPalindrome(s, beg, end);
        if (pos != beg) {
            end -= pos-beg;
            beg = pos;
            m[end-beg]=end+beg;
            return false;
        }else {
            m.erase(end-beg);
            if ((end-beg) > (re-rb)) {
                rb = beg;
                re = end;
            }
            return true;
        }

    }
    int isPalindrome(string& s, int beg, int end) {
        int res = -1;
        for(int i = 0; i < (end-beg)/2; i++) {
            if(s[beg+i] != s[end-1 - i] && i > res) res = i;
        }
        return beg+res+1;
    }
};

優(yōu)化

參考優(yōu)秀的題解惠呼，大致思想是把每個字符作為中心，向左右展開

class Solution {
public:
    int l=0,h=0;
    string longestPalindrome(string s) {
        int n = int(s.size());
        if (n <= 1) {
            return s;
        }
        for (int i = 0; i < n; i++) {
            i = findLongest(s, i, n);
        }
        return s.substr(l, h-l+1);
    }
    int findLongest(const string& s,int i, int n) {
        int high = i;
        while (high < n-1 && s[high+1] == s[i]) {
            high++;
        }// 中部字符全部相同
        int ans = high;
        while (i > 0 && high < n-1 && s[i-1]==s[high+1]) {
            i--;
            high++;//向兩邊展開
        }
        if ((high - i) > h-l) {
            h = high;
            l = i;    //更新最長串的位置
        }
        return ans;
    }
};

62. 不同路徑

思路

大佬們都是用dp峦耘，而我是推公式剔蹋，就是這么簡單

AC代碼

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m > n) {
            m = m+n;
            n = m-n;
            m = m-n;
        }
        int res = n;
        if (m < 2) {
            return 1;
        }
        if (m == 2) {
            return n;
        }
        vector<int> v(m-2, 0);
        for (int i = 1; i <= n-1; i++) {
            v[0] += i;
            for (int j = 1; j < m - 2; j++) {
                v[j] += v[j-1];
            }
        }
        for (int i = 0; i < m -2; i++) {
            res += v[i];
        }
        return res;
    }
};

最終成績

執(zhí)行用時：0 ms, 在所有 C++ 提交中擊敗了100.00%的用戶

內(nèi)存消耗：5.9MB, 在所有 C++ 提交中擊敗了100.00%的用戶

63. 不同路徑 II

AC代碼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = int(obstacleGrid.size());
        int m = int(obstacleGrid[0].size());
        bool swap = false;
        if (m > n) {
            m = m+n;
            n = m-n;
            m = m-n;
            swap = true;
        }
        
        vector<long long> v(m+1, 0);
        long long t_v0 = 1;
        for (int i = 0; i < n; i++) {
            if ((!swap && obstacleGrid[n-i-1][m-1]) || (swap && obstacleGrid[m-1][n-1-i])) {
                v[0] = 0;
            } else {
                v[0] = t_v0;
            }
            t_v0 = v[0];
            for(int j  = 1; j < m; j++) {
                if ((!swap && obstacleGrid[n-i-1][m-1-j]) || (swap && obstacleGrid[m-1-j][n-1-i])) {
                    v[j] = 0;
                } else {
                    v[j] += v[j-1];
                }
            }
        }
        return (int)v[m-1];
    }
};

優(yōu)化1

不需要轉(zhuǎn)置，這個問題來自于試錯過程中的錯誤判斷
看了題解以后發(fā)現(xiàn)自己的代碼和它驚人的相似辅髓，原來我無師自通學會動規(guī)了泣崩？少梁？哈哈哈哈

優(yōu)化1代碼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = int(obstacleGrid.size());
        int m = int(obstacleGrid[0].size());
        vector<long long> v(m+1, 0);
        long long t_v0 = 1;
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[n-i-1][m-1]) {
                v[0] = 0;
            } else {
                v[0] = t_v0;
            }
            t_v0 = v[0];
            for(int j  = 1; j < m; j++) {
                if (obstacleGrid[n-i-1][m-1-j]) {
                    v[j] = 0;
                } else {
                    v[j] += v[j-1];
                }
            }
        }
        return (int)v[m-1];
    }
};
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個濱河市矫付，隨后出現(xiàn)的幾起案子凯沪，更是在濱河造成了極大的恐慌，老刑警劉巖买优，帶你破解...
    沈念sama閱讀 216,470評論 6贊 501
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件妨马，死亡現(xiàn)場離奇詭異，居然都是意外死亡杀赢，警方通過查閱死者的電腦和手機烘跺，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,393評論 3贊 392
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來脂崔，“玉大人液荸，你說我怎么就攤上這事⊥迅荩” “怎么了娇钱？”我有些...
    開封第一講書人閱讀 162,577評論 0贊 353
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長绊困。 經(jīng)常有香客問我文搂，道長，這世上最難降的妖魔是什么秤朗？ 我笑而不...
    開封第一講書人閱讀 58,176評論 1贊 292
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任煤蹭，我火速辦了婚禮，結果婚禮上取视，老公的妹妹穿的比我還像新娘硝皂。我一直安慰自己，他們只是感情好作谭，可當我...
    茶點故事閱讀 67,189評論 6贊 388
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布稽物。 她就那樣靜靜地躺著，像睡著了一般折欠。 火紅的嫁衣襯著肌膚如雪贝或。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,155評論 1贊 299
  • 城市分裂傳說
    那天锐秦，我揣著相機與錄音咪奖，去河邊找鬼。 笑死酱床，一個胖子當著我的面吹牛羊赵，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播扇谣，決...
    沈念sama閱讀 40,041評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼昧捷，長吁一口氣：“原來是場噩夢啊……” “哼揖闸！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起料身，我...
    開封第一講書人閱讀 38,903評論 0贊 274
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤汤纸，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后芹血，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體贮泞，經(jīng)...
    沈念sama閱讀 45,319評論 1贊 310
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,539評論 2贊 332
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年幔烛，在試婚紗的時候發(fā)現(xiàn)自己被綠了啃擦。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,703評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡饿悬，死狀恐怖令蛉，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情狡恬，我是刑警寧澤珠叔，帶...
    沈念sama閱讀 35,417評論 5贊 343
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站弟劲，受9級特大地震影響祷安，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜兔乞，卻給世界環(huán)境...
    茶點故事閱讀 41,013評論 3贊 325
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一汇鞭、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧庸追，春花似錦霍骄、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,664評論 0贊 22
  • 一樁弒父案读整，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至血筑，卻和暖如春绘沉，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背豺总。 一陣腳步聲響...
    開封第一講書人閱讀 32,818評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留择懂，地道東北人喻喳。 一個月前我還...
    沈念sama閱讀 47,711評論 2贊 368
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像困曙，于是被迫代替她去往敵國和親表伦。 傳聞我的和親對象是個殘疾皇子谦去，可洞房花燭夜當晚...
    茶點故事閱讀 44,601評論 2贊 353