2022.6.28

morning ： Study 《MySQl Will know 》 Learned the first 5 Chapter ,html, Some labels （meta etc. ）;

At noon, ：

subject ：206. Reverse a linked list - Power button （LeetCode）

Answer key ：

My idea is to put the numbers in the linked list into an array , Then invert the number in the array into the linked list . How to use this idea when the length of the linked list is not very long . The time complexity is O(n), The space complexity is O(n)

Code in ：

/**
 * 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* reverseList(ListNode* head) {
        ListNode *p;
        p=head;
        int i=0;
        vector<int> a(5001);
        while(p!=NULL){
            a[i]=p->val;
            i++;
            p=p->next;
        }
        p=head;
        for(int j=0;j<i;j++){
            p->val=a[i-j-1];
            p=p->next;
        }
        return head;
    }
};

      Optimize ： Using linked lists can optimize , The idea is to traverse the linked list , Reverse the pointer （ From to next Reversal is prev);

                 The space complexity is O(1).

class Solution {
public:
    ListNode* reverseList(ListNode* head){
        ListNode* p = NULL;
        ListNode* c = head;
        while (c!=NULL) {
            ListNode* next = c->next;
            c->next = p;
            p = c;
            c = next;
        }
        return p;
    }
};

subject ：3. Longest substring without repeating characters - Power button （LeetCode）

Answer key ：     1. Record the current longest substring length with a number . Constantly updated .

                2. Use an array to record whether the current character has appeared , If there has been , The value of the array is the last occurrence of the character . If not , The value of the array is 0.

                3. Traversal array , If the current character does not appear , Just keep going , Reload the longest substring length , Then change all the values of the array to 0, If there has been , Just find the last position of this character , If it is the previous one of the current position, change the value of the array to the current position , On the contrary, assign the value of the previous character array again .

                4. The time complexity is O(n^2).

The code is as follows ：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)
        return 0;
        int nums[500],maxx=1,j=0;
        memset(nums,0,sizeof(nums));
        nums[s[0]-NULL]=1;
        for(int i=1;i<s.size();i++){
            if(nums[s[i]-NULL]==0){// It didn't appear before 
                nums[s[i]-NULL]=i+1;
                maxx=max(maxx,i-j+1);// Find the longest substring 
            }else{// There have been... Before 
            j=nums[s[i]-NULL];// Find the position where the repeated characters appear 
            memset(nums,0,sizeof(nums));
            if(s[i-1]==s[i]){
                j=i;
                nums[s[i]-NULL]=i+1;
            }else{
            for(int k=j;k<=i;k++)
            nums[s[k]-NULL]=k+1;
            }
            }
        }
        return maxx;
    }
};

subject ：146. LRU cache - Power button （LeetCode）

Answer key ： There are ideas, but the code can't be written , Look at the hashmap The source code of is even more confused .

MySQL The brush topic of