Search-Medium

2020-04-27
Abstract：leetcode 搜索相关题解合集

33. Search in Rotated Sorted Array

image-20200427200546326

解法一：二分查找

线性遍历就不用多说了，本题是部分有序，但是不影响使用二分查找

由于二分后，必然半边是有序的，我们就可以利用这半边作为线索来搜索

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int lo = 0, hi = nums.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.size() - 1]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
};

34. Find First and Last Position of Element in Sorted Array

image-20200430141640301

解法一：标准二分查找

标准的二分查找，只不过找到之后还要向左右再搜索一下，注意一下越界判定就行

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(nums[mid] == target){
                int i = mid, j = mid;
                while(i > 0 && nums[i - 1] == target) i--;
                while(j < nums.size() - 1 && nums[j + 1] == target) j++;
                return {i,j};
            } 
            else if(nums[mid] < target)
                lo = mid + 1;
            else if(nums[mid] > target)
                hi = mid - 1;
        }
        return {-1,-1};
    }
};

130. Surrounded Regions

image-20200504151213466

解法一：递归dfs

因为只有边缘的O不会被替换掉，因此从边缘的O开始找就行了，将边缘的O全部标记，最后再替换掉剩余的O

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;
        for (int i = 0; i < board.size(); i++){
            for (int j = 0; j < board[0].size(); j++){
                if(i == 0 || j == 0 || i == board.size() - 1 || j == board[0].size() - 1)
                    dfs(board, i, j);
            }
        }

        for(vector<char>& v : board)
            for(char& c : v)
                c = c == 'Y' ? 'O' : 'X';
    }

    void dfs(vector<vector<char>>& board, int i, int j){
        int row = board.size() - 1, col = board[0].size() - 1;
        if(i > row || i < 0 || j > col || j < 0 || board[i][j] == 'X' || board[i][j] == 'Y') return;
        board[i][j] = 'Y';
        dfs(board, i + 1, j);
        dfs(board, i, j + 1);
        dfs(board, i - 1, j);
        dfs(board, i, j - 1);
    }
};

解法二：迭代dfs

每次从队首推入

class Solution {
public:
    struct Pos{
        int x, y;
        Pos(int a, int b) : x(a), y(b) {};
    };

    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                if(i == 0 || j == 0 || i == board.size() - 1 || j == board[0].size() - 1)
                    bfs(board, i, j);

        for(vector<char>& v : board)
            for(char& c : v)
                c = c == 'Y' ? 'O' : 'X';
    }

    void bfs(vector<vector<char>>& board, int i, int j){
        int row = board.size() - 1, col = board[0].size() - 1;
        deque<Pos> q;
        q.push_front({ i, j });
        while(!q.empty()){
            Pos curr = q.front(); q.pop_front();
            i = curr.x, j = curr.y;
            if(i > row || i < 0 || j > col || j < 0 || board[i][j] == 'X' || board[i][j] == 'Y')
                continue;
            board[i][j] = 'Y';
            q.push_front({ i + 1, j });
            q.push_front({ i - 1, j });
            q.push_front({ i, j + 1 });
            q.push_front({ i, j - 1 });
        }
    }
};

解法三：迭代bfs

每次从队尾推入

class Solution {
public:
    struct Pos{
        int x, y;
        Pos(int a, int b) : x(a), y(b) {};
    };

    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[0].size(); j++)
                if(i == 0 || j == 0 || i == board.size() - 1 || j == board[0].size() - 1)
                    bfs(board, i, j);

        for(vector<char>& v : board)
            for(char& c : v)
                c = c == 'Y' ? 'O' : 'X';
    }

    void bfs(vector<vector<char>>& board, int i, int j){
        int row = board.size() - 1, col = board[0].size() - 1;
        queue<Pos> q;
        q.push({ i, j });
        while(!q.empty()){
            Pos curr = q.front(); q.pop();
            i = curr.x, j = curr.y;
            if(i > row || i < 0 || j > col || j < 0 || board[i][j] == 'X' || board[i][j] == 'Y')
                continue;
            board[i][j] = 'Y';
            q.push({ i + 1, j });
            q.push({ i - 1, j });
            q.push({ i, j + 1 });
            q.push({ i, j - 1 });
        }
    }
};

