算法分析与设计编程题 递归与分治策略

棋盘覆盖

题目描述

解题代码

// para: 棋盘，行偏移，列偏移，特殊行，特殊列
void dividedCovering(vector<vector<int>>& chessBoard, int dr, int dc, int sr, int sc, int size) {if (size == 1) return;size /= 2; // 划分为四部分if (sr < dr + size && sc < dc + size) { // 特殊点位于左上部分divideCovering(chessBoard, dr, dc, sr, sc, size);}else {int nr = dr + size - 1, nc = dc + size - 1; // 新覆盖点chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr, dc, nr, nc, size);}if (sr < dr + size && sc >= dc + size) { // 特殊点位于右上部分divideCovering(chessBoard, dr, dc + size, sr, sc, size);}else {int nr = dr + size - 1, nc = dc + size;chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr, dc + size, nr, nc, size);}if (sr >= dr + size && sc < dc + size) { // 特殊点位于左下部分divideCovering(chessBoard, dr + size, dc, sr, sc, size);}else {int nr = dr + size, nc = dc + size - 1;chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr + size, dc, nr, nc, size);}if (sr >= dr + size && sc >= dc + size) { // 特殊点位于右下部分divideCovering(chessBoard, dr + size, dc + size, sr, sc, size);}else {int nr = dr + size, nc = dc + size;chessBoard[nr][nc] = 1;divideCovering(chessBoard, dr + size, dc + size, nr, nc, size);}
}void chessBoardCovering(vector<vector<int>>& chessBoard, int sr, int sc) {int n = chessBoard.size();divideCovering(chessBoard, 0, 0, sr, sc, n);
}

线性时间选择

题目描述

解题代码

int partition(vector<int>& nums, int left, int right) {int randIdx = rand() % (right - left + 1) + left; // 选取随机pivotswap(randIdx, nums[left]);int pivot = nums[left];while (left < right) {while (left < right && nums[right] >= pivot) --right;nums[left] = nums[right];while (left < right && nums[left] <= pivot) ++left;nums[right] = nums[left];}nums[left] = pivot;return left;
}int dividedQuickSelect(vector<int>& nums, int left, int right, int k) {if (left >= right) return nums[left];int p = partition(nums, left, right); // 根据基准进行划分if (p == k) return nums[p]; // 划分基准正好为第k小的数else if (p > k) return divideQuickSelect(nums, left, p - 1, k); // 基准大于第k小else return divideQuickSelect(nums, p + 1, right, k); // 基准小于第k小
}int quickSelect(vector<int>& nums, int k) {srand((unsigned)time(nullptr)); // 设定随机种子return divideQuickSelect(nums, 0, nums.size() - 1, k - 1);
}