leetcode刷题记录——2024年1月-能不能吃完饭再说

2487、从链表中移除节点——递归、单调栈

整个过程可以理解为维护一个递减的栈，栈中的节点是按照从大到小的顺序排列的。每遇到一个新节点时，如果栈顶节点的值大于当前节点的值，则将栈顶节点替换为当前节点，即删除栈顶节点，并将当前节点压入栈中。这样最终栈中留下的节点就是需要保留的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *removeNode(ListNode *head,
                         stack<ListNode *> &st)
    {
        if (head == nullptr)
        {
            return nullptr;
        }
        head->next = removeNode(head->next, st);
        if (st.empty())
        {
            st.push(head);
        }
        else
        {
            if (st.top()->val > head->val)
            {
                delete head;
                return st.top();
            }
            else
            {
                st.push(head);
            }
        }
        return head;
    }

    ListNode *removeNodes(ListNode *head)
    {
        stack<ListNode *> st;
        return removeNode(head, st);
    }
};

63、不同路径Ⅱ——动态规划

对于每个位置(i, j)，遍历方向数组dirs中的每个方向。
检查当前位置的上方和左方是否是合法的位置（即不越界），并且上方和左方的位置不是障碍物（值为0）。
如果满足上述条件，将当前位置(i, j)的路径数量dp[i][j]增加上方位置(i+dir.first, j+dir.second)和左方位置(i+dir.first, j+dir.second)的路径数量之和。
如果终点是障碍物，即obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]等于1，说明无法到达终点，返回0；否则返回dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]。

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        vector<vector<int>> dp(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));
        dp[0][0] = 1;
        vector<pair<int, int>> dirs = {
            {-1, 0},
            {0, -1},
        };
        for (int i = 0; i < obstacleGrid.size(); i++)
        {
            for (int j = 0; j < obstacleGrid[0].size(); j++)
            {
                for (auto dir : dirs)
                {
                    if (i + dir.first >= 0 &&
                        j + dir.second >= 0 &&
                        obstacleGrid[i + dir.first][j + dir.second] == 0)
                    {
                        dp[i][j] += dp[i + dir.first][j + dir.second];
                    }
                }
            }
        }
        return obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1] == 1 ? 0 : dp[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1];
    }
};

2397、被列覆盖的最多行数——回溯

用一个unordered_set来存储选中的列，当选中的列数量等于numSelect时判断被覆盖的最多行数。使用回溯遍历所有选择情况。

class Solution
{
private:
    int maxCovered;

public:
    int numOfCovered(vector<vector<int>> &matrix,
                     unordered_set<int> &selected)
    {
        int ret = matrix.size();
        for (size_t i = 0; i < matrix.size(); i++)
        {
            int flag = 0;
            for (size_t j = 0; j < matrix[0].size(); j++)
            {
                if (selected.find(j) == selected.end())
                {
                    flag |= matrix[i][j];
                    if (flag)
                    {
                        ret--;
                        break;
                    }
                }
            }
        }
        return ret;
    }

    void backtrack(vector<vector<int>> &matrix,
                   unordered_set<int> &selected,
                   int col,
                   int numSelect)
    {
        if (selected.size() == numSelect)
        {
            maxCovered = max(maxCovered, numOfCovered(matrix, selected));
            return;
        }
        for (int i = col; i < matrix[0].size(); i++)
        {
            selected.insert(i);
            backtrack(matrix, selected, i + 1, numSelect);
            selected.erase(i);
        }
    }

    int maximumRows(vector<vector<int>> &matrix,
                    int numSelect)
    {
        maxCovered = -1;
        unordered_set<int> selected;
        backtrack(matrix, selected, 0, numSelect);
        return maxCovered;
    }
};

447、回旋镖的数量——哈希表

对于给定的点集 points 中的每个点 p，执行以下操作：

