动态前缀和数组:树状数组
前缀和的不足前缀和是一种常见的算法思想,能够实现在常数时间复杂度下得到某个子区间内所有元素和。以一维数组 nums 为例,定义前缀和数组 preSum,preSum[i] 表示 nums 前 i 个元素的和,利用动态规划的思想,易得 preSum[i] = preSum[i - 1] + nums[i] 的递推关系,因此构造一个前缀和数组的时间复杂度为 O(n),而查询前 i 个元素的和只需查询 preSum[i] 的值,为常数时间。
前缀和方法在数组元素不发生改变的情况下十分高效,但如果数组元素可能会发生改变,与朴素求和做法(不使用前缀和数组,而是直接遍历区间元素累计求和)相比,前缀和数组需要 O(n) 的时间来进行更新。这两种做法要么查询是 O(1)、更新是 O(n),要么查询是 O(n)、更新是 O(1),那有没有一种折衷的方案,使得查询和更新效率都不至于太低呢?本文将介绍的树状数组就符合这样的条件。
树状数组查询由正整数的二进制表示可知,任何一个正整数都可以拆分为为若干个不重复的 2 的幂之和。那么对于一个下标从 1 开始且长度为 n 的数组,它的任意下标 i (1 < ...
从机器指令的角度看一些位级操作
C/C++ 中有时会遇到一些位级操作,通常是一些隐式的类型转换,它们往往很难凭借高级语言层面的直觉来理解或记忆。本文旨在分析这些操作对应的汇编代码,从机器指令的角度来理解这类操作。
补码数转换为更长的无符号数int main() {
short a = -12345;
unsigned b = a;
cout << a << " " << b << endl; // -12345 4294954951
}
首先看以上这个示例,一个短整型数据(2 字节)强制类型转换为无符号整型数据(4 字节)之后,得到的值却是一个看似毫不相关的结果。
void showBytes(unsigned char* ptr, size_t sz) {
for (int i = 0; i < sz; ++i) {
printf("%.2x ", ptr[i]);
}
printf("\n");
}
首先,为了更好地分析这类位级操作,这里编写了一个简单的字节打印函数,通过将指向 ...
高效的LeetCode二叉树本地IDE调试方案
在 LeetCode 刷题过程中,有时候遇到一些难以难以直接观察出来的错误,此时通常想要利用单步调试来解决,但奈何只有 LeetCode Plus 会员才可以使用其网页的调试功能。好在绝大部分本地 IDE 都具备十分强大的调试功能,我们只需要将自己的解题代码复制到本地,并编写简单的测试程序即可。但是对于二叉树相关的题,测试数据的编写显得不那么容易,本文编写了一个匹配 LeetCode 题目中的二叉树定义的类,该类包含一些基本的静态函数,能够很方便地实现二叉树的构造和二叉树的遍历。
LeetCode 二叉树的序列表示方式LeetCode 中针对二叉树的输入数据以一个层序遍历序列的形式给出。与通常我们所说的层序序列不同的是,该层序序列包含从根节点到最后一个非空结点之间的所有空结点,该空结点以 null 的标识符给出,以此保证根据此序列所构造二叉树的唯一性(单纯依靠常规的不含空结点的层序序列无法构造一棵唯一的二叉树)。以下是一个简单的例子:
输入: root = [3, 9, 20, null, null, 15, 7]
带构造与遍历的二叉树类为了方便能在本地 IDE 中直接根据输入数 ...
二分搜索的几种写法与常见问题
最近在比赛和刷题的时候经常遇到二分答案的题,但时不时会因为一些细节上的错误而浪费时间,本文旨在整理常见的二分搜索的写法、二分搜索可能会遇到的一些小问题,以及 C++ 中与二分搜索相关的库函数,以免今后再犯类似的错误。
二分搜索的写法查找某个值的下标定义函数 binarySearch(nums, target) 为搜索有序数组 nums 中是否存在 i 使得 nums[i] == target,如果是,返回 i,否则返回 -1.
int binarySearch(vector<int>& nums, int target) {
int low = 0, high = (int)nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
high = mid ...
算法分析与设计编程题 回溯法
装载问题题目描述
解题代码递归回溯// 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 recu ...