每日算法刷题Day1 5.9:leetcode数组3道题，用时1h

1.LC寻找数组的中心索引(简单)

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

思想:

计算总和和左侧和，要让左侧和等于右侧和，即左侧和=总和-左侧和-当前数字

代码

c++代码:

class Solution {
public:int pivotIndex(vector<int>& nums) {int sum=0,leftSum=0;for(auto x:nums)    sum+=x;for(int i=0;i<nums.size();i++){if(leftSum*2+nums[i]==sum)  return i;leftSum+=nums[i];}return -1;}
};

python代码:

class Solution:def pivotIndex(self, nums: List[int]) -> int:totalSum=sum(nums) #sum是内置函数leftSum=0for i in range(len(nums)):if leftSum*2+nums[i]==totalSum:return ileftSum+=nums[i]return -1

sum是内置函数，用于对可迭代对象中所有元素求和，比如 list、tuple、set 等

相似题

1991. 找到数组的中间位置 - 力扣（LeetCode）
724. 寻找数组的中心下标 - 力扣（LeetCode）

2.LC 搜索插入位置(简单)

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
35. 搜索插入位置 - 力扣（LeetCode）

思路

二分搜索，res初始值为n(找不到插最后面)

代码

c++：

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n=nums.size();int left=0,right=n-1,res=n;while(left<=right){int mid=left+((right-left)>>1);if(nums[mid]==target)   return mid;else if(nums[mid]<target){left=mid+1;}else{right=mid-1;res=mid;}}return res;}
};

python:

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:n = len(nums)left, right, res = 0, n - 1, nwhile left <= right:mid = left + ((right - left) >> 1)if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1res = midelse:left = mid + 1return res

3.LC 合并区间(中等,学习)

56. 合并区间 - 力扣（LeetCode）

思想:

先按照区间的左端点排序，使得合并区间一定是连续的
然后再定义一个二维数组res储存结果，若res数组为空，则放入元素，若待放入元素左端点大于res数组最后一个元组右端点，则放入数组，否则出现重叠，更新res数组最后一个元素右端点

代码

c++:

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.size() == 0)return {};sort(intervals.begin(), intervals.end());vector<vector<int>> res;for (int i = 0; i < intervals.size(); ++i) {int left = intervals[i][0], right = intervals[i][1];if (!res.size() || res.back()[1] < left)res.push_back({left, right});elseres.back()[1] = max(res.back()[1], right);}return res;}
};

python:

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[0])res = []for interval in intervals:left,right=interval[0],interval[1]if not res or res[-1][1]<left:res.append(interval)else:res[-1][1]=max(res[-1][1],right)return res

1..sort(key=)方法,key传入一个函数参数
2.lambda x: x[0]匿名函数，传入x，返回x[0]
3.-1为List最后一个元素索引
4.判断res无元素:not res
5.List的append方法