2022.6.28

早上：学习《MySQl必知必会》学到了第5章，html，一些标签（meta等）；

中午：

题目：206. 反转链表 - 力扣（LeetCode）

题解：

我的思路是把链表中的数放进一个数组里面，然后再将数组中的数反转进链表中。这个思路怎么使用在链表的长度不是很长的时候。时间复杂度为O(n)，空间复杂度为O(n)

代码入下：

/**
 * 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;
    }
};

     优化：使用链表可以优化，思路是在遍历链表时，将指针反转（由指向为next反转为prev);

                空间复杂度为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;
    }
};

题目：3. 无重复字符的最长子串 - 力扣（LeetCode）

题解：     1.用一个数记录当前最长的子串长度。不断更新。

                2.用一个数组记录当前字符有没有出现过，如果出现过，数组的值为该字符上一次出现的位置。如果没有出现，数组的值为0。

                3.遍历数组，如果当前字符没有出现过，就接着走，重新加载最长的子串长度，然后将数组的值全部改成0，如果出现过，就找到这个字符上一次出现的位置，如果是当前位置的前一个就把数组的值改成当前位置，反之将之前出现过字符数组的值再一次赋值。

                4.时间复杂度为O(n^2)。

代码如下：

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){//之前没有出现
                nums[s[i]-NULL]=i+1;
                maxx=max(maxx,i-j+1);//求最长的子串
            }else{//之前出现过
            j=nums[s[i]-NULL];//找到重复字符出现的位置
            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;
    }
};

题目：146. LRU 缓存 - 力扣（LeetCode）

题解：有思路但是代码写不出来，看了一下hashmap的源码更懵逼了。

MySQL的刷题