leetcode刷题记录——2023年12月

leetcode刷题记录——2023年12月

2661、找出叠涂元素——哈希表

超时方法

首先,通过使用unordered_map来构建矩阵mat中元素与其索引的映射关系。遍历矩阵中的每个元素,将元素作为键,将其索引{i, j, 0}作为值,存储在matrix中。这样做的目的是方便后续根据元素值查找对应的索引。

接下来,遍历数组arr中的每个数,依次进行以下操作:

  • 将当前数在matrix中对应索引的第三个元素置为1,表示该数已经在数组arr中出现过。
  • 初始化一个标志变量flag为1,用于标记当前数所在行或列的所有数是否都在数组arr中出现过。
  • 获取当前数在matrix中对应的索引的行号y_pos和列号x_pos
  • 遍历当前数所在行的所有数,如果有任何一个数在matrix中对应索引的第三个元素不等于1(即未在数组arr中出现过),则将flag置为0,并跳出循环。
  • 如果flag仍然为1,说明当前数所在行的所有数都在数组arr中出现过,返回当前数的索引。
  • 如果flag为0,继续下一步操作。
  • flag重新置为1。
  • 遍历当前数所在列的所有数,如果有任何一个数在matrix中对应索引的第三个元素不等于1(即未在数组arr中出现过),则将flag置为0,并跳出循环。
  • 如果flag仍然为1,说明当前数所在列的所有数都在数组arr中出现过,返回当前数的索引。
  • 如果flag为0,继续下一次循环。
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        unordered_map<int, vector<int>> matrix;
        for(int i=0;i<mat.size();i++){
            for(int j=0;j<mat[0].size();j++){
                matrix[mat[i][j]] = {i, j, 0};
            }
        }
        for(int i=0;i<arr.size();i++){
            matrix[arr[i]][2] = 1;
            int flag = 1;
            int y_pos = matrix[arr[i]][0];
            int x_pos = matrix[arr[i]][1];
            for(int x=0;x<mat[0].size();x++){
                if(matrix[mat[y_pos][x]][2] == 0){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                return i;
            }
            flag = 1;
            for(int y=0;y<mat.size();y++){
                if(matrix[mat[y][x_pos]][2] == 0){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                return i;
            }else{
                continue;
            }
        }
        return 0;
    }
};

优化

将刚刚遍历 arr[i] 的行和列改为用哈希表存储行和列的被涂色的元素个数,每次涂色更新并检查该元素的行列中被涂色的元素个数,如果满一行或者一列,则返回 arr 的当前下标。

class Solution
{
public:
    int firstCompleteIndex(vector<int> &arr, vector<vector<int>> &mat)
    {
        int h = mat.size();
        int w = mat[0].size();
        unordered_map<int, pair<int, int>> matrix;
        unordered_map<int, int> row;
        unordered_map<int, int> col;
        for (int i = 0; i < h; i++)
        {
            row[i] = 0;
            for (int j = 0; j < w; j++)
            {
                col[j] = 0;
                matrix[mat[i][j]] = {i, j};
            }
        }
        for (int i = 0; i < h * w; i++)
        {
            int x_pos = matrix[arr[i]].second;
            col[x_pos]++;
            if (col[x_pos] == h)
            {
                return i;
            }
            int y_pos = matrix[arr[i]].first;
            row[y_pos]++;
            if (row[y_pos] == w)
            {
                return i;
            }
        }
        return 0;
    }
};

1094、拼车——哈希表

numPassengers来记录在每个位置上的乘客数量。对于每个行程trip,通过遍历行程的起始位置trip[1]到终止位置trip[2]之间的所有位置,将该位置上的乘客数量加上当前行程的乘客数量trip[0]

在每次更新乘客数量后,代码会检查乘客数量是否超过了汽车的最大乘客容量capacity。如果超过了容量,则返回false表示无法安排所有乘客完成行程。

最后,如果所有行程都遍历完毕且没有超过容量限制,则返回true表示可以安排所有乘客完成行程。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        unordered_map<int, int> numPassengers;
        for(auto& trip:trips){
            for(int i=trip[1];i<trip[2];i++){
                if(numPassengers.find(i) != numPassengers.end()){
                    numPassengers[i] += trip[0];
                }else{
                    numPassengers[i] = trip[0];
                }
                if (numPassengers[i] > capacity) {
                    return false;
                }
            }
        }
        return true;
    }
};

1423、可获得的最大点数——前缀和、滑动窗口

