和为 s 的两个数
和为s的两个数
题目描述
解法一:暴力枚举
暴力枚举,先固定一个数,然后让这个数和另一个数匹配相加,
如果当前的数 + 所有剩余的数 = target,则返回这两个数,否则固定下一个数;
所以暴力枚举只需要两层 for() 即可,但是这种解法实在太慢了,题目中给的是一个有序的数组,我们要利用数组有序的特性
解法二:利用单调性
利用单调性,使用双指针算法解决问题
先固定数组的首尾元素,固定好后,让两个数相加一下,看看能否使用单调性进行优化。
先不管 target 等于多少,这两个数之和 sum 无非就是三种情况
注意:sum 指的是 left 和 right 指向的数组元素之和
- sum < target
- sum > target
- sum = target
对比暴力枚举,利用单调性,使用双指针的算法的时间复杂度得到大大的优化;
暴力枚举需要拿固定的数,和所有剩余的数相加,但是解法二只需要让固定的数相加一次即可,就能判断是否舍弃当前固定的数了
时间复杂度
解法一 O(N^2),解法二O(N)
编写代码
报错原因:
没有返回值,我们已经写了 return 语句,那么为什么编译器还会认为我们没有返回值呢?
我们必须保证所以的路径都要有返回值,而在上述代码,编译器不会管 while 语句中的 return 是否被执行,而是会考虑 只有 return 前的else 成立才会有返回值;
对于其他路径,如 else 不成立时,那么这个函数就没有返回值了,所以为了照顾编译器,强行返回一个值,就是告诉编译器一定会有返回值的:
快乐数
快乐数
题目描述
第一种情况
return true
第二种情况
这个数在定义的过程中,会进入到一个没有 1 的环中,并且无限在环中循环,始终变不到 1
return false
题目解析
可以回忆OJ题:判断链表是否有环 ;
对于一个数,经过快乐数的定义变换后,是一定会成环的,并且题目也给出了提示;
如果题目没给提示,我们就需要验证是否会出现不成环的情况;其实是一定会成环的;
证明快乐数一定成环
鸽巢原理(抽屉原理):n个巢,n+1 只鸽子,至少有一个巢,里面的鸽子数大于1
这道题的数据范围
最终,2^31 -1 的结果是一个10位整数,所以:
2^31 -1 < 999999999
快乐数转换(2^31 -1 ) < 快乐数转换(999999999)=81*10=810
所以快乐数的值的区间一定是[ 0,810 ),我们的巢穴出来了,我们随便找一个数,让他经过快乐数转换 811 次,转换的数一定是在 [ 0,810 )区间内的,在 转换 811 次之内,一定会出现重复的数,也就是一定会成环的。
所以对于这题,我们只需判断环中是否为1 ,来决定最终返回的boolean值
解法:快慢双指针
这里的指针并不是真正的指针,只是一种指针思想,在这题中,我们把变化过程中的数,抽象成指针;
- 1. 定义快慢指针;
- 2. 慢指针每次向后移动一步,快指针每次向后移动两步;
- 3. 对于判断链表是否有环,我们看的是快慢双指针最终能否相遇;
- 4. 对于快乐数,是一定会成环的,快慢双指针一定会相遇,我们只需要判断相遇点的值是否为1 ;
编写代码
因为每一次快乐数转换,都需要 求和 这个数的 每一位数 的平方,因此我们可以把这个过程封装成一个方法 bitSum() ,返回 n 这个数每一位上的平方和
盛最多水的容器
盛最多水的容器
题目解析
right - left = 两根柱子之间的格子个数 = 宽度,返回 S 即可
解法一:暴力枚举
通过两层 for 循环,先让 left 固定左边的柱子, right 依次枚举右边的柱子;一轮枚举后,让 left 固定第二根柱子;但是这种做法是超时的;
解法二:对撞指针
算法原理
首先让 left 和 right 指向 6 和 4 ;
此时如果让 right 固定的是4,让left 向内枚举那么 wide 一直减小
在让 right 固定4,left 向内枚举时,会碰到三种情况:
- height[left] < height [right];
- height[left] = height [right];
- height[left] > height [right];
对于第一种情况,此时根据木桶原理,容器的高度是减小的,所以 S 减小;
第二种情况和第三种情况,根据木桶原理,容器的高度都是不变的,但是 wide 一直在减小;
所以无论是三种情况中的哪一种,向内枚举的 V 一直都是减小的;
所以拿 min( height[left] , height [right]) * wide 得到的 S,
如果固定其中任意一个指针,向内枚举一次,发现 S 减小,那就可以大胆的 舍弃当前 left 和 right 两个指针的较小值,固定较大值。
根据上面的思想,我们可以先固定 left 指向的1,让 right 向内枚举一次,得到的 S 是在减小的,因此可以大胆的舍弃 1,让left++;
此时,我们可以尝试着把 right 指向的 7干掉,让 right--,因为如果固定 7,那拿left 向内枚举,通过木桶原理,得到的 S 一直都是在减小的;
如果当前 left 和 right 是相同的,那么舍弃谁都可以,因为根据木桶原理,向内枚举体积都是在减小的;
总结
- S 是由宽度和木桶的短板决定的,在向内枚举时,优先向内移动两个指针中,指向较小值的指针;
- 每次枚举都求出对应的 S ,直到 left 和 right 对撞,返回这几次枚举中,S 的最大值
时间复杂度
解法一 O(N^2);解法二 O(N)
编写代码
三数之和
三数之和(这个题一定一定一定要画图,空想会错很多,自己把这个题的代码写出来)
题目描述
我们根据题意,可以选出三组和为0的三元组,但是输出结果只要两组数:
所以是因为,第一组和第二组,选出的三元组,虽然顺序不一样,但是三元组的元素一样;
所以不可以包含重复三元组的意思,就是三元组的顺序不重要,只要的是两组三元组的元素不能完全一样。
这道题的难点是去重操作,我们先来想解法
解法一:先排序 + 暴力枚举 + 利用 set 去重
定义三层 for 循环,把能三个数之和等于0的,所有符合条件的三元组求出来,再对求出的组合去重;
去重操作,可以先把三元组从小到大排序,排好序之后再一 一 比对;
但是,如果在一个 length 非常大的数组中,找到了多对重复的,符合条件的三元组,那么一个一个找会非常麻烦。所以我们可以先把整个数组进行排序,然后再规定从左往右的顺序,进行所有三元组的枚举:
如果我们再一次找符合条件的三元组,就会发现找到的三元组已经是排好序的了;
比起刚刚的像刚刚没对数组排序,而是先找三元组,再对三元组排序 ;先对整个数组排序,再枚举所有三元组,更利于我们的查重操作
我们再利用 Java 中的 Set 集合,把所有得到的三元组,放入 HashSet 中,就会对数组去重,并且这是建立在排序整个数组,得到所有符合题意的三元组,才可以完美利用上 Set 的特性。
把所有三元组放入 Set 中,再把 Set 的结果拿出来作为返回值。
暴力枚举的时间复杂度:O( N^3 ),三层 for循环,去重操作针对的是有限个数的三元组,所以去重操作的时间复杂度可以忽略不记。
解法二:排序 + 双指针
用双指针,可以让时间复杂度降维,是非常优秀的算法,来看下面例子:
该数组已经排好序,利用暴力枚举时,我们是先固定一个数,然后在剩余区间中找到两个数组成符合题意的三元组
固定一个数,在剩余的数字,并且是有序的数字中,利用双指针快速找到符合题意的两个数。
处理细节问题:
去重;并且在上图的 left 和 right 区间中,有多对组合能相加凑出4,我们要把他们全部都找到;
- 不漏
- 去重
- 避免指针越界(在去重过程中会出现越界)
这三步操作是本题最重要的
否则
此时 left + right =4,此时 i,left,right拼接成第一对符合题意的三元组;但是我们还要继续这个过程,直到固定当前 i指针 的情况下,left 和 right 相遇。
所以不漏的操作,需要注意:
找到一种结果,不要让 left 和 right 停下来,继续缩小两个指针的区间 。
当然,如果在找到如上图的组合后,后面重复的 0 和 4 就不需要继续枚举了,所以我们去重,是要在找到一种结果之后,left 和 right 要跳过重复元素:
此时 i指针固定的第一个数的所有情况都已经枚举完毕,i++,此时我们发现,i指针 由指向了 -4:
又会出现重复的计算,因此我们去重要注意两个地方
- left 和 right 的去重
- 当使用完一次双指针算法之后,i 指针 也需要跳过重复元素
紧扣这两个情况,就能处理好去重操作
去重完后,我们还要处理双指针越界的情况:
通过刚刚的去重思想,来遍历上面的组合,会让双指针越界,因此我们在移动 i,left,right指针,来避免重复元素的时候,一定要处理指针越界的问题,我们结合代码,来讲解处理越界的情况。
还有一个小细节:
从煮啵写的代码来看,可以发现数据结构的基础很差~~~~
完整代码
修改: 下面i++,for循环就不要 i++了,不然会跳过要固定的下一个a
时间复杂度:O(N^2)
空间复杂度:用到了Arrays.sort(),快排,是递归产生的空间消耗,O(logN)
四数之和
四数之和
解法一:排序 + 暴力枚举 + 利用 set 去重
解法二:排序 + 双指针
- 依次固定一个数 a
- 在 a 后面的区间内,找到“三数之和”思想 得到的三个数,使这三个数的和等于 target - a 即可
- 依次固定一个数 b
- 在 b 后面的区间内,利用“双指针”找到两个数,舍得这两个数的和等于“target - a - b”即可
整体思路,两层 for 循环中套一个双指针算法,这只是整体思路,还需处理细节问题:
处理细节问题:
(1)去重:
- left 和 right 要跳过重复的数
- 利用完双指针,b要跳过重复元素
- 利用“三数之和”后,a要跳过重复元素
(2)不漏(双指针在找到一组符合条件的数时,继续缩小区间)
编写代码:
解析:在计算的时候,会有溢出的风险,也就是计算结果和预期结果不符合:
时间复杂度:O(N^3)
空间复杂度:O(logN),和三数之和的原因相同