LeetCode：2024年04月每日一题

2024-04-01

题目传送门：2810. 故障键盘 - 力扣（LeetCode）

一道双端队列数据结构题，我们换一种思路来想，如果遇上字符i，旋转之前的所有字符相当于换一个方向进行插入操作，因此我们使用一个双端队列来模拟这个操作。

最后实现代码如下：

class Solution {
public:
    string finalString(string s) {
        deque<char> q;
        bool head = false;
        for (auto ch:s){
            if(ch!='i'){
                if (head) q.push_front(ch);
                else q.push_back(ch);
            } else {
                head = !head;
            }
        }
        string ans = (head ? string{q.rbegin(), q.rend()} : string{q.begin(), q.end()});
        return ans;
    }
};

2024-04-02

题目传送门：894. 所有可能的真二叉树 - 力扣（LeetCode）

这道题暴露出自己对于分治算法还是有一些遗忘，需要多加练习。整体思路比较简单，在每层递归中，如果当前不剩余节点，则返回空数组（其实这个判断只会在第一次进行，后面保证左右节点分到的个数都为奇数，因为偶数肯定不满足条件），如果只剩1个，则自己当叶子节点，否则枚举左右两边节点数量。然后进行下一轮递归。下一层递归会返回一个vector，代表不同的左右子树。然后只需排列组会一下便可得到这一层的所有子树形状，封装成vector往上返回即可。

最后实现代码如下：

