2024-01-01

题目传送门：1599. 经营摩天轮的最大利润 - 力扣（LeetCode）

新年快乐🎇🎇🎇！！！，新年第一题就是之前做过的，模拟即可。首先先循环每个时间点，使用一个变量previ记录该时间点上一个时间点后还剩下没上摩天轮的顾客数量，然后当前时间点的顾客数就是之前剩下的加上新来的，这里大于4还是小于等于4分类讨论一下。最后如果最后一个时间点已经过了的话previ还有剩余，则继续转直到将previ转空，中间判断一下转多少次的时候能够有最大利润即可：

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def minOperationsMaxProfit(self, customers: List[int], boardingCost: int, runningCost: int) -> int:
        res = 0
        ans = []
        serv = 0
        for idx,customer in enumerate(customers):
            if customer + res > 4:
                res += (customer-4)
                serv += 4
                ans.append(serv * boardingCost - (idx+1) * runningCost)
            else:
                serv += (res+customer)
                res = 0
                ans.append(serv * boardingCost - (idx+1) * runningCost)

        
        while res:
            idx += 1
            if res > 4:
                serv += 4
                res -= 4
                ans.append(serv * boardingCost - (idx+1) * runningCost)
            else:
                serv += res
                res = 0
                ans.append(serv * boardingCost - (idx+1) * runningCost)
        now,loc = 0,-1
        # return ans
        for i in range(len(ans)):
            if now < ans[i]:
                now = ans[i]
                loc = i+1
        return -1 if loc == -1 else loc

C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {  
public:  
    int minOperationsMaxProfit(vector<int>& customers, int boardingCost, int runningCost) {  
        int previ = 0;  
        int ans = 0,nw = 0;  
        int ans_cnt=-1,cnt=0;  
        for (auto customer:customers) {  
            int tmp = customer + previ;  
            cnt++;  
            if (tmp > 4) {  
                nw += 4*boardingCost - runningCost;  
                previ = tmp - 4;  
                if (nw > ans) ans = nw,ans_cnt = cnt;  
                ans = max(ans, nw);  
            } else {  
                nw += tmp*boardingCost - runningCost;  
                previ = 0;  
                if (nw > ans) ans = nw,ans_cnt = cnt;  
            }  
        }  
        while (previ) {  
            cnt++;  
            if(previ > 4) {  
                nw += 4*boardingCost - runningCost;  
                previ -= 4;  
                if (nw > ans) ans = nw,ans_cnt = cnt;  
            } else {  
                nw += previ*boardingCost - runningCost;  
                previ = 0;  
                if (nw > ans) ans = nw,ans_cnt = cnt;  
            }  
        }  
        return ans_cnt;  
    }  
};

2024-01-02

题目传送门：466. 统计重复个数 - 力扣（LeetCode）

2024-01-03

题目传送门：2487. 从链表中移除节点 - 力扣（LeetCode）

一道链表的题目，充分暴露了我对C++一些特性以及指针相关内容还不是非常的熟练。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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* removeNodes(ListNode* head) {
        ListNode* nw = head;
        vector<int> arr = {nw->val};
        while (nw->next) {
            nw = nw->next;
            arr.push_back(nw->val);
        }
        stack<int> ans_arr;
        int siz = arr.size();
        for (int i=siz-1;i>=0;--i) {
            if (ans_arr.size()==0||arr[i] >= ans_arr.top()) {
                ans_arr.push(arr[i]);
            }
        }
        ListNode *hhead =  new ListNode(), *now =  new ListNode();
        now = hhead;
        while (!ans_arr.empty()) {
            ListNode *tmp = new ListNode();
            int nw_val = ans_arr.top(); ans_arr.pop();
            tmp->val = nw_val;
            now->next = tmp;
            now = tmp;
        }
        return hhead->next;
    }
};
注意

需要非常注意的就是在初始化指针的时候一定要这么写ListNode *hhead = new ListNode(), *now = new ListNode();

为什么不能ListNode *tmp;

这里的tmp是一个指向ListNode类型的指针。但是，这个指针在使用之前没有被分配任何内存。这意味着tmp指向的是一个未知的、未初始化的内存位置。当您尝试通过now->next = tmp;给now->next赋值时，您实际上是在让now->next指向一个不确定的内存位置。这是非常危险的，因为这块内存可能是空的，或者已经被其他数据占用，从而导致未定义行为或程序崩溃。

为什么不能ListNode* tmp = nullptr;

