[数据结构与算法]剑指 Offer第五天

剑指 Offer 29. 顺时针打印矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<bool>> st(n, vector<bool>(m));
        vector<int> res;
        int d = 1, x = 0, y = 0;
        for (int i = 0; i < n * m; i ++ ) {
            res.push_back(matrix[x][y]);
            st[x][y] = true;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

剑指 Offer 22. 链表中倒数第k个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        int n = 0;
        auto p = head;
        while (p) p = p->next, n ++ ;
        p = head;
        for (int i = 0; i < n - k; i ++ ) p = p->next ;
        return p;
    }
};

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

class Solution {
public:
    typedef long long LL;
    double myPow(double x, LL n) {
        if (!x) return 0;
        else if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        return quick_pow(x, n);
    }
        
        double quick_pow(double x, LL n) {
            double res = 1.0;
            while (n) {
                if (n & 1) {
                    res *= x;
                    n -- ;
                }
                else {
                    x *= x;
                    n >>= 1;
                }
            }
            return res;
        }
};

剑指 Offer 17. 打印从1到最大的n位数

class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> res;
        long long p = pow(10, n);
        for (int i = 1; i < p; i ++ ) res.push_back(i);
        return res;
    }
};

剑指 Offer 19. 正则表达式匹配

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;
        for (int i = 0; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                if (j + 1 <= m && p[j + 1] == '*') continue;
                if (i && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                }
                else if (p[j] == '*'){
                    f[i][j] = f[i][j - 2] || (i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')); 
                }
            }
        return f[n][m];
    }
};