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

剑指 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;
    }
};