美文网首页
Day12 替换空格+两个链表的第一个公共节点+第一个只出现一次

Day12 替换空格+两个链表的第一个公共节点+第一个只出现一次

作者: 吃掉夏天的怪物 | 来源:发表于2021-06-23 22:29 被阅读0次

    剑指 Offer 05. 替换空格(简单)

    方法一 如果不要求原地修改,就很简单

    class Solution {
    public:
        string replaceSpace(string s) {
            string ans="";
            for(auto it:s){
                if(it == ' '){
                    ans = ans + "%20";
                }else{
                    ans = ans + it;
                }
            }
            return ans;
        }
    };
    

    方法二 如果要求原地算法,就得先统计空格的个数,再算出数组的长度,从后往前放置。

    class Solution {
    public:
        string replaceSpace(string s) {
            int count = 0, len = s.size();
            // 统计空格数量
            for (char c : s) {
                if (c == ' ') count++;
            }
            // 修改 s 长度
            s.resize(len + 2 * count); //⭐
            // 倒序遍历修改
            for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
                if (s[i] != ' ')
                    s[j] = s[i];
                else {
                    s[j - 2] = '%';
                    s[j - 1] = '2';
                    s[j] = '0';
                    j -= 2;
                }
            }
            return s;
        }
    };
    
    

    剑指 Offer 52. 两个链表的第一个公共节点(简单)

    脑袋还没反应过来,手就已经做出来了hhh
    让走A链表的指针和走B链表的指针交换一下位置,当他俩开始走相同的点的时候,就是第一个公共结点。相当于(a+c)+b = (b+c)+a


    两个链表的第一个公共节点.png
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode* pa = headA;
            ListNode* pb = headB;
            while(pa != nullptr || pb!= nullptr){
                if(pa == pb) return pa;
                pa = pa ==nullptr? headB:pa->next;
                pb = pb == nullptr? headA:pb->next;
            }
            return nullptr;
            
        }
    };
    

    剑指 Offer 50. 第一个只出现一次的字符(简单)

    如果可以遍历两次也,就也一下子就写出来了

    class Solution {
    public:
        char firstUniqChar(string s) {
          if(s.empty()) return ' ';
          vector<int> dic(26,0);
          for(auto it:s){
              dic[it-'a']++;
          }
         for(auto it:s){
              if(dic[it-'a'] == 1) return it;
          }
          return  ' ';
            
        }
    };
    

    看到之前的写法是用的map

    class Solution {
    public:
        char firstUniqChar(string s) {
            unordered_map<char,int> m;
            for(auto t:s){
                m[t]++;
            }
            for(auto t :s){
                if(m[t] == 1)
                    return t;
            }
            return ' ';
            
        }
    };
    

    官方题解的用队列的方法也蛮有意思的:

    ⭐在维护队列时,我们使用了「延迟删除」这一技巧。也就是说,即使队列中有一些字符出现了超过一次,但它只要不位于队首,那么就不会对答案造成影响,我们也就可以不用去删除它。只有当它前面的所有字符被移出队列,它成为队首时,我们才需要将它移除。

    class Solution {
    public:
        char firstUniqChar(string s) {
            unordered_map<char, int> position;
            queue<pair<char, int>> q;
            int n = s.size();
            for (int i = 0; i < n; ++i) {
                if (!position.count(s[i])) {
                    position[s[i]] = i;
                    q.emplace(s[i], i);
                }
                else {
                    position[s[i]] = -1;
                    while (!q.empty() && position[q.front().first] == -1) {
                        q.pop();
                    }
                }
            }
            return q.empty() ? ' ' : q.front().first;
        }
    };
    

    相关文章

      网友评论

          本文标题:Day12 替换空格+两个链表的第一个公共节点+第一个只出现一次

          本文链接:https://www.haomeiwen.com/subject/kkipyltx.html