创建一个哈希表 cnt，用于统计 p 到其他点的距离出现的次数。
对于 points 中的每个点 q，计算 p 到 q 的距离，并将距离的平方作为键，值加1存入哈希表 cnt 中。
遍历哈希表 cnt，对于每个距离出现次数大于等于2的项，假设出现次数为 m，则将 m * (m - 1) 加到 ans 中。

class Solution
{
public:
    int numberOfBoomerangs(vector<vector<int>> &points)
    {
        int ans = 0;
        for (auto &p : points)
        {
            unordered_map<int, int> cnt;
            for (auto &q : points)
            {
                int dis = (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
                ++cnt[dis];
            }
            for (auto &[_, m] : cnt)
            {
                ans += m * (m - 1);
            }
        }
        return ans;
    }
};

2696、删除子串后的字符串最小长度——栈

如果栈stk为空，将当前字符入栈。

如果栈stk不为空，判断栈顶元素stk.top()与当前字符s[i]的映射关系。如果它们是映射关系中的一对，即map[stk.top()] == s[i]，则将栈顶元素出栈。

如果它们不是映射关系中的一对，将当前字符入栈。

遍历完字符串后，栈stk中剩余的字符数量就是需要删除的最少字符数量。我们将栈中剩余的字符全部出栈，并将出栈的次数累计到变量ret中。

class Solution
{
public:
    int minLength(string s)
    {
        stack<char> stk;
        unordered_map<char, char> map;
        map['A'] = 'B';
        map['C'] = 'D';
        int ret = 0;
        for (size_t i = 0; i < s.length(); i++)
        {
            if (stk.empty())
            {
                stk.push(s[i]);
            }
            else
            {
                if (map[stk.top()] == s[i])
                {
                    stk.pop();
                }
                else
                {
                    stk.push(s[i]);
                }
            }
        }
        while (!stk.empty())
        {
            stk.pop();
            ret++;
        }
        return ret;
    }
};

2085、统计出现过一次的公共字符串——哈希表

略

class Solution
{
public:
    int countWords(vector<string> &words1,
                   vector<string> &words2)
    {
        unordered_map<string, pair<int, int>> mp;
        for (string &word : words1)
        {
            if (mp.find(word) != mp.end())
            {
                mp[word].first++;
            }
            else
            {
                mp[word] = make_pair(1, 0);
            }
        }
        for (string &word : words2)
        {
            if (mp.find(word) != mp.end())
            {
                mp[word].second++;
            }
        }
        int res = 0;
        for (auto &item : mp)
        {
            if (item.second.first == 1 &&
                item.second.second == 1)
            {
                res++;
            }
        }
        return res;
    }
};

82、删除排序链表中的重复元素——双指针

当发现当前节点的下一个节点值和下下一个节点的值相同时，就存在至少两个重复序列，需要删除此重复序列。使用一个循环找到第一个不等于当前节点的下一个节点值的节点，然后将当前节点的 next 指针指向这个节点，同时删除重复的节点。需要注意空节点的判断。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (!head) {
            return head;
        }
        ListNode *ret = new ListNode(0);
        ret->next = head;
        ListNode *cur = ret;
        while (cur->next && cur->next->next)
        {
            if (cur->next->val == cur->next->next->val)
            {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x)
                {
                    ListNode *del = cur->next;
                    cur->next = cur->next->next;
                    delete del;
                }
            }else{
                cur = cur->next;
            }
        }
        return ret->next;
    }
};

2744、最大字符串配对数目——哈希表

如果当前遍历的字符串存在集合中，则配对数目加一，否则将字符串反转后插入集合。

class Solution
{
public:
    int maximumNumberOfStringPairs(vector<string> &words)
    {
        unordered_set<string> set;
        int ret = 0;
        for (string &word : words)
        {
            if (set.find(word) != set.end())
            {
                ret++;
            }
            else
            {
                reverse(word.begin(), word.end());
                set.insert(word);
            }
        }
        return ret;
    }
};

