算法分析与设计编程题 回溯法
装载问题题目描述
解题代码递归回溯// goods[i]表示货物i的重量, c1,c2分别表示货船1和货船2的载重量
vector<vector<int>> optimalLoading(vector<int>& goods, int c1, int c2) {
int n = goods.size(); // 货物数量
int maxSum = 0; // 当前最大载货量
// curSelection[i]表示货物i是否放入货船1中（true表示放入）
vector<bool> curSelection(n, false);
// optimSelection记录maxSum对应的货物存放方式
vector<bool> optimSelection;
// 递归搜索函数
function<void(int, int)> dfs = [&](int sum, int idx) {
if (idx == n) { // 搜索达到最大深度，得到一个解
if (sum > maxS ...
算法分析与设计编程题 贪心算法
活动安排问题题目描述
解题代码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 recur ...
数据结构编程题 图
图定义邻接表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;
& ...