代碼隨想錄
一. 數組的理論基礎
概念：數組是存放在連續內存空間上的相同類型數據的集合
特點：（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;
}?總結：主要用到的是雙指針、滑動窗口、前綴和