2788、按分隔符拆分字符串

略

class Solution
{
public:
    vector<string> splitWordsBySeparator(vector<string> &words, char separator)
    {
        vector<string> ret;
        for (string &str : words)
        {
            string tmp;
            for (size_t i = 0; i < str.length(); i++)
            {
                if (str[i] != separator)
                {
                    tmp += str[i];
                }
                else if (tmp.length() > 0)
                {
                    ret.push_back(tmp);
                    tmp.clear();
                }
            }
            if (tmp.length() > 0)
            {
                ret.push_back(tmp);
                tmp.clear();
            }
        }
        return ret;
    }
};

135、分发糖果——贪心

每个孩子至少分配到 1 个糖果，所以初始时将所有孩子的糖果数初始化为 1。

如果一个孩子的评分比其左边的孩子高，那么根据题目要求，他应该比左边的孩子获得更多的糖果。所以我们可以将这个孩子的糖果数设置为左边孩子的糖果数加 1。

同样地，如果一个孩子的评分比其右边的孩子高，那么他应该比右边的孩子获得更多的糖果。所以我们可以在从右到左的遍历中，将当前孩子的糖果数与右边孩子的糖果数加 1 后的较大值赋给当前孩子的糖果数。

class Solution
{
public:
    int candy(vector<int> &ratings)
    {
        vector<int> candy(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++)
        {
            if (ratings[i] > ratings[i - 1])
            {
                candy[i] = candy[i - 1] + 1;
            }
        }
        int sum = candy[ratings.size() - 1];
        for (int i = ratings.size() - 2; i >= 0; i--)
        {
            if (ratings[i] > ratings[i + 1])
            {
                candy[i] = max(candy[i], candy[i + 1] + 1);
            }
            sum += candy[i];
        }
        return sum;
    }
};

68、文本左右对齐——贪心

使用了一个临时数组 tmp 来存储当前行的单词，以及变量 tmp_len 和 word_count 来记录当前行的字符长度和单词数量。

迭代遍历输入的单词列表。对于每个单词，它首先计算将该单词加入到当前行后的字符长度 tmp_len + word.length()。

然后根据当前行的字符长度，判断是否需要换行：

如果 tmp_len + word_count > maxWidth，说明当前行已经超过最大宽度，需要进行换行操作。
如果 tmp_len + word_count == maxWidth，说明当前行正好达到最大宽度，需要将当前行添加到结果列表中然后换行。
否则，将当前单词加入到当前行中。

在第一种情况的换行操作中，首先计算当前行需要填充的空格数 space_count。如果当前行只有一个单词（即 tmp.size() == 1），则直接将该单词添加到行末尾，并在行末尾填充剩余的空格。

如果当前行有多个单词，则计算每个单词间隔应有的空格数 every 和剩余的空格数 left（分配给前面单词的空隙）。然后通过循环遍历 tmp 数组，将单词和相应数量的空格添加到行中。在循环结束后，如果行的长度小于最大宽度，再在行末尾填充剩余的空格。

在每次换行操作或达到最大宽度的情况下，都会清空临时数组 tmp 和相关的计数器，并将处理后的行添加到结果列表中。

处理完所有的单词后，还需要处理最后一行。如果 tmp 数组中还有剩余的单词，就将它们拼接成一行，并在行末尾填充剩余的空格。

