Learning summary on June 28, 2022

  One 、3. Longest substring without repeating characters - Power button （LeetCode）

  Title Description ：

Given a string s , Please find out that there are no duplicate characters in it   Longest substrings   The length of .

Example  1:

Input : s = "abcabcbb"
Output : 3 
explain : Because the longest substring without repeating characters is "abc", So its length is 3.
Example 2:

Input : s = "bbbbb"
Output : 1
explain : Because the longest substring without repeating characters is "b", So its length is 1.
Example 3:

Input : s = "pwwkew"
Output : 3
explain : Because the longest substring without repeating characters is  "wke", So its length is 3.
     Please note that , Your answer must be Substring The length of ,"pwke"  Is a subsequence , Not substring .
 

Tips ：

0 <= s.length <= 5 * 104
s  By the English letters 、 Numbers 、 Symbols and spaces

  Ideas ：

Record the last position of the character in the traversal string , Judge whether it has appeared in the string by position . The following problem-solving ideas are explained in detail in the code .

Code implementation ：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start=0,l=0,max=0,a[128];
        for(int i=0;i<128;i++)// Record the last position of the letter before the traversed position 
        {
            a[i]=-1;// initialization , Initialized number , Can only be less than 0 The number of 
        }
        for(int i=0;i<s.length();i++)
        {
            if(a[s[i]]>=start)// This character has appeared before 
            {
                if(l>max)// Update the length of the longest non repeating substring 
                {
                    max=l;
                }
                l=i-a[s[i]];// Update the effective length of the new substring 
                start=a[s[i]]+1;// Update the starting position of the new substring in the parent string 
                a[s[i]]=i;// The letter has appeared , Update the last position of the letter before the traversal position 
            }
            else// This character does not appear 
            {
                a[s[i]]=i;// This letter has never appeared , Record the last position of the letter before the traversed position 
                l++;// Length plus one 
            }
        }
        if(l>max)// It is possible to traverse to the end , The longest non repeating substring appears , that max No updates , So update here 
        {
            max=l;
        }
        return max;
    }
};

Two 、146. LRU cache - Power button （LeetCode）

Title Description ：

  Please design and implement a meeting   LRU ( Recently at least use ) cache Constrained data structure .
Realization LRUCache class ：
LRUCache(int capacity) With Positive integer As capacity  capacity initialization LRU cache
int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
void put(int key, int value)  If the keyword  key Already exist , Change its data value  value ; If it doesn't exist , Then insert the group into the cache  key-value . If the insert operation causes the number of keywords to exceed  capacity , Should be Eviction The longest unused keyword .
Be careful ： function get and put Must be O(1) The average time complexity of running .

Example ：

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

explain
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // The cache is {1=1}
lRUCache.put(2, 2); // The cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // This operation causes the keyword to 2 To void , The cache is {1=1, 3=3}
lRUCache.get(2);    // return -1 ( Not found )
lRUCache.put(4, 4); // This operation causes the keyword to 1 To void , The cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 ( Not found )
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
 

Tips ：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
Call at most 2 * 105 Time get and put

Ideas ：

Double linked list + Hashtable . Because sometimes , The node to be moved is located in the middle of the linked list , On the move , You have to delete nodes and add nodes , Delete this node , We have to find the precursor node and the successor node of this node at the same time , So it is convenient to use a two-way linked list . then ,get() Functions and put() function , Check whether the node exists , At the same time, the time complexity should be O(1), So we have to use hash table .

Code implementation ：

 class LRUCache {
    struct LinkNode {// Node structure 
        int value;
        int key;
        LinkNode* prior;
        LinkNode* next;
    };

    LinkNode* head=new LinkNode;// Head node , It is convenient to delete and add nodes 
    LinkNode* tail=new LinkNode;// Caudal node 
    map<int,LinkNode*> mp;//map, Easy to find key and value, The function  get  and  put  Must be  O(1)  The average time complexity of running 
    int c,sum=0;// Cache capacity , Cached capacity 

public:
    LRUCache(int capacity) {
        c = capacity;// Get cache capacity 
        head->next = tail;// Empty two-way linked list 
        tail->prior = head;
    }
    
    int get(int key) {
        if(mp.count(key))
        {
            remove(mp[key]);// Just used , So move this node forward , Delete the node first 
            add(head,mp[key]);// Add more nodes 
            return mp[key]->value;// There is 
        }
        return -1;// non-existent 
    }
    
    void put(int key, int value) {
        if(mp.count(key))//key The value is 
        {
            remove(mp[key]);// Just used , So move this node forward , Delete the node first 
            add(head,mp[key]);// Add nodes 
            mp[key]->value=value;// because key The value is , but value Values may be different from those already stored value Values are different , So it's mainly in the function 
            return;
        }
        LinkNode* node=new LinkNode;// non-existent , Add nodes 
        node->key=key;
        node->value=value;
        add(head,node);
        sum++;
        mp[key]=node;
        if(sum>c)
        {
            LinkNode* p=tail->prior;
            remove(tail->prior);// Delete the last node , That is, the node that has not been used for the longest time 
            sum--;
            mp.erase(p->key);
        }
        return;
    }

    void remove(LinkNode* node)// Delete node node
    {
        node->next->prior=node->prior;
        node->prior->next=node->next;
    }

    void add(LinkNode* node,LinkNode* p)// At node node Add nodes later p
    {
        p->next=node->next;
        p->prior=node;
        node->next->prior=p;
        node->next=p;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

3、 ... and 、215. The... In the array K The biggest element - Power button （LeetCode）

Title Description  

Given an array of integers nums And integer k, Please return the... In the array k The biggest element .

Please note that , What you need to look for is the number after array sorting k The biggest element , Not the first. k A different element .

Example 1:

Input : [3,2,1,5,6,4] and k = 2
Output : 5
Example  2:

Input : [3,2,3,1,2,4,5,5,6] and k = 4
Output : 4
 

Tips ：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

Ideas ：

Use sorting algorithm （ The fast platoon used here ）, Then take the penultimate k Just one element .

Code implementation ：

class Solution {
public:
    void quickSort(vector<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);
    }
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums,0,nums.size()-1);
        return nums[nums.size()-k];
    }
};