200. Number of Islands

image-20200506145713267

解法一：同上题

贴一个递归dfs

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        int res = 0, row = grid.size(), col = grid[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& grid, int i, int j) {
        if(i < 0 || j < 0 || i > grid.size() - 1 || j > grid[0].size() - 1 ||
           grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1); 
    }
};

240. Search a 2D Matrix II

image-20200507205502068

解法一：逐行二分查找

先看target在不在这行的区间，如果在就二分查找一下，直到找到，复杂度O(mlogn)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int row = matrix.size(), col = matrix[0].size();
        for(int i = 0; i < row; i++) {
            if(matrix[i][0] <= target && matrix[i][col - 1] >= target && binarySearch(matrix[i], target)) {
                return true;
            }
        }
        return false;
    }

    bool binarySearch(vector<int> row, int target) {
        int lo = 0, hi = row.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if(target == row[mid]) return true;
            else if(target < row[mid]) hi = mid - 1;
            else lo = mid + 1;
        }
        return false;
    }
};

解法二：减治法

  • 从左下角开始找，如果大了向上移动一行，小了则向右移动一列，这样不会错过target，因为只有左下角的变化是单向的，也就是不会出现两条路径上都增大或减小的情况

  • 复杂度O(m + n)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size() - 1, col = 0;
        while (row > - 1 && col < matrix[0].size()) {
            int val = matrix[row][col];
            if(val == target) 
                return true;
            else if(val < target)
                col++;
            else 
                row--; 
        }
        return false;
    }
};

153. Find Minimum in Rotated Sorted Array

image-20200510163022286

解法零：暴力法

线性遍历，太俗就不说了

解法一：二分查找

  • 因为数组被旋转了，所以查找的时候只有一边是有序的
  • 如果满足 nums[mid] > nums[mid + 1] 或 nums[mid] < nums[mid - 1]都说明边界找到了
  • 如果没找到，判断哪一边是有序的，如果 nums[mid] < nums[0]，说明当前在边界右边，要向左搜索，否则向右搜索
  • 有一种情况可能会让我们的代码越界，那就是数组没有被旋转的时候，此时会一直向右搜索直到 mid = nums.size() - 1，当我们判断 mid + 1 时就会越界，因此对于这种情况要特殊处理
class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        if(nums.size() == 1) return nums[0];
        if(nums[hi] > nums[lo]) return nums[0];
        while(lo <= hi) {
            int mid = (lo + hi) / 2;
            if(nums[mid] > nums[mid + 1])
                return nums[mid + 1];
            if(nums[mid] < nums[mid - 1])
                return nums[mid];
            if(nums[mid] > nums[0])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return -1;
    }
};

162. Find Peak Element

image-20200510180157121

解法一：暴力法

线性遍历，没想到居然95%，那就贴一下吧

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len = nums.size();
        if(len == 1 || nums[0] > nums[1]) return 0;
        if(nums[len - 1] > nums[len - 2]) return len - 1; 
        for(int i = 1; i < nums.size() - 1; i++) {
            if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
                return i;
        }
        return -1;
    }
};

解法二：二分查找

322. Coin Change

image-20200512163016773

解法一：DP

首先这题可以看作完全背包问题

如果已知amount < n的答案，那么对于amount == n，有

dp[n] = min(dp[n], dp[n - coin_j]) { coin_j < amount }

所以从0构造amount的前缀解，在通过转移方程即可求得结果

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1); // dp值最大为amount
        dp[0] = 0;
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < coins.size(); j++) {
                if(coins[j] <= i)
                    dp[i] = std::min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

解法二：贪心 + dfs

这种找零钱的题第一反应当然是要从最大的开始找

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        std::sort(coins.rbegin(), coins.rend());
        int cnt = 0;
        for(int i = 0; i < coins.size(); i++) {
            if(amount == 0) return cnt;
            if(coins[i] > amount) continue;
            int val = amount / coins[i];
            amount -= coins[i] * val;
            cnt += val;
        }
        return cnt == 0 ? -1 : cnt;
    }
};