class Solution
{
public:
    vector<string> fullJustify(vector<string> &words,
                               int maxWidth)
    {
        vector<string> ret;
        vector<string> tmp;
        int tmp_len = 0;
        int word_count = 0;
        for (string &word : words)
        {
            tmp_len += word.length();
            // 如果加上当前单词后，长度大于最大宽度，说明需要换行
            if (tmp_len + word_count > maxWidth)
            {
                int space_count =
                    maxWidth - tmp_len + word.length() - tmp.size() + 1;
                string line = "";
                if (tmp.size() == 1)
                {
                    line += tmp[0];
                    line += string(maxWidth - line.length(), ' ');
                }
                else
                {
                    int left = space_count % (tmp.size() - 1);
                    int every = space_count / (tmp.size() - 1);
                    for (size_t i = 0; i < tmp.size(); i++)
                    {
                        if (i < left)
                        {
                            line += tmp[i] + " ";
                            fill_n(back_inserter(line), every + 1, ' ');
                        }
                        else if (i == tmp.size() - 1)
                        {
                            line += tmp[i];
                        }
                        else
                        {
                            line += tmp[i] + " ";
                            fill_n(back_inserter(line), every, ' ');
                        }
                    }
                    if (line.length() < maxWidth)
                    {
                        line += string(maxWidth - line.length(), ' ');
                    }
                }
                ret.push_back(line);

                tmp.clear();
                tmp.push_back(word);
                tmp_len = word.length();
                word_count = 1;
            }
            // 如果加上当前单词，包括空格正好满一行
            else if (tmp_len + word_count == maxWidth)
            {
                tmp.push_back(word);
                string line = "";
                for (string &str : tmp)
                {
                    line += str + " ";
                }
                line.pop_back();
                ret.push_back(line);

                tmp.clear();
                tmp_len = 0;
                word_count = 0;
            }
            // 否则将当前单词纳入当前行
            else
            {
                tmp.push_back(word);
                word_count++;
            }
        }
        // 处理最后一行
        if (tmp.size() > 0)
        {
            string line = "";
            for (string &str : tmp)
            {
                line += str + " ";
            }
            line.pop_back();
            if (line.length() < maxWidth)
            {
                line += string(maxWidth - line.length(), ' ');
            }
            ret.push_back(line);
        }
        return ret;
    }
};

2859、计算 K 置位下标对应元素和——位运算

位运算，bitset直接秒了

class Solution
{
public:
    int sumIndicesWithKSetBits(vector<int> &nums,
                               int k)
    {
        int ret = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            int bit = 0;
            bitset<32> bs(i);
            for (int j = 0; j < 32; ++j)
            {
                bit += bs[j] == 1 ? 1 : 0;
            }
            ret += bit == k ? nums[i] : 0;
        }
        return ret;
    }
};

30、非串联所有单词的子串——滑动窗口

外层循环用于遍历所有可能的起始位置，从 0 到 word_len - 1，这样在内层遍历时就能够按照 words 中单个字符串长度进行滑动窗口的移动了，而不需要一个字符一个字符的移动窗口。比如对于字符串s = abcasdsaf ，单个字符串长度为3，那么就可以将字符串s划分为三次迭代，为 abcasdsaf、bcasdsaf、casdsaf。

内层循环用于滑动窗口，从当前起始位置开始，每次移动 word_len 的距离。对于刚刚的 abcasdsaf、bcasdsaf、casdsaf，外层第一次迭代内层可以遍历abcasd、asdsaf，外层第二次迭代内层可以遍历bcasds，外层第三次迭代内层可以遍历casdsa，这样就把字符串s中的所有长度符合的子串都遍历过了。只需要使用哈希表统计子串中单词的出现频率是否符合即可。

class Solution
{
public:
    vector<int> findSubstring(string s,
                              vector<string> &words)
    {
        vector<int> ret;
        int word_len = words[0].size();
        int substr_len = words.size() * word_len;
        unordered_map<string, int> words_map;
        for (string &word : words)
        {
            words_map[word]++;
        }
        for (size_t i = 0; i < word_len; i++)
        {
            for (size_t j = i; j < s.length() - substr_len + 1; j = j + word_len)
            {
                unordered_map<string, int> tmp_map;
                string tmp = s.substr(j, substr_len);
                for (size_t k = 0; k < words.size(); k++)
                {
                    tmp_map[tmp.substr(k * word_len, word_len)]++;
                }
                if (tmp_map == words_map)
                {
                    ret.push_back(j);
                }
            }
        }
        return ret;
    }
};