/**
 * 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:
    vector<TreeNode*> allPossibleFBT(int n) {
        vector<TreeNode*> ans;
        if (n % 2 == 0) return ans;
        if (n == 1) {
            ans = {new TreeNode(0)};
            return ans;
        }
        for(int i=1; i<n; i+=2){
            vector<TreeNode*> left_ans = allPossibleFBT(i);
            vector<TreeNode*> right_ans = allPossibleFBT(n-1-i);
            for(TreeNode* lnode:left_ans){
                for(TreeNode* rnode:right_ans){
                    TreeNode *root = new TreeNode(0, lnode, rnode);
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

2024-04-03

题目传送门：1379. 找出克隆二叉树中的相同节点 - 力扣（LeetCode）

一道简单的遍历题目，我们只需要在递归遍历的时候让克隆树执行和原树一样的操作即可。停止条件就是当克隆树节点对应的原树位置的节点等于目标节点时返回克隆树节点指针。

最后实现代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        
        if (target==original) return cloned;
        if (original->left!=nullptr){
            TreeNode* tmp = getTargetCopy(original->left,cloned->left, target);
            if(tmp != nullptr) return tmp;
        }
        if (cloned->right!=nullptr){
            TreeNode* tmp = getTargetCopy(original->right,cloned->right, target);
            if(tmp != nullptr) return tmp;
        }
        return static_cast<TreeNode*>(nullptr);
        
    }
};

2024-04-04

题目传送门：2192. 有向无环图中一个节点的所有祖先 - 力扣（LeetCode）

一道较为明显的拓扑排序板子题目，这里在合并祖先的时候使用了vector的insert方法。详情用法可见C++->vector->insert部分的介绍。

最后实现代码如下：

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<int> in(n,0);
        vector<vector<int>> anc(n);
        vector<vector<int>> e(n);
        for(auto & edge:edges){ 
            in[edge[1]]++;
            e[edge[0]].push_back(edge[1]);
        }
        queue<int> que;
        for(int i=0;i<n;++i){
            if (in[i]==0) que.push(i);
        }
        while (!que.empty()) {
            int u = que.front(); que.pop();
            for(auto &v:e[u]){
                anc[v].push_back(u);
                anc[v].insert(anc[v].end(),anc[u].begin(),anc[u].end());
                sort(anc[v].begin(),anc[v].end());
                auto nwend = unique(anc[v].begin(),anc[v].end());
                anc[v].erase(nwend, anc[v].end());
                in[v]--;
                if (in[v]==0) que.push(v);
            }
        }
        return anc;
    }
};

2024-04-05

题目传送门：1026. 节点与其祖先之间的最大差值 - 力扣（LeetCode）

自底向上进行DFS，对于当前节点，调用dfs后返回以所有儿子为根的子树的最大值和最小值，然后更新以当前节点为根的子树的最大值和最小值。在递归的过程中，维护最大差值。最大差值 $ans$ 可以表述为：

ans = \max(maxx,ans)

maxx = \max(abs(当前节点值-当前节点为根子树最大值),abs(当前节点值-当前节点为根子树最小值))

其中maxx代表每个节点为根的子树的最大差值

最后实现代码如下：

/**
 * 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 maxAncestorDiff(TreeNode* root) {
        int maxx = 0;
        function<pair<int,int>(TreeNode*)> dfs = [&](TreeNode* u) {
            pair<int,int> tmp = make_pair(u->val,u->val);
            if (u->left!=nullptr) {
                pair<int,int> temp = dfs(u->left);
                tmp.first = min(min(temp.first, temp.second), tmp.first);
                tmp.second= max(max(temp.first, temp.second),tmp.second);
            }
            if (u->right!=nullptr) {
                pair<int,int> temp = dfs(u->right);
                tmp.first = min(min(temp.first, temp.second), tmp.first);
                tmp.second= max(max(temp.first, temp.second),tmp.second);
            }
            maxx = max(maxx,max(abs(tmp.first - u->val),abs(tmp.second - u->val)));
            return tmp;
        };
        dfs(root);
        return maxx;
    }
};

2024-04-06

题目传送门：1483. 树节点的第 K 个祖先 - 力扣（LeetCode）

本题目是一道使用倍增思想的DP题目。定义ancs[i][j]代表i节点的第 $2^j$ 个祖先，然后进行刷表即可。

最后实现代码如下：

class TreeAncestor {
public:
    vector<vector<int>> ancs;
    constexpr static int LOG = 16;
    TreeAncestor(int n, vector<int>& parent) {
        ancs = vector<vector<int>>(n,vector<int>(LOG, -1));
        for (int i=0; i<n; ++i) {
            ancs[i][0] = parent[i];
        }
        for (int i=1;i<LOG;++i) {
            for (int j=0; j<n; ++j){
                if (ancs[j][i-1] != -1){
                    ancs[j][i] = ancs[ancs[j][i-1]][i-1];
                }
            }
        }
    }

    int getKthAncestor(int node, int k) {
        for(int i=LOG; i>=0; --i){
            if ((k>>i)&1) {
                node = ancs[node][i];
                if (node==-1) return -1;
            }
        }
        return node;
    }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

2024-04-07

题目传送门：1600. 王位继承顺序 - 力扣（LeetCode）

这道题其实就是一个多叉树的前序遍历，但是因为使用的是字符串，所以需要使用到unordered_set以及unordered_map等相关STL（使用方法见C++文档）:

最后实现代码如下：

class ThroneInheritance {
private:
    unordered_map<string, vector<string>> edges;
    unordered_set<string> dead;
    string king;
public:
    ThroneInheritance(string kingName) {
        king = kingName;
    }
    
    void birth(string parentName, string childName) {
        edges[parentName].push_back(childName);
    }
    
    void death(string name) {
        dead.insert(name);
    }
    
    vector<string> getInheritanceOrder() {
        vector<string> ans;

        function<void(string)> dfs = [&](string u) {
            if (!dead.count(u)) ans.push_back(u);
            if (edges.count(u)) {
                for (auto v:edges[u]){
                    dfs(v);
                }
            }
        };
        dfs(king);
        return ans;
    }
};

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance* obj = new ThroneInheritance(kingName);
 * obj->birth(parentName,childName);
 * obj->death(name);
 * vector<string> param_3 = obj->getInheritanceOrder();
 */

2024-04-08

题目传送门：2009. 使数组连续的最少操作数 - 力扣（LeetCode）

假设 $x$ 是修改后的连续数字的最大值，则修改后的连续数字的范围为闭区间 $[x−n+1,x]$ ，其中 $n$ 是 nums 的长度。在修改前，对于已经在 $[x−n+1,x]$ 中的数，我们无需修改。那么， $x$ 取多少，可以使无需修改的数最多呢？

由于元素的位置不影响答案，且要求所有元素互不相同，我们可以将 nums 从小到大排序，并去掉重复元素。设 a 为nums 排序去重后的数组。将 a[i] 画在一条数轴上，本题相当于有一个长度为 n 的滑动窗口，我们需要计算窗口内最多可以包含多少个数轴上的点。

最后实现代码如下：

class Solution {
public:
    int minOperations(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int now_n = unique(nums.begin(), nums.end()) - nums.begin();
        int ans = 0, r = 0;
        for (int l=0; l<now_n; ++l) {
            while (r<now_n && nums[r]-nums[l] < n) r++;
            ans = max(r-l, ans);
        }
        return n - ans;
    }
};

