lc 61~70

61. 旋转链表

单链表

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        //要做1.尾节点指向原头节点 2.head更新为原倒数第K个节点，3.原倒数第k+1个节点指向nullptr
        int n = 0;//求长度
        ListNode *tail;//记录尾节点
        for(auto p = head; p; p = p->next){
            tail = p;
            n++;
        }
        k %= n;//如果k等于n相当于没变，周期为n
        if(!k) return head;

        auto p = head;
        //找到倒数第k+1个节点
        for(int i = 0; i < n - k - 1; i++) p = p->next;
        tail->next = head;
        head = p->next;
        p->next = nullptr;
        return head;
    }
};

62. 不同路径

DP

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        //dp[i][j]代表从(0,0)走到(i,j)的路径数，当i=0||j=0时都是1条，否则就等于上面下来的加
        //左边过来的路径和
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++){
                if(!i && !j) dp[i][j] = 1;
                else{
                    if(i) dp[i][j] += dp[i - 1][j];
                    if(j) dp[i][j] += dp[i][j - 1];
                }
            }
        return dp[m - 1][n - 1];
    }
};

组合数公式(个人模板，三个)

class Solution {
public:
    int uniquePaths(int m, int n) {
        //x为总步数，y为向下的步数，则Cxy即为答案
        int x = m - 1 + n - 1, y = min(m - 1, n - 1);//一定要取下min,不然会溢出,不然下面就不用LL用double再向上取整
        return C(x, y);

        //法2.
        // long long ans = 1;
        // for (int x = n, y = 1; y < m; ++x, ++y) {
        //     ans = ans * x / y;
        // }
        // return ans;
    }

    int C(int x, int y){
        // long long res = 1;//要转LL，不然下面先乘会溢出
        double res = 1;
        for(long long i = x, u = 1; u <= y; i--, u++)
            res = res * i / u;
        return (int)(res + 0.5);
    }
};

63. 不同路径 II

DP

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& o) {
        int n = o.size(), m = o[0].size();
        vector<vector<int>> dp(n, vector<int>(m));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
                if(!i && !j) dp[0][0] = 1 - o[0][0];//有障碍物就0，无就1
                else{
                    if(o[i][j]) dp[i][j] = 0;
                    else{
                        if(i) dp[i][j] += dp[i - 1][j];
                        if(j) dp[i][j] += dp[i][j - 1];
                    }
                }
            }
        return dp[n - 1][m - 1];
    }
};

64. 最小路径和

DP

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++){
                if(!i && !j) dp[i][j] = grid[i][j];
                else{
                    if(i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]);
                    if(j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j]);
                }
            }
        return dp[m - 1][n - 1];
    }
};

65. 有效数字

模拟(很麻烦)

class Solution {
public:
    bool isNumber(string s) {
        //先去掉前后的空格,现在题意好像是就没空格，但无所谓了
        int l = 0, r = s.size() - 1;
        while(l <= r && s[l] == ' ') l ++;
        while(l <= r && s[r] == ' ') r --;
        if(l > r) return false;
        s = s.substr(l, r - l + 1);
        //剩下的就是该判断是不是有效数字的串了
        if(s[0] == '+' || s[0] == '-') s = s.substr(1);//去掉正负号
        if(s.empty()) return false;
        //.直接跟数字是有效的，跟e/E不行
        if(s[0] == '.' && (1 == s.size() || s[1] == 'e' || s[1] == 'E')) return false;
        //剩下的情况继续筛
        int dot = 0, e = 0;//不能出现多个. e E
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '.'){
                dot++;
                if(dot > 1 || e) return false;//注意.前面有e E也是错的
            }else if(s[i] == 'e' || s[i] == 'E'){
                e++;
                //如果第一个就是e E,e多个，e后没东西了就是无效的
                if(!i || e > 1 || i + 1 == s.size()) return false;
                //如果后面出现正负号，正负号后没东西无效，有东西就跳过正负号、
                if(s[i + 1] == '+' || s[i + 1] == '-'){
                    if(i + 2 == s.size()) return false;
                    else i++;
                }
            }else if(s[i] > '9' || s[i] < '0') return false;
        }
        return true;
    }
};

66. 加一

简单，注意最后有进位用insert插入

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int t = 1;
        for(int i = digits.size() - 1; i >= 0; i--){
            t += digits[i];
            digits[i] = t % 10;
            t /= 10;
        }
        if(t) digits.insert(digits.begin(), t);
        return digits;
    }
};

67. 二进制求和

先翻转，求出结果再翻转

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int t = 0;
        for(int i = 0; i < a.size() || i < b.size(); i++){
            if(i < a.size()) t += a[i] - '0';
            if(i < b.size()) t += b[i] - '0';
            ans += to_string(t % 2);
            t /= 2;
        }
        if(t) ans += to_string(t);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

68. 文本左右对齐

模拟，关键是把题意弄清楚

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        //左对齐:最后一行或者该行只能放一个单词，其余情况左右对齐，且空格均摊，有余数再从左均摊
        //左对齐单词间一个空格，其余空格放后面
        vector<string> ans;
        int size = words.size();
        for(int i = 0; i < size; ){
            string line = words[i]; //每行的单词,先放第一个
            //开始往后搜该行最多放几个单词，注意相邻单词间至少有一个空格
            int k = i + 1, len = line.size();
            while(k < size && len + 1 + words[k].size() <= maxWidth)//注意这里一定是<=,不是<
                len += 1 + words[k++].size();//1代表空格长度
            //如果k越界，就是最后一行，或k还是i+1没变，即只能放一个单词，左对齐
            if(k >= size || k == i + 1){
                for(int j = i + 1; j < k; j++)
                      line += ' ' + words[j];
                while(line.size() < maxWidth) line += ' '; 
            }else{
                //cnt代表单词间隙数，即刚才预放置的空格数，r代表总共需要放的空格数
                int cnt = k - i - 1, r = maxWidth - len + cnt;
                //余数为 r % cnt, 前面放 r/cnt+1,后面r/cnt
                int ii = 0;
                for(; ii < r % cnt; ii++)
                    line += string(r / cnt + 1, ' ') + words[i + ii + 1];
                while(ii < cnt) line += string(r / cnt, ' ') + words[i + ii + 1], ii++;
            }
            ans.push_back(line);
            i = k;
        }
        return ans;
    }
};

69. x 的平方根

简单小数二分

class Solution {
public:
    int mySqrt(int x) {
        double l = 0, r = x;
        while(r - l > 1e-10){
            double mid = (l + r) / 2;
            if(mid * mid >= x) r = mid;
            else l = mid;
        }
        return (int)r;
    }
};

巧用二分模板

class Solution {
public:
    int mySqrt(int x) {
        //二分模板，如2.6,即找到2,也就是找平方小于等于x的那部分的右端点
        int l = 0, r = x;
        while(l < r){
            int mid = l + 1ll + r >> 1;//把1ll放中间转为longlong,防止溢出
            if(mid <= x / mid) l = mid; //这样写也防止溢出
            else r = mid - 1;
        }
        return l;
    }
};

70. 爬楼梯

DP

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};

滚动数组

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        while(--n){
            int c = a + b;
            a = b, b = c;
        }
        return b;
    }
};