力扣Day6

3道easy+6道medium+2道hard，主要是把链表和栈弄清楚了。

(easy)20. 有效的括号

一道练习栈使用方法的模板题，由于栈先进后出，所以后进的括号必然得先出，不然就不符合规则；然后栈只存前括号。看题解单纯是因为自己忘了栈的用法😄。代码如下：

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if(n&1)
            return 0;
        stack<char> stack;
        for(int i = 0;i < n;i++)
        {
            char temp = s[i];
            char pair = ' ';
            if(temp == ')')
                pair = '(';
            if(temp == ']')
                pair = '[';
            if(temp == '}')
                pair = '{';
            if(pair != ' ')
            {
                if(stack.empty() || stack.top() != pair)
                    return 0;
                stack.pop();
            }
            else
                stack.push(temp);
        }
        if(stack.empty())
            return 1;
        return 0;
    }
};

(medium)71. 简化路径

最开始我的思路其实是把每个/abc存进栈里面，因为先进后出嘛，如果遇到..就直接pop；但后面不知道咋从头调用栈，只能去看题解咋说，好家伙，都用vector是吧，那我也用。就是把非/的路径先存进temp，如果temp为..则判断vector是否为空，为空则不保存(我咋印象中实际上unix这种如果为空得保存啊)，不为空则pop_back()；若为.则跳过，其他都push_back() 好家伙，一个个浓眉大眼的都用vector模拟栈是吧。代码如下：

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> s;
        int n = path.size();
        string temp = {};
        int i = 0;
        while(i < n)
        {
            if(path[i] != '/')
            {
                int j = i + 1;
                while(j < n && path[j] != '/')
                {
                    j++;
                }
                if(j <= n)//取等于n是因为存在最后一位为路径的情况
                {
                    temp = path.substr(i,j - i);
                    if(temp == ".." && !s.empty())
                        s.pop_back();
                    else if(temp != ".." && temp != ".")
                        s.push_back(temp);
                }
                i = j;
            }
            else
                i++;
        }
        string ans;
        if(s.empty())
            ans = "/";
        else
        {
            for(string& k: s)
                ans += "/" + k;
        }
        return ans;
    }
};

(medium)155. 最小栈

一个模拟栈的题，真要让我不用任何数据结构做我好像还真只能嗯用数组、cnt这种，但用vector要舒服一点点，就用vector了。代码如下：

#define MAXN ((1<<32) - 1)
class MinStack {
public:
    //int cnt;
    int MINX;
    vector<int> stack;
    vector<int> minstack;
    //unordered_map<int,int> minstack;
    MinStack() {
        //cnt = 0;
        MINX = INT_MAX;
        minstack.push_back(MINX);
        //minstack[cnt] = MINX;
    }
    
    void push(int val) {
        stack.push_back(val);
        //cnt++;
        MINX = min(MINX,val);
        //minstack[cnt] = MINX;
        minstack.push_back(MINX);
    }
    
    void pop() {
        //cnt--;
        stack.pop_back();
        minstack.pop_back();
        MINX = minstack.back();

    }
    int top() {
        return stack.back();
    }
    
    int getMin() {
        return MINX;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

(medium)150. 逆波兰表达式求值

也是一道经典栈应用题，每次遇到符号取栈中最后两个数出来操作，然后结果继续入栈，最后返回stack.back()即可。代码如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> temp;
        int n = tokens.size();
        for(int i = 0; i < n; i++)
        {
            if(tokens[i] == "+")
            {
                int t1 = temp.back();
                temp.pop_back();
                int t2 = temp.back();
                temp.pop_back();
                int t3 = t2 + t1;
                temp.push_back(t3);
            }
            else if(tokens[i] == "-")
            {
                int t1 = temp.back();
                temp.pop_back();
                int t2 = temp.back();
                temp.pop_back();
                int t3 = t2 - t1;
                temp.push_back(t3);
            }
            else if(tokens[i] == "*")
            {
                int t1 = temp.back();
                temp.pop_back();
                int t2 = temp.back();
                temp.pop_back();
                int t3 = t2 * t1;
                temp.push_back(t3);
            }
            else if(tokens[i] == "/")
            {
                int t1 = temp.back();
                temp.pop_back();
                int t2 = temp.back();
                temp.pop_back();
                int t3 = t2 / t1;
                temp.push_back(t3);
            }
            else
            {
                int j = tokens[i].size();
                bool flag = 1;
                int sum = 0;
                for(int k = 0;k < j; k++)
                {
                    if(tokens[i][k] == '-')
                        flag = 0;
                    else
                        sum = sum * 10 + tokens[i][k] - '0';
                }
                if(!flag)
                    sum = -sum;
                temp.push_back(sum);
            }
        }
        return temp.back();
    }
};