2024-04-09

题目传送门：2529. 正整数和负整数的最大计数 - 力扣（LeetCode）

纯签到题。

最后实现代码如下：

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int a = 0,b = 0;
        for(auto&num:nums){
            if (num>0) a++;
            if (num<0) b++;
        }
        return max(a, b);
    }
};

2024-04-10

题目传送门：1702. 修改后的最大二进制字符串 - 力扣（LeetCode）

这道题题解建议看灵神的推理方法，讲解的十分透彻。
题解传送门：贪心，简洁写法（Python/Java/C++/Go/JS/Rust）

最后实现代码如下：

class Solution {
public:
    string maximumBinaryString(string binary) {
        int n = binary.size();
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (binary[i] == '0') {
                while (j <= i || (j < n && binary[j] == '1')) {
                    j++;
                }
                if (j < n) {
                    binary[j] = '1';
                    binary[i] = '1';
                    binary[i + 1] = '0';
                }
            }
        }
        return binary;
    }
};

2024-04-11

题目传送门：1766. 互质树 - 力扣（LeetCode）

这道题就是一道DFS题目，因为取值非常小，所以可以先进行预处理，先把50以内所有互质的数预处理出来。由于根节点到任意节点的搜索路径就是该节点的祖先节点的集合，所以搜索路径上最近的与其互质的就是答案。在搜索遍历树处理答案的时候，有许多信息可以复用。

最后实现代码如下：

class Solution {
private:
    vector<vector<int>> gcds; 
    vector<vector<int>> tmp;
    vector<vector<int>> g;
    vector<int> dep;
    vector<int> ans;
public:
    void dfs(vector<int> &nums, int x, int depth) {
        dep[x] = depth;
        for (int val : gcds[nums[x]]) {
            if (tmp[val].empty()) {
                continue;
            }

            int las = tmp[val].back();
            if (ans[x] == -1 || dep[las] > dep[ans[x]]) {
                ans[x] = las;
            }
        }
        tmp[nums[x]].push_back(x);

        for(int val : g[x]) { 
            if (dep[val] == -1) { // 被访问过的点dep不为-1
                dfs(nums, val, depth + 1);
            }
        }
        tmp[nums[x]].pop_back();
    }
    vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();

        // 初始化
        gcds.resize(51);
        tmp.resize(51);
        ans.resize(n, -1);
        dep.resize(n, -1);
        g.resize(n);

        for (int i = 1; i <= 50; i++) {
            for (int j = 1; j <= 50; j++) {
                if (gcd(i, j) == 1) {
                    gcds[i].push_back(j);
                } 
            }
        }

        for (const auto &val : edges) {
            g[val[0]].push_back(val[1]);
            g[val[1]].push_back(val[0]);
        }

        dfs(nums, 0, 1);
        return ans;
    }
};

2024-04-12

题目传送门：2923. 找到冠军 I - 力扣（LeetCode）

有点像拓扑排序第一步，统计每个节点的入度。这里我们设定A比B强，表示有一条边由A指向B。最后我们返回入度为0的节点即可。

最后实现代码如下：

class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> rank(n,0);
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                if (grid[i][j] == 1) {
                    rank[j] ++;
                }
            }
        }
        for (int i=0; i<n; ++i){
            if (rank[i]==0) return i;
        }
        return -1;
    }
};

2024-04-13

题目传送门：2924. 找到冠军 II - 力扣（LeetCode）

与昨天的题目思路完全一样，最后实现代码如下：

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> ins(n, 0);
        for(auto &edge:edges) {
            ins[edge[1]]++;
        }
        int cnt = 0, ans = -1;
        for(int i=0;i<n;++i) {
            if (ins[i]==0) cnt++,ans=i;
        }
        if (cnt == 1) return ans;
        return -1;
    }
};

2024-04-14

题目传送门：705. 设计哈希集合 - 力扣（LeetCode）

STL unordered_set 练习题，最后实现代码如下：

class MyHashSet {
private:
    unordered_set<int> myset;
public:
    MyHashSet() {}
    void add(int key) {myset.insert(key);}
    void remove(int key) {myset.erase(key);}
    bool contains(int key) {return myset.find(key) != myset.end();}
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

2024-04-15

题目传送门：706. 设计哈希映射 - 力扣（LeetCode）

STL unordered_map 练习题，最后实现代码如下：

class MyHashMap {
private:
    unordered_map<int, int> mp;
public:    
    void put(int key, int value) {mp[key] = value;}
    
