寻找数组的中心索引
给定一个整数类型的数组 nums
,请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个。
示例 1:
输入:
nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11),与右侧数之和 (5 + 6 = 11) 相等。
同时, 3 也是第一个符合要求的中心索引。示例 2:
输入:
nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心索引。说明:
nums
的长度范围为[0, 10000]
。
任何一个nums[i]
将会是一个范围在[-1000, 1000]
的整数。作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/array-and-string/yf47s/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
思路
似乎无可避免的要先遍历几乎整个数组得到右边的元素和,然后从第一个元素向右依次按条件查找中心索引。其中两边的元素和只需在每次循环内与当前元素和下一个元素做运算即可,这里应该还可以把右边元素和放到下一次循环if语句前执行,不清楚会不会影响性能。
class Solution {
public:
int pivotIndex(vector<int>& nums) {
if(nums.size()>1){
int sl=0, sr=0;
for(int i=1; i<nums.size(); i++)
sr += nums[i];
for(int j=0; j<nums.size(); j++){
if(sl == sr)
return j;
sl += nums[j];
sr -= nums[j+1];
}
}
return -1;
}
};
44ms 30.7MB
迷惑:题解里的有一位1ms 39.1MB的Java代码
我感觉和我写的差不多啊,都是C艹的锅
class Solution {
public int pivotIndex(int[] nums) {
if(nums.length <= 2) {
return -1;
}
int leftSum = 0;
int middleIndex = 0;
int rightSum = 0;
for (int i = 1; i < nums.length; i++) {
rightSum += nums[i];
}
while(middleIndex != nums.length - 1 && leftSum != rightSum) {
leftSum += nums[middleIndex];
rightSum -= nums[middleIndex + 1];
middleIndex++;
}
if(leftSum == rightSum) {
return middleIndex;
}else {
return -1;
}
}
}
作者:bobby996
链接:https://leetcode-cn.com/problems/find-pivot-index/solution/10000-9054-by-bobby996/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2示例 2:
输入: [1,3,5,6], 2
输出: 1示例 3:
输入: [1,3,5,6], 7
输出: 4示例 4:
输入: [1,3,5,6], 0
输出: 0作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/array-and-string/cxqdh/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
二分查找,冲!
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
//看到题解里的一行STL气自己不会T T
int left = 0;
int right = nums.size();
int mid = 0;
while(left < right){
mid = left + (right - left)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid;
}
return left;
}
};
//8ms 10MB
合并区间
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。提示:
intervals[i][0] <= intervals[i][1]作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/array-and-string/c5tv3/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
思路
这里当时想的是先将vector内的元素按区间左端排序,然后使用双指针处理当前区间和下一区间。但是手撸快速排序失败了,不熟悉迭代器的变量类型与指针的区别,搞得很混乱。不幸中的万幸是从题解里看到了有思路一样的,聊以自慰。
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (int i = 0; i < intervals.size();) {
int t = intervals[i][1];
int j = i + 1;
while (j < intervals.size() && intervals[j][0] <= t) {
t = max(t, intervals[j][1]);
j++;
}
ans.push_back({ intervals[i][0], t });
i = j;
}
return ans;
}
作者:ikaruga
链接:https://leetcode-cn.com/problems/merge-intervals/solution/merge-intervals-by-ikaruga/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。