代码随想录
一. 数组的理论基础
概念：数组是存放在连续内存空间上的相同类型数据的集合
特点：（1）数组可以通过下标进行访问对应的数据并且下标是从0开始的 -> 随机访问；（2）数组内存空间的地址是连续的 -> 移动数据较为复杂
注意：
（1）使用C++的时候要注意区别 vector 和 array，vector 的底层实现是 array，但是 vector 可以实现自动扩展的容器 -> 适用于大小不确定的情况，但是 array 是适用于固定大小的情况，使用于编译期已知大小、性能要求高的场景
（2）C++中二维数组在地址空间上是连续的
Java 是没有指针的，同事也不对程序员暴露地址，由Java虚拟机来实现，是以下这种形式
二. 题目
2.1 LC704.二分查找
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() -1;while(left <= right){int mid = left + ((right - left) >> 1);if(nums[mid] < target){left = mid +1;}else if(nums[mid] > target){right = mid - 1;}else{return mid;}}return -1;}
};
2.2 LC27.移除元素
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;int fast = 0;while(fast < nums.size()){if(nums[fast] == val){fast++;}else{nums[slow] = nums[fast];slow++;fast++;}}return slow;}
};2.3 LC977.有序数组的平方
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int left = 0;int right = nums.size() -1;vector<int> ans(nums.size());int pos = nums.size() -1;while(left <= right){int leftRes = pow(nums[left], 2);int rightRes = pow(nums[right], 2);if(leftRes <= rightRes){ans[pos] = rightRes;right--;}else{ans[pos] = leftRes;left++;}pos--;}return ans;}
};2.4 LC209.长度最小的子数组
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int start = 0;int end = 0;int sum = 0;int ans = INT_MAX;while(start <= end && end < nums.size()){sum += nums[end];while(sum >= target){ans = min(ans, end - start + 1);sum -= nums[start];start++;}end++;}return ans==INT_MAX?0:ans;}
};2.5 LC59.螺旋矩阵||
class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> matrix(n, vector<int>(n));int idx = 0;int left = 0;int right = n-1;int up =0;int below = n-1;while(idx <= pow(n, 2)){for(int i = left; i <= right; i++){idx++;matrix[up][i] = idx;}if(++up > below) break;for(int i =up; i<=below;i++){idx++;matrix[i][right] = idx; }if(--right < left) break;for(int i=right;i>=left;i--){idx++;matrix[below][i] = idx;}if(--below < up) break;for(int i=below;i>=up;i--){idx++;matrix[i][left] = idx;}if(++left > right) break;}return matrix;}
};2.6 KC58.区间和
#include<iostream>
#include<vector>
using namespace std;int main(){int a, b, n;cin >> n;vector<int> arr(n);vector<int> presum(n);for(int i=0;i<n;i++){// cin >> arr[i];scanf("%d", &arr[i]);if(i == 0){presum[i] = arr[i];}else{presum[i] = presum[i-1] + arr[i];}}while(~scanf("%d%d",&a,&b)){int sum = 0;if(a == 0){sum = presum[b];}else{sum = presum[b] - presum[a-1];}printf("%d\n", sum);}
}注意：这里的 ~scanf 的写法可以记录下来
2.7 KC44.开发商购买土地
#include<iostream>
#include<vector>
#include <climits>
using namespace std;int main(){int m, n;cin >> m >> n;int sum = 0;vector<vector<int>>vec(m, vector<int>(n,0));for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin >> vec[i][j];sum += vec[i][j];}}vector<int> horizontal(m, 0);for(int i=0;i<m;i++){for(int j=0;j<n;j++){horizontal[i] += vec[i][j];}}vector<int> vertical(n, 0);for(int j=0;j<n;j++){for(int i=0;i<m;i++){vertical[j] += vec[i][j];}}int res = INT_MAX;int hdiff = 0;for(int i=0;i<m;i++){hdiff += horizontal[i];res = min(res, abs(sum - 2* hdiff));}int vdiff = 0;for(int j=0;j<n;j++){vdiff += vertical[j];res = min(res, abs(sum - 2*vdiff));}cout << res << endl;
}总结：主要用到的是双指针、滑动窗口、前缀和
