LeetCode61-70

发表于 | 更新于: | 分类于 ， | | 阅读次数:
字数统计: 1.3k 字 | 阅读时长 ≈ 7 分钟

61、旋转链表

模拟题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int len = 0;
        for(struct ListNode *ptr = head; ptr; ptr=ptr->next){
            len++;
            if(ptr->next==NULL){
                ptr->next = head;
                break;
            }
        }
        if(len==0)
            return NULL;
        k %= len;
        for(int i=1; i<=len-k; i++)
            head = head->next;
        struct ListNode *ans = head;
        for(int i=1; i<len; i++)
            head = head->next;
        head->next = NULL;
        return ans;
    }
};

62、不同路径

排列组合，当 m 和 n 较大时，应该使用 Lucas 定理。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int uniquePaths(int m, int n) {
        int total = m+n-2;
        int frac = min(m-1, n-1);
        long long fenzi = 1, fenmu = 1;
        for(int i=1; i<=frac; i++){
            fenzi *= total-i+1;
            fenmu *= i;
        }
        return fenzi/fenmu;
    }
};

63、不同路径 II

同上一题，只不过加了障碍，判断一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid[0].size();
        vector<long long> ans(m, 0);
        for(int i=0; i<n; i++){
            ans[0] = i==0? (obstacleGrid[i][0]+1)%2 : ((obstacleGrid[i][0]+1)%2 && ans[0]);
            for(int j=1; j<m; j++)
                ans[j] = obstacleGrid[i][j]==1?0:ans[j-1]+ans[j];
        }
        return ans[m-1];
    }
};

64、最小路径和

水 dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int i, j;
        for(i=1; i<grid.size(); i++)
            grid[i][0] += grid[i-1][0];
        for(j=1; j<grid[0].size(); j++)
            grid[0][j] += grid[0][j-1];
        for(i=1; i<grid.size(); i++)
            for(j=1; j<grid[0].size(); j++)
                grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        return grid[grid.size()-1][grid[0].size()-1];
    }
};

65、 有效数字

见过的最恶心的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    bool isNumber(string s) {
        vector<int> num(10,0);
        s.erase(0,s.find_first_not_of(" "));
        s.erase(s.find_last_not_of(" ") + 1);
        if(s[s.length()-1]=='e' || s[s.length()-1]=='+' || s[s.length()-1]=='-')
            return false;
        for(int i=0; i<s.length(); i++){
            if(s[i]=='-' || s[i]=='+'){
                num[0]++;
                if(i>0 && (s[i-1]=='-' || s[i-1]=='+'))
                    return false;
            }
            else if(s[i]=='e')
                num[1]++;
            else if(s[i]>='0' && s[i]<='9')
                num[3]++;
            else if(s[i]=='.' && num[1]==0){
                num[2]++;
            }
            else
                return false;
        }
        if(num[0]>2 || num[1]>1 || num[2]>1 || s[0]=='e' || num[3]==0)
            return false;
        if(num[1]==1){
            int index = s.find('e');
            if(index==s.length()-1 || (index==1 && s[0]=='.') || (index>0 && (s[index-1]=='-' || s[index-1]=='+')))
                return false;
        }
        if(num[0]){
            int index = s.find('-');
            if(index<0 || index>=s.length())
                index = s.find('+');
            if(index==s.length()-1 || (index>0 && ((isdigit(s[index-1]) && isdigit(s[index+1])) || s[index-1]=='.')))
               return false;
            int sum = 0;
            for(int i=index+1; i<s.length(); i++){
                if(s[i]>='0' && s[i]<='9')
                    sum++;
            }
            if(sum==0)
                return false;
        }
        return true;
    }
};

66、 加一

模拟题，考虑下进位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int num = 1;
        for(int i=digits.size()-1; i>=0.; i--){
            num += digits[i];
            digits[i] = num % 10;
            num /= 10;
        }
        if(num)
            digits.insert(digits.begin(), 1);
        return digits;
    }
};