Four 、P1044 [NOIP2003 Popularization group ] Stack - Luogu | New ecology of computer science education (luogu.com.cn)

Background

Stack is the classic data structure in computer , To put it simply , A stack is a linear table that is limited to insert and delete operations at one end .

The stack has two most important operations , namely pop（ Pop an element from the top of the stack ） and push（ Stack an element ）.

The importance of stacks is self-evident , Any course on data structure will introduce stacks . Ning Ning was reviewing the basic concept of stack , I think of a problem that is not mentioned in the book , And he can't give the answer himself , So I need your help .

Title Description

Ning Ning is thinking about such a problem ： A sequence of operands ,1,2,…,n（ Shown here 1 To 3 The situation of ）, Stack A The depth of is greater than  n.

Now you can do two things ,

1. Count a number , Move from the header of the sequence of operands to the header of the stack （ Corresponding to the data structure stack push operation ）
2. Count a number , Move from the head of the stack to the end of the output sequence （ Corresponding to the data structure stack pop operation ）

Use these two operations , From a sequence of operands, we can get a series of output sequences , The figure below shows  1 2 3  Generating sequences  2 3 1  The process of .

（ The original state is shown in the figure above ）

Your program will respond to a given  n, Computes and outputs a sequence of operands  1,2,…,n  The total number of possible output sequences after operation .

Input format

The input file contains only one integer  n（1≤n≤18）.

Output format

The output file has only one line , That is, the total number of possible output sequences .

I/o sample

Input #1 Copy

3

Output #1 Copy

5

explain / Tips

【 Title source 】

NOIP 2003 Third question of popularization group

Ideas ： Recursive method .

Stack can be used for stack in and stack out operations . The following ideas are explained in the code .

Code implementation ：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int a[20][20];// The number of lines represents the number of numbers that have not been put on the stack , The number of columns represents the number of numbers in the stack 
    for(int i=0;i<20;i++)
    {
        a[0][i]=1;// If all elements are put on the stack , That element only comes out of the stack , And there is only one out of stack sequence 
    }
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<20;j++)
        {
            if(j==0)// The elements in the stack are 0 Time , The only operations that can be performed are stacking 
            {
                a[i][j]=a[i-1][j+1];
            }
            else
            {
                a[i][j]=a[i-1][j+1]+a[i][j-1];// The number of elements in the stack is not 0 when , You can enter and exit the stack 
            }
        }
    }
    printf("%d",a[n][0]);// The number of stack sequences , That is, the number of elements not stacked is n, The elements in the stack are 0 Time 
}

5、 ... and 、P1449 Postfix expression - Luogu | New ecology of computer science education (luogu.com.cn)

Title Description

The so-called suffix expression refers to such an expression ： Parentheses are no longer used in expressions , The operation symbol is placed after two operation objects , All calculations are in the order in which the symbols appear , Strictly from left to right （ Regardless of the priority of the operator ）.

Such as ：3*(5–2)+7 The corresponding suffix expression is ：3．5．2．-*7．[email protected]’@’ Is the end symbol of the expression .‘.’ Is the end symbol of the operands .

Input format

Input ： Postfix expression

Output format

Output ： Value of expression

I/o sample

Input  

3.5.2.-*[email protected]

Output  

16

explain / Tips

String length ,1000 Inside .

 

Ideas ： There is no need to consider '+' '-' For monocular operators .

There is no need to consider the situation above , This question is very simple .

Attention should be paid to the fetching of operands . Each operand is followed by a '.', This makes it convenient for us to take operands . The operand we get should be the first numeric character we encounter to '.' The previous integer number composed of all numeric characters , Then put it on the stack .

Then for the operator , This question does not consider the monocular operator . So every time you get two operands , Then put the operation result on the stack , Finally, the element at the bottom of the stack is the operation result of the suffix expression .

Code implementation ：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[1001];// String entered 
    int c[1001];// Store operands 
    int i=0,j=0;
    while((s[i]=getchar())!='@')// Input string 
    {
        i++;
    }
    s[i]='\0';
    for(i=0; i<strlen(s); i++)
    {
        if(s[i]>='0'&&s[i]<='9')// Fetch operand , Push 
        {
            int m=1,x;
            x=s[i]-'0';
            i++;
            while(s[i]!='.')// Take the first numeric character encountered , To '.' A number consisting of all previous characters 
            {
                x=x*10+s[i]-'0';
                m++;
                i++;
            }
            c[j]=x;// Push 
            j++;
        }
        if(s[i]=='-')// They're all binocular operators 
        {
            int x=c[j-2]-c[j-1];
            j=j-2;
            c[j]=x;// Put the result of the operation on the stack 
            j++;
        }
        if(s[i]=='+')
        {
            int x=c[j-2]+c[j-1];
            j=j-2;
            c[j]=x;
            j++;
        }
        if(s[i]=='*')
        {
            int x=c[j-2]*c[j-1];
            j=j-2;
            c[j]=x;
            j++;
        }
        if(s[i]=='/')
        {
            int x=c[j-2]/c[j-1];
            j=j-2;
            c[j]=x;
            j++;
        }
    }
    printf("%d",c[0]);// The element at the bottom of the stack is the operation result of the suffix expression 
    return 0;
}