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

快来打我* 2022-10-19 14:55 158阅读 0赞

1.  原子的数量  
    给定一个化学式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;
        }
    };

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

**暴力遍历**

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.  我的日程安排表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); */

1.  统计不同回文子序列  
    给定一个字符串 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];
        }
    };

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); */

1.  我的日程安排表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];
        }
    };

1.  图像渲染  
    有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 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;
        }
    };