算法分析与设计编程题 贪心算法
活动安排问题题目描述
解题代码vector<bool> greedySelector(vector<vector<int>>& intervals) {
int n = intervals.size();
// 将活动区间按结束时间的从小到大排序
auto cmp = [](vector<int>& interval1, vector<int>& interval2) {
return interval1[1] < interval2[1];
};
sort(intervals.begin(), intervals.end(), cmp);
vector<bool> res(n, false);
// 结束时间最早的活动必定位于某个最优解之中
int minStart = intervals[0][1];
res[0] = true;
for (int i = 1; i < n; ++i) ...
算法分析与设计编程题 动态规划
矩阵连乘题目描述
解题代码void printOptimalParens(vector<vector<int>>& partition, int i, int j) {
if (i == j) cout << "A" << i; // 单个矩阵，无需划分
else {
cout << "(";
printOptimalParens(partition, i, partition[i][j]);
printOptimalParens(partition, partition[i][j] + 1, j);
cout << ")";
}
}
// nums[i]: nums[0]为矩阵A1的行数，nums[i](i >= 1)表示矩阵Ai的列数
// 如输入为 nums = { 30,35,15,5,10,20,25 }，代表矩阵行列数如下：
// A1: 30 * 35, A2: 35 * 15, A3: 15 * 5, A4: 5 * ...
算法分析与设计编程题 递归与分治策略
棋盘覆盖题目描述
解题代码// 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 < ...
常见排序算法
插入排序直接插入void insertSort(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
int j = i;
while (j >= 1 && nums[j] < nums[j - 1]) {
swap(nums[j], nums[j - 1]);
--j;
}
}
}
折半插入void binaryInsertSort(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
int key = nums[i];
int low = 0, high = i - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] >= key) { ...
数据结构编程题 查找
二叉树定义以下为本文解题代码的二叉树定义。
struct TreeNode {
int val;
TreeNode* left, *right;
TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr)
: val(val), left(left), right(right) {}
};
递归二分查找题目描述写出二分查找的递归算法。初始调用时，left 为1，right 为 n.
解题代码bool recurBS(vector<int>& nums, int target, int left, int right) {
if (left > right) return false;
int mid = (left + right) / 2;
if (nums[mid] == target) return true;
else if (nums[mid] > target) {
return recu ...
数据结构编程题 图
图定义邻接表struct ArcNode { // 边结点
int verIdx, weight;
ArcNode* next;
ArcNode(int verIdx, int weight, ArcNode* next) : verIdx(verIdx), weight(weight), next(next) {}
};
struct VNode { // 顶点结点
char vertex;
ArcNode* first;
};
struct AlGraph {
vector<VNode> VNodes;
};
邻接矩阵struct MGraph {
vector<char> vertices; // 顶点集
vector<vector<int>> edges; // 邻接矩阵
};
邻接表转邻接矩阵题目描述写出从图的邻接表转化为邻接矩阵的算法。
解题代码MGraph adjList2Matrix(AlGraph& AG) ...
数据结构编程题 二叉树
二叉树定义以下为本文解题代码的二叉树定义。
struct TreeNode {
int val;
TreeNode* left, *right;
TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr)
: val(val), left(left), right(right) {}
};
非递归先序遍历题目描述编写先序遍历二叉树的非递归算法。
解题代码void nonRecurPre(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s;
while (root != nullptr || !s.empty()) {
if (root != nullptr) {
cout << root->val << " ";
s.emplace(root);
root = root->left ...
数据结构编程题 栈和队列
判断合法序列题目描述假设 I 和 O 分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。编写一个算法，判定所给的序列是否合法。若合法，返回 true，否则返回 false.
解题代码bool isLegalSequence(const string& sequence) {
int iCnt = 0;
for (int i = 0; i < sequence.size(); ++i) {
if (sequence[i] == 'I') {
++iCnt;
}
else {
--iCnt;
}
if (iCnt < 0) {
return false;
}
}
return iCnt ...
数据结构编程题 链表
链表定义以下为本文解题代码的链表定义。
struct ListNode {
int val;
ListNode* next;
ListNode(int val = 0, ListNode* next = nullptr) : val(val), next(next) {}
};
递归删除结点题目描述设计一个递归算法，删除不带头结点的单链表 L 中的所有值为 x 的结点，并返回新的链表头节点。
解题代码ListNode* deleteNodeRecur(ListNode* head, int x) {
if (head == nullptr) return head;
head->next = deleteNodeRecur(head->next, x);
if (head->val == x) {
ListNode* nextNode = head->next;
delete head;
return nextNode;
...
数据结构编程题 顺序表
删除最小值题目描述从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
解题代码bool deleteMin(vector<int>& nums, int& val) {
if (nums.empty()) {
return false;
}
int minVal = INT32_MAX, minIdx = 0;
for (int i = 0; i < nums.size(); ++i) {
if (minVal > nums[i]) {
minVal = nums[i];
minIdx = i;
}
}
nums[minIdx] = nums.back();
val = minVal;
return true;
}
逆置顺序表题目描述 ...
