Constexpression's blog

力扣每日一题

2023-04-10

2023.4.10 链表中的下一个更大节点

STL - emplace 与 push 的区别：emplace可以直接传入构造对象需要的元素，然后自己调用其构造函数 S.emplace(1,2)

实际上不难，太久没刷了。用单调栈就行。

注意STL的使用。每次先对vector进行一次push_back(0),才不会越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        ListNode* cur = head;
        vector<int> ans;
        stack<pair<int,int>> s;
        int i = -1;
        while(cur) {
            i++;
            ans.push_back(0);
            while (!s.empty() && cur->val > s.top().first) {
                ans[s.top().second] = cur->val;
                s.pop();
            }
            s.emplace(cur->val,i);
            cur = cur->next;
        }
        return ans;
    }
};

2023.4.14 \1023. 驼峰式匹配

最近状态不太好…

这道题主要是理解难。实际上不难…

理解了就能写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<bool> camelMatch(vector<string>& queries, string pattern) {
        int n = queries.size();
        vector<bool> ans(n,true); 
        for(int i = 0; i < n; i++) {
            int k = 0;
            for(int j = 0; j < queries[i].size(); j++) {
                if(queries[i][j] == pattern[k] && k <pattern.size()) {
                    k++;
                }
                else if(isupper(queries[i][j])){
                    ans[i] = false;
                    break;
                }
            }
            if(k < pattern.size()) ans[i] = false;
        }
        return ans;
    }
};

2023.4.15 \1042. 不邻接植花

实际不难。就是一个基于邻接图的简单的搜索思想。

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
class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        int l = paths.size();
        vector<vector<int>> adj(n);
        vector<int> ans(n);
        //生成邻接表
        for(int i = 0; i < l; i++) {
            adj[paths[i][0]-1].push_back(paths[i][1]-1) ;
            adj[paths[i][1]-1].push_back(paths[i][0]-1) ;
        }
        for(int i = 0; i < n; i++) {
            vector<bool> colored(5,false);
            for(int j = 0; j < adj[i].size(); j++){
                colored[ans[adj[i][j]]] = true;
            }
            for(int k = 1; k < 5; k++){
                if(colored[k] == false){
                    ans[i] = k;
                    break;
                }
            }
        }
        return ans;
    }
};

2023.4.16 \1157. 子数组中占绝大多数的元素

……你这个threshold小于子数组长度大于一半的子数组长度应该放在前面啊要不然谁知道…

如果不考虑时间的话就是一个很机械的算法。但是到数量过多的时候就要考虑剪枝和随机化了。

2023.4.17 \2409. 统计共同度过的日子数

简单题。处理用到stoi和substr函数。构造日期表这种想法也不错。

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 countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        vector<int> days = {31,28,31,30,31,30,31,31,30,31,30,31};
        vector<int> already(1,0);
        for(int i = 0; i < 12; i++){
            already.push_back(already.back()+days[i]);
        }
        int aa = getDate(arriveAlice,already);
        int al = getDate(leaveAlice,already);
        int ba = getDate(arriveBob,already);
        int bl = getDate(leaveBob,already);
        return max(0,min(bl,al) - max(ba,aa)+1);
    }

    int getDate(string str,vector<int> &already) {
        int mon = stoi(str.substr(0,2));
        int date = stoi(str.substr(3));
        return already[mon-1] + date; 
    }

};

2023.6.1 \2517. 礼盒的最大甜蜜度

每日一题，堂堂复活！

这个题难点在于想到用二分去优化

其实说白了也就是基于穷举法的优化

有一个疑点是：怎么知道在某个mid下我在糖果中选取的种类是最多的，而不会浪费糖果呢？

举个例子，对于目标甜度是3的情况

3

prices：1 4 5 7

此时显然按答案算法是1，但是肯定可以配出(1,5),(4,7)两种。

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
class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
       int n = price.size();
       sort(price.begin(),price.end());
       int left = 0, right = price[n - 1] - price[0];
       while(left < right) {
           int mid = (left + right + 1) >> 1;
           if (calculate(price, k, mid)){
               right = mid-1;
           }
           else {
               left = mid;
           }
       } 
       return right;
    }
    bool calculate(vector<int> &price, int k, int mid) {
        int num = 0;
        int pre = INT_MIN >> 1;;
        for(int i = 0; i < price.size(); i++) {
            if(price[i] - pre >= mid) {
                num++;
                pre = price[i];
            }
        }
        return num < k;
    }
};
Tags: 算法
← 读Query-Aware 怎么编写makefile →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章