    int get(int key) {
        if (mp.find(key)!=mp.end()) return mp[key];
        return -1;
    }
    void remove(int key) {mp.erase(key);}
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

2024-04-16

题目传送门：924. 尽量减少恶意软件的传播 - 力扣（LeetCode）

一道细节较多的DFS/并查集题目，其实就是找init中存在的最大连通块（第一次读题都快了以为是找图中的割点），只不过找到了需要注意：

如果一个连通块中，只有一个initial中的节点被感染，则将他移除这个连通块不会感染。但是如果有2个及以上的节点被感染，则删掉一个以后这个连通块仍然会被感染。所以具体来说我们需要找的是只有一个initial节点在连通块中的最大连通块。（判断两个点是否在一个连通块中可以通过并查集或者unordered_set）

还有需要注意的是，存在特殊情况找不到一个点在一个连通块中（每个连通块都存在2个及以上的initial中的点），此时返回下标最小的initial点即可。

最后实现代码如下：

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size(), m = initial.size();
        sort(initial.begin(),initial.end()); // 排序方便选最小，这样如果都在一个连通块中也可很快选出最小的
        vector<bool> vis(n, false);
        unordered_set<int> se;
        for (auto init:initial) se.insert(init);
        function<pair<int, bool>(int)> dfs = [&](int u){
            int num = 1; bool flag = false;
            for(int i=0;i<n;++i){
                if (graph[u][i] && !vis[i]) {
                    vis[i] = true;
                    if (se.find(i)!=se.end()) flag = true;
                    pair<int,bool> tmp = dfs(i);
                    num += tmp.first;
                    flag |= tmp.second;
                }
            }
            return make_pair(num, flag);
        };
        int ans=initial[0],nw=0;
        for (auto init:initial) {
            if (vis[init]) continue;
            vis[init] = true;
            pair<int,bool> tmp = dfs(init);
            if (tmp.second!=true && (tmp.first > nw || (tmp.first == nw && init < ans))) nw=tmp.first, ans=init;
        }
        return ans;
    }
};

2024-04-17

题目传送门：928. 尽量减少恶意软件的传播 II - 力扣（LeetCode）

此题为上一道题目的衍生版本，最后实现代码如下：

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<int> init_size(n);
        for (auto init:initial) init_size[init] = 1;
        vector<int> ufa(n);
        iota(ufa.begin(), ufa.end(), 0);
        for (int u=0; u<n; ++u){
            if(init_size[u]==1) continue;
            for(int v=0; v<n; ++v){
                if(init_size[v]==1) continue;
                if (graph[u][v] == 1) {merge(uf, u, v);}
            }
        }
    }
};

2024-04-18

题目传送门：2007. 从双倍数组中还原原数组 - 力扣（LeetCode）

STL map使用题，使用一个map记录当前键值以及当前键值所出现的次数，遍历map是按照键值从小到大顺序的，对于当前键值，如果*2后的键值出现次数大于等于当前键值数量，则将当前键值加入答案队列中（数量保持一致），否则则证明不存在这个数列，返回空。注意0进行特殊判定一下。

最后实现代码如下：

class Solution {
public:
    vector<int> findOriginalArray(vector<int>& changed) {
        sort(changed.begin(), changed.end());
        map<int, int> mp;
        vector<int> ans={};
        for(auto &i:changed) {
            if (mp.find(i)==mp.end()) mp[i] = 1;
            else mp[i]++;
        }
        for(auto it = mp.begin();it != mp.end(); ++it){
            if (it->first == 0 && it->second%2) return vector<int>{};
            if (it->second == 0) continue;
            auto it2 = mp.find(it->first*2);
            if (it2!=mp.end() && it2->second >= it->second) {
                if (it->first == 0)it->second /= 2;
                for(int i=1;i<=it->second;++i) ans.push_back(it->first);
                it2->second -= it->second;
                it->second = 0;
            } else {
                return vector<int>{};
            }
        }
        return ans;
    }
};

2024-04-19

题目传送门：1883. 准时抵达会议现场的最小跳过休息次数 - 力扣（LeetCode）

读完题目后，观察数据范围不难判断此题应该是一道dp，设dp[i][j]代表到达第i个地方使用j次跳过所需要的最小时间（i>j）。可以非常简单写出状态转移方程：

