算法第二天|209.长度最小的子数组，59.螺旋矩阵2， 区间和，开发商购买土地

209.长度最小的子数组

class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int num = nums.size(); int l = 0, ans = num + 1, sum = 0; for(int r = 0; r < num; r++){ sum += nums[r]; while(sum >= target){ ans = min(ans, r-l+1); sum -= nums[l]; l++; } } return ans <= num ? ans:0; } };

思路：滑窗，右指针循环迭代，数组内依次相加，检测到有超过target的比较最小的，减去左指针

58. 区间和

#include <iostream> #include <vector> using namespace std; int main() { int n, a, b; cin >> n; vector<int> arr(n); vector<int> ans(n); int temp = 0; for (int i = 0; i < n; i++) { cin >> arr[i]; temp += arr[i]; ans[i] = temp; } while (cin >> a >> b) { int sum; if (a == 0) sum = ans[b]; else sum = ans[b] - ans[a - 1]; cout << sum << endl; } }

思路：第一次接触到前缀和概念，在构造数组的时候，计算出区间和

59螺旋矩阵2

class Solution { int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public: vector<vector<int>> generateMatrix(int n) { vector ans(n, vector<int>(n)); int i = 0, j = 0, di = 0; for (int val = 1; val <= n * n; val++) { ans[i][j] = val; int x = i + DIRS[di][0]; int y = j + DIRS[di][1]; if (x < 0 || x >= n || y < 0 || y >= n || ans[x][y]) { di = (di + 1) % 4; } i += DIRS[di][0]; j += DIRS[di][1]; } return ans; } };

DIRS代表四个方向

开发商购买土地

#include <iostream> #include <vector> #include <climits> using namespace std; int main () { int n, m; cin >> n >> m; int sum = 0; vector<vector<int>> vec(n, vector<int>(m, 0)) ; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> vec[i][j]; sum += vec[i][j]; } } // 统计横向 vector<int> horizontal(n, 0); for (int i = 0; i < n; i++) { for (int j = 0 ; j < m; j++) { horizontal[i] += vec[i][j]; } } // 统计纵向 vector<int> vertical(m , 0); for (int j = 0; j < m; j++) { for (int i = 0 ; i < n; i++) { vertical[j] += vec[i][j]; } } int result = INT_MAX; int horizontalCut = 0; for (int i = 0 ; i < n; i++) { horizontalCut += horizontal[i]; result = min(result, abs(sum - horizontalCut - horizontalCut)); } int verticalCut = 0; for (int j = 0; j < m; j++) { verticalCut += vertical[j]; result = min(result, abs(sum - verticalCut - verticalCut)); } cout << result << endl; }