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 和标记数组 vis。dfs 函数是递归的，它首先将当前节点标记为已访问，并初始化总人数 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，对于每个元素nums[i]：

在q非空且堆顶元素小于当前元素nums[i]时，说明当前元素为堆顶元素的第二大元素，将堆顶元素弹出并更新结果数组res，直到堆顶元素不小于当前元素nums[i]
在st非空且栈顶元素对应的值小于当前元素nums[i]时，说明找到了栈顶元素的下一个更大元素，将栈顶元素弹出并将其加入最小堆队列q。
将当前元素的索引推入栈st中。

使用单调栈和最小堆，能够在一次遍历中找到每个元素之后的第二大元素。首先，它处理最小堆队列q中比当前元素小的元素，将它们存储到结果数组res中，并从队列中移除。然后，它处理单调栈st中比当前元素小的元素，将它们存储到最小堆队列q中。最后，它将当前元素的索引推入栈st中。

此段代码的时间复杂度为O(nlogn)，其中n是数组的长度。这是因为在最坏情况下，最小堆队列q中的元素个数可以达到n个，并且每个元素的插入和弹出操作的时间复杂度都是O(logn)。

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        // 寻找第一个大元素的单调栈
        stack<int> st;
        // 存储已经找到第一个大元素的元素小堆队列
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; 
        for (int i = 0; i < nums.size(); ++i) {
            // 寻找第二个更大元素
            while (!q.empty() && q.top().first < nums[i]) {
                // 找到了
                res[q.top().second] = nums[i];
                q.pop();
            }

            // 寻找第一个更大元素
            while (!st.empty() && nums[st.top()] < nums[i]) {
                // 找到了，放入队列
                q.push({nums[st.top()], st.top()});
                st.pop();
            }

            st.push(i);  // 将当前元素的索引推入栈中
        }

        return res;  // 返回结果数组
    }
};

110、平衡二叉树——深度优先搜索

递归计算每个节点的左子树和右子树的高度，并判断高度差是否超过1。如果高度差超过1，则将一个成员变量ret置为false，表示该二叉树不平衡。最后返回ret的值来判断二叉树是否平衡。

在计算高度时，如果发现左子树或右子树的高度差超过1，则直接返回-1作为标记，表示当前子树不平衡。这样可以有效地减少不必要的递归操作。

