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

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

思路：二分查找

二分二段性，必须先将后半段重复元素删除，并特判后半段是否有元素小于第一个元素，这个时候才能对当前数组二分查找第一个小于第一个元素的下标

class Solution {
public:
    int minArray(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        while (n > 1 && nums[n - 1] == nums[0]) n -- ;
        if (nums[n - 1] > nums[0]) return nums[0]; 
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

剑指 Offer 12. 矩阵中的路径

class Solution {
public:
    int n, m;
    bool exist(vector<vector<char>>& g, string& str) {
        n = g.size(), m = g[0].size();
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ ) 
                if (dfs(g, str, i, j, 0))
                    return true;
        return false;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    bool dfs(vector<vector<char>>&g, string& str, int x, int y, int u) {
        if (str[u] != g[x][y]) return false;
        if (u == str.size() - 1) return true;
         // 可行性剪枝

        char t = g[x][y];
        g[x][y] = '#';
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m) {
                if (dfs(g, str, a, b, u + 1)) return true;
            }
        }
        g[x][y] = t;
        return false;
    }
};

剑指 Offer 05. 替换空格

class Solution {
public:
    string replaceSpace(string s) {
        string res;
        for (auto& c : s) {
            if (c == ' ') res += "%20";
            else res += c;
        }
        return res;
    }
};

剑指 Offer 13. 机器人的运动范围

class Solution {
public:
    int res = 0;
    vector<vector<bool>> st;
    int movingCount(int m, int n, int k) {
        st.resize(m, vector<bool>(n));
        dfs(0, 0, m, n, k);
        return res;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    void dfs(int x, int y, int n, int m, int k) {
        if (get(x) + get(y) > k) return ;
        // cout << x << ' ' << y <<endl;
        res ++ ;
        st[x][y] = true;
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && st[a][b] == false) {
                dfs(a, b, n, m, k);
            } 
        }
    }

    int get(int x) {
        int res = 0;
        while (x) res += x % 10, x /= 10;
        return res;
    }
};

剑指 Offer 06. 从尾到头打印链表

思路：翻转vector

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        while (head) {
            res.push_back(head->val);
            head = head->next;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

思路二：递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        if (!head) return {};
        if (!head->next) {
            res.push_back(head->val);
            return res;
        }
        auto t = reversePrint(head->next);
        res.push_back(head->val);
        return res;
    }
};