如果您将ListNode* tmp = nullptr;并在之后的代码中尝试通过tmp指针访问或修改数据，那么这同样会导致错误。原因如下：

  1. 空指针解引用: 当tmp被设置为nullptr时，它指向的是空地址。任何尝试通过空指针（nullptr）访问或修改数据的行为都会导致运行时错误，通常是段错误（segmentation fault）。在您的代码中，如果tmp是nullptr，那么像now->next = tmp;这样的赋值操作是安全的，但之后的tmp->val = nw_val;尝试解引用nullptr，这会导致错误。

  2. 未分配实际的节点: 在链表操作中，通常需要创建新的节点来存储数据。如果tmp只是一个空指针，那么它不能用于存储任何实际的数据。您需要为每个新节点分配内存来存储数据和指向下一个节点的指针。

总结

要解决这个问题，您需要在使用tmp之前为其分配内存，如下所示：

1
ListNode* tmp = new ListNode(); // 分配内存并初始化

这样，tmp不再是一个空指针，而是指向一个新分配且已初始化的ListNode对象。这允许您安全地使用tmp来存储数据并将其加入到链表中。

2024-01-04

题目传送门：2397. 被列覆盖的最多行数 - 力扣（LeetCode）

一道暴力搜索板子题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int ans = 0;
        int m = matrix.size(),n = matrix[0].size();
        vector<bool> cols(n,false);
        auto judge = [&](int x) {
            int now_ans = 0;
            for(int i=0;i<n;++i){
                if (matrix[x][i]==1 && cols[i]==false) return false;
            }
            return true;
        };
        function<void(int,int)> dfs = [&](int idx,int pre) {
            if (idx==numSelect) {
                int nw = 0;
                for(int i=0;i<m;++i){
                    if (judge(i)) nw += 1;
                }
                ans = max(ans,nw);
                return;
            } 
            for (int i=pre+1;i<n;++i) {
                cols[i] = true;
                dfs(idx+1, i);
                cols[i] = false;
            }
        };
        dfs(0,-1);
        return ans;
    }
};

2024-01-05

题目传送门：1944. 队列中可以看到的人数 - 力扣（LeetCode）

在读完题目以及看完数据范围后不难想到应该用单调栈的方法解决这道题，反向遍历数组，单调栈维护一个顶小底大的栈，代表当前元素可能可以看见的右边的人。

我们只需要在每次在判断当前元素时，统计我们要进行多少次弹栈操作。就是我们能够看到的人的数量，但是最后还有一个地方需要注意一下，见下面红色。

注意

这里还有一个细节，弹完栈后，需要判断当前栈是否为空，如果不为空，我们能看到的人还要+1（虽然比我们高但是能看到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        stack<int> stk;
        int n = heights.size();
        vector<int> ans(n,0);
        for(int i=n-1;i>=0;--i){
            int tmp = 0;
            while(!stk.empty() && heights[stk.top()] < heights[i]) {
                stk.pop();
                tmp++;
            }
            if (stk.empty()) ans[i] = tmp;
            else ans[i] = tmp+1;
            stk.push(i);
        }
        return ans;
    }
};

2024-01-06

题目传送门：2807. 在链表中插入最大公约数 - 力扣（LeetCode）

一道非常简单的签到题，复习一下链表写法和gcd写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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* insertGreatestCommonDivisors(ListNode* head) {
        function<int(int,int)> ggcd=[&](int a,int b) {
            return a%b==0?b:ggcd(b,a%b);
        };
        ListNode *nw = head;
        if (nw->next == nullptr) return head;
        ListNode *nwnxt = nw->next;
        while (nwnxt != nullptr) {
            int val = ggcd(max(nw->val,nwnxt->val),min(nw->val,nwnxt->val));
            ListNode *tmp = new ListNode(val, nwnxt);
            nw->next = tmp;
            nw = nwnxt;
            nwnxt = nwnxt->next;
        }
        return head;
    }
};

2024-01-07

题目传送门：383. 赎金信 - 力扣（LeetCode）

建立26个桶，统计每个字符个数即可。签到题：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.size() > magazine.size()) return false;
        vector<int> cnt(26,0);
        for(auto note:magazine) cnt[note-'a']++;
        for(auto note:ransomNote){
            cnt[note-'a']--;
            if (cnt[note-'a'] < 0) return false;
        }
        return true;
    }
};

2024-01-08

题目传送门：447. 回旋镖的数量 - 力扣（LeetCode）

