力扣LeetBook数组和字符串--数组简介
写了多年算法归来仍是数组
上一次疯狂刷题还是两个月以前准备研究生机试，大学四年参加过两次蓝桥杯，之前也看过AcWing的基础课，无奈一直都是半瓶子水，学了忘，忘了学。现决定改过自新，从0开始好好刷题，争取研一暑假找到实习。
此系列用于记录在力扣刷题的心得、代码
1.寻找数组的中心索引
题目链接
思路：
- 遍历先求数组之和。
- 再次遍历求左侧之和，使用总和减去左侧之和得到右侧之和。（注意此处左侧之和是包含中间值的），所以比较时，左侧之和应当减去中间值。
代码
C++版本
class Solution {
public:int sum=0;//记录数组之和int pivot=-1;int pivotIndex(vector<int>& nums) {for(int i=0;i<nums.size();i++)sum+=nums[i];int suml=0,sumr=0;//分别记录左侧和右侧的和for(int i=0;i<nums.size();i++){suml+=nums[i];if(suml-nums[i]==sum-suml)//需要减去中间值nums[i]{pivot=i;break;}}return pivot;}
};
Python版本
class Solution:def pivotIndex(self, nums: List[int]) -> int: # 函数开始（缩进+1）total = sum(nums) # 函数体内（缩进+1）left_sum = 0pivot = -1for i in range(len(nums)): # for 循环开始（缩进+1）left_sum += nums[i] # for 循环体（缩进+1）if left_sum - nums[i] == total - left_sum: # if 开始（缩进+1）pivot = i # if 代码块（缩进+1）break # if 代码块（缩进+1）# if 结束（回到 for 缩进）# for 结束（回到函数缩进）return pivot # 函数结束（回到 class 缩进）
2.搜索插入位置
题目链接
思路：二分法。最后处理完，若找不到该元素，则left为插入的位置。
C++版本
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]>target)right=mid-1;else if(nums[mid]<target)left=mid+1;else if(nums[mid]==target)return mid;}return left;//或return right+1}
};
Python版本
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left=0right=len(nums)-1while(left<=right):mid=(left+right)//2 #py中，/是浮点数除法，//是整数除法if nums[mid]<target:left=mid+1elif nums[mid]>target:right=mid-1elif nums[mid]==target:return midreturn left
3.合并区间
题目链接
- 讲一下vector这个容器。
- vector<vector> 是 C++ 中的一种嵌套容器，可以理解为 二维动态数组或 数组的数组。它类似于 Python 中的 List[List[int]]，用于表示矩阵、表格等结构化数据。
- 初始化：
// 初始化一个 3x4 的二维数组，所有元素为 0
vector<vector<int>> matrix(3, vector<int>(4, 0));// 初始化并直接赋值
vector<vector<int>> mat = {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};
- 访问方法
// 范围for循环遍历
for (const auto& row : matrix) { // 遍历每一行for (int num : row) { // 遍历行中的每个元素cout << num << " ";}cout << endl;
}// 下标遍历
for (int i = 0; i < matrix.size(); i++) //行
{for (int j = 0; j < matrix[i].size(); j++)//列{cout << matrix[i][j] << " ";}cout << endl;
}
merged.back()是[1,3]merged.back()[0]是1（起始值）merged.back()[1]是3（结束值）
开始解题：额外开一个二维数组merge，用于存储合并后的结果。开始后先对原数组按照起点大小进行排序，把第一个数组存入merge，遍历原数组，若当前区间的起始点 <= 最后一个merge区间的结束点，说明有重叠，合并。无重叠直接加入。
c++版本。
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end());vector<vector<int>>merge;merge.push_back(intervals[0]);//加入第一个数组for(int i=0;i<intervals.size();i++)//遍历每一行{if(merge.back()[1]>=intervals[i][0])//需要合并{merge.back()[1]=max(merge.back()[1],intervals[i][1]);}else merge.push_back(intervals[i]);}return merge;}
};
Python版本。
class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()#先排序，默认按照起点由小到大merge=list()#空列表merge.append(intervals[0])for elem in intervals:#若前尾比后头大if merge[-1][1]>=elem[0]:merge[-1][1]=max(merge[-1][1],elem[1])else:merge.append(elem) #不重合就加入return merge