从长度为 len 的牌组两端取走 k 张卡牌,要点数最大,则说明留下来的连续 len-k 张牌组要点数最小。可以利用前缀和解决。

首先建立前缀和,使用一个循环遍历前缀和数组 prefix,从索引 left 开始,直到索引 len,求出长度为 left 的子数组的和,即 prefix[i] - prefix[i-left]。在循环中,使用变量 diff 来记录每个子数组的和,如果 diff 小于 min_left,则更新 min_left 的值为 diff

最后返回整个牌组的点数减去留下来的牌的最小点数。

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int len = cardPoints.size();
        int left = len-k;
        int min_left = INT_MAX;
        vector<int> prefix(len+1, 0);
        for(int i=1;i<len+1;i++){
            prefix[i] = prefix[i-1]+cardPoints[i-1];
        }
        for(int i=left;i<len+1;i++){
            int diff = prefix[i]-prefix[i-left];
            min_left = diff < min_left? diff:min_left;
        }
        return prefix[len]-min_left;
    }
};

优化

优化之后,这段代码不再使用前缀和数组来存储每个位置之前的卡牌点数和。相反,它使用了一个变量 window_size 来记录长度为 left 的滑动窗口的和。在第一个循环中,代码只计算了滑动窗口的初始和,并将其作为 min_left 的初始值。在第二个循环中,代码更新滑动窗口的和,并在每次更新后检查是否需要更新 min_left 的值。同时,它将当前卡牌的点数添加到 sum 中。

最后返回 sum 减去最小窗口大小 min_left 为最大点数。

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int len = cardPoints.size();
        int left = len-k;
        int min_left = INT_MAX;
        int window_size = 0;
        int sum = 0;
        for(int i=0;i<left;++i){
            window_size += cardPoints[i];
        }
        min_left = window_size < min_left? window_size:min_left;
        sum += window_size;
        for(int i=left;i<len;++i){
            window_size = window_size+cardPoints[i]-cardPoints[i-left]; 
            min_left = window_size < min_left? window_size:min_left;
            sum += cardPoints[i];
        }
        return sum-min_left;
    }
};

1038、从二叉搜索树到更大和数——深度优先搜索

将二叉搜索树(BST)转换为累加树(Greater Sum Tree)。

int inorderTravel(TreeNode* root, int num)函数是一个递归函数,用于遍历二叉搜索树并计算累加和。它接受两个参数:当前节点root和累加和num。函数首先检查当前节点是否为空,如果为空,则返回0。然后递归调用inorderTravel函数遍历右子树,将返回的累加和保存在变量right中。接下来,检查当前节点的右子节点是否为空,如果为空,则将当前节点的值加上right和num,并更新当前节点的值为累加和。如果右子节点不为空,则只将当前节点的值加上right。然后递归调用inorderTravel函数遍历左子树,将当前节点的值作为累加和传递给左子树,并将返回的累加和保存在变量left中。最后,如果left为0,则返回当前节点的值作为累加和,否则返回left。

