devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【每日一题】2024年3月汇编（上）

作者：我家自动化 | 2024-03-26 09:28:55

赞

踩

【每日一题】2024年3月汇编（上）

3.1【2369】检查数组是否存在有效划分

2369. 检查数组是否存在有效划分icon-default.png?t=N7T8https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/

1.这样的判断可以用动态规划来解决，用一个长度为(n+1) 的数组来记录  是否存在有效划分，dp[i] 表示前 i 个元素组成的数组是否至少存在一个有效划分。边界情况 dp[0] 恒为 true而 dp[n] 即为结果。

动态规划的公式为：

这道题目是一个简单的dp，经历了上个月树的一整个月的dfs，bfs的洗礼，盲猜这个月都是dp。

  1. class Solution {
  2. public:
  3.     bool validPartition(vector<int>& nums) {
  4.          int n = nums.size();
  5.         vector<int> dp(n + 1,0);
  6.        
  7.         dp[0] = true;
  8.         for(int i = 1; i <= n; i++){
  9.             if(i >= 2){
  10.                 dp[i] = dp[i - 2] && validTwo(nums[i - 1],nums[i - 2]);
  11.             }
  12.             if(i >= 3){
  13.                 dp[i] = dp[i] || dp[i -3] && validThree(nums[i -3], nums[i -2],nums[i - 1]);
  14.             }
  15.         }
  16.         return dp[n];
  17.     }
  18.     bool validTwo(int num1,int num2){
  19.         return num1 == num2;
  20.     }
  21.     bool validThree(int num1, int num2, int num3){
  22.         return (num1 == num2 && num2 == num3) || (num1 + 1 == num2 && num2 + 1 == num3);
  23.     }
  24. };

3.2【2368】受限条件下可能达到的节点数目

2368. 受限条件下可到达节点的数目icon-default.png?t=N7T8https://leetcode.cn/problems/reachable-nodes-with-restrictions/

没想到今天的题目又回到了树的遍历问题，和上个月的一道题很像，是一个求邻接表然后进行dfs的题目

  1. 对于lamda表达式：捕获列表（Capture List）：[&]，这表示以引用的方式捕获外部变量。参数列表（Parameter List）：(int x, int f)，这是lambda函数接受的两个整数参数。返回类型：这里返回类型为 void，由于使用了 function<void(int,int)> 进行了明确的类型声明。

  2.  lamda表示式定义的第二个参数是为了，遍历的时候不往回找，一直往下找。
  3. 临近表的操作定义二维数组存储即可，做限制的函数一维数组置1即可。
  1. class Solution {
  2. public:
  3.     int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
  4.         //邻接表
  5.         vector<vector<int>> g(n);
  6.         for(auto &v : edges){
  7.             g[v[0]].push_back(v[1]);
  8.             g[v[1]].push_back(v[0]);
  9.         }
  10.         //做限制
  11.         vector<int> isrestricted(n);
  12.         for(auto &x : restricted){
  13.             isrestricted[x] = 1;
  14.         }
  15.         int cnt = 0; 
  16.         function<void(int,int)> dfs = [&](int x,int f){
  17.             cnt ++;
  18.             for(auto &y : g[x]){
  19.                  if(y != f && !isrestricted[y])
  20.                  dfs(y,x);
  21.             }
  22.         };
  23.         dfs(0,-1);
  24.         return cnt;
  25.     }
  26. };

3.3【225】用队列实现栈

225. 用队列实现栈icon-default.png?t=N7T8https://leetcode.cn/problems/implement-stack-using-queues/

easy题目，熟悉队列基本操作，还有拓展准备一下一个队列的解法

 方法一：两个队列(O(1))

  1. class MyStack {
  2. public:
  3.     queue<int> q1;
  4.     queue<int> q2;
  5.  
  6.     MyStack() {
  7.      
  8.     }
  9.     
  10.     void push(int x) {
  11.             q2.push(x);
  12.             while(!q1.empty()){
  13.                 q2.push(q1.front());
  14.                 q1.pop();
  15.             }
  16.             swap(q1,q2);
  17.     }
  18.     
  19.     int pop() {
  20.           int r = q1.front();
  21.           q1.pop();
  22.           return r;
  23.     }
  24.     
  25.     int top() {
  26.     return(q1.front());
  27.     }
  28.     
  29.     bool empty() {
  30.           return(q1.empty());
  31.     }
  32. };
  33.