这个方法是一个字符一个字符移动的，显然会超时

class Solution
{
public:
    vector<int> findSubstring(string s,
                              vector<string> &words)
    {
        vector<int> ret;
        int word_len = words[0].size();
        int substr_len = words.size() * word_len;
        unordered_map<string, int> words_map;
        for (string &word : words)
        {
            words_map[word]++;
        }
        for (size_t i = 0; i < s.length() - substr_len + 1; i++)
        {
            unordered_map<string, int> tmp_map;
            bool flag = true;
            for (size_t j = i; j < i + substr_len; j = j + word_len)
            {
                string tmp = s.substr(j, word_len);
                if (words_map.find(tmp) == words_map.end())
                {
                    flag = false;
                    break;
                }
                else
                {
                    tmp_map[tmp]++;
                    if (tmp_map[tmp] > words_map[tmp])
                    {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag && tmp_map.size() == words_map.size())
            {
                ret.push_back(i);
            }
        }
        return ret;
    }
};

365、水壶问题——广度优先搜索

使用栈（stk）来保存搜索过程中的状态，每个状态表示两个水壶的当前水量。使用一个哈希集合（visited）来记录已经访问过的状态，避免重复搜索（使用了一个lambda表达式(hash_function)来定义哈希函数，保证unordered_set能够正确地处理pair类型的键值。）。

算法的思路是从初始状态（0, 0）开始，不断进行倒水操作，直到达到目标状态。具体的操作包括：

倒满jug1：将当前状态的第一个水壶的水量设为jug1Capacity，第二个水壶的水量不变。
倒满jug2：将当前状态的第一个水壶的水量不变，第二个水壶的水量设为jug2Capacity。
倒空jug1：将当前状态的第一个水壶的水量设为0，第二个水壶的水量不变。
倒空jug2：将当前状态的第一个水壶的水量不变，第二个水壶的水量设为0。
从jug1倒到jug2：将当前状态的第一个水壶的水量减去能倒入第二个水壶的水量，第二个水壶的水量设为两个水壶的水量之和对jug2Capacity取余。
从jug2倒到jug1：将当前状态的第二个水壶的水量减去能倒入第一个水壶的水量，第一个水壶的水量设为两个水壶的水量之和对jug1Capacity取余。

在每次操作之后，将得到的新状态压入栈中继续搜索，直到栈为空或者找到目标状态。如果最终栈为空仍然没有找到目标状态，则返回false。

typedef pair<int, int> PII;
class Solution
{
public:
    bool canMeasureWater(int jug1Capacity,
                         int jug2Capacity,
                         int targetCapacity)
    {
        stack<PII> stk;
        auto hash_function = [](const PII &o)
        { return hash<int>()(o.first) ^ hash<int>()(o.second); };
        unordered_set<PII, decltype(hash_function)>
            visited(0, hash_function);
        stk.push({0, 0});
        while (!stk.empty())
        {
            if (visited.find(stk.top()) != visited.end())
            {
                stk.pop();
                continue;
            }
            visited.emplace(stk.top());
            PII node = stk.top();
            stk.pop();
            if (node.first == targetCapacity ||
                node.second == targetCapacity ||
                node.first + node.second == targetCapacity)
            {
                return true;
            }
            // fill 1
            stk.push({jug1Capacity, node.second});
            // fill 2
            stk.push({node.first, jug2Capacity});
            // empty 1
            stk.push({0, node.second});
            // empty 2
            stk.push({node.first, 0});
            // 1 to 2
            stk.push({0, (node.first + node.second) % jug2Capacity});
            // 2 to 1
            stk.push({(node.first + node.second) % jug1Capacity, 0});
        }
        return false;
    }
};

36、有效的数独——哈希表

创建了一个名为box的二维向量，用于存储每个3x3小方格中已经出现的数字。box的维度为3x3，每个元素是一个无序集合（unordered_set<char>），用于存储小方格中已经出现的数字。

使用两个嵌套的for循环遍历数独的每个格子。外层循环迭代行（变量i），内层循环迭代列（变量j）。在每个格子的位置，首先检查当前行、当前列和当前小方格中是否已经出现了当前数字。如果在任何一个位置已经出现了当前数字，说明数独无效，直接返回false。如果当前格子的值不是.（代表空格），则将当前数字插入到当前行和当前小方格的集合中。内层循环结束后，清空当前行和当前列的集合，为下一行或下一列做准备。外层循环结束后，如果没有发现无效的数字，则返回true，表示数独有效。

class Solution
{
public:
    bool isValidSudoku(vector<vector<char>> &board)
    {
        vector<vector<unordered_set<char>>>
            box(3, vector<unordered_set<char>>(3));
        for (size_t i = 0; i < 9; i++)
        {
            unordered_set<char> row;
            unordered_set<char> col;
            for (size_t j = 0; j < 9; j++)
            {
                if (row.find(board[i][j]) != row.end() ||
                    col.find(board[j][i]) != col.end() ||
                    box[i / 3][j / 3].find(board[i][j]) != box[i / 3][j / 3].end())
                {
                    return false;
                }
                if (board[i][j] != '.')
                {
                    row.insert(board[i][j]);
                    box[i / 3][j / 3].insert(board[i][j]);
                }
                if (board[j][i] != '.')
                {
                    col.insert(board[j][i]);
                }
            }
            row.clear();
            col.clear();
        }
        return true;
    }
};

289、生命游戏——矩阵

关键是创建一个和原矩阵相同大小的辅助矩阵change，用于记录细胞状态的变化。定义一个表示细胞相邻位置的偏移量的数组paths，包含了细胞上下左右以及斜对角方向的8个相邻位置。

每一个细胞，统计其周围活细胞的数量。使用内层循环遍历paths数组中的每一个偏移量，计算相邻位置的行索引和列索引，并判断是否在矩阵范围内。如果在范围内，并且对应位置的细胞状态发生了变化（即change中的值为0且board中的值为1，或者change中的值为1且board中的值为0），则将活细胞数量加一。

根据康威生命游戏的规则更新细胞的状态。如果当前细胞是活细胞（即board[i][j]为1），并且周围活细胞的数量是2或3，则细胞状态保持不变；否则，将细胞状态设置为死细胞（即board[i][j]赋值为0），并将change[i][j]设置为1，表示细胞状态发生了变化。如果当前细胞是死细胞，并且周围活细胞的数量是3，则将细胞状态设置为活细胞（即board[i][j]赋值为1），并将change[i][j]设置为1。

class Solution
{
public:
    void gameOfLife(vector<vector<int>> &board)
    {
        int h = board.size();
        int w = board[0].size();
        vector<vector<int>> change(h, vector<int>(w, 0));
        vector<pair<int, int>> paths = {
            {0, 1},
            {0, -1},
            {1, 0},
            {-1, 0},
            {1, 1},
            {1, -1},
            {-1, 1},
            {-1, -1}};
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                int live = 0;
                for (auto &path : paths)
                {
                    if (i + path.first >= 0 && i + path.first < h &&
                        j + path.second >= 0 && j + path.second < w)
                    {
                        int i_ = i + path.first;
                        int j_ = j + path.second;
                        if ((change[i_][j_] == 0 && board[i_][j_] == 1) ||
                            (change[i_][j_] == 1 && board[i_][j_] == 0))
                        {
                            live++;
                        }
                    }
                }
                if (board[i][j])
                {

                    if (live == 2 || live == 3)
                    {
                        continue;
                    }
                    board[i][j] = 0;
                    change[i][j] = 1;
                }
                else
                {
                    if (live == 3)
                    {
                        board[i][j] = 1;
                        change[i][j] = 1;
                    }
                }
            }
        }
    }
};

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END