leetcode解题思路分析（四十七）402 - 408 题

ゝ一纸荒年。 2022-12-17 09:59 150阅读 0赞

1.  移掉K位数字  
    给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

**使用栈存储并遍历，逐个剔除大数，最后再去掉0即可**

class Solution { 
    public:
        string removeKdigits(string num, int k) { 
            string res;
            int n = num.size(), m = n - k;        
            for (char c : num) { 
                while (k && res.size() && res.back() > c) { 
                    res.pop_back();
                    --k;
                }
                res.push_back(c);
            }
            res.resize(m);
            //去除前导0， 如10200，k = 1
            while (!res.empty() && res[0] == '0') { 
                res.erase(res.begin());
            }
            return res.empty() ? "0" : res;
        }
    };

1.  青蛙过河  
    如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河。

**本题思路是理清楚第x个石头和后面一次石头的关系，假设第x个石头用了y步到达，则下一个石头可能是x + y, y, 或者 x + y - 1, y -1 或者 x + y + 1， y + 1三种其一，反之亦然。存储对应键值对即可得解**

class Solution { 
    public:
        bool canCross(vector<int>& stones) { 
            unordered_set<int> h;
            for(auto x:stones) h.insert(x);
            unordered_map<long long, bool> memo;
            
            function<bool(int,int)> dfs = [&] (int x, int y) { 
                if(y<=0 || !h.count(x)) return false;
                if(x==1&&y==1) return true;
                
                long long t = (long long)x<<32|y;
                if(memo.count(t)) return memo[t];
                
                if(dfs(x-y,y)||dfs(x-y,y-1)||dfs(x-y,y+1))
                    return memo[t] = true;
                return memo[t] = false;
            };
            
            for(int i = 1 ; i <= 1001 ; i ++)
                if(dfs(stones.back(),i))
                    return true;
            return false;
        }
    };

1.  左叶子之和

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
        int m_ret = 0;
    public:
        int sumOfLeftLeaves(TreeNode* root) { 
            getSum(root);
            return m_ret;
        }
    
        void getSum(TreeNode *root)
        { 
            if (root == NULL) 
                return;
            
            if (root->left != NULL)
            { 
                if (root->left->left == NULL && root->left->right == NULL)
                { 
                    m_ret += root->left->val;
                }
                else getSum(root->left);
            }
            getSum(root->right);
        }
    };

1.  数字转换为16进制  
    给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

**计算机原生2进制，转化16进制即四位一判断即可**

class Solution { 
    public:
        string toHex(int num1) 
        { 
            if(num1 == 0) 
                return "0";
            string res = "";
            string hex[16] = { "0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};
            unsigned int num2 = num1;
            while (num2 != 0)
            { 
                res = hex[num2 % 16] + res;  
                num2 /= 16;
            }
            return res;
        }
    };

1.  根据身高建队列  
    假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

**先排身高更高的，这是要防止后排入人员影响先排入人员位置。同身高需要按k升序排序，否则插入位置会越界  
每次排入新人员\[h,k\]时，已处于队列的人身高都>=h，所以新排入位置就是people\[k\]**

class Solution { 
    public:
        vector<vector<int>> reconstructQueue(vector<vector<int>>& people) { 
            // 排序
            sort(people.begin(), people.end(),
                    [](const vector<int>& lhs, const vector<int>& rhs)
                     { return lhs[0] == rhs[0] ? lhs[1] <= rhs[1] : lhs[0] > rhs[0];});
            int len = people.size();
            list<vector<int>> tmp;
            // 循环插入
            for(int i = 0; i < len; ++i){ 
                auto pos = tmp.begin();
                advance(pos, people[i][1]);
                tmp.insert(pos, people[i]);
            }
            // 重建vector返回
            return vector<vector<int>>(tmp.begin(), tmp.end());
        }
    };

1.  接雨水2  
    给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

**本题思路和接雨水1类似，即短板效应寻找，采用堆是一个比较好的选择。**

class Solution { 
    public:
        int trapRainWater(vector<vector<int>>& g) { 
            typedef pair<int, pair<int, int>> PIII;
            int n = g.size(), m = g[0].size();
            
            vector<vector<bool>> st(n, vector<bool>(m, false));
            priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
            
            for (int i = 0; i < n; i ++ )
            { 
                st[i][0] = st[i][m - 1] = true;
                heap.push({ g[i][0], { i, 0}});
                heap.push({ g[i][m - 1], { i, m - 1}});
            }
    
            for (int j = 0; j < m; j ++ )
            { 
                st[0][j] = st[n - 1][j] = true;
                heap.push({ g[0][j], { 0, j}});
                heap.push({ g[n - 1][j], { n - 1, j}});
            }
            
            int res = 0;
            int dx[] = { -1, 0, 1, 0}, dy[] = { 0, 1, 0, -1};
            while (heap.size())
            { 
                auto t = heap.top();
                heap.pop();
    
                for (int k = 0; k < 4; k ++ )
                { 
                    int x = t.second.first, y = t.second.second, h = t.first;
                    int a = x + dx[k], b = y + dy[k];
                    if (a >= 0 && a < n && b >= 0 && b < m)
                    { 
                        if (st[a][b] == false)
                        { 
                            st[a][b] = true;
                            if (h > g[a][b]) res += h - g[a][b];
                            heap.push({ max(g[a][b], h), { a, b}});
                        }
                    }
                }
            }
    
            return res;
        }
    };

1.  最长回文串  
    给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

**本题很简单，遍历一遍然后把偶数算上，奇数-1算上，就结束了**

class Solution { 
    public:
        int longestPalindrome(string s) { 
            unordered_map<char, int> count;
            int ans = 0;
            for (char c : s)
                ++count[c];
            for (auto p : count) { 
                int v = p.second;
                ans += v / 2 * 2;
                if (v % 2 == 1 and ans % 2 == 0)
                    ++ans;
            }
            return ans;
        }
    };