1 2	double tmp_t = (double)dist[i-1]/speed; dp[i][j] = min(ceil(dp[i-1][j]) + tmp_t, dp[i-1][j-1]+tmp_t)

下面再来讨论一下边界以及初始化条件，首先为了方便起见，将所有dp数组初始化成一个非常大的int值，dp[0][0] = 0,

当j=0时，不能使用上面的状态转移方程(存在j-1)项，因此可以写为

1	dp[i][0] = ceil(dp[i-1][0]-EPS)+tmp_t;

以上便是这道DP的核心部分，但是当我提交后发现一直过不了。这是因为：

浮点数运算的细节（摘自LeetCode官方题解）

根据 IEEE 754 标准，浮点数在计算机中存储的精度是有限的，而本题中我们不可避免的会使用「浮点数运算」以及「向上取整」运算，如果强行忽略产生的计算误差，会得到错误的结果。

举一个简单的例子，假设使用的语言中「向上取整」运算的函数为 ceil，下面的运算：

1	ceil(8.0 + 1.0 / 3 + 1.0 / 3 + 1.0 / 3)

应当是 9，而计算机会给出 10。这是因为浮点数误差导致：

1	8.0 + 1.0 / 3 + 1.0 / 3 + 1.0 / 3

计算出的结果约为：

1	9.000000000000002

向上取整后会得到 10，产生了错误的答案。

因此我们引入常量 EPS 表示一个极小值，例如 $10^{-7}$ 。在进行「向上取整」运算前，我们将待取整的浮点数减去 EPS 再进行取整，就可以避免上述的误差。

同时，我们需要说明 EPS 不会引入其它的问题。在本题中速度最大为 $10^{6}$ ，时间与速度成反比，那么 EPS 的粒度只需要高于时间的精度 $10^{-6}$ 即可，取 $10^{-7}$ 或 1 $10^{-8}$ 都是可行的。

最后实现代码如下：

class Solution {
private:
    // 可忽略误差
    static constexpr double EPS = 1e-7;
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<vector<double>> dp(1002,vector<double>(1002,1e8+7));
        dp[0][0] = 0;
        for(int i=1;i<=n;++i){
            double tmp_t = (double)dist[i-1]/speed;
            dp[i][0] = ceil(dp[i-1][0]-EPS)+tmp_t;
            for(int j=1;j<i;++j){
                dp[i][j] = min(ceil(dp[i-1][j]-EPS)+tmp_t,dp[i-1][j-1]+tmp_t);
            }
        }
        for(int i=0;i<n;++i){
            if (dp[n][i] <= hoursBefore) return i;
        }
        return -1;
    }
};

就是因为加了EPS才AC了，我们C++真是太神奇辣！！！

2024-04-20

题目传送门：39. 组合总和 - 力扣（LeetCode）

打暴搜即可，超过target进行剪枝。

最后实现代码如下：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> tmp;
        int n = candidates.size();
        function<void(int,int)> dfs = [&](int loc, int nw_sum) {
            if (nw_sum > target) return;
            if (nw_sum == target) {
                ans.push_back(tmp);
                return;
            }
            for(int i=loc;i<n;++i){
                tmp.push_back(candidates[i]);
                dfs(i, nw_sum+candidates[i]);
                tmp.pop_back();
            }
        };
        dfs(0, 0);
        return ans;
    }
};

2024-04-21

题目传送门：216. 组合总和 III - 力扣（LeetCode）

和昨天题目差不多大暴搜，多了一个剪枝条件加上即可。

最后实现代码如下：

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> tmp;
        function<void(int,int,int)> dfs = [&](int cnt,int loc,int nw_sum) {
            if (nw_sum > n || cnt > k) return;
            if (nw_sum == n && cnt == k){
                ans.push_back(tmp);return;
            }
            for(int i=loc;i<=9;++i){
                tmp.push_back(i);
                dfs(cnt+1,i+1,nw_sum+i);
                tmp.pop_back();
            }
        };
        dfs(0,1,0);
        return ans;
    }
};

2024-04-22

题目传送门：377. 组合总和 Ⅳ - 力扣（LeetCode）

刚看到这个题还没反应过来是DP，直接一发暴搜，但是超时了，让我仔细思考了一下，发现其实就是一个和爬楼梯一样的简单DP。

但是需要注意的是，可能会存在溢出的情况，所以我们的dp数组开成unsigned类型

