题目 给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅AN],数组中有可能有重复出现的整数。 现在小明要按以下方法将其修改为没有重复整数的数组。 小明会依次修改 A2,A3,⋅⋅⋅,AN。 当修改 Ai 时,小明会检查 Ai 是否在 A1∼Ai−1 中出现过。 如果出现过,则小明会给 Ai 加上 1;如果新的 Ai...

学习来源:https://www.acwing.com/video/795/ 题目 众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。 但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。 现在小葱给了你 n 个数,希望你从这 n 个数中找到三个数,使得这三个数的和是 K 的倍数,且这个和最大。 数据保证一定有解。 输入格式 第一行包括 2 个正整数 n, K。 第二行 n...

双指针法则 双指针基本理解 双指针例题 1. 删除排序数组中的重复项 2. 移动零 3. 盛最多的水 双指针基本理解 首先什么是双指针, 双指针其中一个为快指针一个为慢指针, 慢指针顾名思义运行或者前进的速度较慢, 为什么会这样呢一定是比快指针所需满足的条件多, 因此慢指针所指的一般是过滤完的内容. 为什么要用双指针, 这里用到了典型的算法解题思维-----升维, 就是一个一维数组我把它变成二维数...

在行列都排好序的矩阵中找数 1、题目描述 给定一个有N*M的整型矩阵matrix和一个整数K,matrix的每一行和每一 列都是排好序的。实现一个函数,判断K是否在matrix中。 【要求】 时间复杂度为O(N+M),额外空间复杂度为O(1)。 2、思路。 这里从数据状况来思考。由于数据每一行和列都是排好序的。 每一次先判断右上角的数a,如果是小于就说明a下面的数不可能。 ​ 便往左移动,到达b的...

二分法及相关例题

算法学习  算法

  

2020-05-18 11:42:55

1. 实现折半查找 样例输入1 3 1 1 4 6 4 样例输出1 2 样例输入2 5 2 1 4 6 7 8 5 1 样例输出2 0 1 2. 是否可以求和 样例输入1 5 1 2 3 4 5 -1 4 样例输出1 Yes 3. 两数之和 样例输入1 5 1 2 3 4 5 4 样例输出1 Yes 样例输入2 5 1 2 4 4 5 4 样例输出2 No 4.报数游戏 样例输入1 5 5 1 5...

分治思想-选pivot问题

算法学习  算法

  

2020-05-21 06:14:44

前言 选择的pivot会影响比较次数。为了进一步理解如何选pivot,我们从找出数组中第k小的数问题入手来理解。 例子:寻找第k小的元素 问题叙述 给定一个乱序数组A,试求该数组中第k小的元素? 最直接的解决办法就是数组排序返回index为k-1的元素,排序选用快排或归并(若不考虑内存使用),时间复杂度是O(nlogn)。 思考一下,实际上这个问题没有必要将数组完全排序再找第k个元素。 解决思路 ...

掌握并归排序 AcWing787 并归排序 AcWing788 逆序对的数量 目录 并归排序 并归排序的应用-逆序对的数量 并归排序 并归排序的核心思想是分治 分界点 递归左右 并归 分到不可再分后、合起来就是排序好的了 并归排序的应用-逆序对的数量 什么是逆序对? 那么如何利用并归快速求解逆序对问题呢? 首先并归有个步骤是拆成两半,假设我们的并归算法可以返回逆序对 在归并中 左半边的逆序对 me...

基本算法——差分

算法学习  算法

  

2020-05-24 08:12:00

文章目录 一维差分 题解 模板 二维差分 题解 模板 目标,掌握差分的概念、和解题的思路 差分就是前缀和的逆过程!!! 一维差分 什么是一维差分? 那么差分可以用来干嘛呢? 让我们来看这样一个操作 通过差分,我们可以快速对前缀和数组的一个区间的数进去操作 再思考,如何构建差分呢??需要构建嘛 题目 输入一个长度为n的整数序列。 接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[...

基本算法——前缀和

算法学习  算法

  

2020-05-24 11:35:00

文章目录 一维前缀和 题解 模板 二维前缀和 题解 模板 AcWing795 前缀和 AcWing796 二维矩阵的和 一维前缀和 前缀和的概念: 题目: 输入一个长度为n的整数序列。 接下来再输入m个询问,每个询问输入一对l, r。 对于每个询问,输出原序列中从第l个数到第r个数的和。 题解 看到求区间和、就可以用到前缀和 思路:前缀和数组的构建,利用前缀和性质快速求解区间和 所以解题的步骤一般...

基本算法——二分法

算法学习  算法

  

2020-05-24 21:42:13

文章目录 整数二分 题解 模板 浮点二分 题解 目标:掌握整数二分和浮点二分,了解二分的思想 AcWing789 数的范围 整数二分 AcWing790 数的三次方根 浮点二分 这里我要反思之前写的两篇博客,感觉内容上自己思考的太少、而且细节上确实很多点没有讲到 以后会经量把自己的思路也加上去、希望大家能看的更加明白 整数二分 题目: 给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。 ...

文章目录 kmp字符串 题解 模板 kmp字符串 kmp是一种高效存储字符串匹配的算法 简单来说就是给定一个模式(母)串S,以及一个模板(子)串P 求出模板(子)串P在模式(母)串S中所有出现的位置的起始下标。 当然你也可以暴力的去做,但是不如看看kmp的想法吧 遇到两个字符不匹配的情况时,希望可以多跳几个字符,减少比较次数 KMP算法的思想是: 在模式串和主串匹配过程中,当遇到不匹配的字符时,对...

数据结构——单调栈

算法学习  算法

  

2020-05-31 14:07:19

文章目录 单调栈 题解 单调栈 单调栈可以用来优化 最常用的情景:给定一个序列,找到序列每一个数左边离它最近且比他小的数 题目 给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。 3 4 2 7 5 -1 3 -1 2 2 结论:我们用栈存储一列升序的数,取栈顶即可,当添加一个数时,也必须保证升序,将比他大的删除,即tt– 题解 模板 大家可以根据模板自...