一道unordered_map哈希题，O(n2)O(n^2)复杂度，对于每个位置，遍历所有位置，使用一个哈希表存储与该位置相距特定距离下有哪些位置（哈希表索引是距离），最后就可以根据这个哈希表计算以该点为中心的回旋镖数量。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0,n=points.size();
        for(int i=0;i<n;++i){
            unordered_map<int,int> cnt;
            for(int j=0;j<n;++j){
                if (i == j) continue;
                int dis = (points[i][0]-points[j][0]) * (points[i][0]-points[j][0]) + (points[i][1]-points[j][1]) * (points[i][1]-points[j][1]);
                if(cnt.find(dis)==cnt.end()) cnt[dis] = 1;
                else cnt[dis] ++;
            }
            for(auto ele:cnt) {
                ans += ele.second * (ele.second-1);
            }
        }
        return ans;
    }
};

2024-01-09

题目传送门：

2024-01-14

题目传送门：83. 删除排序链表中的重复元素 - 力扣（LeetCode）

链表遍历签到题目，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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) {
        ListNode *nw = head;
        while(nw!= nullptr&& nw->next!= nullptr){
            ListNode *nxt = nw->next;
            while(nxt!= nullptr&&nw->val == nxt->val) nxt = nxt->next;
            nw->next = nxt;
            nw = nw->next;
        }
        return head;
    }
};

2024-01-15

题目传送门：82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

链表遍历题目，是昨天题目的加强版,下面给出只遍历一遍的做法，需要注意的细节是：

  1. 头节点也可能被删除，所以要开一个head之前的点。
  2. 需要判断下一个和下下个节点是否存在，只有都存在才可能出现相等的情况。

最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 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) {
        ListNode *headpre = new ListNode(0, head);
        ListNode *nw = headpre;
        while (nw->next && nw->next->next) {
            if (nw->next->val == nw->next->next->val) {
                int x = nw->next->val;
                while (nw->next && nw->next->val == x) {
                    nw->next = nw->next->next;
                }
            } else {
                nw = nw->next;
            }
        }
        return headpre->next;
    }
};

2024-01-16

题目传送门：2719. 统计整数数目 - 力扣（LeetCode）

一道数位DP的题目

2024-01-17

题目传送门：2744. 最大字符串配对数目 - 力扣（LeetCode）

双重循环直接解决问题。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {
        int n = words.size();
        int ans = 0;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(words[i][0] == words[j][1] && words[i][1] == words[j][0]) ans++;
            }
        }
        return ans;
    }
};

2024-01-20

题目传送门：2788. 按分隔符拆分字符串 - 力扣（LeetCode）

签到题（对于Python来说哈哈），C的话主要可能需要使用stringstream以及getline函数，具体见我的C整理。

最终代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string> splitWordsBySeparator(vector<string>& words, char separator) {
        vector<string> res;
        for (string &word : words) {
            stringstream ss(word);
            string sub;
            while (getline(ss, sub, separator)) {
                if (!sub.empty()) {
                    res.push_back(sub);
                }
            }
        }
        return res;
    }
};

2024-01-21

题目传送门：410. 分割数组的最大值 - 力扣（LeetCode）

一道DP题目，设置dp二维数组dp[n+1][k+1]dp[n+1][k+1]其中nn表示数组长度，kk表示分割次数。定义dp[i][j]dp[i][j]的含义是从第1个数到第ii个数分成kk段后的最大值。那么不难想到状态转移方程应该表示为：

dp[j][i]=min⁡(dp[j][i],max⁡(dp[kk][i−1],nums_sum[j]−nums_sum[kk]))dp[j][i] = \min(dp[j][i],\max(dp[kk][i-1], nums\_sum[j]-nums\_sum[kk]))

其中nums_sumnums\_sum是前缀和数组, 因此nums_sum[j]nums\_sum[j]表示的是前jj个数的和。

接下来就是dp限制条件和初始状态的定义了，观察上述状态转移方程，不难得知方程想要正确运行需要j≥ij\geq i且kk≥i−1kk\geq i-1 且j>kkj > kk。这样如果采用递推的方法的话我们就可以确定循环的顺序了。