但是直接贪心可能会导致找不出来的情况，所以要加入dfs进行搜索

int coinChange(vector<int>& coins, int amount) {
        std::sort(coins.rbegin(), coins.rend());
        int res = INT32_MAX;
        dfs(coins, amount, 0, 0, res);
        return res == INT32_MAX ? -1 : res;
    }

void dfs(vector<int>& coins, int amount, int idx, int cnt, int& res) {
        if (amount == 0) { res = std::min(cnt, res); return;}
        if (idx >= coins.size()) return;
        for(int i = amount / coins[idx]; i > -1; i--) {
            dfs(coins, amount - coins[idx] * i, idx + 1, cnt + i, res);
        }
    }

但是做到这里会超时，如果进行剪枝，结果就大大不同，只需要8ms，可能这题测试用例的特殊性，导致剪枝效果超过了DP

for(int i = amount / coins[idx]; i > -1 && i + count < res; i--) {
    dfs(coins, amount - coins[idx] * i, idx + 1, cnt + i, res);
}

// 即在for-loop条件中加入 i + count < res， 如果本次结果已经比所得的最小值大了，那么就没必要继续搜索下去了

378. Kth Smallest Element in a Sorted Matrix

image-20200517110032569

解法一：小根堆

遍历一次构造小根堆，再pop k - 1 次即可

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int, vector<int>, greater<int>> q;
        for(auto v : matrix)
            for(int i : v)
                q.push(i);
        for(int i = 0; i < k - 1; i++) q.pop();
        return q.top();
    }
};

解法二：快速选择

先转一维数组，Array里写过，相当于剪枝版的快排，但此处是局部有序的，应该考虑二分

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int len = matrix.size() * matrix[0].size();
        if(k > len) return -1;
        vector<int> nv;
        for(auto v : matrix)
            for(int i : v)
                nv.push_back(i);
        return getKth(nv, k - 1);
    }

    int getKth(vector<int>& v, int k) {
        int l = 0, r = v.size() - 1;
        while(true) {
            int idx = partition(v, l, r);
            if(idx == k) return v[idx];
            else if(idx < k) {
                l = idx + 1;
            }
            else {
                r = idx - 1;
            }
        }
    }

    int partition(vector<int>& v, int l, int r) {
        ::swap(v[l], v[rand() % (r - l + 1) + l]);
        int pivot = v[l], mid = l;
        for(int i = l + 1; i <= r; i++) {
            if(v[i] < pivot) ::swap(v[++mid], v[i]);
        }
        ::swap(v[l], v[mid]);
        return mid;
    } 

};

解法三：二分查找

  • 第k小说明在矩阵中有k - 1个小于它的数
  • 取搜索区间的中位数（可能不在矩阵内），计算矩阵中比这个中位数小的数
  • 如果结果 idx < k，也就是要继续向上搜索
  • 否则说明在包括mid在内的 [l, mid] 闭区间内
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int len = matrix.size();
        int l = matrix[0][0], r = matrix[len - 1][len - 1];
        while(l < r) {
            int mid = (l + r) >> 1;
            int idx = divide(matrix, mid);
            idx < k ? l = mid + 1 : r = mid;
        }
        return l;
    }

    int divide(vector<vector<int>>& matrix, int mid) {
        int idx = 0, last = matrix.size() - 1;
        int y = last, x = 0;
        while(y > -1 && x <= last) {
            if(matrix[y][x] <= mid) {
                idx += y + 1;
                x++;
            } else y--;
        }
        return idx;
    }

};

436. Find Right Interval

image-20200523135552024

image-20200523135602524

解法一：二分查找

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        int len = intervals.size();
        vector<int> res(len, -1);
        map<int, int> tmap;

        for(int i = 0; i < len; i++) 
            tmap[intervals[i][0]] = i;
        
        for(int i = 0; i < len; i++) {
            auto t = tmap.lower_bound(intervals[i][1]); 
            if(t != tmap.end())
                res[i] = t->second;
        }
        return res;
    }
};
© 2020 Overyam - Powered by Hexo - Theme Chan