当前位置：首页 > news >正文

leetcode解题思路分析（一百三十六）1158 - 1169 题

news 来源：原创 2024/4/20 9:39:40

市场分析 I
请写出一条SQL语句以查询每个用户的注册日期和在 2019 年作为买家的订单总数。

left join 和 group by

# Write your MySQL query statement below
select Users.user_id as buyer_id, join_date, ifnull(UserBuy.cnt, 0) as orders_in_2019
from Users
left join (
    select buyer_id, count(order_id) cnt 
    from Orders
    where order_date between '2019-01-01' and '2019-12-31'
    group by buyer_id
) UserBuy
on Users.user_id = UserBuy.buyer_id

拼写单词
返回词汇表 words 中你掌握的所有单词的长度之和。

哈希表记录即可

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> chars_cnt;
        for (char c : chars) {
            ++chars_cnt[c];
        }
        int ans = 0;
        for (string word : words) {
            unordered_map<char, int> word_cnt;
            for (char c : word) {
                ++word_cnt[c];
            }
            bool is_ans = true;
            for (char c : word) {
                if (chars_cnt[c] < word_cnt[c]) {
                    is_ans = false;
                    break;
                }
            }
            if (is_ans) {
                ans += word.size();
            }
        }
        return ans;
    }
};

最大层内元素和
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。请返回层内元素之和最大的那几层（可能只有一层）的层号，并返回其中最小的那个。

层序遍历再判断即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) 
    {
        int ret    = 0;
        int maxSum = INT_MIN;
        int level  = 1;

        queue<TreeNode*> TreeQueue;

        if (root)
            TreeQueue.push(root);

        while (TreeQueue.size())
        {
            int cnt = TreeQueue.size();
            int sum = 0;

            for (int i = 0; i < cnt; ++i)
            {
                TreeNode* pNode = TreeQueue.front();
                sum += pNode->val;

                TreeQueue.pop();
                if (pNode->left)  TreeQueue.push(pNode->left);
                if (pNode->right) TreeQueue.push(pNode->right);
            }

            if (sum > maxSum)
            {
                maxSum = sum;
                ret = level;
            }

            level++;
        }

        return ret;
    }
};

地图分析
你现在手里有一份大小为 n x n 的网格 grid，上面的每个单元格都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

本题本质上是对每个海洋单元格找最近陆地距离，然后将这些距离进行比较取最大值。因此可以看成是一个源点（虚拟源点，到各个陆地节点均有权为0的联通线）到各个海洋单元格的最小距离问题，或者是一个动态规划问题（对于每个海洋区域 (x, y)(x,y)，离它最近的陆地区域到它的路径要么从上方或者左方来，要么从右方或者下方来。考虑做两次动态规划，第一次从左上到右下，第二次从右下到左上，记 f(x, y)f(x,y) 为 (x, y)(x,y) 距离最近的陆地区域的曼哈顿距离，则可以简单的推出转移方程）。

// dijkstra
class Solution {
public:
    static constexpr int MAX_N = 100 + 5;
    static constexpr int INF = int(1E6);
    static constexpr int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int n;
    int d[MAX_N][MAX_N];

    struct Status {
        int v, x, y;
        bool operator < (const Status &rhs) const {
            return v > rhs.v;
        }
    };

    priority_queue <Status> q;

    int maxDistance(vector<vector<int>>& grid) {
        this->n = grid.size();
        auto &a = grid;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = INF;
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (a[i][j]) {
                    d[i][j] = 0;
                    q.push({0, i, j});
                }
            }
        }

        while (!q.empty()) {
            auto f = q.top(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = f.x + dx[i], ny = f.y + dy[i];
                if (!(nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= n - 1)) {
                    continue;
                }
                if (f.v + 1 < d[nx][ny]) {
                    d[nx][ny] = f.v + 1;
                    q.push({d[nx][ny], nx, ny});
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!a[i][j]) {
                    ans = max(ans, d[i][j]);
                }
            }
        }

        return (ans == INF) ? -1 : ans;
    }
};



// DP
class Solution {
public:
    static constexpr int MAX_N = 100 + 5;
    static constexpr int INF = int(1E6);
    
    int f[MAX_N][MAX_N];
    int n;