(hard)224. 基本计算器

屎一样的题让我写出屎一样的代码。因为只有±，所以运算顺序直接从左往右不需要栈，需要栈是因为有(，栈用来存储括号即可。预处理地方将每一个两个-间没有数字的地方加一个0，避免连续-的出现。代码如下：

bool vis1[300010];
bool vis2[300010];
class Solution {
public:
  long long calc(long long a, long long b, char c) {
    switch (c) {
    case '+':
      return (a + b);
    case '-':
      return (a - b);
    }
    return 0;
  }
  bool isnum(char a) {
    if (a >= '0' && a <= '9')
      return 1;
    return 0;
  }
  long long calculate(string ss) {
    memset(vis1, 0, sizeof(vis1));
    memset(vis2, 0, sizeof(vis2));
    long long n = ss.size();
    vector<char> s;
    int cnt = 0;
    int lastnum = 0;
    int lastfu = 0;
    for (int i = 0; i < n; i++) {
      if (ss[i] == '-') {
        if (i == 0 || lastnum < lastfu) {
          cnt++;
          s.push_back('0');
        }
        lastfu = i;
      }
      if (isnum(ss[i]))
        lastnum = i;
      s.push_back(ss[i]);
    }
    n = n + cnt;
    //括号作为表达式隔断符
    // temp存数值，temp2存操作符，temp3存左括号位置
    vector<long long> temp;
    vector<char> temp2;
    vector<pair<long long, long long>> temp3;
    long long i = 0;
    while (i < n) {
      long long j = i + 1;
      if (isnum(s[i])) {
        long long sum = s[i] - '0';
        while (j < n && isnum(s[j])) {
          sum = sum * 10 + s[j] - '0';
          j++;
        }
        temp.push_back(sum);
      } else if (s[i] == '-' || s[i] == '+') {
        if (i + 1 < n && s[i] == '-' && isnum(s[i + 1])) {
          long long sum = 0;
          while (j < n && isnum(s[j])) {
            sum = sum * 10 + s[j] - '0';
            j++;
          }
          sum = -sum;
          temp.push_back(sum);
          temp2.push_back('+');
        } else
          temp2.push_back(s[i]);
      } else if (s[i] == '(') {
        temp3.push_back({temp.size(), temp2.size()});
      } else if (s[i] == ')') {
        long long s1 = temp3.back().first;
        long long s2 = temp3.back().second;
        long long sum = temp[s1];
        long long k = s1;
        s1++;
        while (s1 < temp.size() && s2 < temp2.size()) {
          if (!vis1[s1] && !vis2[s2]) {
            sum = calc(sum, temp[s1], temp2[s2]);
            vis1[s1] = 1;
            vis2[s2] = 1;
          }
          s1++;
          s2++;
        }
        temp[k] = sum;
        // printf("%d\n",sum);
        temp3.pop_back();
      }
      i = j;
    }
    long long s1 = 0;
    long long s2 = 0;
    long long sum = temp[s1];
    long long k = s1;
    s1++;
    while (s1 < temp.size() && s2 < temp2.size()) {
      if (!vis1[s1] && !vis2[s2]) {
        sum = calc(sum, temp[s1], temp2[s2]);
        vis1[s1] = 1;
        vis2[s2] = 1;
      }
      s1++;
      s2++;
    }
    temp[k] = sum;
    return temp[0];
  }
};

(easy)141. 环形链表

快慢指针版题。快慢指针是指：一个链表用p1和p2两个指针，每次p1和p2距离都会+1的一类问题。C++ 11 auto真好用😋

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto t1 = head;
        if(t1 == NULL)
            return 0;
        auto t2 =t1->next;
        while(t1!=NULL&&t2!=NULL)
        {
            if(t1 == t2)
                return 1;
            t1 = t1->next;
            t2 = t2->next;
            if(t2!=NULL)
                t2 = t2->next;
        }
        return 0;
    }
};