*方法二 一个队列(O(n))

  1. queue<int> q1;
  2.     MyStack() {
  3.      
  4.     }  
  5.     void push(int x) {
  6.         int n = q1.size();
  7.        q1.push(x);
  8.        for(int i = 0; i < n; i++){
  9.            q1.push(q1.front());
  10.            q1.pop();
  11.        }

3.4【232】用栈实现队列

232. 用栈实现队列icon-default.png?t=N7T8https://leetcode.cn/problems/implement-queue-using-stacks/

较为简单，双栈实现队列的push，pop等工作

  1. class MyQueue {
  2. public:
  3.     stack<int> instack,oustack;
  4.     MyQueue() {
  5.  
  6.     }
  7.     
  8.     void push(int x) {
  9.         instack.push(x);
  10.     }
  11.     
  12.     int pop() {
  13.         if(oustack.empty()){
  14.         while(!instack.empty()){
  15.             oustack.push(instack.top());
  16.             instack.pop();
  17.         }
  18.         }
  19.        int r =  oustack.top();
  20.        oustack.pop();
  21.        return r;
  22.     }
  23.     
  24.     int peek() {
  25.         if(oustack.empty()){
  26.          while(!instack.empty()){
  27.             oustack.push(instack.top());
  28.             instack.pop();
  29.         }
  30.         }
  31.         return oustack.top();
  32.     }
  33.     
  34.     bool empty() {
  35.        return(instack.empty() && oustack.empty());
  36.     }
  37. };
  38.  
  39. /**
  40.  * Your MyQueue object will be instantiated and called as such:
  41.  * MyQueue* obj = new MyQueue();
  42.  * obj->push(x);
  43.  * int param_2 = obj->pop();
  44.  * int param_3 = obj->peek();
  45.  * bool param_4 = obj->empty();
  46.  */

3.6【2917】找出数组中的k-or值

2917. 找出数组中的 K-or 值icon-default.png?t=N7T8https://leetcode.cn/problems/find-the-k-or-of-an-array/

题目难以理解什么意思，主要是按照给的范围遍历位运算

由于给定了nums中元素的范围，我们位从1到31遍历，每一次循环右移i位与1按位与，就是最后一位和1与，记录数目。如果说大于给定的k，对于这个第i位，1向左移动i位和ans按位或 。

  1. class Solution {
  2. public:
  3.     int findKOr(vector<int>& nums, int k) {
  4.         int ans = 0;
  5.  for(int i = 0; i < 31; i++)
  6. {
  7.     int cnt = 0;;
  8.     for(int num: nums){
  9.         if(num >> i & 1 ){
  10.             cnt ++;
  11.         }
  12.     }
  13.       if(cnt >= k){
  14.           ans |=  1<<i;
  15.       }
  16. }    
  17. return ans;
  18. }
  19. };

3.8【2834】找出美丽数组的最小和

2834. 找出美丽数组的最小和icon-default.png?t=N7T8https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/

作一个贪心，卡住范围，整体思路就不难了

  1. 分析题目，按照贪心，要最小和，所以从1开始，按顺序递增的加，但是到二分之target就不能取了，然后就从target依次往后取。
  2.  根据等差数列求和公式就可以解决
  3. 注意int不行，要给个long long防止溢出
  1. class Solution {
  2. public:
  3.     int minimumPossibleSum(int n, int target) {
  4.         const int mod = 1e9 + 7;
  5.         int m = target / 2;
  6.         if(n <= m){
  7.             return (long long)(1 + n) * n / 2 % mod;
  8.          }
  9.          else{
  10.              return ((long long)(1 + m) * m /2 + ((long long)target + target + (n - m) - 1) * (n - m) /2) % mod;
  11.          }
  12.     }
  13. };

3.10【299】猜数字游戏

299. 猜数字游戏icon-default.png?t=N7T8https://leetcode.cn/problems/bulls-and-cows/

今天的题目其实就是一个模拟，熟悉数组存储数据个数。

 先把猜对的对应上的数字记录下来，然后如果不对应，用两个数组全部对应，我一开始的思路是先把对应的记录下来，然后删除再去比其他的就要麻烦不少。

用两个数组记录其他的地方出现的数字的个数，最后再通过min，找出猜对了，但是位置不对的个数。

  1. class Solution {
  2. public:
  3.     string getHint(string secret, string guess) {
  4.         int bulls = 0;
  5.         vector<int> cntS(10),cntG(10);
  6.         for(int i = 0; i < secret.size(); i++){
  7.             if(secret[i] == guess[i]) {
  8.                 bulls++;
  9.             }
  10.             else{
  11.                 ++cntG[secret[i] - '0'];
  12.                 ++cntS[guess[i] - '0'];
  13.             }
  14.         }
  15.  
  16.         int cows = 0;
  17.         for(int i = 0; i < 10;i++){
  18.             cows += min(cntS[i],cntG[i]);
  19.         }
  20.         return to_string(bulls) + 'A' + to_string(cows) + 'B';
  21.     }
  22. };

3.11【2129】将标题首字母大写

2129. 将标题首字母大写icon-default.png?t=N7T8https://leetcode.cn/problems/capitalize-the-title/

看题目知道是一个模拟题，大小写转换比较经典，如果用c++的话，一句话一句话的模拟会发现确实很麻烦，题解中用到一个l，一个r指向每一个单词的前后端，思路更为清晰

  1.  toupper，tolower大小写字母转换
  2. 整体思路，while大循环，tittle后边加个空格，防止结尾不同处理。先把r移动到单词的最右边 ，判断单词个数是否需要首字母置为大写，再所有的字母置为小写，最后把最后的空格删掉
  1. class Solution {
  2. public:
  3.     string capitalizeTitle(string title) {
  4.         int l = 0,r = 0;
  5.         int n = title.size();
  6.         title.push_back(' ');
  7.         while(r < n){
  8.             while(title[r] != ' '){r ++;}
  9.             if(r - l > 2){
  10.                 title[l] = toupper(title[l]);
  11.                 ++l;
  12.             }
  13.             while(l < r){
  14.                 title[l] = tolower(title[l]);
  15.                 ++l;
  16.             }
  17.             l = r + 1;
  18.             ++r;
  19.         }
  20.         title.pop_back();
  21.         return title;
  22.     }
  23. };

3.12【1261】在受污染的二叉树中查找元素

1261. 在受污染的二叉树中查找元素icon-default.png?t=N7T8https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree/

DFS+哈希表，还原二叉树以后，找target的个数是否大于0
  1.  用DFS还原二叉树，再判断个数，难度不大
  1. class FindElements {
  2. public:
  3.     unordered_set<int> valSet;
  4.     void dfs(TreeNode* node,int val){
  5.         if(!node){
  6.             return;
  7.         }
  8.         node -> val = val;
  9.         valSet.insert(val);
  10.         dfs(node -> left,val * 2 + 1);
  11.         dfs(node -> right,val * 2 + 2);
  12.     }
  13.  
  14.     FindElements(TreeNode* root) {
  15.             dfs(root,0);
  16.     }
  17.     
  18.     bool find(int target) {
  19.        return valSet.count(target) > 0;
  20.     }
  21. };

3.13【2864】最大二进制奇数

2864. 最大二进制奇数icon-default.png?t=N7T8https://leetcode.cn/problems/maximum-odd-binary-number/

复刷指数：0

简单题，直接模拟

  1. class Solution {
  2. public:
  3.     string maximumOddBinaryNumber(string s) {
  4.         int sum = 0;
  5.         for(int i = 0; i < s.size(); i++){
  6.             if(s[i] == '1'){
  7.                 sum++;
  8.             }
  9.         }
  10.         string s1;
  11.         
  12.         for(int i = 0; i < sum - 1 ;i++){
  13.             s1.push_back('1');
  14.         }
  15.         for(int i = 0; i < s.size() - sum; i++){
  16.             s1.push_back('0');
  17.         }
  18.         s1.push_back('1');
  19.         return s1;
  20.     }
  21. };

3.14【2789】合并后数组的最大元素

2789. 合并后数组中的最大元素icon-default.png?t=N7T8https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/

复刷指数：1

倒叙遍历+贪心。难度不大

  1. 我们从后往前倒序遍历一次数组，依次比较两个相邻的元素，如果两个相邻的元素能够合并，就将其合并。如果不能合并，就继续往前判断。因为这样的操作流程，在比较过程中，靠后的数是所有操作流程可能性中能产生的最大值，而靠前的数，是所有操作流程可能性中能产生的最小值。如果在遍历过程中，比较的结果是不能合并，那么其他任何操作流程都无法合并这两个数。如果可以合并，那我们就贪心地合并，因为这样能使接下来的比较中，靠后的数字尽可能大。

  1. class Solution {
  2. public:
  3.     long long maxArrayValue(vector<int>& nums) {
  4.         long long sum = nums.back();
  5.         for(int i = nums.size() - 2; i >= 0; i--){
  6.             sum = nums[i] <= sum ? nums[i] + sum : nums[i];
  7.         }
  8.         return sum;
  9.     }
  10. };

3.16【2684】矩阵中移动的最大次数

2684. 矩阵中移动的最大次数icon-default.png?t=N7T8https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/

两轮遍历，注意限制索引

  1. 如果满足要求就让ans等于列数，如果不满足，就把这个地方设为最大值，后边都不会比他大了
  2.  从第一列开始遍历，因为和前面一列进行比较，这个方法主要是因为搜索过程只能前进不能后退
  1. class Solution {
  2. public:
  3.     int maxMoves(vector<vector<int>>& grid) {
  4.         int m = grid.size();
  5.         int n = grid[0].size();
  6.         int ans = 0;
  7.         for(int i = 1; i < n; i++){//列
  8.             for(int j = 0; j < m; j++){
  9.                 if(grid[j][i] > grid[j][i - 1] || j > 0 && grid[j][i] > grid[j-1][i -1] ||j + 1 < m && grid[j][i] > grid[j + 1][i -1]){//限制索引
  10.                     ans = i;
  11.                 }
  12.                 else{
  13.                     grid[j][i] = INT_MAX;
  14.                 }
  15.             }
  16.         }
  17.         return ans;
  18.     }
  19. };

3.17【310】最小高度树

310. 最小高度树icon-default.png?t=N7T8https://leetcode.cn/problems/minimum-height-trees/

复刷指数：5

很漂亮的一道题，难度已经是中等题的天花板，是一个从外向内部剥菜的思想，内嵌BFS

 

  1. 核心思想：最矮树的根一定不是入度为1的点（画图看下，很容易证明），把最矮树的叶子节点全部减掉，剩下的仍然是最矮树。所以对一个图，不断的把它的叶子节点减掉，减到最后剩下的就一定是最矮树的根。
  2. 普通思想就是BFS遍历每一个节点，统计每个节点的高度，用map存储起来，查询高度集合中最小的，但是会超时。我们从边缘开始，先找到所有出度为1的节点，然后把所有出度为1的节点进队列，然后不断地bfs，最后找到的就是两边同时向中间靠近的节点，那么这个中间节点就相当于把整个距离二分了，那么它当然就是到两边距离最小的点啦，也就是到其他叶子节点最近的节点了。
  1. class Solution {
  2. public:
  3.     vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
  4.         vector<int> res;
  5.         if(n == 1){
  6.             res.push_back(0);
  7.             return res;
  8.         }
  9. //      建立度的表
  10.         vector<int> degree(n,0);
  11.         vector<vector<int>> map (n,vector<int>());
  12.         for(auto &edge : edges){
  13.             degree[edge[0]]++;
  14.             degree[edge[1]]++;
  15.             map[edge[0]].push_back(edge[1]);
  16.             map[edge[1]].push_back(edge[0]);
  17.         }
  18. //      建立队列，把度为1的点扔进去开始剥皮
  19.         queue<int> q;
  20.         for(int i = 0; i < n; i++){
  21.             if(degree[i] == 1) {q.push(i);}
  22.         }
  23.         while(!q.empty()){
  24.             res.clear();//我们每次要清空，这样最后就剩下最小高度树了
  25.             int size = q.size();
  26.             for(int i = 0; i < size; i++){
  27.                 int cur = q.front();
  28.                 q.pop();
  29.                 res.push_back(cur);//把所有当前节点加入结果集
  30.                 vector<int> neighbors = map[cur];//用一个数组接一下
  31.                 //经典BFS
  32.                 for(int neighbor : neighbors){
  33.                     degree[neighbor] --;
  34.                     if(degree[neighbor] == 1){
  35.                         q.push(neighbor);
  36.                     }
  37.                 }
  38.             }
  39.         }
  40.         return res;
  41.     }
  42. };

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/316071
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号