最后实现代码如下：

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned> dp(target+3,0);
        dp[0] = 1;
        for(int i=1;i<=target;++i){
            for(auto num:nums){
                if (num <= i){
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    }
};

2024-04-23

题目传送门：1052. 爱生气的书店老板 - 力扣（LeetCode）

滑动窗口一下，很简单的啦！

最后实现代码如下：

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int init=0,n=customers.size();
        for(int i=0; i<n; ++i) if (!grumpy[i]) init += customers[i];
        int tmp = 0;
        for(int i=0; i<minutes; ++i) if(grumpy[i]) tmp += customers[i];
        int ans = tmp;
        for(int i=1;i<=n-minutes;++i){
            if (grumpy[i-1]) tmp -= customers[i-1];
            if (grumpy[i-1+minutes]) tmp += customers[i-1+minutes];
            if (tmp > ans) ans = tmp;
        }
        return init + ans;
    }
};

2024-04-24

题目传送门：2385. 感染二叉树需要的总时间 - 力扣（LeetCode）

我首先想到的办法是做两次DFS，第一遍建图，第二遍以给定节点为根，算最长时间。

最后实现代码如下：

/**
 * 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 amountOfTime(TreeNode* root, int start) {
        vector<vector<int>> edges(100003); 
        function<void(TreeNode*)> dfs = [&](TreeNode* u) {
            if(u->left!=nullptr){
                edges[u->val].emplace_back(u->left->val);
                edges[u->left->val].emplace_back(u->val);
                dfs(u->left);
            }
            if(u->right!=nullptr){
                edges[u->val].emplace_back(u->right->val);
                edges[u->right->val].emplace_back(u->val);
                dfs(u->right);
            }
        };
        dfs(root);
        function<int(int,int)> dfs2 = [&](int u,int fa){
            int tmp=0;
            for (auto v:edges[u]) {
                if (v==fa) continue;
                tmp = max(tmp, dfs2(v,u));
            }
            return 1+tmp;
        }; 
        return dfs2(start,-1)-1;
    }
};

但是上面这个代码太极限了，卡着时限交了三次评测机过了一次（笑）：

Pasted image 20240425155926

于是需要再想想有没有改进方法。

2024-04-25

题目传送门：2739. 总行驶距离 - 力扣（LeetCode）

签到题目，最后实现代码如下：

class Solution {
public:
    int distanceTraveled(int mainTank, int additionalTank) {
        int ans = 0;
        while (mainTank >=5 ) {
            ans += 50; mainTank -= 5;
            if (additionalTank) mainTank++,additionalTank--;
        }
        return ans + mainTank*10;
    }
};

2024-04-26

题目传送门：1146. 快照数组 - 力扣（LeetCode）

此题如果想到了是二分+哈希表就比较容易了，二分还是比较好想，观察数据范围为50000，便可知每次进行snap操作，对整个数组进行复制是不现实的。

对于此题，可以采用unordered_set对历史修改进行维护：

1	unordered_map<int, vector<pair<int, int>>> history;

其中，map的索引代表的是位置，pair的第一个值记录对当前位置进行修改时的snap_id,第二个值记录对当前位置修改时，更改的值val。后续进行get操作时，只需要对pair第一个进行二分即可（找小于等于给定snap_id的最后一个更改值）

最后实现代码如下：

class SnapshotArray {
private:
    int cnt = 0;
    unordered_map<int, vector<pair<int, int>>> history; 
public:
    SnapshotArray(int length) {}
    
    void set(int index, int val) {
        history[index].emplace_back(cnt, val);
    }
    
    int snap() {
        return cnt++;
    }
    
    int get(int index, int snap_id) {
        auto& tmp = history[index];
        int l = 0, r = tmp.size();
        while (l < r) {
            int mid = l + ((r-l)>>1);
            if (tmp[mid].first > snap_id) r = mid;
            else l = mid+1;
        }
        if ((l-1)<0) return 0;
        return tmp[l-1].second;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

2024-04-27

题目传送门：2639. 查询网格图中每一列的宽度 - 力扣（LeetCode）

签到题目，最后实现代码如下：

class Solution {
public:
    vector<int> findColumnWidth(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> res(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int x = grid[i][j];
                int length = 0;
                if (x <= 0) {
                    length = 1;
                }
                while (x != 0) {
                    length += 1;
                    x /= 10;
                }
                res[j] = max(res[j], length);
            }
        }
        return res;
    }
};

2024-04-28

题目传送门：1017. 负二进制转换 - 力扣（LeetCode）

这里需要使用到我们小学所学进制转换的知识，让我们来回顾一下：

负二进制表示的定义

负二进制数表示形式使用基数 -2。对于一个整数 $n$ ，我们希望将其表示为负二进制形式：

n = a_0 \cdot (-2)^0 + a_1 \cdot (-2)^1 + a_2 \cdot (-2)^2 + \ldots

其中 $a_i$ 是二进制位，取值只能为0或1。

取模的意义

当我们说对2取模时，我们的目标是找到当前位 $a_i$ 的值，并调整 $n$ 以继续处理下一位。

转换过程

假设我们在某一步计算中，当前的值为 $n$ 。

确定当前位的值：

a_i = n \mod 2

然而，对于负数取模，可能会得到负数结果。为确保 $a_i$ 是0或1，我们使用如下公式：

a_i = (n\mod 2 + 2) \mod 2

这个公式确保了 $a_i$ 结果为0或1，无论 $n$ 是正数还是负数。（非常重要！！！）

调整 $n$ 的值：

由于我们已经确定了当前位 $a_i$ 的值，我们需要调整 $n$ 以便处理下一位。调整方法是：

n = n - a_i

这一步确保我们已经扣除了当前位的影响。

处理下一位：

我们需要将 $n$ 除以基数 -2，以继续处理下一位：

n = \frac{n}{-2}

通过这种方式，调整后的 $n$ 准备好处理下一位。

数学解释

假设我们在第 $k$ 步，有当前值 $n_k$ ：

n_k = a_k \cdot (-2)^k + a_{k+1} \cdot (-2)^{k+1} + a_{k+2} \cdot (-2)^{k+2} + \ldots

通过上述步骤，我们确定当前位 $a_k$ ：

a_k = (n_k \mod 2 + 2) \mod 2

然后，我们调整 $n$ 以扣除当前位：

n_k' = n_k - a_k

最后，我们将调整后的 $n_k'$ 除以 -2，以继续处理下一位：

n_{k+1} = \frac{n_k'}{-2}

代码中的体现

将上述逻辑表示为代码,最后实现代码如下：

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0 || n == 1) return to_string(n);
        string res;
        while (n != 0) {
            int rem = (n % 2 + 2) % 2;  // 确定当前位的值
            res.push_back('0' + rem);  // 将当前位添加到结果字符串
            n -= rem;  // 调整 n 的值
            n /= -2;  // 准备处理下一位
        }
        reverse(res.begin(), res.end());  // 反转结果字符串
        return res;
    }
};

总结

通过对2取模并进行调整，我们可以确保每一位 $a_i$ 是0或1，并且通过除以-2继续处理下一位。这种方法利用了数学上的取模和调整，使得负二进制转换过程简洁而高效。

2024-04-29

题目传送门：1329. 将矩阵按对角线排序 - 力扣（LeetCode）

模拟一下，对每个对角线都来排个序就可以了，非常的简单。

最后实现代码如下：

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int> tmp;
        for(int i=0;i<n;++i){
            int cnt = 0;
            while(i+cnt < n && cnt < m) tmp.emplace_back(mat[i+cnt][cnt]),cnt++;
            sort(tmp.begin(),tmp.end());
            cnt -= 1;
            while(cnt >= 0) mat[i+cnt][cnt] = tmp[cnt],cnt--,tmp.pop_back();
        }
        for(int i=0;i<m;++i){
            int cnt = 0;
            while(cnt < n && cnt+i < m) tmp.emplace_back(mat[cnt][cnt+i]),cnt++;
            sort(tmp.begin(),tmp.end());
            cnt -= 1;
            while(cnt >= 0) mat[cnt][cnt+i] = tmp[cnt],cnt--,tmp.pop_back();;
        }
        return mat;
    }
};

2024-04-30

题目传送门：2798. 满足目标工作时长的员工数目 - 力扣（LeetCode）

签到题目，循环一遍比大小即可，最后实现代码如下：

class Solution {
public:
    int numberOfEmployeesWhoMetTarget(vector<int>& hours, int target) {
        int ans = 0;
        for (int i = 0; i < hours.size(); i++) {
            if (hours[i] >= target) {
                ans++;
            }
        }
        return ans;
    }
};

2024年4月勋章