(medium)2. 两数相加

byd什么题涉及到链表都要开始恶心人一下是吧😓。主要是List->next是需要先创建才能访问的。思路就是简单的当前位置的val=l1->val+l2->val+flag，flag是记录是否进位。具体代码如下：

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* nxt1 = l1;
        ListNode* nxt2 = l2;
        ListNode* Node = new ListNode();
        ListNode* l3 = Node;
        bool flag = 0;
        while(nxt1!=NULL||nxt2!=NULL||flag)
        {
            if(nxt1 == NULL)
                nxt1 = new ListNode(0);
            if(nxt2 == NULL)
                nxt2 = new ListNode(0);
            int t1 = nxt1 -> val;
            int t2 = nxt2 -> val;
            t1 = t1 + t2 + flag;
            if(t1 >= 10)
            {
                flag = 1;
                l3->next = new ListNode(t1 - 10);
            }
            else
            {
                flag = 0;
                l3->next = new ListNode(t1);
            }
            nxt1 = nxt1->next;
            nxt2 = nxt2->next;
            l3 = l3->next;
        }
        return Node->next;
    }
};

(easy)21. 合并两个有序链表

感觉做法和上题基本一模一样。代码如下：

/**
 * 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) {
        ListNode* l3 = new ListNode();
        ListNode* nxt1 = list1;
        ListNode* nxt2 = list2;
        ListNode* nxt3 = l3;
        while(nxt1 != NULL || nxt2 != NULL)
        {
            if(nxt1 == NULL)
            {
                nxt3->next = new ListNode(nxt2->val);
                nxt2 = nxt2->next;
            }
            else if(nxt2 == NULL)
            {
                nxt3->next = new ListNode(nxt1->val);
                nxt1 = nxt1->next;
            }
            else
            {
                int t1 = nxt1->val;
                int t2 = nxt2->val;
                if(t1 > t2)
                {
                    nxt3->next = new ListNode(nxt2->val);
                    nxt2 = nxt2->next;
                }
                else
                {
                    nxt3->next = new ListNode(nxt1->val);
                    nxt1 = nxt1->next;
                }
            }
            nxt3 = nxt3->next;
        }
    return l3->next;
    }
};

(medium)138. 随机链表的复制

不懂，看的题解才懂。md链表的题个个题面都是写的一坨是吧😓。其实就相当于是把a链表复制到b链表，但是需要复制的信息还有a链表中每个指针指向的地方，比如在a链表中，X->zhizhen是Y，那么新链表中对应X的x的zhizhen值也得指向对应Y的y。考点就在于如果直接复制，那么可能在复制X到x的时候Y对应的y还没建立。代码如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* l1 = head;
        unordered_map<Node*, Node*> ys;
        while(l1!=NULL)
        {
            ys[l1] = new Node(l1->val);
            l1 = l1->next;
        }
        l1 = head;
        while(l1!=NULL)
        {
            ys[l1]->next = ys[l1->next];
            ys[l1]->random = ys[l1->random];
            l1 = l1->next;
        }
        return ys[head];
    }
};

(medium)92. 反转链表 II

建的反向链表做的，在i点判断，如果i>=l&&i<r就存反向链表的值，否则就是正向的值。优化倒是可以优化，但不想优化了，效率大概是扫2遍，O(2n)。代码如下：

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
     //第一想法是建一个反向链表，l,r就取反向链表的值，其余范围就取正向链表的值
     //pre是反向链表,l1是正向链表移动值,l2是反向链表移动值,before_l用于指向某个点在正向链表中其上一个点,l3用于临时存储next
     ListNode* pre = new ListNode();
     ListNode* l1 = head;
     ListNode* l2 = pre;
     ListNode* before_l = pre;
     ListNode *l3 = NULL;
     int cnt = 0;
     //建立反向链表pre
     while(l1 != NULL)
     {
         cnt++;
         l2->next = new ListNode(l1->val);
         l1 = l1->next;
         l3 = l2->next;
         if(before_l != l2)
         {
             l2->next = before_l;
             before_l = l2;
         }
         l2 = l3;
     }
     int num = 0;
     l2->next = before_l;
     l1 = head;
     ListNode* result = new ListNode();
     ListNode* l4 = result;
     //[1,l)赋正向链表的值
     while(num < left - 1 && l1 != NULL)
     {
         num++;
         l4->next = new ListNode(l1->val);
         l1 = l1->next;
         l4 = l4->next;
     }
     int num2 = cnt;
     //再把反向链表移动到right
     while(num2 > right)
     {
         num2--;
         l2 = l2->next;
     }
     //[l,r)赋反向链表的值
     while(num < right && l1 != NULL)
     {
         num++;
         l4->next = new ListNode(l2->val);
         l2 = l2->next;
         l4 = l4->next;
         l1 = l1->next;
     }
     //[r,cnt]赋正向链表的值
     while(num <= cnt && l1 != NULL)
     {
         num++;
         l4->next = new ListNode(l1->val);
         l1 = l1->next;
         l4 = l4->next;
     }
     return result->next;
    }
};

按原思路修改的，只旋转l,r部分，这样能做到只扫一遍(准确来说可能不用扫满一遍，只需要扫1,r的范围即可)。即反转[l,r]内的，然后l-1指向r，l指向r+1。代码如下：

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        //思路是反转[l,r]内的，然后(l-1)->next指向r，l->next指向r+1
        ListNode* tmp = NULL;
        ListNode* pre = NULL;
        ListNode* now = head;
        int cnt = 0;
        while(now != NULL)
        {
            cnt++;
            bool flag = 0;
            //pre2是l-1位置的
            ListNode* pre2 = pre;
            //当处于[l,r)范围时进行反转(不取r是因为最后跳出的时候需要刚好是r)
            while(cnt>=left&&cnt<right&&now != NULL)
            {
                flag = 1;
                tmp = now->next;
                now->next = pre;
                pre = now;
                now = tmp;
                cnt++;
            }
            if(flag)
            {
                if(pre2!=NULL)
                {
                    //l->next指向r+1
                    pre2->next->next = now->next;
                    //(l-1)->next指向r
                    pre2->next = now;
                }
                else//如果是从头开始反转部分内容
                {
                    //l->next指向r+1
                    head->next = now->next;
                    //r作为起点
                    head = now;
                }
                now->next = pre;
                break;
            }
            else
            {
                pre = now;
                now = now->next;
            }
        }
        return head;
    }
};

(hard)25. K 个一组翻转链表

直接套用自己上道题的代码，完美😋。代码如下：

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        //思路是反转[l,r]内的，然后(l-1)->next指向r，l->next指向r+1
        ListNode* tmp = NULL;
        ListNode* pre = NULL;
        ListNode* now = head;
        int cnt = 0;
        while(now != NULL)
        {
            cnt++;
            bool flag = 0;
            //pre2是l-1位置的
            ListNode* pre2 = pre;
            //当处于[l,r)范围时进行反转(不取r是因为最后跳出的时候需要刚好是r)
            while(cnt>=left&&cnt<right&&now != NULL)
            {
                flag = 1;
                tmp = now->next;
                now->next = pre;
                pre = now;
                now = tmp;
                cnt++;
            }
            if(flag)
            {
                if(pre2!=NULL)
                {
                    //l->next指向r+1
                    pre2->next->next = now->next;
                    //(l-1)->next指向r
                    pre2->next = now;
                }
                else//如果是从头开始反转部分内容
                {
                    //l->next指向r+1
                    head->next = now->next;
                    //r作为起点
                    head = now;
                }
                now->next = pre;
                break;
            }
            else
            {
                pre = now;
                now = now->next;
            }
        }
        return head;
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        int num = 0;
        ListNode* now = head;
        while(now != NULL)
        {
            num++;
            now = now->next;
        }
        for(int i=0;i<num/k;i++)
        {
            if(i*k>num)
                break;
            head = reverseBetween(head,i*k+1,i*k+k);
        }
        return head;
    }
};