/**
 * 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 depth(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        int left = depth(root->left);
        if(left == -1){
            return -1;
        }
        int right = depth(root->right);
        if(right == -1){
            return -1;
        }
        int dif = left>right?left-right:right-left;
        if(dif > 1){
            ret = false;
            return -1;
        }
        return left>right?left+1:right+1;
    }
    bool isBalanced(TreeNode* root) {
        depth(root);
        return ret;
    }
private:
    bool ret = true;
};

111、二叉树的最小深度——深度优先搜索

如果当前节点root为空，表示到达了叶子节点的空子节点，返回深度0。如果当前节点root的左右子节点都为空，表示到达了叶子节点，返回深度1。

如果当前节点root的左子节点存在，递归调用DFS函数计算左子树的最小深度，并将结果加1得到left。

如果当前节点root的右子节点存在，递归调用DFS函数计算右子树的最小深度，并将结果加1得到right。

返回左右子树的最小深度中的较小值作为当前节点的最小深度。

/**
 * 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 dfs(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        if(root->left == nullptr && root->right == nullptr){
            return 1;
        }
        int left = root->left ? dfs(root->left) + 1: INT_MAX;
        int right = root->right ? dfs(root->right) + 1: INT_MAX;
        return left > right ? right : left;
    }
    int minDepth(TreeNode* root) {
        return dfs(root);
    }
};

2697、字典序最小回文串——双指针

略

class Solution {
public:
    string makeSmallestPalindrome(string s) {
        int i=0, j=s.length()-1;
        while(i<=j){
            if(s[i]>s[j]){
                s[i]=s[j];
            }else{
                s[j]=s[i];
            }
            i++;
            j--;
        }
        return s;
    }
};

112、路径综合——深度优先搜索

如果当前节点 root 是空节点，说明已经遍历到了叶子节点的下一层，返回 false。将当前节点 root 的值加上上一层节点的值 pre，以计算当前路径的节点值之和。如果当前节点是叶子节点，并且路径节点值之和等于目标和 sum，则返回 true，表示找到了满足条件的路径。递归地在左子树中查找路径，传递当前路径节点值之和 root->val 作为上一层节点的值 pre。递归地在右子树中查找路径，传递当前路径节点值之和 root->val 作为上一层节点的值 pre。如果左子树或右子树中存在满足条件的路径，则返回 true。

/**
 * 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 pathSum(TreeNode* root, int sum, int pre){
        if(root == nullptr){
            return false;
        }
        root->val += pre; 
        if(root->val == sum && root->left == nullptr && root->right == nullptr){
            return true;
        }
        return pathSum(root->left, sum, root->val) | pathSum(root->right, sum, root->val);

    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        return pathSum(root, targetSum, 0);
    }
};

2415、反转二叉树的奇数层——层序遍历

创建一个大小为 size 的整数向量 nums，用于保存当前层的节点值。利用一个循环，遍历当前层的所有节点。在每次循环中，从队列中取出一个节点 node。如果 flag 为 true，表示当前层需要翻转节点值。将节点 node 再次入队，并将节点值存储到 nums 向量中，索引为 size - cnt - 1。如果 flag 为 false，表示当前层不需要翻转节点值。检查节点 node 的左子节点和右子节点是否存在，并将它们入队。当完成当前层的节点遍历后，再次判断 flag 是否为 true。如果是，则需要翻转节点值。利用一个循环，遍历当前层的所有节点。在每次循环中，从队列中取出一个节点 node。将 nums 向量中对应位置的节点值赋给节点 node。将节点 node 出队后，检查它的左子节点和右子节点是否存在，并将它们入队。完成当前层的节点翻转后，增加 level 的值，进入下一层的循环。

/**
 * 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:
    TreeNode *reverseOddLevels(TreeNode *root)
    {
        queue<TreeNode *> q;
        q.push(root);
        int level = 0;
        while (!q.empty())
        {
            int size = q.size();
            bool flag = level % 2 == 1;
            vector<int> nums(size);
            int cnt = size;
            while (cnt--)
            {
                TreeNode *node = q.front();
                q.pop();
                if (flag)
                {
                    q.push(node);
                    nums[size - cnt - 1] = node->val;
                }
                else
                {
                    if (node->left)
                        q.push(node->left);
                    if (node->right)
                        q.push(node->right);
                }
            }
            if (flag)
            {
                cnt = size;
                while (cnt--)
                {
                    TreeNode *node = q.front();
                    node->val = nums[cnt];
                    q.pop();
                    if (node->left)
                        q.push(node->left);
                    if (node->right)
                        q.push(node->right);
                }
            }
            level++;
        }
        return root;
    }
};

119、杨辉三角 Ⅱ——数组

利用一个外层循环，从第 2 行开始遍历到目标行 rowIndex。利用一个内层循环，从当前行的倒数第 2 个元素开始遍历到第 1 个元素。在内层循环中，将向量 res 中的元素更新为当前元素与前一个元素之和。这是因为杨辉三角的每个元素等于它上方两个元素之和。内层循环结束后，当前行的元素更新完成。外层循环结束后，所有行的元素更新完成，向量 res 中存储着目标行的元素。

class Solution
{
public:
    vector<int> getRow(int rowIndex)
    {
        vector<int> res(rowIndex + 1, 1);
        for (int i = 2; i <= rowIndex; i++)
        {
            for (int j = i - 1; j >= 1; j--)
            {
                res[j] = res[j - 1] + res[j];
            }
        }
        return res;
    }
};

134、加油站——贪心

超时方法

diff用于存储每个加油站的编号和该加油站的汽油剩余量与消耗量之差。这样得到的diff向量表示了从每个加油站出发能够到达的下一个加油站之间的剩余汽油量，然后进行排序。遍历排序后的diff向量中的每个加油站，从剩余汽油量最多的加油站开始尝试绕行整个循环。对于每个加油站，使用循环来模拟从当前加油站出发绕行一圈的过程。在模拟绕行的过程中，累计每个加油站的剩余汽油量与消耗量之差，即sum += gas[cite] - cost[cite]。如果累计的剩余汽油量小于0，表示无法到达下一个加油站，将标志位flag设置为false，并跳出循环。如果绕行一圈后，标志位flag仍然为true，表示成功绕行整个循环，返回当前加油站的编号作为起始点。遍历完整个diff向量后，都没有找到能够绕行的起始点，返回-1表示无解。

时间复杂度O(nlogn)

class Solution
{
public:
    int canCompleteCircuit(vector<int> &gas,
                           vector<int> &cost)
    {
        int n = gas.size();
        vector<pair<int, int>> diff;
        for (size_t i = 0; i < n; i++)
        {
            diff.push_back(make_pair(i, gas[i] - cost[i]));
        }
        sort(diff.begin(), diff.end(), [](pair<int, int> &a, pair<int, int> &b)
             { return a.second > b.second; });
        for (auto &pos : diff)
        {
            int sum = 0;
            int cite = pos.first;
            int cnt = n;
            bool flag = true;
            while (cnt--)
            {
                sum += gas[cite] - cost[cite];
                cite = (cite + 1) % n;
                if (sum < 0)
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                return pos.first;
            }
        }
        return -1;
    }
};

优化

维护两个变量totalSum和currSum来跟踪总剩余汽油量和当前剩余汽油量。如果当前剩余汽油量不够到达下一个加油站，就重置起始点，并将当前剩余汽油量重置为0。最后，如果总剩余汽油量小于0或起始点超过了加油站数量，表示无解，返回-1。否则，返回起始点。

class Solution
{
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        int n = gas.size();
        
        int totalSum = 0; // 总剩余汽油量
        int currSum = 0; // 当前剩余汽油量
        int start = 0; // 起始点
        
        for (int i = 0; i < n; i++)
        {
            int diff = gas[i] - cost[i];
            totalSum += diff;
            currSum += diff;
            
            if (currSum < 0)
            {
                // 当前剩余汽油量不够到达下一个加油站，重置起始点
                start = i + 1;
                currSum = 0;
            }
        }
        
        if (totalSum < 0 || start >= n)
        {
            // 总剩余汽油量小于0，无法绕行整个循环
            // 或者起始点超过了加油站数量，表示无解
            return -1;
        }
        
        return start;
    }
};

383、赎金信——哈希表

很基础的哈希表题目，略。

class Solution
{
public:
    bool canConstruct(string ransomNote,
                      string magazine)
    {
        unordered_map<char, int> magazine_map;
        bool ret = true;
        for (size_t i = 0; i < magazine.size(); i++)
        {
            if (magazine_map.find(magazine[i]) != magazine_map.end())
            {
                magazine_map[magazine[i]]++;
            }
            else
            {
                magazine_map[magazine[i]] = 1;
            }
        }

        for (auto &ch : ransomNote)
        {
            if (magazine_map.find(ch) == magazine_map.end() || magazine_map[ch] == 0)
            {
                ret = false;
            }
            if (magazine_map.find(ch) != magazine_map.end())
            {
                magazine_map[ch]--;
            }
        }
        return ret;
    }
};

205、同构字符串——哈希表

代码首先检查s和t的长度是否相等，如果不相等则直接返回false。

然后，使用一个unordered_map s_t_map来存储s中字符到t中字符的映射关系，键为s中的字符，值为t中对应位置的字符。同时，使用一个unordered_set t_mapped来记录已经映射过的t中的字符。

接下来，遍历字符串s的每个字符。如果当前字符在s_t_map中不存在（即s中的字符还没有被映射），则检查对应位置的字符t[i]是否已经被映射过，如果已经映射过，则说明存在多个字符映射到同一个字符，此时返回false。否则，将s中的字符和t中对应位置的字符建立映射关系，并将t中对应位置的字符标记为已映射。

如果当前字符在s_t_map中已经存在（即s中的字符已经被映射过），则检查该字符映射的t中的字符是否与当前位置的字符相等，如果不相等则返回false。

class Solution
{
public:
    bool isIsomorphic(string s, string t)
    {
        if (s.length() != t.length())
        {
            return false;
        }

        bool ret = true;
        unordered_map<char, char> s_t_map;
        unordered_set<char> t_mapped;
        int len = s.length();
        for (size_t i = 0; i < len; i++)
        {
            if (s_t_map.find(s[i]) == s_t_map.end())
            {
                if (t_mapped.find(t[i]) != t_mapped.end())
                {
                    ret = false;
                    break;
                }
                s_t_map[s[i]] = t[i];
                t_mapped.insert(t[i]);
            }
            else
            {
                if (s_t_map[s[i]] != t[i])
                {
                    ret = false;
                    break;
                }
            }
        }
        return ret;
    }
};

746、使用最小花费爬楼梯——动态规划

经典爬楼梯

class Solution
{
public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int steps = cost.size();
        vector<int> dp(3, 0);
        for (size_t i = 2; i <= steps; i++)
        {
            dp[2] = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[2];
    }
};

162、寻找峰值——二分查找

由于nums[-1]和nums[n]可视为负无穷，因此数组必定存在峰值。

首先，初始化左边界 left 为 0，右边界 right 为数组长度 len。然后，计算中间位置 mid 为 (left + right) / 2。

接下来，使用一个循环来进行二分查找。循环条件是 left < right 并且 mid 在有效的数组索引范围内（即 mid >= 0 并且 mid < len）。在循环中，首先计算 mid 位置元素的左右相邻元素的值，使用 long 类型来处理溢出情况（左右两边界为负无穷）。如果当前元素 nums[mid] 小于等于右边相邻元素 right_val，那么右半边肯定存在一个峰值元素，将 left 更新为 mid。如果当前元素 nums[mid] 小于等于左边相邻元素 left_val，那么左半边一定存在一个峰值元素，将 right 更新为 mid。否则，当前元素就是峰值元素，跳出循环。

class Solution
{
public:
    int findPeakElement(vector<int> &nums)
    {
        int len = nums.size();
        int left = 0, right = len;
        int mid = (left + right) / 2;
        while (left < right && mid >= 0 && mid < len)
        {
            long left_val = mid - 1 >= 0 ? nums[mid - 1] : LONG_MIN;
            long right_val = mid + 1 < len ? nums[mid + 1] : LONG_MIN;
            if (nums[mid] <= right_val)
            {
                left = mid;
            }
            else if (nums[mid] <= left_val)
            {
                right = mid;
            }
            else
            {
                break;
            }
            mid = (left + right) / 2;
        }
        return mid;
    }
};

1962、移除石子使总数最小——优先队列

首先将数组建堆，然后操作k次，每次都pop_heap先将根节点移到末尾，然后减去堆顶元素除以2取整，再通过push_heap将末尾元素插入堆中。最后计算剩下的石子。

class Solution
{
public:
    int minStoneSum(vector<int> &piles, int k)
    {
        int heaps = piles.size();
        int sum = 0;
        if (piles.size() == 0)
        {
            return 0;
        }
        // 建堆
        make_heap(piles.begin(), piles.end());
        while (k--)
        {
            pop_heap(piles.begin(), piles.end());
            piles[heaps - 1] -= floor(piles[heaps - 1] / 2);
            push_heap(piles.begin(), piles.end());
        }
        for (int i = 0; i < heaps; i++)
        {
            sum += piles[i];
        }
        return sum;
    }
};

1954、收集足够苹果的最小花园边长

暴力破解

class Solution
{
public:
    long long minimumPerimeter(long long neededApples)
    {
        long long ret;
        long long sum = 0;
        for (ret = 0; sum < neededApples; ret++)
        {
            sum += 12 * ret * ret;
        }
        return 8 * (ret - 1);
    }
};

2660、保龄球游戏的获胜者

略

class Solution
{
public:
    int isWinner(vector<int> &player1,
                 vector<int> &player2)
    {
        int sum1 = player1[0], sum2 = player2[0];
        if (player1.size() > 1)
        {
            sum1 += sum1 == 10 ? 2 * player1[1] : player1[1];
            sum2 += sum2 == 10 ? 2 * player2[1] : player2[1];
        }
        for (size_t i = 2; i < player1.size(); i++)
        {
            sum1 += (player1[i - 1] == 10 || player1[i - 2] == 10) ? 2 * player1[i] : player1[i];
            sum2 += (player2[i - 1] == 10 || player2[i - 2] == 10) ? 2 * player2[i] : player2[i];
        }
        return sum1 == sum2 ? 0 : (sum1 > sum2 ? 1 : 2);
    }
};

2706、购买两块巧克力——排序

略

class Solution
{
public:
    int buyChoco(vector<int> &prices, int money)
    {
        sort(prices.begin(), prices.end(), [](int &a, int &b)
             { return a < b; });
        int ret = money - prices[0] - prices[1];
        return ret < 0 ? money : ret;
    }
};

151、反转字符串中的单词

略

class Solution
{
public:
    string reverseWords(string s)
    {
        string tmp;
        string res;
        vector<string> words;
        for (size_t i = 0; i < s.length(); i++)
        {
            tmp += s[i];
            if (s[i] == ' ' || i == s.length() - 1)
            {
                if (s[i] == ' ')
                    tmp.pop_back();
                if (tmp.length() > 0)
                {
                    words.push_back(tmp);
                    tmp.clear();
                }
            }
        }
        for_each(words.rbegin(), words.rend(), [&res](string &word)
                 { res+=word;res+=' '; });
        res.pop_back();
        return res;
    }
};

209、长度最小的子数组——双指针

首先将 nums[right] 添加到 sum 中，并将 right 的值加 1。在循环内部更新左指针，如果当前子数组的长度比 ret 记录的子数组长度更短，则更新 ret 的值为当前子数组的左边界和右边界。然后从 sum 中减去 nums[left]，并将 left 的值加 1，表示将左边界向右移动一位。主循环继续执行，直到 right 达到数组的末尾。

class Solution
{
public:
    int minSubArrayLen(int target,
                       vector<int> &nums)
    {
        int left = 0, right = 0;
        int sum = 0;
        pair<int, int> ret = {0, nums.size() + 1};
        while (right < nums.size())
        {

            sum += nums[right];
            right++;

            while (sum >= target)
            {
                if (right - left < ret.second - ret.first)
                {
                    ret = {left, right};
                }
                sum -= nums[left];
                left++;
            }
        }
        return ret.second - ret.first <= nums.size()
                   ? ret.second - ret.first
                   : 0;
    }
};

167、两数之和 II – 输入有序数组——双指针

如果 tmp 等于 target，表示找到了符合条件的两个数，将 left + 1 和 right + 1 分别存储到 idx[0] 和 idx[1] 中，然后跳出循环。

如果 tmp 小于 target，说明当前和偏小，需要增大和，将 left 向右移动一位，即 left++。

如果 tmp 大于 target，说明当前和偏大，需要减小和，将 right 向左移动一位，即 right--。

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums,
                       int target)
    {
        vector<int> idx(2, 0);
        int left = 0, right = nums.size() - 1;
        int tmp = 0;
        while (left < right)
        {
            tmp = nums[left] + nums[right];
            if (tmp == target)
            {
                idx[0] = left + 1;
                idx[1] = right + 1;
                break;
            }
            else if (tmp < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return idx;
    }
};

290、单词规律——哈希表

略

class Solution
{
public:
    bool wordPattern(string pattern,
                     string s)
    {
        vector<string> words;
        string tmp;
        for (size_t i = 0; i < s.length(); i++)
        {
            if (s[i] == ' ')
            {
                if (tmp.length() > 0)
                {
                    words.push_back(tmp);
                    tmp.clear();
                }
                continue;
            }
            tmp += s[i];
            if (s.length() == i + 1)
            {
                words.push_back(tmp);
            }
        }
        if (words.size() != pattern.length())
            return false;
        unordered_map<char, string> maps;
        unordered_set<string> hasMapped;
        int cnt = 0;
        for (auto &ch : pattern)
        {
            if (maps.find(ch) == maps.end() && hasMapped.find(words[cnt]) == hasMapped.end())
            {
                hasMapped.insert(words[cnt]);
                maps[ch] = words[cnt++];
            }
            else
            {
                if (maps[ch] != words[cnt++])
                {
                    return false;
                }
            }
        }
        return true;
    }
};

231、2的幂——位运算

对 n 和 (n - 1) 进行按位与操作，结果等于 0，说明 n 和 (n - 1) 没有共同的二进制位，即 n 只有一个二进制位为 1，这时 n 是 2 的幂，返回 true。

class Solution
{
public:
    bool isPowerOfTwo(int n)
    {
        return n > 0 && (n & (n - 1)) == 0;
    }
};

242、有效字母异位词——哈希表

统计次数

class Solution
{
public:
    bool isAnagram(string s, string t)
    {
        unordered_map<char, int> map;
        for (size_t i = 0; i < s.length(); i++)
        {
            map[s[i]]++;
        }
        for (size_t i = 0; i < t.length(); i++)
        {
            map[t[i]]--;
        }
        for (auto &it : map)
        {
            if (it.second != 0)
                return false;
        }
        return true;
    };
};

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

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

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

THE END

leetcode刷题记录——2023年12月

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

超时方法

优化

1094、拼车——哈希表

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

优化

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

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

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

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

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

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

70、爬楼梯——动态规划

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

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

110、平衡二叉树——深度优先搜索

111、二叉树的最小深度——深度优先搜索

2697、字典序最小回文串——双指针

112、路径综合——深度优先搜索

2415、反转二叉树的奇数层——层序遍历

119、杨辉三角 Ⅱ——数组

134、加油站——贪心

超时方法

优化

383、赎金信——哈希表

205、同构字符串——哈希表

746、使用最小花费爬楼梯——动态规划

162、寻找峰值——二分查找

1962、移除石子使总数最小——优先队列

1954、收集足够苹果的最小花园边长

2660、保龄球游戏的获胜者

2706、购买两块巧克力——排序

151、反转字符串中的单词

209、长度最小的子数组——双指针

167、两数之和 II – 输入有序数组——双指针

290、单词规律——哈希表

231、2的幂——位运算

242、有效字母异位词——哈希表

1SQL注入基础教程

2Nachos文件系统调用与shell

3Adaline自适应线性神经元和学习收敛

4系统调用详解:以Nachos为例实现系统调用

5SeedLab——Environment Variable and Set-UID Program Lab

6机器学习入门-python实现感知器算法