209. Subarray with minimum length
Given an array of n positive integers and a positive integer target.
Find the array with the smallest length that satisfies the sum of the target
subarray
$ [nums_l, nums_{l+1}, ... , nums_{r-1}, nums_r] $ and returns its length. Returns 0 if no subarray exists that matches the condition.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] is the smallest subarray of length for the condition.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1,1]
Output: 0
Tip:
1 <= target <= 109
1 <= <= 105
1 <= nums[i] <= 105
discrimination
Two loops nested to enumerate the interval start position and end position respectively, enumerating all possible intervals;
It is clear that the complexity\(O(n^2)\),TLE。
Positive solution (sliding window)
We want to reduce the complexity to\(O(n)\), which means that only one loop is used;
If you use a loop to enumerate the start of the interval, it's back to violence, so you have to loop to enumerate the end of the interval;
You can think of the window as a caterpillar that continues to eat the next number if the sum of the numbers in its stomach <target;
Instead, spit out the earliest eaten count;
The process records the length of the window each time, taking min; the
Upcode (●'◡'●)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int ans=INT32_MAX,sum=0,len=0,i=0,n=();
for(int j=0;j<n;j++){//recurring enumeration window
sum+=nums[j];//stammer
while(sum>=target){//vomit
len=j-i+1;
ans=min(len,ans);
sum-=nums[i++];
}
}
return ans==INT32_MAX?0:ans;//Unsolvable situation on special leave
}
};
59. Spiral Matrix II
Given a positive integer n, generate an n x n square matrix containing all the elements from 1 to n2 with the elements spiraled in clockwise order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
Tip:
1 <= n <= 20
Positive solution (simulation)
A loop-by-loop simulation that loops the number of laps on the outside and the four edges on the inside;
Code:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int mid = n / 2,cnt = 1,len = 1,sx = 0, sy = 0,loop = n / 2;
int i,j;
while (loop --) {
i = sx;
j = sy;
for (j; j < n - len; j++) {
res[i][j] = cnt++;
}
for (i; i < n - len; i++) {
res[i][j] = cnt++;
}
for (; j > sy; j--) {
res[i][j] = cnt++;
}
for (; i > sx; i--) {
res[i][j] = cnt++;
}
sx++;
sy++;
len += 1;
}
if (n%2==1) {
res[mid][mid] = cnt;
}
return res;
}
};
interval (math.) and
Title Description
Given an array of integers, Array, calculate the sum of the elements of the array in each of the specified intervals.
Input Description
The first line of input is the length n of the integer array Array, and the next n lines, one integer per line, represent the elements of the array. Subsequent inputs are the subscripts of the intervals for which the sum is to be computed:\(a，b （b > = a）\), until the end of the document.
Output Description
Outputs the sum of the elements in each specified interval.
Input Example:
5
1
2
3
4
5
0 1
1 3
Example output.
3
9
Alerts
Scope of data:
0 < n <= 100000
Positive solutions (prefixes and)
emm...
This question is basically a prefix and template question.
Without further ado, on to the code!
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, a, b;
cin >> n;
vector<int> vec(n);
vector<int> p(n);
int presum = 0;
for (int i = 0; i < n; i++) {
cin >> vec[i];
presum += vec[i];
p[i] = presum;//prefix and
}
while (cin >> a >> b) {
int sum;
if (a == 0) sum = p[b];
else sum = p[b] - p[a - 1];//Note that it'sa-1rather thana
cout << sum << endl;
}
}
Purchase of land by developers
[Title Description]
An urban area is divided into n * m consecutive blocks, each of which has a different weight representing the value of its land. Currently, two development companies, Company A and Company B, wish to purchase land in this urban area.
Now, it is necessary to allocate all the blocks in this city region to Company A and Company B.
However, due to urban planning constraints, it is only permissible to divide the area horizontally or vertically into two subareas, and each subarea must contain one or more blocks.
To ensure a level playing field, you need to find an allocation that minimizes the difference between the total value of the land in the respective subregions of Company A and Company B. You need to find an allocation that minimizes the difference between the total value of the land in the respective subregions.
Note: Blocks may not be subdivided.
[Enter description]
The first line enters two positive integers, representing n and m. The first line enters two positive integers, representing n and m.
Each of the next n lines outputs m positive integers.
Output Description
Please output an integer representing the minimum difference between the total value of land in the two sub-regions.
[Input Example]
3 3
1 2 3
2 1 3
1 2 3
[Sample output]
0
[Reminder Message]
If the region is divided as follows:
1 2 | 3
2 1 | 3
1 2 | 3
The minimum difference between the total value of land within two subregions can be as small as zero.
[Data range]:
1 <= n, m <= 100；
n and m are not 1 at the same time.
Positive solutions (prefixes and)
In fact, it is easy to solve for the interval by first counting both horizontal and vertical single columns using prefix sums
The code is as follows:
#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];
}
}
// Statistical cross-section
vector<int> horizontal(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0 ; j < m; j++) {
horizontal[i] += vec[i][j];
}
}
// Statistical longitudinal
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;
}
time complexity\(O(n^2)\);
Although it may not seem fast, the complexity of the violence is going to be\(O(n^3)\)That's a pretty quick comparison.
It's not easy to write a blog, so please give me some support 8~!