题目：寻找数组的中心索引
给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
中心索引的定义如下：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回-1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
示例：
1
2
3
4
5
6
7
8
| 输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，
与右侧数之和 (5 + 6 = 11) 相等。同时, 3 也是第一个符合要求的中心索引。
输入：nums = [1, 2, 3]
输出：-1
解释：数组中不存在满足此条件的中心索引。
|
说明：
- nums 的长度范围为 [0, 10000]。
- 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
个人理解：
题目难度为简单，中心索引，就是左右和一样，首先获取总和，右边等于总和减去左边再减去当前元素。当左右相等，即为中心索引。从左向右遍历，多个索引时，可以优先获取左边的。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int pivotIndex(vector<int>& nums) {
int sum = 0,left = 0,right = 0;
for (int i = 0; i < nums.size(); i++)
sum += nums[i];
for (int i = 0; i< nums.size(); i++){
right = sum - nums[i] - left;
if(left == right){
return i;
}
left += nums[i];
}
return -1;
}
};
|
题目：搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
可以假设数组中无重复元素。
示例：
1
2
3
4
5
6
7
8
9
10
11
| 输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 2
输出: 1
输入: [1,3,5,6], 7
输出: 4
输入: [1,3,5,6], 0
输出: 0
|
个人理解：
类似于在数组中寻找一个值，以前学过的二分法应该是最好的，我采用的是暴力搜索的方法，效率低一些。
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
if(nums[nums.size() - 1] < target) return nums.size();
int index = 0;
for (int i = 0; i < nums.size(); i++){
if(nums[i] == target) index = i;
if (nums[i] < target && nums[i+1] > target){
index = i + 1;
}
}
return index;
}
};
|
题目：合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例：
1
2
3
4
5
6
7
| 输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
个人理解：
区间的话，在纸上画一画可以找到规律，先把列表中所有的区间按照左端点，由小到大进行排列，会发现更容易找到区间关系。
如果第二个区间，左端点，小于第一个区间右端点，就可以用两个区间的左端点最小的和右端点最大分别作为新区间的左右端点。
由此得出两种情况，我们先定义 merged 存储最终结果，将列表中第一个区间推入，
- 如果第二个区间的左端点，小于第一个区间右端点，那么两个区间合并
- 不小于的话，就将第二个推入，第三个与第二个比较
代码如下(C++):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() == 0) return {};
sort(intervals.begin(),intervals.end());
vector<vector<int>> merged;
for(int i = 0; i < intervals.size(); i++){
int L = intervals[i][0], R = intervals[i][1];
if(!merged.size() || merged.back()[1] < L){
merged.push_back({L,R});
}else{
merged.back()[1] = max(merged.back()[1], R);
}
}
return merged;
}
};
|
声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。
