虽说自己致力于搞客户端,但作为工程师的内功,算法能力必不可少,而且决定了日后的高度。拖拉许久,看了几篇文章之后,决定以 LeetCode 为平台,附以一些参考资料,边学边练。
做题的本质还是练习,一为透彻理解,二为保持状态。 LeetCode 现在有了中文版,名叫力扣,相比于牛客网等清爽很多,就做题而言功能已经很完善了,也带有比较纯粹的社交圈子。上面还有一些介绍基础知识的探索卡片,同样简洁,我就是从这里开始的。
这一道就是数组和字符串
卡片的第一道习题。
题目
寻找数组的中心索引
给定一个整数类型的数组 nums,请编写一个能够返回数组“中心索引”的方法。
我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个。
来源:力扣(LeetCode),详见👇
链接:https://leetcode-cn.com/problems/find-pivot-index
解读
这道题应该是考察对于数组操作的理解。
题目很容易懂,中心索引就是个分界符,左右两边的数字之和相等,目标就是返回它的位置。如果没有返回 -1 ,如果多个返回第一个。
限制条件里给的用例都是整数,在可以正常运算的范围内,不需要考虑大数计算。
所以当成一个数学问题 + 数组操作即可解决。
基础方法
最直接的思维,从第一个数字开始遍历,计算前后数字的和,比较是否相等。
class Solution {
public int pivotIndex(int[] nums) {
int sumA = 0, sumB = 0;
int res = -1;
// 第一个遍历,当前待验证的索引
for (int index = 0; index < nums.length ; ++index) {
// 第二个遍历,计算前后的数字之和
for (int i = 0; i < nums.length; ++i) {
if (i < index) {
sumA += nums[i];
}else if (i > index){
sumB += nums[i];
}
}
if (sumA == sumB) {
res = index;
break;
}else{
sumA = 0;
sumB = 0;
}
}
return res;
}
}
这个解法就是单纯的暴力计算了,没啥优化。因为嵌套了一个循环,所以时间复杂度为 O(n^2) 。
刚开始我把第二个遍历从下标 1 开始了,结果跑到一半失败,因为有个测试用例是这样 [0, 1, -1] ,应该返回的结果是 0 ,第一个元素左边是空的,当做和为 0 ,同样需要判断。
提交后结果如下,可见用时还是很长的:
高级方法
也是看了一下别人的思考过程 =_= 大体上是做了这么个变换:
首先左边之和 + 右边之和 + 中心索引 = 整个数组之和
sumLeft + sumRight + index = sum
中心索引两边的数字之和不是相等吗,就有了
sumLeft = sumRight
因此做个代换,就成了
2 * sumLeft = sum - index
这样只需要先算一遍数组之和,然后再累加判断即可。虽然还是两次循环,但已经不用嵌套了,时间复杂度也就从 O(n^2) 降低到了 O(n) 。除此之外,针对数组长度为 0 和 1 的情况单独做了判断。根据定义,以及两端之外当做 0 的约定,显然结果分别为不存在和第一个,即 -1 和 0。
class Solution {
public int pivotIndex(int[] nums) {
if (nums.length == 0)
return -1;
if (nums.length == 1)
return 0;
int sum = 0;
for (int i: nums){
sum += i;
}
int sumA = 0;
for (int i = 0; i < nums.length; ++i){
if (2 * sumA == sum - nums[i]){
return i;
}
sumA += nums[i];
}
return -1;
}
}
这样就快很多了,结果如下:
最后这个击败数量好像有点奇怪,我看了下时间和空间上最优解的,变化不大,而且时间上最快 1ms 那个原样提交,得到的结果跟上面还是一样。可能是早先的测试用例有所不同吧,导致这个数据有问题。这个方法的解决程度应该足够了。
结语
如果不是科班出身,算法的基础能力比较薄弱(比如目前的我),最好还是多看些参考资料。这样理解起来会更加轻松,方法得当,效率才高嘛。这道题虽然难度 easy ,笨办法可解,但通过学习就能获得更好的思路,开拓视野。练习的目的也就达到了。
值得一提的是,现在网上找东西信息量严重溢出,容易一找就沉迷一下午,然后被各种大佬打击到。所以找的喜欢的就行了,赶紧干起来为妙,哈哈。
最后推荐一个非常平易近人,传递思维的Gitbook,作者是个暴躁成都老哥🤣写的蛮好: