【leetcode刷题】剑指 Offer（第 2 版）

1、剑指 Offer 03. 数组中重复的数字

leetcode

因为数字范围是0-n-1，可以用下标来记录数字。

class Solution {
   
public:
    int findRepeatNumber(vector<int>& nums) {
   
        int i=0;
        while(i<nums.size())
        {
   
            if(nums[i]==i)
            {
   
                i++;
                continue;
            }
            if(nums[nums[i]]==nums[i])    // 之前nums[i]已经放着i，此时又出现，说明重复
            {
   
                return nums[i];
            }
            swap(nums[i], nums[nums[i]]);
        }
        return -1;
    }
};
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

2、剑指 Offer 04. 二维数组中的查找

leetcode

这里不能从左上角开始找，因为向右和向下都是递增，无法判断下一步该向左还是向右。
而从右上角开始，向左会减小，向右会变大，可以通过和target大小比较来判断下一步。

时间复杂度 O(M+N)

class Solution {
   
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
   
        int m = matrix.size();
        if(m==0)
        {
   
            return false;
        }
        int n = matrix[0].size();
        int i=0, j=n-1;
        while(i<m && j>=0)
        {
   
            if(matrix[i][j]==target)
            {
   
                return true;
            }else if(target<matrix[i][j])    // 往左是变小
            {
   
                j--;
            }else if(target > matrix[i][j])   // 往右边是变大
            {
   
                i++;
            }
        }

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

3、剑指 Offer 10- I. 斐波那契数列

leetcode

class Solution {
   
public:
    int fib(int n) {
   
        int MOD = 1000000007;
        if (n < 2) {
   
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
   
            p = q; 
            q = r; 
            r = (p + q)%MOD;
        }
        return r;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、剑指 Offer 11. 旋转数组的最小数字

leetcode

class Solution {
   
public:
    int minArray(vector<int>& numbers) {
   
        int l = 0, r = numbers.size()-1;
        while(l<r)
        {
   
            int mid = l + (r - l) / 2;
            if(numbers[mid]<numbers[r])
            {
      
                r=mid;
            }else if(numbers[mid] > numbers[r]){
   
                l = mid+1;
            }else if(numbers[mid]==numbers[r]){
   
                r--;
            }
        }
        return numbers[l];
    }
};
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

5、剑指 Offer 12. 矩阵中的路径

leetcode

class Solution {
   
public:
    bool ans = false;
    int X[4] = {
   -1, 1, 0, 0};
    int Y[4] = {
   0, 0, -1, 1};
    vector<vector<int>> vis;
    void dfs(vector<vector<char>>& board, string word, int x, int y, int idx)
    {
   
        int m = board.size();
        int n = board[0].size();
        if(idx>word.size())
        {
   
            return;
        }
        if(idx==word.size())
        {
   
            ans = true;
            return;
        }
        for(int i=0;i<4;i++)
        {
   
            int newX = x+X[i];
            int newY = y+Y[i];
            if(newX>=0&&newX<m && newY>=0&&newY<n)
            {
   
                if(vis[newX][newY]==0 && board[newX][newY]==word[idx])
                {
   
                    vis[newX][newY]=1;
                    dfs(board, word, newX, newY, idx+1);
                    vis[newX][newY]=0;
                }
            }
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
   
        int m = board.size();
        int n = board[0].size();
        for(int i=0;i<m;i++)
        {
   
            for(int j=0;j<n;j++)
            {
   
                if(board[i][j]==word[0])
                {
   
                    vis = vector<vector<int> > (m, vector<int>(n, 0));
                    vis[i][j]=1;
                    dfs(board, word, i, j, 1);
                    if(ans)
                    {
   
                        return ans;
                    }
                }
            }
        }
        return false;

    }
};
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

6、剑指 Offer 14- I. 剪绳子

leetcode

class Solution {
   
public:
    int cuttingRope(int n) {
   
        if(n==1 || n==2)
        {
   
            return 1;
        }
        if(n==3)
        {
   
            return 2;
        }
        if(n%3==0)
        {
   
            int m = n/3;
            return pow(3, m);
        }else if(n%3==1)
        {
   
            int num = n/3;
            int res = 1;
            return pow(3, num-1) * 4;
        }else if(n%3==2)
        {
   
            int num = n/3;
            int res = n - num *3;
            return pow(3, num) * res;
        }
        return -1;
    }
};
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

7、剑指 Offer 14- II. 剪绳子 II

leetcode

class Solution {
   
public:
    int cuttingRope(int n) {
   
        if(n <= 3) 
            return n - 1;
        int b = n % 3, p = 1000000007;
        long ret = 1;
        int lineNums=n/3;           //线段被我们分成以3为大小的小线段个数
        for(int i=1;i<lineNums;i++) //从第一段线段开始验算，3的ret次方是否越界。注意是验算lineNums-1次。
            ret = 3*ret % p;
        if(b == 0) 
            return (int)(ret * 3 % p);   //刚好被3整数的，要算上前一段
        if(b == 1) 
            return (int)(ret * 4 % p);   //被3整数余1的，要算上前一段

        return (int)(ret * 6 % p);       //被3整数余2的，要算上前一段
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8、剑指 Offer 16. 数值的整数次方

leetcode

快速幂

class Solution {
   
public:
    double myPow(double x, int n) {
   
        if(n==0)
        {
   
            return 1;
        }else if(n==1)
        {
   
            return x;
        }else if(n==-1)
        {
   
            return 1/x;
        }
        long e = n;
        if(e<0)
        {
   
            e = abs(e);
            x = 1/x;
        }
        double res=1;
        while(e!=0)
        {
   
            int b = e%2;
            if(b==0)
            {
   
                res*=
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