当前位置：网站首页>Learning summary on June 29, 2022
Learning summary on June 29, 2022
2022-07-01 11:22:00 【Ls really can't】
One 、15. Sum of three numbers - Power button （LeetCode）
Title Description
Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .
Be careful ： Answer cannot contain duplicate triples .
Example 1：
Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]
Example 2：Input ：nums = []
Output ：[]
Example 3：Input ：nums = [0]
Output ：[]
Tips ：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
Ideas
In limine , Using violence to solve problems , The time complexity is O(n^3), Overtime .
Double pointers are used later , The left pointer points to nums[] The... In the array i The next number after the number , The right pointer points to nums[] The last number of the array . Through the movement of the double pointer , Look for and num[] No i The sum of the numbers equals 0 Number of numbers .
Code implementation
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> a;
if(nums.size()<3)// Array nums The length of is less than 3, It cannot form the sum of three numbers
{
return {};
}
/*for(int i=0;i<nums.size();i++)// An array nums After arranging the order , It is more conducive to judge whether the sum of the three numbers is repeated
{
for(int j=0;j<nums.size();j++)
{
if(nums[i]<nums[j])
{
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
}*/
sort(nums.begin(),nums.end());
if(nums[0]>0||nums[nums.size()-1]<0)// After ordering , The first number is greater than 0, The last number is less than 0, It is impossible to form a sum of three numbers equal to 0
{
return {};
}
for(int i=0;i<nums.size();i++)
{
if(nums[i]>0)// After ordering , The first number of three numbers is greater than 0, The sum of those three numbers must be greater than 0
{
return a;
}
if(i>0&&nums[i]==nums[i-1])// The first number of three numbers is the same as its previous number , Eliminate repetition
{
continue;
}
int l=i+1;
int r=nums.size()-1;
while(l<r)
{
if(nums[l]+nums[r]+nums[i]==0)
{
a.push_back(vector<int>{nums[i],nums[l],nums[r]});
while(l<r&&nums[l]==nums[l+1])// Remove duplicate elements
{
l++;
}
while(l<r&&nums[r]==nums[r-1])// Remove duplicate elements
{
r--;
}
/*if(nums[l]!=nums[l+1]&&nums[r]!=nums[r-1])
{
l++;
r--;
}*/
l++;
r--;
}
else if(nums[l]+nums[r]+nums[i]<0)
{
l++;
}
else
{
r--;
}
}
}
return a;
}
};Two 、912. Sort array - Power button （LeetCode）
Title Description
Give you an array of integers nums, Please arrange the array in ascending order .
Example 1：
Input ：nums = [5,2,3,1]
Output ：[1,2,3,5]
Example 2：Input ：nums = [5,1,1,2,0,0]
Output ：[0,0,1,1,2,5]
Tips ：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
Ideas
Directly use the quick sort algorithm .
Code implementation
class Solution {
public void quickSort(int[] nums, int l, int r)
{
if(l>r)
{
return;
}
int left=l;
int right=r;
int sign=nums[left];
while(left<right)
{
while(left<right&&nums[right]>=sign)
{
right--;
}
if(nums[right]<sign)
{
nums[left]=nums[right];
}
while(left<right&&nums[left]<=sign)
{
left++;
}
if(nums[left]>sign)
{
nums[right]=nums[left];
}
if(left>=right)
{
nums[right]=sign;
}
}
quickSort(nums,l,right-1);
quickSort(nums,left+1,r);
}
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
}3、 ... and 、21. Merge two ordered lists - Power button （LeetCode）
Title Description
Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists .
Example 1：
Input ：l1 = [1,2,4], l2 = [1,3,4]
Output ：[1,1,2,3,4,4]
Example 2：Input ：l1 = [], l2 = []
Output ：[]
Example 3：Input ：l1 = [], l2 = [0]
Output ：[0]
Tips ：
The range of the number of nodes in the two linked lists is [0, 50]
-100 <= Node.val <= 100
l1 and l2 All according to Non decreasing order array
Ideas ：
First, determine that the head node of the synthetic linked list is list1 The head node of is still list2 Head node of , And then traverse at the same time list1、list2 Two lists , Finally, there must be a linked list that is not empty , Then connect the remaining elements of the non empty linked list directly after the synthetic linked list .
Code implementation
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
ListNode* head;
ListNode* p;
if(list1->val>=list2->val)
{
head=list2;
list2=list2->next;
}
else
{
head=list1;
list1=list1->next;
}
p=head;
while(list1!=NULL&&list2!=NULL)
{
if(list1->val<=list2->val)
{
p->next=list1;
p=p->next;
list1=list1->next;
}
else
{
p->next=list2;
p=p->next;
list2=list2->next;
}
}
while(list1!=NULL)
{
p->next=list1;
p=p->next;
list1=list1->next;
}
while(list2!=NULL)
{
p->next=list2;
p=p->next;
list2=list2->next;
}
/*if(list1!=NULL)// Two while You can also use these two if Replace
{
p->next=list1;
}
if(list2!=NULL)
{
p->next=list2;
}*/
return head;
}
};Four 、P1540 [NOIP2010 Improvement group ] Machine translation - Luogu | New ecology of computer science education (luogu.com.cn)
Background
Xiaochen has a machine translation software installed on his computer , He often uses this software to translate English articles .
Title Description
The principle of this translation software is very simple , It's just from beginning to end , Replace each English word with the corresponding Chinese meaning in turn . For every English word , The software will first look up the Chinese meaning of the word in memory , If there is , The software will use it to translate ; If not in memory , The software will look it up in the dictionary in external memory , Find out the Chinese meaning of the word and translate , And put the word and its translation into memory , For subsequent search and translation .
Suppose there's... In memory M A unit , Each unit can store a word and its translation . Whenever the software stores a new word in memory , If the number of stored words in the current memory does not exceed M-1, The software will store the new word in an unused memory unit ; If it's stored in memory M Word , The software will clear the word that first entered the memory , Free up units , Store new words .
Suppose that the length of an English article is N Word . Given this article to be translated , How many times does the translation software need to look up the dictionary in external memory ？ Suppose before the translation begins , There are no words in memory .
Input format
common 2 That's ok . Separate two numbers in each line with a space .
The first line is two positive integers M,N Represents the memory capacity and the length of the article .
Second behavior N Nonnegative integers , In the order of the articles , Number of each （ Not larger than 1000） Represents an English word . The two words in the article are the same word , If and only if their corresponding nonnegative integers are the same .
Output format
An integer , For the number of times the software needs to look up a dictionary .
I/o sample
Input
3 7 1 2 1 5 4 4 1Output
5explain / Tips
Sample explanation
The whole process of looking up a dictionary is as follows ： Each line represents the translation of a word , Before the colon is the memory condition after the translation ：
1： Find words 1 And call into memory .1 2： Find words 2 And call into memory .1 2： Find words in memory 1.1 2 5： Find words 5 And call into memory .2 5 4： Find words 4 And call in memory to replace the word 1.2 5 4： Find words in memory 4.5 4 1： Find words 1 And call in memory to replace the word 2.I checked 5 Sub dictionary .
Data range
- about 10% Data are available. M=1,N≤5;
- about 100% Data are available. 1001≤M≤100,1≤N≤1000.
Ideas
Title “ If it's stored in memory MM Word , The software will clear the word that first entered the memory , Free up units , Store new words ”, Is similar to queue “ fifo ” The nature of , So use queues to store words in memory . Also, you need to query whether there is this word in memory ,map The key value in is unique , So at the same time map Store words in memory . There are comments in the detailed thinking code .
Code implementation
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n,a[1001],head=0,tail=0,b[1001];// Array a Is to store the content of the article , Then there is a sequential queue
scanf("%d %d",&m,&n);
map<int,int> mp;//STL
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
int sum=0,cnt=0;//sum Indicates used memory ,cnt Indicates the number of times to look up the dictionary
for(int i=0; i<n; i++)
{
if(mp.count(a[i])==0)//mp Without this element
{
cnt++;// The word is not in memory , The number of dictionary searches has increased
if(sum<m)// Memory capacity is not full
{
mp.insert(pair<int,int>(a[i],a[i]));// Insert directly into mp in
b[tail++]=a[i];// Join the team directly
sum++;// Memory capacity increases
}
else// Memory capacity is full , Remove the queue header element from the queue
{
mp.erase(b[head]);// from mp Delete the team head element
head++;// Out of the team
mp.insert(pair<int,int>(a[i],a[i]));//map Insert new elements in
b[tail++]=a[i];// The team
// The memory capacity is always full , So there is no need to change
}
}
}
printf("%d",cnt);
return 0;
}5、 ... and 、P1886 The sliding window /【 Templates 】 A monotonous queue - Luogu | New ecology of computer science education (luogu.com.cn)
Title Description
There's a long one for n Sequence a, And a size of k The window of . Now this one slides from the left to the right , Slide one unit at a time , Find the maximum and minimum values in the window after each slide .
for example ：
The array is [1,3,-1,-3,5,3,6,7], and k = 3.
Input format
There are two lines of input , The first line has two positive integers n,k. The second line n It's an integer , Represents a sequence a
Output format
The output consists of two lines , The first line is the minimum value of each window slide
The second line is the maximum value of each window slidingI/o sample
Input
8 3 1 3 -1 -3 5 3 6 7Output
-1 -3 -3 -3 3 3 3 3 5 5 6 7explain / Tips
【 Data range 】
about 50% The data of ,1≤n≤10^5;
about 100% The data of ,1≤k≤n≤10^6,ai∈[−2^31,2^31).
Ideas
A monotonous queue .
First , The elements in the queue must be within the scope of the window , And because you only move back one position at a time , Therefore, you only need to judge whether the team head element is within the scope of the window .
then , Because of the monotonicity of the elements in the error queue , So we need to keep the tail of the team with the current i The element referred to is compared . When finding the minimum value in the window , Only when the tail element is smaller than the current i When referring to the element , To maintain the current i When the selected element enters the queue , The elements in the queue continue to remain monotonous . Find the maximum value in the window similar , The difference is that only the tail element is larger than the current i When referring to the element , To maintain the current i When the selected element enters the queue , The elements in the queue continue to remain monotonous .
Last , Remember that only when the length of the window is greater than or equal to k When the value of , To find the maximum .
Also pay attention to , Don't get their order wrong , Otherwise the result will be wrong .
Code implementation
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[1000001],n,k,x[1000001],y[1000001];
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int head=0,tail=0;
for(int i=0;i<n;i++)
{
if(head<tail&&y[head]<i-k+1)// The queue header element is not within the scope of the window , Just take the team leader element out of the team
{
head++;
}
while(head<tail&&a[y[tail-1]]>=a[i])// Queue non-empty time , Compare the tail element with the new element , If it is larger than the new element , Or equal to , Just out of the team
{
tail--;
}
y[tail++]=i;// Put new elements in the team
if(i>=k-1)// Only the elements passed by the window are greater than or equal to k Time , Just started looking for the maximum
{
printf("%d ",a[y[head]]);
}
}
printf("\n");
head=0,tail=0;
for(int i=0;i<n;i++)
{
if(head<tail&&x[head]<i-k+1)// The queue header element is not within the scope of the window , Just take the team leader element out of the team
{
head++;
}
while(head<tail&&a[x[tail-1]]<=a[i])// Queue non-empty time , Compare the tail element with the new element , If less than or equal to the new element , Just out of the team
{
tail--;
}
x[tail++]=i;// Put new elements in the team
if(i>=k-1)// Only the elements passed by the window are greater than or equal to k Time , Just started looking for the maximum
{
printf("%d ",a[x[head]]);
}
}
return 0;
}6、 ... and 、P5788 【 Templates 】 Monotonic stack - Luogu | New ecology of computer science education (luogu.com.cn)
Background
The template questions , No background .
2019.12.12 Update data , Relax the time limit , No longer stuck .
Title Description
The number of items given is n The whole number sequence of a1…n.
Defined function f(i) Represents the... In the sequence i The first element after the first element is greater than ai The elements of the Subscript , namely f(i)=min i<j≤n,aj>ai {j}. If it does not exist , be f(i)=0.
Try to find out f(1…n).
Input format
First line a positive integer n.
The second line n A positive integer a1…n.
Output format
a line n It's an integer f(1…n) Value .
I/o sample
Input
5 1 4 2 3 5Output
2 5 4 5 0explain / Tips
【 Data scale and agreement 】
about 30% The data of ,100n≤100;
about 60% The data of , n≤5×10^3;
about 100% The data of , 1≤n≤3×10^6,1≤ai≤10^9.
Ideas ：
Traverse from the end of the array forward . If there are elements in the stack and the element at the top of the stack is smaller than the current element , Out of the stack , Until there is no element in the stack or the element at the top of the stack is smaller than the current element . After the stack is finished , If there are elements in the stack , The position of the subscript of the first element larger than the current element in the array is the top element , otherwise , There is no first element larger than the current element . Then put the subscript of the current element on the stack .
Code implementation
#include<bits/stdc++.h>
using namespace std;
void next(int a[],int n,int b[])
{
int top=0,c[3000001];// Order of the stack
for(int i=n;i>=1;i--)
{
while(top>0&&a[i]>=a[c[top-1]])// There are elements in the stack and the element at the top of the stack is smaller than the current element
{
top--;// Out of the stack
}
if(top>0)// There are elements in the stack
{
b[i]=c[top-1];// Equal to the top element of the stack
}
else
{
b[i]=0;
}
c[top++]=i;// Save subscript
}
}
int main()
{
int n,a[3000001],b[3000001];
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
next(a,n,b);
for(int i=1;i<=n;i++)
{
printf("%d ",b[i]);
}
return 0;
}边栏推荐
- redis中value/set
- sshd_config 中 PermitRootLogin 的探讨
- [AI information monthly] 350 + resources! All the information and trends that can't be missed in June are here! ＜ Download attached ＞
- Continuous delivery -pipeline getting started
- Getting started with Paxos
- redis中value/String
- No statements may be issued when any streaming result sets are open and in use on a given connection
- y48.第三章 Kubernetes从入门到精通 -- Pod的状态和探针(二一)
- 2022/6/29学习总结
- Export and import of incluxdb on WIN platform
猜你喜欢
How to set decimal places in CAD
英特爾實驗室公布集成光子學研究新進展
CAD如何设置标注小数位
Applymiddleware principle
Redis configuration environment variables
Unittest 框架介绍及第一个demo
Skip the test cases to be executed in the unittest framework
关于Keil编译程序出现“File has been changed outside the editor,reload?”的解决方法
Jd.com renewed its cooperation with Tencent: issuing class A shares to Tencent with a maximum value of US $220million
Mingchuang plans to be listed on July 13: the highest issue price is HK $22.1, and the net profit in a single quarter decreases by 19%
随机推荐
VScode快捷键（最全）[通俗易懂]
为什么一定要从DevOps走向BizDevOps？
The developer said, "this doesn't need to be tested, just return to the normal process". What about the testers?
Tempest HDMI leak receive 3
Skip the test cases to be executed in the unittest framework
Tianrunyun, invested by Tian Suning, was listed: its market value was 2.2 billion Hong Kong, and its first year profit decreased by 75%
MIT's latest paper, "the need for interpretable features: motivation and classification": building interpretability in the constituent elements of machine learning models
redis中value/set
2022/6/29学习总结
Network security learning notes 01 network security foundation
Xiaomi mobile phone unlocking BL tutorial
Intel Labs annonce de nouveaux progrès en photonique intégrée
提问：测试工程师应该具备哪些职业素养？
Give up high paying jobs in Shenzhen and go back home
名创拟7月13日上市：最高发行价22.1港元 单季净利下降19%
TEMPEST HDMI泄漏接收 5
Flip the array gracefully
redis中value/hush
Epoll introduction
華為設備配置大型網絡WLAN基本業務