1
2
3
for(int i=2; i<=k; ++i){
	for(int j=i; j<=n; ++j){
		for(int kk=i-1; kk<=j-1; ++kk)

最后就是初始条件的确定了，其实就是初始化dp[i][1]=nums_sum[i]dp[i][1] = nums\_sum[i] ,然后循环就可以从第二个分割开始循环了。

注意

dp数组最开始初始化一定是INT_MAX

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(n+1,vector<int>(k+1, INT_MAX));
        vector<int> nums_sum(n+1,0);
        dp[0][1] = 0;
        for(int i=0;i<n;++i) {
            dp[i+1][1] = dp[i][1] + nums[i];
            nums_sum[i+1] = nums_sum[i] + nums[i];
        }
        for(int i=2; i<=k; ++i){
            for(int j=i; j<=n; ++j){
                for(int kk=i-1; kk<=j-1; ++kk){
                    dp[j][i] = min(dp[j][i],max(dp[kk][i-1], nums_sum[j]-nums_sum[kk]));
                }
            }
        }
        return dp[n][k];
    }
};

记忆化搜索同理，逻辑反过来就行,会更简单易懂一些：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        dp[0][1] = 0;
        for (int i = 1; i <= n; ++i) dp[i][1] = dp[i - 1][1] + nums[i - 1];
        function<int(int, int)> dfs = [&](int u, int v) {
            if (v == 1) return dp[u][1];
            if (dp[u][v] != INT_MAX) return dp[u][v];
            int tmp = INT_MAX;
            for (int i = v - 1; i < u; ++i) {
                tmp = min(tmp, max(dfs(i, v - 1), dp[u][1] - dp[i][1]));
            }
            return dp[u][v] = tmp;
        };
        return dfs(n, k);
    }
};

还是建议使用递推，因为效率更高！！！

2024-01-22

题目传送门：670. 最大交换 - 力扣（LeetCode）

这道题解决方法应该还是很多的，但是因为之前在学习单调栈，所以这里第一时间想到的是基于单调栈的解法。

主体思路很简单，就是我们倒着扫描这个数的每一位，维护一个单调栈，这样每次我们扫描的时候就可以知道当前第i个数是否有下一个比他大的数。如果有我们使用一个数组ans记录比他大的数的索引。最后正着扫一遍数组，如果碰到第一个第ii个数的ans[i]中存储了索引，则进行交换操作即可。

注意

判断出栈的时候是>>不是>=>=，这是因为当值一样时，换更后面的显然更优，最后判断当前数存不存索引的时候一定要判断当前数和栈底数的大小关系（因为有可能一样大，这时就不需要进行交换）

最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maximumSwap(int num) {
        string num_s = to_string(num);
        int n = num_s.size();
        vector<int> stk;
        vector<int> ans(n,-1);
        for(int i=n-1;i>=0;--i){
            while(!stk.empty() && num_s[i]-'0' > num_s[stk[stk.size()-1]] - '0')stk.pop_back();
            if (!stk.empty() && num_s[i]-'0' < num_s[stk[0]] - '0') ans[i] = stk[0];
            stk.emplace_back(i);
        }
        for(int i=0;i<n;++i){
            if (ans[i]!=-1) {
                int tmp = num_s[ans[i]]-'0';
                num_s[ans[i]] = num_s[i];
                num_s[i] = tmp + '0';
                break;
            }
        }
        return stoi(num_s);
    }
};

2023-01-23

题目传送门：2765. 最长交替子数组 - 力扣（LeetCode）

签到题目，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int n = nums.size(),pre = nums[0];
        int ans = -1;
        for(int i=1;i<n;++i){
            if (nums[i] == pre+1) {
                int tmp = 2;
                pre = nums[i];
                int dir = -1;
                while (i+1<n && pre + dir == nums[i+1]){
                    dir *= -1;
                    i += 1;
                    pre = nums[i];
                    tmp ++;
                }
                ans = max(ans,tmp);
            }
            pre = nums[i];
        }
        return ans;
    }
};

2024-01-24

题目传送门：2865. 美丽塔 I - 力扣（LeetCode）

这道题同样也是一道单调栈的题目，还是有点意思。

1

2024-01-25

题目传送门：2859. 计算 K 置位下标对应元素的和 - 力扣（LeetCode）

一道位运算签到题目，统计二进制数有多少个置位，只需要&1和右移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int n = nums.size();
        function<int(int)>bitCount = [&](int i){
            int nw = 0;
            while(i){
                nw += i&1;
                i = i>>1;
            }
            return nw;
        };
        int ans = 0;
        for(int i=0;i<n;++i){
            if (bitCount(i)==k) {
                ans += nums[i];
            }
        }
        return ans;
    }
};

2024-01-26

题目传送门：

本站由 @anonymity 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。