leetcode解题思路分析（八十三）726

原子的数量
给定一个化学式formula（作为字符串），返回每种原子的数量。

使用哈希表存储原子名和数量，使用栈来应对可能出现的括号，由此可解

class Solution { 
public:
    string countOfAtoms(string formula) { 
        int i = 0, n = formula.length();
        auto parseAtom = [&]() -> string { 
            string atom;
            atom += formula[i++]; // 扫描首字母
            while (i < n && islower(formula[i])) { 
                atom += formula[i++]; // 扫描首字母后的小写字母
            }
            return atom;
        };
        auto parseNum = [&]() -> int { 
            if (i == n || !isdigit(formula[i])) { 
                return 1; // 不是数字，视作 1
            }
            int num = 0;
            while (i < n && isdigit(formula[i])) { 
                num = num * 10 + int(formula[i++] - '0'); // 扫描数字
            }
            return num;
        };
        stack<unordered_map<string, int>> stk;
        stk.push({ });
        while (i < n) { 
            char ch = formula[i];
            if (ch == '(') { 
                i++;
                stk.push({ }); // 将一个空的哈希表压入栈中，准备统计括号内的原子数量
            } else if (ch == ')') { 
                i++;
                int num = parseNum(); // 括号右侧数字
                auto atomNum = stk.top();
                stk.pop(); // 弹出括号内的原子数量
                for (auto &[atom, v] : atomNum) { 
                    stk.top()[atom] += v * num; // 将括号内的原子数量乘上 num，加到上一层的原子数量中
                }
            } else { 
                string atom = parseAtom();
                int num = parseNum();
                stk.top()[atom] += num; // 统计原子数量
            }
        }
        auto &atomNum = stk.top();
        vector<pair<string, int>> pairs;
        for (auto &[atom, v] : atomNum) { 
            pairs.emplace_back(atom, v);
        }
        sort(pairs.begin(), pairs.end());
        string ans;
        for (auto &p : pairs) { 
            ans += p.first;
            if (p.second > 1) { 
                ans += to_string(p.second);
            }
        }
        return ans;
    }
};

自除数
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。

暴力遍历

class Solution { 
public:
    vector<int> selfDividingNumbers(int left, int right) { 
        vector<int> res;
        for (int i = left; i <= right; i ++ )               //遍历范围内每个数
        { 
            int t = i;
            bool flag = true;                               //设置一个标志位
            while (t)                                       //用t来遍历i中的位
            { 
                int div = t % 10;
                if (div == 0) flag = false;                 //只要其中有值为0的位，或者除不尽的位
                else if ((i % (t % 10)) != 0) flag = false; //就把标志位设为false
                t /= 10;
            }
            if (flag) res.push_back(i);                     //把符合条件的数放入结果数组中
        }
        return res;
    }
};

我的日程安排表1
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。

使用set即可

class MyCalendar { 
private:
    map<int, int> m;
public:
    MyCalendar() { 
    }
    bool book(int start, int end) { 
        // start 已重复
        if (m.find(start) != m.end())
        { 
            return false;
        }
        auto pos = m.emplace(start, end).first;
        // 和上一个比较
        if (pos != m.begin())
        { 
            --pos;
            if (pos->second > start)
            { 
                m.erase(start);
                return false;
            }
            // 恢复回去
            ++pos;
        }
        // 和下一个比较
        ++pos;
        if (pos != m.end())
        { 
            if (pos->first < end)
            { 
                m.erase(start);
                return false;
            }
        }
        return true;
    }
};
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar* obj = new MyCalendar(); * bool param_1 = obj->book(start,end); */

统计不同回文子序列
给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。

动态规划求解

class Solution { 
public:
    int countPalindromicSubsequences(string s) { 
        int n = s.size();
        vector<vector<int>> f(n,vector<int>(n,0));
        for(int i=0;i<n;i++)f[i][i]=1;
        const int mod = 1e9+7;
        for(int i=n-2;i>=0;i--)
        { 
            for(int j=i+1;j<n;j++)
            { 
                if(s[i]!=s[j])f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
                else
                { 
                    f[i][j] = f[i+1][j-1]*2+2;
                    int l=i+1,r=j-1;
                    while(l<=r&&s[l]!=s[i])l++;
                    while(l<=r&&s[r]!=s[i])r--;
                    // 第2.1种情况 中间有1个s[i]
                    if(l==r)f[i][j]--;
                    // 第2.2种情况 中间有≥2个s[i]
                    else if(l<r)f[i][j] -=2+f[l+1][r-1];
                }
                f[i][j]=(f[i][j]>=0)?f[i][j]%mod:f[i][j]+mod;
            }
        }
        return f[0][n-1];
    }
};

我的日程安排表2
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

用数组存储每个区间以及存储twice的情况，判断twice，加入则加入普通存储

class MyCalendarTwo { 
    vector<vector<int>> datas;
    vector<vector<int>> twice;
    bool find(int start, int end)
    { 
        for (const vector<int>& d : twice)
        { 
            if (!(d[0] >= end || d[1] <= start))
                return true;
        }
        return false;
    }
public:
    MyCalendarTwo() { 
        datas.clear();
        twice.clear();
    }
    bool book(int start, int end) { 
        if (find(start, end))
            return false;
        for (const vector<int>& d : datas)
        { 
            if (!(d[0] >= end || d[1] <= start))
                twice.push_back({ max(d[0], start), min(end, d[1])});
        }
        datas.push_back({ start, end});
        return true;
    }
};
/** * Your MyCalendarTwo object will be instantiated and called as such: * MyCalendarTwo* obj = new MyCalendarTwo(); * bool param_1 = obj->book(start,end); */

我的日程安排表2
给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

线段树处理。

const int MX = 1e5 + 5;
const int M = 1e9;
class MyCalendarThree { 
public:
    int ls[MX], rs[MX], sum[MX], lz[MX];
    int cnt, root;
    MyCalendarThree() { 
        ls[0] = rs[0] = sum[0] = lz[0] = 0;
        cnt = 0;
        root = ++cnt;
        init_node(root);
    }
    void init_node(int rt) { 
        ls[rt] = rs[rt] = sum[rt] = lz[rt] = 0;
    }
    void PushUP(int rt) { 
        int l = ls[rt], r = rs[rt];
        sum[rt] = max(sum[l] + lz[l], sum[r] + lz[r]);
    }
    void update(int L, int R, int l, int r, int &rt) { 
        if(rt == 0) { 
            rt = ++cnt;
            init_node(rt);
        }
        if(L <= l && R >= r) { 
            lz[rt]++;
            return;
        }
        int m = (l + r) >> 1;
        if(L <= m) update(L, R, l, m, ls[rt]);
        if(R > m) update(L, R, m + 1, r, rs[rt]);
        PushUP(rt);
    }
    int book(int l, int r) { 
        if(l < r) update(l, r - 1, 0, M, root);
        return sum[root] + lz[root];
    }
};

图像渲染
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

dfs和bfs的简单运用

class Solution { 
public:
    const int dx[4] = { 1, 0, 0, -1};
    const int dy[4] = { 0, 1, -1, 0};
    void dfs(vector<vector<int>>& image, int x, int y, int color, int newColor) { 
        if (image[x][y] == color) { 
            image[x][y] = newColor;
            for (int i = 0; i < 4; i++) { 
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size()) { 
                    dfs(image, mx, my, color, newColor);
                }
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { 
        int currColor = image[sr][sc];
        if (currColor != newColor) { 
            dfs(image, sr, sc, currColor, newColor);
        }
        return image;
    }
};