67、二进制求和

模拟题，考虑二进制进位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string addBinary(string a, string b) {
        string ans = "";
        int flag = 0, sum = 0;
        int len_a = a.size(), len_b = b.size();
        while(len_a>0 || len_b>0){
            sum = flag;
            if(len_a>0)
                sum += a[--len_a]-'0';
            if(len_b>0)
                sum += b[--len_b]-'0';
            flag = sum/2;            ans.insert(ans.begin(), '0'+sum%2);
        }
        if(flag)
            ans = '1' + ans;
        return ans;
    }
};

68、文本左右对齐

模拟题，对空格数做判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans;
        vector<vector<string>> tmp;
        int len = 0, pos = 0, i;
        while(pos<words.size()){
            ans.clear();
            i = pos;
            ans.push_back(words[i]);
            len = words[i++].length()+1;
            while(i<words.size() && len+words[i].length()<=maxWidth){
                ans.push_back(words[i]);
                len += words[i++].length() + 1;
            }
            tmp.push_back(ans);
            pos = i;
        }
        ans.clear();
        string tmp_ans;
        for(int k=0; k<tmp.size()-1; k++){
            len = 0;
            tmp_ans = "";
            for(int j=0; j<tmp[k].size(); j++)
                len += tmp[k][j].length();
            int konggeshu, yushu;
            if(tmp[k].size()==1){
                tmp_ans = tmp[k][0] + string(maxWidth-tmp[k][0].length(), ' ');
            }
            else{
                konggeshu = (maxWidth-len)/(tmp[k].size()-1);
                yushu = (maxWidth-len)%(tmp[k].size()-1);
                for(int i=0; i<tmp[k].size()-1; i++){
                    tmp_ans += tmp[k][i]+string(konggeshu, ' ');
                    if(yushu>0){
                        tmp_ans += " ";
                        yushu--;
                    }
                }
                tmp_ans += tmp[k][tmp[k].size()-1];
            }
            ans.push_back(tmp_ans);
        }
        tmp_ans = tmp[tmp.size()-1][0];
        for(int i=1; i<tmp[tmp.size()-1].size(); i++)
            tmp_ans += " " + tmp[tmp.size()-1][i];
        tmp_ans += string(maxWidth-tmp_ans.length(), ' ');
        ans.push_back(tmp_ans);
        return ans;
    }
};

69、x 的平方根

直接用库函数，思考如何自己手动计算一个数的平方根。

1
2
3
4
5
6
class Solution {
public:
    int mySqrt(int x) {
        return int(sqrt(x));
    }
};

70、爬楼梯

斐波那契数列，这里使用矩阵快速幂加速。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct transferMatrix{
    long long matrix[2][2];
    transferMatrix operator*(const transferMatrix& matrix_tmp){
        transferMatrix matrix_ans;
        memset(matrix_ans.matrix, 0, sizeof(matrix_ans.matrix));
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    matrix_ans.matrix[i][j] += matrix[i][k] * matrix_tmp.matrix[k][j];
                }
            }
        }
        return matrix_ans;
    }
};
class Solution {
public:
    transferMatrix quick_pow(transferMatrix a, int n){
        transferMatrix ans;
        ans.matrix[0][0] = ans.matrix[1][1] = 1;
        ans.matrix[0][1] = ans.matrix[1][0] = 0;
        while(n){
            if(n%2)
                ans = ans*a;
            a = a*a;
            n /= 2;
        }
        return ans;
    }
    int climbStairs(int n) {
        transferMatrix ans;
        ans.matrix[0][0] = ans.matrix[0][1] = ans.matrix[1][0] = 1;
        ans.matrix[1][1] = 0;
        ans = quick_pow(ans, n);
        return ans.matrix[0][0];
    }
};
-------------本文结束感谢您的阅读-------------
您的鼓励就是我创作的动力，求打赏买面包~~
0%