算法康复训练06

编程练习 机考
算法与数据结构
发布日期:   2022-04-19
更新日期:   2022-04-19
文章字数:   1.4k
阅读时长:   7 分
阅读次数:  

1. 知识点

2h🤪~

题目 难度 知识点
电话号码的字母组合 🐸 DFS
删除列表倒数第n个结点 🐸 链表
有效的括号 🐸 栈stack
合并两个有序链表 🐸 链表

2. 分题题解

2.1 电话号码的字母组合

孩子长点心！这题真心不难，但是一开始报错了，经过检查发现是mp[]第一维度写得下标越界了0，1

空间复杂度是因为temp每次都在复制，这里可以优化一下，dfs居然时间复杂度赢了？！

AK

class Solution {
public:
    vector<string>ans;
    vector<vector<char> >mp;
    string str;
    int len;
    void dfs(int pos,int aid,string temp){
        //当前位置以及取出来的字母序号
        temp+=mp[str[pos-1]-'0'][aid];
        if(pos>len){
            return;
        }
        if(pos==len){
            ans.push_back(temp);
        }else{
            pos++;
            for(int i=0;i<mp[str[pos-1]-'0'].size();i++){
                dfs(pos,i,temp);
            }
        }
    }
    //所有的字母表示
    vector<string> letterCombinations(string digits) {
        len=digits.length();
        if(len==0){
            return {};
        }
        //初始化
        str=digits;
        mp.resize(10);
        mp[2].push_back('a');mp[2].push_back('b');mp[2].push_back('c');
        mp[3].push_back('d');mp[3].push_back('e');mp[3].push_back('f');
        mp[4].push_back('g');mp[4].push_back('h');mp[4].push_back('i');
        mp[5].push_back('j');mp[5].push_back('k');mp[5].push_back('l');
        mp[6].push_back('m');mp[6].push_back('n');mp[6].push_back('o');
        mp[7].push_back('p');mp[7].push_back('q');mp[7].push_back('r');mp[7].push_back('s');
        mp[8].push_back('t');mp[8].push_back('u');mp[8].push_back('v');
        mp[9].push_back('w');mp[9].push_back('x');mp[9].push_back('y');mp[9].push_back('z');
        
        for(int i=0;i<mp[digits[0]-'0'].size();i++){
            dfs(1,i,"");
        }
        return ans;
    }
};

2.2 删除链表的倒数第n个结点

  • 最容易想的是两遍遍历┗|｀O′|┛ 嗷~~
/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        //计算正数是第几个
        int cnt=0;
        ListNode*p,*pre;
        p=head;
        while(p){
            cnt++;
            p=p->next;
        }
        //需要切割掉的下标
        int tid=cnt-n+1;
        if(tid==1){
            //删除头节点
            if(cnt==1){
                return NULL;
            }else{
                return head->next;
            }
        }
        cnt=0;
        pre=head;p=head;
        while(p){
            pre=p;
            cnt++;
            p=p->next;
            if(cnt==tid-1){
                //执行删除操作
                pre->next=p->next;
                delete(p);
                break;
            }
        }
        return head;
    }
};
  • 进阶：一遍扫描

我能想的比较low的方法就是用vetor储存然后……也没感觉到哪里优化了🤣

执行用时：4 ms, 在所有 C++ 提交中击败了77.60%的用户

内存消耗：10.5 MB, 在所有 C++ 提交中击败了20.03%的用户

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
       //一遍遍历解法
       vector<ListNode*>ps;//存放每个结点的指针
       ps.push_back(NULL);//NULL ,NODE1, NODE2……
       ListNode*p,*pre;
       p=head;
       int cnt=0;
       while(p){
           cnt++;
           ps.push_back(p);
           p=p->next;
       }
       ps.push_back(NULL);
       //删除第cnt-n+1
       if(cnt-n==0){
           return ps[cnt-n+2];
       }else{
           ps[cnt-n]->next=ps[cnt-n+1]->next;
           delete(ps[cnt-n+1]);
           return ps[1];
       }
       
    }
};

2.3 有效的括号

100% and97.78%

有点飘飘然啊哈哈，虽然其实都是数据结构基础题，但是AK速度很有成就感~

class Solution {
public:
    bool isValid(string s) {
        stack<char>st;//栈
        int len=s.length();
        for(int i=0;i<len;i++){
            if(s[i]=='('||s[i]=='{'||s[i]=='['){
                //左括号
                st.push(s[i]);
            }else{
                //右括号
                if(st.empty()){
                    //cout<<"右括号无对应";
                    return false;//肯定没有对应的
                }else{
                    char ch=st.top();
                    if(s[i]==')'&&ch=='('){
                        st.pop();
                    }else if(s[i]=='}'&&ch=='{'){
                        st.pop();
                    }else if(s[i]==']'&&ch=='['){
                        st.pop();
                    }else{
                        //cout<<"括号不对应";
                        return false;//左右括号不对应
                    }
                }
            }
        }
        if(!st.empty()){
            //cout<<"非空"<<endl;
            return false;
        }else{
            return true;
        }
    }
};

2.4 合并两个有序链表

emmm粗暴的方法是直接新开一个链表，一边双指针遍历一遍重建，时间复杂度60.7%，空间复杂度5.03%菜

/**
 * 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*p1=list1,*p2=list2,*pre1=list1,*pre2=list2;
        ListNode*head=NULL,*pre=NULL,*p=NULL;
        if(p1==NULL){
            return p2;
        }else if(p2==NULL){
            return p1;
        }
        while(p1&&p2){
            if(head==NULL){
                if(p1->val<p2->val){
                    head=new ListNode(p1->val);
                    p1=p1->next;
                }else{
                    head=new ListNode(p2->val);
                    p2=p2->next;
                }
                pre=head;
            }else{
                if(p1->val<p2->val){
                    p=new ListNode(p1->val);
                    p1=p1->next;
                }else{
                    p=new ListNode(p2->val);
                    p2=p2->next;
                }
                pre->next=p;
                pre=p;
            }
        }
        //某一个链表还很长
        while(p1){
            p=new ListNode(p1->val);
            p1=p1->next;
            pre->next=p;
            pre=p;
        }
        while(p2){
            p=new ListNode(p2->val);
            p2=p2->next;
            pre->next=p;
            pre=p;
        }
        return head;
    }
};

3. 参考资料

4. 一点娱乐

4.1 如何在hexo博客插入B站视频

关于如何在hexo下插入B站视频,俺在尝试看看可不可行周深的歌太上头啦，最厉害的V!安利一下

{% raw %}
<div style="position: relative; width: 100%; height: 0; padding-bottom: 75%;">
<iframe src="//player.bilibili.com/player.html?aid=767819655&bvid=BV1xr4y1s7rr&cid=564914892&page=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true" style="position: absolute; width: 100%; height: 100%; Left: 0; top: 0;" > </iframe></div>
{% endraw %}

4.2 关于分享一部电影

《本杰明巴顿奇事》

因为周末没有抽出时间所以只看了十分钟的解说……九月之后想补上的一部电影，因为被台词戳中了🥰

片尾

文章作者: Gao
文章链接: https://ghy0202.github.io/2022/04/19/suan-fa-xun-lian-06/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Gao !
编程练习 机考
赏
评论
  目录