芜湖网站优化公司,2016个人做淘宝客网站,手机登录凡科网,服装网站建设目录 1、线性枚举
1#xff09;问题描述
2#xff09;动图演示
3#xff09;示例说明
4#xff09;算法描述
5#xff09;源码详解 2、前缀和差分
1#xff09;问题描述
2#xff09;动图演示
3#xff09;样例分析
4#xff09;算法描述
5#xff09;源码…目录 1、线性枚举
1问题描述
2动图演示
3示例说明
4算法描述
5源码详解 2、前缀和差分
1问题描述
2动图演示
3样例分析
4算法描述
5源码详解 3、双指针
1问题描述
2动图演示
3样例说明
4算法描述
5源码详解 4、二分枚举
1问题描述编辑
2动图演示
3样例说明
4算法描述
5源码详解 5、三分枚举
6、插入排序
1问题描述
2动图演示
3样例说明
4算法描述
5源码详解 7、选择排序
1问题描述
2动图演示
3样例说明
4算法描述
5源码详解 8、冒泡排序
1问题描述
2动图演示
3样例说明
4算法描述
5源码详解 1、线性枚举
1问题描述 2动图演示 3示例说明 蓝色的数据代表的是数组数据红色的数据代表当前枚举到的数据这样就可以遍历所有的数据进行逻辑处理了。
4算法描述 遍历数组进行条件判断条件满足则执行逻辑。这里的条件就是 枚举到的数 是否小于 当前最小值执行逻辑为 将 当前枚举到的数 赋值给 当前最小值
5源码详解
int findMin(int* nums, int numsSize){int i, min 100000;for(i 0; i numsSize; i) { // (1)if(nums[i] min) { // (2)min nums[i];}}return min; // (3)
} (1) 遍历数组中所有的数(2) 如果 当前枚举到的数 比记录的变量min小则将它赋值给min否则不做任何处理(3) 最后min中存储的就是整个数组的最小值。
2、前缀和差分
1问题描述 2动图演示 3样例分析 如上图所示只需要记录一个前缀和然后就可以通过一次减法将区间的值计算出来。时间复杂度 O(1)。这种就是差分的思想。
原理
sum[r] a[1] a[2] a[3] a[l-1] a[l] a[l 1] ...... a[r];
sum[l - 1] a[1] a[2] a[3] a[l - 1];
sum[r] - sum[l - 1] a[l] a[l 1] ...... a[r];
4算法描述 第一个枚举利用一个数组sum存储前 i 个元素的和。 第二个枚举读入 m 组数据 l,r对每组数据通过 O(1) 获取答案即sum[r] - sum[l - 1]。
5源码详解
int sum[maxn];
int* prefixSum(int* nums, int numsSize, int m, int *l, int *r){int i;int *ret;for(i 0; i numsSize; i) {sum[i] nums[i];if(i) sum[i] sum[i-1]; // (1) }ret (int *) malloc( m * sizeof(int) ); // (2) for(i 0; i m; i) {int leftsum l[i] 0 ? 0 : sum[l[i]-1]; // (3) int rightsum sum[r[i]];ret[i] rightsum - leftsum; // (4) }return ret;
} (1) 计算前缀和(2) 需要返回的数组(3) 这里是为了防止数组下标越界(4) 核心 O(1) 的差分计算
3、双指针
1问题描述 2动图演示 3样例说明 维护两个指针 i 和 j区间 [i,j] 内的子串应该时刻保持其中所有字符不重复一旦发现重复字符就需要自增 i即执行 i i 1否则执行 j j 1直到 j 不能再增加为止。 过程中记录合法情况下 j − i 1 的最大值。
4算法描述 如上文所述这种利用问题特性通过两个指针不断调整区间从而求出问题最优解的算法就叫 “尺取法”由于利用的是两个指针所以又叫 “双指针” 算法。 这里 “尺” 的含义主要还是因为这类问题最终要求解的都是连续的序列子串就好比一把尺子一样故而得名。 算法描述如下 1初始化 i 0, j i − 1代表一开始 “尺子” 的长度为 0 2增加 “尺子” 的长度即 j j 1 3判断当前这把 “尺子” [i,j] 是否满足题目给出的条件 3.a如果不满足则减小 “尺子” 长度即 i i 1回到 3 3.b如果满足记录最优解回到 2 上面这段文字描述的比较官方其实这个算法的核心只有一句话 满足条件时j不满足条件时i 如图所示当区间 [i,j] 满足条件时用蓝色表示此时 j 自增反之闪红此时 i 自增。
5源码详解
int getmaxlen(int n, char *str, int l, int r) {int ans 0, i 0, j -1, len; // 1)memset(h, 0, sizeof(h)); // 2)while (j n - 1) { // 3)h[ str[j] ]; // 4)while (h[ str[j] ] 1) { // 5)--h[ str[i] ];i;}len j - i 1; if(len ans) // 6)ans len, l i, r j;}return ans;
} 1初始化 i 0, j -1代表 s[i:j] 为一个空串从空串开始枚举2需要维护一个哈希表哈希表记录的是当前枚举的区间 s[i:j] 中每个字符的个数3只推进子串的右端点4在哈希表中记录字符的个数5当 h[ str[j] ] 1满足时代表出现了重复字符str[j]这时候左端点 i 推进直到没有重复字符为止6记录当前最优解的长度 j - i 1更新这个算法执行完毕我们就可以得到最长不重复子串的长度为 ans并且 i 和 j 这两个指针分别只自增 n 次两者自增相互独立是一个相加而非相乘的关系所以这个算法的时间复杂度为 O(n) 。
4、二分枚举
1问题描述
2动图演示 3样例说明 需要找值为 5 的这个元素。 黄色箭头代表都是左区间端点 l红色箭头代表右区间端点 r。蓝色的数据为数组数据绿色的数字代表的是数组下标初始化 l 0r 7由于数组有序则可以直接折半令 mid (lr)/23则 55 一定落入区间 [0,3]这时候令 r 3继续执行直到 l r 结束迭代。 最后当 mid 2 时找到数据 5。
4算法描述 a令初始情况下数组下标从 0 开始且数组长度为 n则定义一个区间它的左端点是 l 0右端点是 r n−1 b生成一个区间中点 mid (lr)/2并且判断 mid 对应的数组元素和给定的目标值的大小关系主要有三种 b.1目标值 等于 数组元素直接返回 mid b.2目标值 大于 数组元素则代表目标值应该出现在区间 [mid1,r]迭代左区间端点lmid1 b.3目标值 小于 数组元素则代表目标值应该出现在区间 [l,mid−1]迭代右区间端点rmid−1 c如果这时候 lr则说明没有找到目标值返回 −1否则回到 b继续迭代。
5源码详解
int search(int *nums, int numsSize, int target) {int l 0, r numsSize - 1; // (1)while(l r) { // (2)int mid (l r) 1; // (3)if(nums[mid] target) { return mid; // (4)}else if(target nums[mid]) {l mid 1; // (5)}else if(target nums[mid]) {r mid - 1; // (6)}}return -1; // (7)
} (1) 初始化区间左右端点(2) 一直迭代左右区间的端点直到 左端点 大于 右端点 结束(3) 1等价于除 2也就是这里mid代表的是l和r的中点(4) nums[mid] target表示正好找到了这个数则直接返回下标mid(5) target nums[mid]表示target这个数在区间 [1,][mid1,r] 中所以才有左区间赋值如下l mid 1;(6) target nums[mid]表示target这个数在区间 [,−1][l,mid−1] 中所以才有右区间赋值如下r mid - 1;(7) 这一步呼应了 (2)表示这不到给定的数直接返回 -1
5、三分枚举 三分枚举 类似 二分枚举 的思想也是将区间一下子砍掉一块基本完全不可能的块从而减小算法的时间复杂度。只不过 二分枚举 解决的是 单调性 问题。而 三分枚举 解决的是 极值问题。 6、插入排序
1问题描述 给定一个 n 个元素的数组数组下标从 0 开始采用「 插入排序 」将数组按照 「升序」排列。 2动图演示 3样例说明
图示含义蓝色柱形代表尚未排好序的数绿色柱形代表正在执行 比较 和 移动 的数橙色柱形代表已经排好序的数红色柱形代表待执行插入的数 我们看到首先需要将 「第二个元素」 和 「第一个元素」 进行 「比较」如果 前者 小于等于 后者则将 后者 进行向后 「移动」前者 则执行插入 然后进行第二轮「比较」即 「第三个元素」 和 「第二个元素」、「第一个元素」 进行 「比较」 直到 「前三个元素」 保持有序 。 最后经过一定轮次的「比较」 和 「移动」之后一定可以保证所有元素都是 「升序」 排列的。 4算法描述 整个算法的执行过程分以下几步 1 循环迭代变量 i1→n−1 2 每次迭代令 xa[i]ji−1循环执行比较 x 和 a[j]如果产生 x≤a[j] 则执 行 a[j1]a[j]。然后执行jj1继续执行 2否则跳出循环回到 1。 5源码详解
#include stdio.hint a[1010];void Input(int n, int *a) {for(int i 0; i n; i) {scanf(%d, a[i]);}
}void Output(int n, int *a) {for(int i 0; i n; i) {if(i)printf( );printf(%d, a[i]);}puts();
}void InsertSort(int n, int *a) { // (1)int i, j; for(i 1; i n; i) {int x a[i]; // (2)for(j i-1; j 0; --j) { // (3)if(x a[j]) { // (4)a[j1] a[j]; // (5)}elsebreak; // (6)}a[j1] x; // (7)}
} int main() {int n;while(scanf(%d, n) ! EOF) {Input(n, a);InsertSort(n, a);Output(n, a);}return 0;
} (1) void InsertSort(int n, int *a)为 插入排序 的实现代表对a[]数组进行升序排序。(2) 此时a[i]前面的 i-1个数都认为是排好序的令x a[i](3) 逆序的枚举所有的已经排好序的数(4) 如果枚举到的数a[j]比需要插入的数x大则当前数往后挪一个位置(5) 执行挪位置的 (1)O(1) 操作(6) 否则跳出循环(7) 将x插入到合适位置
7、选择排序
1问题描述 给定一个 n 个元素的数组数组下标从 00 开始采用「 选择排序 」将数组按照 「升序」排列。 2动图演示 3样例说明
图示含义蓝色柱形代表尚未排好序的数绿色柱形代表正在执行 比较 的数橙色柱形代表已经排好序的数红色柱形有两种1、记录最小元素 2、执行交换的元素 我们发现首先从 「第一个元素」 到 「最后一个元素」 中选择出一个 「最小的元素」和 「第一个元素」 进行 「交换」 然后从 「第二个元素」 到 「最后一个元素」 中选择出一个 「最小的元素」和 「第二个元素」 进行 「交换」。 最后一定可以保证所有元素都是 「升序」 排列的。 4算法描述 整个算法的执行过程分以下几步 1 循环迭代变量 i0→n−1 2 每次迭代令 miniji1 3 循环执行比较 a[j] 和 a[min]如果产生 a[j]a[min] 则执行 minj。执行 jj1继续执行这一步直到 jn 4 交换 a[i] 和 a[min]回到 1。 5源码详解
#include stdio.hint a[1010];void Input(int n, int *a) {for(int i 0; i n; i) {scanf(%d, a[i]);}
}void Output(int n, int *a) {for(int i 0; i n; i) {if(i)printf( );printf(%d, a[i]);}puts();
}void Swap(int *a, int *b) {int tmp *a;*a *b;*b tmp;
}void SelectionSort(int n, int *a) { // (1)int i, j;for(i 0; i n - 1; i) { // (2)int min i; // (3)for(j i1; j n; j) { // (4)if(a[j] a[min]) {min j; // (5)}}Swap(a[i], a[min]); // (6) }
}int main() {int n;while(scanf(%d, n) ! EOF) {Input(n, a);SelectionSort(n, a);Output(n, a);}return 0;
} (1) void SelectionSort(int n, int *a)为选择排序的实现代表对a[]数组进行升序排序。(2) 从首元素个元素开始进行 n−1 次跌迭代。(3) 首先记录min代表当前第 i 轮迭代的最小元素的下标为 i。(4) 然后迭代枚举第 i1 个元素到 最后的元素。(5) 选择一个最小的元素并且存储下标到 min中。(6) 将 第 i 个元素 和 最小的元素 进行交换。
8、冒泡排序
1问题描述 给定一个 n 个元素的数组数组下标从 0 开始采用「 冒泡排序 」将数组按照 「升序」排列。 2动图演示 3样例说明
图示含义蓝色柱形代表尚未排好序的数绿色柱形代表正在执行比较的两个数黄色柱形代表已经排好序的数 我们看到首先需要将 「第一个元素」 和 「第二个元素」 进行 「比较」如果 前者 大于 后者则进行 「交换」然后再比较 「第二个元素」 和 「第三个元素」 以此类推直到 「最大的那个元素」 被移动到 「最后的位置」 。 然后进行第二轮「比较」直到 「次大的那个元素」 被移动到 「倒数第二的位置」 。 最后经过一定轮次的「比较」 和 「交换」之后一定可以保证所有元素都是 「升序」 排列的。 4算法描述 整个算法的执行过程分以下几步 1 循环迭代变量 i0→n−1 2 每次迭代令 ji循环执行比较 a[j] 和 a[j1]如果产生 a[j]a[j1] 则交换两者的值。然后执行 jj1这时候对 j 进行判断如果 j≥n−1则回到 1否则继续执行 2。 5源码详解
#include stdio.hint a[1010];void Input(int n, int *a) {for(int i 0; i n; i) {scanf(%d, a[i]);}
}void Output(int n, int *a) {for(int i 0; i n; i) {if(i)printf( );printf(%d, a[i]);}puts();
}void Swap(int *a, int *b) {int tmp *a;*a *b;*b tmp;
}void BubbleSort(int n, int *a) { // (1)bool swapped;int last n;do {swapped false; // (2)for(int i 0; i last - 1; i) { // (3)if(a[i] a[i1]) { // (4)Swap(a[i], a[i1]); // (5)swapped true; // (6)}}--last;}while (swapped);
} int main() {int n;while(scanf(%d, n) ! EOF) {Input(n, a);BubbleSort(n, a);Output(n, a);}return 0;
} (1) void BubbleSort(int n, int *a)为冒泡排序的实现代表对a[]数组进行升序排序。(2) swapped标记本轮迭代下来是否有元素产生了交换。(3) 每次冒泡的结果会执行last的自减所以待排序的元素会越来越少。(4) 如果发现两个相邻元素产生逆序则将它们进行交换。保证右边的元素一定不比左边的小。(5) swap实现了元素的交换这里需要用转换成地址作为传参。(6) 标记更新。一旦标记更新则代表进行了交换所以下次迭代必须继续。