    int maxDistance(vector<vector<int>>& grid) {
        this->n = grid.size();
        vector<vector<int>>& a = grid;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                f[i][j] = (a[i][j] ? 0 : INF);
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (a[i][j]) {
                    continue;
                }
                if (i - 1 >= 0) {
                    f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                }
                if (j - 1 >= 0) {
                    f[i][j] = min(f[i][j], f[i][j - 1] + 1);
                }
            }
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (a[i][j]) {
                    continue;
                }
                if (i + 1 < n) {
                    f[i][j] = min(f[i][j], f[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    f[i][j] = min(f[i][j], f[i][j + 1] + 1);
                }
            }
        }

        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!a[i][j]) {
                    ans = max(ans, f[i][j]);
                }
            }
        }

        if (ans == INF) {
            return -1;
        } else {
            return ans;
        }
    }
};

按字典序排在最后的子串
给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

贪心思想：
最终返回所有子串中字典序最大的子串，这个子串的开始一定是字符串中的最大字符，否则不可能为最大子串。
字符串中以s[i]开始的字符串，字符串长度越长，最终排序越大，因此最终返回结果一定为后缀字符串。

class Solution {
public:
    // 双指针解法, 最终结果一定为后缀字符串， 且最后的子串开始字符一定为串中的最大字符
    string lastSubstring(string s) {
        int n = s.size(), pos = n - 1;
        char maxChar = s[n - 1];    // 存放字符串中的最大字符
        for (int i = n - 2; i >= 0; i--) {    // 从后向前遍历, 找到最大字符出现的第一个位置
            if (s[i] >= maxChar) pos = i, maxChar = s[i];
        }
        int r = pos + 1, j, k;  // pos指向最大字符串的开始位置
        while (r < n) {
            if (s[r] != maxChar) {  // 不是最大字符，右移
                r++;
            } else {    // 找到下一个最大字符，通过比较决定是否更新pos
                j = pos + 1, k = r + 1;
                while (j < r && k < n) {    // 限制比较范围
                    if (s[j] == s[k]) j++, k++;
                    else {
                        if (s[j] < s[k]) { pos = r; r = pos + 1; }    // 更新pos，最大字符串发生变化
                        else r = k + 1;   // pos不变，最大字符串长度增加
                        break;
                    } 
                }
                if (j == r || k == n) r = k;  // pos不变，最大字符串长度增加
            }
        }
        return s.substr(pos);   // 返回以pos开始的后缀字符串
    }
};

查询无效交易
如果出现下述两种情况，交易可能无效：
交易金额超过 $1000
或者，它和另一个城市中同名的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）
给定字符串数组交易清单 transaction 。每个交易字符串 transactions[i] 由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。
返回 transactions，返回可能无效的交易列表。你可以按任何顺序返回答案。

按题意设计即可。



struct Transaction
{
    int id;
    int time;
    int amount;
    string city;
    string full;

    Transaction(int id, int time, int amount, string city, string& full) : id(id), time(time), amount(amount), city(city), full(full)
    {}

    // bool operator <(const Transaction &s) const
    // {
    //     return time < s.time;
    // }
};

class Solution {
private:
    vector<string> SplitStrings(const string& str)
    {
        vector<string> res;
        stringstream ss(str);
        string curr;
        while(std::getline(ss, curr, ','))
        {
            res.push_back(curr);
        }
        return res;
    }

public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        // 映射表
        unordered_map<string, vector<Transaction>> name2transactions;

        // 返回结果
        vector<string> res;

        // 记录是否已经输出，避免重复
        int n = transactions.size();
        bool hasReturn[n];
        memset(hasReturn, 0, sizeof(hasReturn));

        // 遍历transaction并判断
        for (int i = 0; i < n; ++i)
        {
            vector<string> strs = SplitStrings(transactions[i]);
            string name = strs[0];
            int time = stoi(strs[1]);
            int amount = stoi(strs[2]);
            string city = strs[3];

            if (amount > 1000)
            {
                hasReturn[i] = true;
                res.push_back(transactions[i]);
            }

            // 遍历当前的vector<Transaction>
            for (Transaction& t : name2transactions[name])
            {
                // 判断是否合规
                if (abs(time - t.time) <= 60 && city != t.city)
                {
                    // 不合规需要加到返回结果里
                    if (!hasReturn[t.id])
                    {
                        hasReturn[t.id] = true;
                        res.push_back(t.full);
                    }
                    if (!hasReturn[i])
                    {
                        hasReturn[i] = true;
                        res.push_back(transactions[i]);
                    }
                }
            }

            name2transactions[name].emplace_back(Transaction(i, time, amount, city, transactions[i]));
        }

        return res;
    }
};