/**
 * 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 inorderTravel(TreeNode* root, int num){
        if(root == nullptr){
            return 0;
        }
        int right = inorderTravel(root->right, num);
        if(root->right ==nullptr){
            root->val += right+num;
        }else{
            root->val += right;
        }
        int left = inorderTravel(root->left, root->val);
        return left==0?root->val:left;
    }
    TreeNode* bstToGst(TreeNode* root) {
        inorderTravel(root, 0);
        return root;
    }
};

2477、到达首都的最少油耗——贪心、深度优先搜索

创建了一个邻接表 g 来表示图的连接关系,并初始化一个标记数组 vis 来记录节点的访问状态。

调用了 dfs 函数,传入首都的节点编号 0,座位数 seats,邻接表 g 和标记数组 visdfs 函数是递归的,它首先将当前节点标记为已访问,并初始化总人数 oil 为 1(表示当前节点的人数)。

接下来,遍历当前节点的邻接节点,如果邻接节点未被访问,则递归调用 dfs 函数,并将返回的人数即前一节点的乘车人数 people 加到总人数 上,最后能得到在这个节点的乘车人数。

使用 (people + s -1) / s 计算从前一节点到当前节点的平均耗油量,并将结果累加到 res 中,这个表达式向上取整同时考虑了seats==1的情况。

class Solution {
public:
    long long res = 0;
    long long dfs(int n, int s, vector<vector<int>>& g, vector<int>& vis){
        int peopleSum = 1;
        vis[n] = 1;
        for(int i=0;i<g[n].size();i++){
            if(vis[g[n][i]] == 0){
                int people =  dfs(g[n][i], s, g, vis);
                peopleSum += people;
                // 从g[n][i]到n的平均耗油量为people/s的向上取整
                res += (people + s -1) / s;
            }
        }
        return peopleSum;

    }

    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int len = roads.size();
        if(len == 0){
            return 0;
        }
        vector<vector<int>> g(len+1);
        vector<int> vis(len+1, 0);
        for(auto& road:roads){
            g[road[0]].push_back(road[1]);
            g[road[1]].push_back(road[0]);
        }
        dfs(0, seats, g, vis);
        return res;
    }
};

83、删除有序链表中的重复元素

/**
 * 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 == nullptr){
            return nullptr;
        }
        ListNode* cur = head;
        int pre = cur->val;
        while(cur->next != nullptr){
            if(cur->next->val == pre){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                continue;
            }
            pre = cur->next->val;
            cur = cur->next;
        }
        return head;
    }
};

1466、重新规划路线——深度优先搜索

难点主要在构图。用vector<vector<pair<int, int>>>邻接矩阵表示图,pair的第一个元素表示相邻节点,pair的第二个元素表示两个节点的边的方向。

深度优先遍历图,如果当前边的方向为1,则说明需要修改该路线的方向,ret+1。遍历完成ret即需要规划的路线数量。

class Solution {
public:
    int ret = 0;
    void dfs(vector<vector<pair<int, int>>>& g, vector<int>& vis, int city){
        vis[city] = 1;
        for(auto& dst:g[city]){
            if(vis[dst.first] == 0){
                if(dst.second == 1){
                    ret++;
                }
                dfs(g, vis, dst.first);
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        int NumofCity = connections.size();
        vector<vector<pair<int, int>>> g(NumofCity+1);
        vector<int> vis(NumofCity+1, 0);
        for(auto& s:connections){
            g[s[0]].push_back({s[1], 1});
            g[s[1]].push_back({s[0], 0});
        }
        dfs(g, vis, 0);
        return ret;
    }
};

2008、出租车的最大盈利——排序、二分查找、动态规划

首先将订单按照终点大小排序。然后遍历订单,每次遍历找到终点小于当前订单的起点的最大订单,然后比较当前订单的前一订单的最大盈利终点小于当前订单的起点的最大订单的盈利加上当前订单的盈利大小,更新dp数组。

class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        int m = rides.size();
        // 按照终点排序
        sort(rides.begin(), rides.end(), 
            [](const vector<int>& a,const vector<int>& b)->bool{
                return a[1] < b[1];
            }    
        );
        vector<long long> dp(m+1 ,0);
        for(int i=0;i<m;i++){
            // i乘客前的终点小于i的起点的最大乘客
            int j = upper_bound(rides.begin(), rides.begin() + i, rides[i][0], 
                [](int x, const vector<int> &r) -> bool {
                    return x < r[1];
                }
            ) - rides.begin();
            dp[i+1] = max(dp[i],  dp[j] + rides[i][2] + rides[i][1] - rides[i][0]);
        }
        return dp[m];
    }
};

2048、下一个更大的数值平衡数——枚举

class Solution {
public:
    bool isBalanceNum(int num){
        vector<int> count(10);
        while (num > 0) {
            count[num % 10]++;
            num /= 10;
        }
        for (int d = 0; d < 10; ++d) {
            if (count[d] > 0 && count[d] != d) {
                return false;
            }
        }
        return true;
    }

    int nextBeautifulNumber(int n) {
        int cnt = 1;
        while(false == isBalanceNum(n+cnt)){
            cnt++;
        }
        return cnt+n;
    }
};

70、爬楼梯——动态规划

最经典的动态规划问题,好像高中就做过这个大题。
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(3, 1);
        for(int i=2;i<=n;i++){
            dp[2] = dp[0]+dp[1];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[2];
    }
};

100、相同的树——深度优先搜索

简单题,略。

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==nullptr && q==nullptr){
            return true;
        }else if(p==nullptr || q==nullptr){
            return false;
        }

        bool ret = true;
        ret = ret & isSameTree(p->left, q->left);
        if(p->val != q->val){
            return false;
        }
        ret = ret & isSameTree(p->right, q->right);
        return ret;
    }
};

2454、下一个更大元素 Ⅳ——单调栈、优先队列

困难题,要暴力破解肯定不难,主要难在优化的方法。

单调栈st,用于寻找每个元素之后的第一个更大元素。最小堆队列q,用于存储已经找到第一个更大元素的元素。

遍历数组nums,对于每个