350. Intersection of two arrays II
Given two arrays, write a function to calculate their intersection. Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
explain:
The number of occurrences of each element in the output result shall be consistent with the minimum number of occurrences of elements in the two arrays.
We can ignore the order of the output results.
Original idea:
1. Select a shorter array 2 Compare the values in the short array with those in the long array and output equal values
(the problem lies in 1. How to select a shorter array is the intersect(nums2,nums1) in method 2, but I didn't expect to use the hash table to record the occurrence times of each value; 2. Thought of using two pointers to compare arrays, but didn't think of sorting)
Train of thought correction:
1. Sorting method
(1) Create two pointers I and j, pointing to the first place of the array respectively
(2) Create a temporary stack to store the result set
(3) Compare the value of the position indicated by the pointer; if the two values are different, move the small one backward; if the two values are equal, press the intersection into the stack and move the two pointers backward
(4) The end of an array traversal means that there will be no intersection between the two
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int length1=nums1.size();
int length2=nums2.size();
vector<int>result;
int p1=0,p2=0;
while(p1<length1&&p2<length2){
if(nums1[p1]<nums2[p2]){
p1++;
}else if(nums1[p1]>nums2[p2]){
p2++;
}else{
result.push_back(nums1[p1]);
p1++;
p2++;
}
}
return result;
}
};//4ms 9.7MB
The second way to write:
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(begin(nums1),end(nums1));
sort(begin(nums2),end(nums2));
int i=0,j=0,k=0;
while(i<nums1.size()&&j<nums2.size()){
if(nums1[i]<nums2[i]){
++i;//Pointer i moves back
}else if(nums1[i]>nums2[i]){
++j;//Pointer j moves back
}else{
nums1[k++]=nums1[i++];//When equal, add the number to nums1 (save space) and move the pointer back
++j;
}
}
return vector<int>(begin(nums1),begin(nums1)+k);//Returns the first k elements in nums1
}
};
2. hash table
map mapping relationship: < element, occurrence times >
//The same number may appear multiple times in both arrays -- > use the hash table to store the number of occurrences of each number
//For a number, the number of occurrences in the intersection = the minimum number of occurrences of the number in two arrays
//hash table mapping for smaller arrays
//1. Traverse the first array and record the number of occurrences of each number in the hash table
//2. Traverse the second array. If this number exists in the hash table, add it to the answer and reduce the corresponding times in the hash table
The first way to write:
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size()>nums2.size()){
return intersect(nums2,nums1); //Exchange nums2,nums1; Make nums1 the smallest array
}
//Construct the hash table of nums1
unordered_map<int,int>m;//hash table m
for(int num:nums1){ //Simplified circular writing
/*for (int i = 0; i < nums1.size();i++) {
int num = nums1[i];
*/
++m[num]; //Number of occurrences of each value in num1
}
vector<int>intersection:
for(int num:nums2){ //Traverse nums2
if(m.count(num)){
intersection.push_back(num);
--m[num]; //Reduce the corresponding element count in m, that is, the value in the hash table is reduced
if(m[num]==0){
m.erase(num);//Delete num
}
}
}
return intersection;
}
};The second way to write:
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size()>nums2.size()){
return intersect(nums2,nums1); //Exchange nums2,nums1; Make nums1 the smallest array
}
//Construct the hash table of nums1
unordered_map<int,int>m;//hash table m
for(int num:nums1){
++m[num]; //Number of occurrences of each value in num1
}
int k=0;
for(int num:nums2){ //Traverse nums2
int it=m.find(num);
if(it !=end(m)&&--it->second>=0){ //If it exists and is positive, copy it to the count of the corresponding element in nums1[k]
nums1[k++]=num;
}
}
return vector(begin(nums1),begin(nums1)+k);//Returns the first k elements in nums1
}
};121. The best time to buy and sell stocks
Given an array prices, its ith element prices[i] represents the price of a given stock on day I.
You can only choose to buy this stock one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.
Return the maximum profit you can make from this transaction. If you can't make any profit, return 0.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), the maximum profit is 6-1 = 5. (note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price; at the same time, you cannot sell the stock before buying.)
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: in this case, no transaction is completed, so the maximum profit is 0.
Tips:
1 <= prices.length <= 10 5
0 <= prices[i] <= 10 4
Original idea:
1. Determine which day to buy (the minimum value compared with the previous array); 2. Select the date with the largest difference after the buying date, that is, the selling date; 3. Output difference
(explanation: at first, I thought it was a little complicated. I thought I couldn't know the stock price of the next day on that day. Later, I read the problem solution and found that I directly traversed the array to obtain the maximum and minimum values)
Train of thought correction:
1. Violence law} is the easiest to think of, but it is overtime
Find the maximum difference between two numbers in the array
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
int ans=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
ans=max(ans,prices[j]-price[i];
}
}
return ans;
}
};2. One time traversal
1. It is assumed to be sold on day i; 2. Record the historical lowest price with the variable minprice, and the profit can be obtained.
How to record the lowest point in history -- > traverse the price array
class Solution {
public:
int maxProfit(vector<int>& prices) {
int inf=1e9;
int minprice=inf,maxprofit=0;
for(int i=0;i<prices.size();i++){
int price=prices[i]; //Suppose it is sold on day i, which is simplified as: int price:prices time: 92ms
maxprofit=max(maxprofit,price-minprice);
minprice=min(price,minprice);
}
return maxprofit;
}
};//112ms 91.1MB3. Dynamic planning
1. Determine the meaning of dp array
2.dp(i) and DP (i-1) - > state transition equation
3. Determine initial conditions, dp(0)
Solution:
1.dp[i] represents the maximum profit of the previous I days
2. State transition equation: always maximize benefits
dp[i]=max(dp[i-1],price[i]-minprice)
3.dp[0]=0
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=price.size();
if(n==0) return 0; //boundary condition
int minprice=prices[0];
vector<int>dp(n,0);
for(int i=1;i<n;i++){
minprice=min(minprice,price[i]);
dp[i]=max(dp[i-1],price[i]-minprice); //State transition equation
}
return dp[n-1];//Range index 0~n-1
}
};