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;
    }
};

优化思路

  1. 两层while循环多次判断p<n,效率底下，实际上只需要当t_numRows==0或t_numRows==numRows-1时改变方向即可

  2. 实际上需要的string数组长度是min(n, numRows)

    优化代码

    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;
 }
};

    再次优化

    可以直接找新旧数列的数字关系，直接计算

    优化代码

    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;
 }
};

    最终成绩

    执行用时：8 ms, 在所有 C++ 提交中击败了98.89%的用户

    内存消耗：7.7 MB, 在所有 C++ 提交中击败了100.00%的用户

## 75. 颜色分类

AC代码 计数

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];
        }
    }
};

优化 三指针法

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. 求根到叶子节点数字之和

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. 两数相除

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;
    }
};

思路

利用最基本的列竖式法，先转成正数，再计算

优化

  1. 不满足题目的假设我们的环境只能存储 32 位有符号整数的条件

  2. 类似上面的算法，把所有数转化为负数，再对divisor=0x80000000时特判

优化代码

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;
    }
};

最终成绩

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6 MB, 在所有 C++ 提交中击败了100.00%的用户

36. 有效的数独

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;
    }
};

优化

参考优秀的题解，大致思想是把每个字符作为中心，向左右展开

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;
    }
};

最终成绩

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：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];
    }
};

优化1

不需要转置，这个问题来自于试错过程中的错误判断
看了题解以后发现自己的代码和它惊人的相似，原来我无师自通学会动规了？？哈哈哈哈

优化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];
    }
};
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,319评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,801评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,567评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,156评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,019评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,090评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,500评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,192评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,474评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,566评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,338评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,212评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,572评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,890评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,169评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,478评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,661评论 2赞 335