【鏈表】復(fù)習(xí)/刷題記錄

leetcode 203. Remove Linked List Elements

/**
 * 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* removeElements(ListNode *head, int val) {
        // ListNode *tem = (ListNode*)malloc(sizeof(ListNode));
        // tem->next = head;
        
        // ListNode *p = tem;
        
        // while(p->next != NULL) {
        //     if(p->next->val == val) {
        //         p->next = p->next->next;
        //     }
        //     if(p->next && p->next->val != val) p = p->next;
        //     if(p == NULL) break;
        // }
        // return tem->next;

        if(head == NULL) return head;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

法1 循環(huán)

法2 遞歸

這個(gè)寫法很短，看題解所得

好久沒看過鏈表了，寫題一臉懵逼（

21. Merge Two Sorted Lists

自己寫的腌臜玩意

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *ans = (ListNode*)malloc(sizeof(ListNode)); ans->next = NULL;
        ListNode *ANS = ans;
        ListNode *p1 = list1, *p2 = list2;
        while(p1 && p2) {
            ListNode *tem = (ListNode*)malloc(sizeof(ListNode));    // try 定義到外面 公用？
            if(p1->val <= p2->val) {
                tem->val = p1->val;
                tem->next = NULL;
                ans->next = tem;
                p1 = p1->next;  ans = ans->next;
            }
            else {
                tem->val = p2->val;
                tem->next = NULL;
                ans->next = tem;
                p2 = p2->next;  ans = ans->next;
            }
        }
        while(p1) {
            ListNode *tem = (ListNode*)malloc(sizeof(ListNode));
            tem->val = p1->val;
                tem->next = NULL;
                ans->next = tem;
                p1 = p1->next;  ans = ans->next;
        }
        while(p2) {
            ListNode *tem = (ListNode*)malloc(sizeof(ListNode));
            tem->val = p2->val;
                tem->next = NULL;
                ans->next = tem;
                p2 = p2->next;  ans = ans->next;
        }
        return ANS->next;
    }
};

簡(jiǎn)潔的代碼：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *ans = (ListNode*)malloc(sizeof(ListNode));
        ans->next = NULL;
        ListNode *ANS = ans;
        while(list1 && list2) {
            if(list1->val <= list2->val) {
                ans->next = list1; 
                ans = ans->next;
                list1 = list1->next;
            }
            else {
                ans->next = list2; 
                ans = ans->next;
                list2 = list2->next;
            }
        }
        ans->next = (list1 ? list1 : list2);
        return ANS->next;
    }
};

改進(jìn)的地方：

不需要保留list1,list2這兩個(gè)鏈表的首元素地址了，也就不需要重新定義變量
當(dāng)有一個(gè)鏈表已經(jīng)空了的時(shí)候，這時(shí)候直接讓ans的next指向另外一個(gè)鏈表，其實(shí)就是另一個(gè)鏈表剩下的部分，簡(jiǎn)化了代碼量

141. Linked List Cycle

法1

因?yàn)樽疃嘤?e4個(gè)點(diǎn)，所以當(dāng)遍歷到第 1e4+1 個(gè)點(diǎn)時(shí)肯定是有環(huán)的

class Solution {
public:
    bool hasCycle(ListNode *head) {
        int cnt = 0;
        while(head) {
            cnt++;
            head = head->next;
            if(cnt >= 10001) break;
        }
        return (cnt >= 10001);
    }
};

法2

容易想到第一次訪問過一個(gè)點(diǎn)就記錄一下，注意vis數(shù)組里存的是鏈表元素的數(shù)據(jù)類型（ListNode）

class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode*, int> mp;
        int cnt = 0;
        while(head)  {
            if(mp[head]) return 1;
            mp[head] = 1;
            head = head->next;
        }
        return 0;
    }
};

206. Reverse Linked List

反轉(zhuǎn)鏈表

注意LeetCode用C++編譯器但是寫malloc不free會(huì)報(bào)錯(cuò)

class Solution {
public:
   ListNode* reverseList(ListNode* head) {
       if(head == NULL) return head;
       ListNode *tem = new ListNode;
       tem->val = head->val; tem->next = NULL;
       head = head->next;
       while(head) {
           ListNode *p = new ListNode;
           p->val = head->val; p->next = tem;
           tem = p;
           head = head->next;
       }
       return tem;
   }
};

20. Valid Parentheses

法1 因?yàn)橐欢ㄓ欣ㄌ?hào)是連在一起的，思路是每次找 {} , () , [] 三者中的一個(gè)，去掉之后check剩余部分

寫得很腌臢，明顯可以用 s.replace("{}", "") 來簡(jiǎn)化

class Solution {
public:
    bool isValid(string s) {
        if(s.empty()) return 1;
        int n = s.size();
        if(n % 2 || s[0] == ']' || s[0] == ')' || s[0] == '}') return 0;
        int fl = -1;
        int i = s.find("()");
        if(i != -1) {
            fl = i;
        }
        else {
            i = s.find("[]");
            if(i != -1) {
                fl = i;
            }
            else {
                i = s.find("{}");
                if(i != -1) {
                    fl = i;
                }
            }
        }
        if(fl == -1) return 0;
        else {
            string tem = ""; 
            if(fl > 0) tem += s.substr(0, fl); 
            if(fl + 2 < n) tem += s.substr(fl + 2);
            return isValid(tem);
        }
    }
};

該好好復(fù)習(xí)STL了！！！

法2 利用stack，如果遇到左括號(hào)直接push，如果是右括號(hào)，它一定是跟棧頂?shù)睦ㄌ?hào)配對(duì)。如果不配直接return 0，能配對(duì)就彈出棧頂

class Solution {
public:
    bool isValid(string s) {
        // 正解應(yīng)該是stack + 肯定可以直接配對(duì)
        stack<char> Sta;
        for(auto x : s) {
            // if(!Sta.empty()) cout << Sta.top() << endl;
            if(x == '(' || x == '[' || x == '{') Sta.push(x);
            else {
                if(Sta.empty()) return 0;
                char tem = Sta.top();
                if(x == '}') {
                    if(tem == '{') Sta.pop();
                    else return 0;
                }
                else if(x == ']') {
                    if(tem == '[') Sta.pop();
                    else return 0;
                }
                else if(x == ')') {
                    if(tem == '(') Sta.pop();
                    else return 0;
                }
            }
        }
        return Sta.empty();  
    }
};

232. Implement Queue using Stacks

做法就是純模擬啦，記得棧和隊(duì)列不要看錯(cuò)了。

原來通過做這道題我才知道，我根本不會(huì)cpp......只是會(huì)C with STL的菜雞罷了（嗚嗚嗚

this和構(gòu)造函數(shù)什么的，完全都忘記了啊

typedef struct {
    int val;
    struct MyQueue *next;
} MyQueue;


MyQueue* myQueueCreate() { /// 頭指針
    MyQueue *head = (MyQueue*)malloc(sizeof(MyQueue));
    head->next = NULL; head->val = 0;
    return head;
}

void myQueuePush(MyQueue* obj, int x) {
    MyQueue *tem = obj;
    MyQueue *p = myQueueCreate();
    p->val = x;
    while(tem->next) tem = tem->next;
    tem->next = p;
}

int myQueuePop(MyQueue* obj) {
    if(obj->next == NULL) return NULL;
    MyQueue *tem = obj->next;
    int x = tem->val;
    obj->next = tem->next;
    return x;
}

int myQueuePeek(MyQueue* obj) {
    if(obj->next == NULL) return NULL;
    MyQueue *tem = obj->next;
    int x = tem->val;
    return x;
}

bool myQueueEmpty(MyQueue* obj) {
    return (obj->next == NULL);
}

void myQueueFree(MyQueue* obj) {

}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

posted @ 2023-03-18 11:18 starlightlmy 閱讀(23) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

starlight_

acmer ^ ^