算法分析与设计编程题 动态规划
矩阵连乘题目描述
解题代码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;
& ...
数据结构编程题 顺序表
删除最小值题目描述从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
解题代码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;
}
逆置顺序表题目描述设 ...
有关C++字符串拷贝的一个小问题
最近面试被问到了一个 C++ 中的小问题，就是如果有字符串 s1 和 s2，将 s1 赋值给 s2 后，它们的内存分布是什么样的。当时感觉可能是共享的，但也不太确定，回来后查阅资料发现结果并不是那么简单。
查阅资料首先是询问 chatGPT 得到的答案，如下：
如果两个 string 对象存储相同的字符串，它们可能会共享同一个内存块，也可能会分别分配自己的内存块。当一个 string 对象被创建时，它会分配一个新的内存块，并将字符串复制到该内存块中。当第二个 string 对象被创建时，它可能会使用与第一个 string 对象相同的内存块，也可能会分配一个新的内存块并将字符串复制到该内存块中。
代码测试看来又是一个没有标准解决方案的问题，于是我编写了一个简单的程序用来在不同的环境下测试。
void* operator new(size_t count) {
cout << "Allocate " << count << " Bytes" << endl;
return malloc(count);
}
int ...
