【每日一题】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。

class Solution {
public:
    bool validPartition(vector<int>& nums) {
         int n = nums.size();
        vector<int> dp(n + 1,0);
       
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            if(i >= 2){
                dp[i] = dp[i - 2] && validTwo(nums[i - 1],nums[i - 2]);
            }
            if(i >= 3){
                dp[i] = dp[i] || dp[i -3] && validThree(nums[i -3], nums[i -2],nums[i - 1]);
            }
        }
        return dp[n];
    }
    bool validTwo(int num1,int num2){
        return num1 == num2;
    }
    bool validThree(int num1, int num2, int num3){
        return (num1 == num2 && num2 == num3) || (num1 + 1 == num2 && num2 + 1 == num3);
    }
};

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即可。
class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
        //邻接表
        vector<vector<int>> g(n);
        for(auto &v : edges){
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        //做限制
        vector<int> isrestricted(n);
        for(auto &x : restricted){
            isrestricted[x] = 1;
        }
        int cnt = 0; 
        function<void(int,int)> dfs = [&](int x,int f){
            cnt ++;
            for(auto &y : g[x]){
                 if(y != f && !isrestricted[y])
                 dfs(y,x);
            }
        };
        dfs(0,-1);
        return cnt;
    }
};

3.3【225】用队列实现栈

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

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

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

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;

    MyStack() {
     
    }
    
    void push(int x) {
            q2.push(x);
            while(!q1.empty()){
                q2.push(q1.front());
                q1.pop();
            }
            swap(q1,q2);
    }
    
    int pop() {
          int r = q1.front();
          q1.pop();
          return r;
    }
    
    int top() {
    return(q1.front());
    }
    
    bool empty() {
          return(q1.empty());
    }
};

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

queue<int> q1;
    MyStack() {
     
    }  
    void push(int x) {
        int n = q1.size();
       q1.push(x);
       for(int i = 0; i < n; i++){
           q1.push(q1.front());
           q1.pop();
       }
    

3.4【232】用栈实现队列

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

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

class MyQueue {
public:
    stack<int> instack,oustack;
    MyQueue() {

    }
    
    void push(int x) {
        instack.push(x);
    }
    
    int pop() {
        if(oustack.empty()){
        while(!instack.empty()){
            oustack.push(instack.top());
            instack.pop();
        }
        }
       int r =  oustack.top();
       oustack.pop();
       return r;
    }
    
    int peek() {
        if(oustack.empty()){
         while(!instack.empty()){
            oustack.push(instack.top());
            instack.pop();
        }
        }
        return oustack.top();
    }
    
    bool empty() {
       return(instack.empty() && oustack.empty());
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

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按位或 。

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int ans = 0;
 for(int i = 0; i < 31; i++)
{
    int cnt = 0;;
    for(int num: nums){
        if(num >> i & 1 ){
            cnt ++;
        }
    }
      if(cnt >= k){
          ans |=  1<<i;
      }
}    
return ans;
}
};

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防止溢出
class Solution {
public:
    int minimumPossibleSum(int n, int target) {
        const int mod = 1e9 + 7;
        int m = target / 2;
        if(n <= m){
            return (long long)(1 + n) * n / 2 % mod;
         }
         else{
             return ((long long)(1 + m) * m /2 + ((long long)target + target + (n - m) - 1) * (n - m) /2) % mod;
         }
    }
};

3.10【299】猜数字游戏

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

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

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

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

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0;
        vector<int> cntS(10),cntG(10);
        for(int i = 0; i < secret.size(); i++){
            if(secret[i] == guess[i]) {
                bulls++;
            }
            else{
                ++cntG[secret[i] - '0'];
                ++cntS[guess[i] - '0'];
            }
        }

        int cows = 0;
        for(int i = 0; i < 10;i++){
            cows += min(cntS[i],cntG[i]);
        }
        return to_string(bulls) + 'A' + to_string(cows) + 'B';
    }
};

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移动到单词的最右边 ,判断单词个数是否需要首字母置为大写,再所有的字母置为小写,最后把最后的空格删掉
class Solution {
public:
    string capitalizeTitle(string title) {
        int l = 0,r = 0;
        int n = title.size();
        title.push_back(' ');
        while(r < n){
            while(title[r] != ' '){r ++;}
            if(r - l > 2){
                title[l] = toupper(title[l]);
                ++l;
            }
            while(l < r){
                title[l] = tolower(title[l]);
                ++l;
            }
            l = r + 1;
            ++r;
        }
        title.pop_back();
        return title;
    }
};

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

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

DFS+哈希表,还原二叉树以后,找target的个数是否大于0
  1.  用DFS还原二叉树,再判断个数,难度不大
class FindElements {
public:
    unordered_set<int> valSet;
    void dfs(TreeNode* node,int val){
        if(!node){
            return;
        }
        node -> val = val;
        valSet.insert(val);
        dfs(node -> left,val * 2 + 1);
        dfs(node -> right,val * 2 + 2);
    }

    FindElements(TreeNode* root) {
            dfs(root,0);
    }
    
    bool find(int target) {
       return valSet.count(target) > 0;
    }
};

3.13【2864】最大二进制奇数

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

复刷指数:0

简单题,直接模拟

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int sum = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '1'){
                sum++;
            }
        }
        string s1;
        
        for(int i = 0; i < sum - 1 ;i++){
            s1.push_back('1');
        }
        for(int i = 0; i < s.size() - sum; i++){
            s1.push_back('0');
        }
        s1.push_back('1');
        return s1;
    }
};

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

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

复刷指数:1

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

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

class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        long long sum = nums.back();
        for(int i = nums.size() - 2; i >= 0; i--){
            sum = nums[i] <= sum ? nums[i] + sum : nums[i];
        }
        return sum;
    }
};

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

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

两轮遍历,注意限制索引

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

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,最后找到的就是两边同时向中间靠近的节点,那么这个中间节点就相当于把整个距离二分了,那么它当然就是到两边距离最小的点啦,也就是到其他叶子节点最近的节点了。
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> res;
        if(n == 1){
            res.push_back(0);
            return res;
        }
//      建立度的表
        vector<int> degree(n,0);
        vector<vector<int>> map (n,vector<int>());
        for(auto &edge : edges){
            degree[edge[0]]++;
            degree[edge[1]]++;
            map[edge[0]].push_back(edge[1]);
            map[edge[1]].push_back(edge[0]);
        }
//      建立队列,把度为1的点扔进去开始剥皮
        queue<int> q;
        for(int i = 0; i < n; i++){
            if(degree[i] == 1) {q.push(i);}
        }
        while(!q.empty()){
            res.clear();//我们每次要清空,这样最后就剩下最小高度树了
            int size = q.size();
            for(int i = 0; i < size; i++){
                int cur = q.front();
                q.pop();
                res.push_back(cur);//把所有当前节点加入结果集
                vector<int> neighbors = map[cur];//用一个数组接一下
                //经典BFS
                for(int neighbor : neighbors){
                    degree[neighbor] --;
                    if(degree[neighbor] == 1){
                        q.push(neighbor);
                    }
                }
            }
        }
        return res;
    }
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/465766.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【iOS】ARC学习

文章目录 前言一、autorelease实现二、苹果的实现三、内存管理的思考方式__strong修饰符取得非自己生成并持有的对象__strong 修饰符的变量之间可以相互赋值类的成员变量也可以使用strong修饰 __weak修饰符循环引用 __unsafe_unretained修饰符什么时候使用__unsafe_unretained …

webstorm 使用prettier格式化保存 导致代码缩进与gitlab代码不一致问题

问题 webstorm显示缩进正常 gitlab显示不正常 解决 .prettierrc.js module.exports {printWidth: 100,tabWidth: 2,useTabs: false, //设置为false 不使用tab作为缩进符semi: true,vueIndentScriptAndStyle: true,singleQuote: true,quoteProps: as-needed,bracketSpaci…

肖恩的投球游戏——前缀和

题目链接&#xff1a;1.肖恩的投球游戏 - 蓝桥云课 (lanqiao.cn) 前缀和&#xff1a; package lanqiao;import java.util.Arrays; import java.util.Scanner;/*** 2023/11/29* 前缀和问题*/ public class lanqiao3693_肖恩的投球游戏 {public static void main(String[] args) …

vue3+vite项目打包遇到的问题

一、项目打包出现空白页 vite.config.js中&#xff0c;添加base: ./ import { defineConfig } from vite import vue from vitejs/plugin-vueexport default defineConfig({base: ./, })router/index.js&#xff0c;将路由模式改成hash模式 import { createRouter, createWe…

性能分析调优模型

性能测试除了为获取性能指标外&#xff0c;更多是为了发现性能瓶颈和性能问题&#xff0c;然后针对性能问题和性能瓶颈进行分析和调优。在当今互联网高速发展的时代&#xff0c;结合传统软件系统模型以及互联网网站特征&#xff0c;性能调优的模型可以归纳总结为如图1-5-1所示的…

idea 的基本配置

一、安装目录介绍 其中&#xff1a;bin 目录下&#xff1a; 二、配置信息目录结构 这是 IDEA 的各种配置的保存目录。这个设置目录有一个特性&#xff0c;就是你删除掉整个目录之后&#xff0c;重新启动 IntelliJ IDEA 会再自动帮你生成一个全新的默认配置&#xff0c;所以很多…

力扣● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 编辑距离总结篇

● 583. 两个字符串的删除操作 注意审题&#xff1a; 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 删除最少的字符使两者相同&#xff0c;说明留下来的就是最大公共子序列。不要求…

01.Vue2入门

一、为什么要学习Vue 1.前端必备技能 2.岗位多&#xff0c;绝大互联网公司都在使用Vue 3.提高开发效率 4.高薪必备技能&#xff08;Vue2Vue3&#xff09; 二、什么是Vue 概念&#xff1a;Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套 **构建用户界面 ** 的 渐进式 …

多种双拼方案的实现

首发日期 2024-03-14, 以下为原文内容: 就像 GNU/Linux 用户, 虽然比例小, 却又分散为一堆不同的发行版. 双拼用户在拼音输入法之中的比例也很小, 同时也分为各种不同的双拼方案. 那么作为一个 双拼 输入法, 最重要的事情是什么呢 ? 嗯, 那当然是支持自定义双拼方案 ! 实际上…

网络协议与层次划分:探索计算机网络体系结构

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

AWTK slider_circle 控件发布

slider_circle 控件。 主要特色&#xff1a; 支持正向和反向支持设置滑块的半径支持背景线宽和颜色支持前景线宽和颜色支持设置是否显示值的文本支持设置起始角度和结束角度支持设置格式化值的格式字符串支持使用图片填充背景和前景 界面效果&#xff1a; 注意&#xff1a; …

【绘图案例-绘图的方式1 Objective-C语言】

一、接下来,我们来说这个,绘图的方式 1.新建一个项目,Name:04-绘图的方式, 方式:就是,我要同样画一条线,然后,用不同的代码,把它写出来,这就叫方式, 我们在storyboard里边,还拖一个UIView,这些步骤都一样, 我们来一个,宽= 300, 高 = 300 , 然后,再来一个水…

zabbix配置

1 下载zabbix 1 配置yum源 rpm -Uvh https://repo.zabbix.com/zabbix/5.0/rhel/7/x86_64/zabbix-release- 5.0-1.el7.noarch.rpm yum clean all yum makecache fast 完成后会出现zabbix.repo文件 2安装zabbix服务 yum -y install zabbix-server-mysql zabbix-web-mysql z…

计算机网络——物理层(信道复用技术)

计算机网络——物理层&#xff08;信道复用技术&#xff09; 信道复用技术频分多址与时分多址 频分复用 FDM (Frequency Division Multiplexing)时分复用 TDM (Time Division Multiplexing)统计时分复用 STDM (Statistic TDM)波分复用码分复用 我们今天接着来看信道复用技术&am…

20W-50W厚膜无感电阻TO-220封装技术规格散热说明

EAK为设计工程师提供了一种开放式屏蔽基板器件&#xff0c;用于需要卓越热性能的应用&#xff0c;开发了一种额定功率高达 50W 的厚膜功率电阻器。该电阻器采用 TO-220 开放式屏蔽基板封装&#xff0c;并具有与基板粘合的绝缘锥形文丘里管&#xff0c;以实现最大的散热。 电阻器…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Counter)

计数器组件&#xff0c;提供相应的增加或者减少的计数操作。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 可以包含子组件。 接口 Counter() 从API version 9开始&#xff0c;该接口…

Flask 专题

[CISCN2019 总决赛 Day1 Web3]Flask Message Board 查看session解密 但不知道密钥&#xff0c;题目说FLASK,那肯定就是找密钥,发现输入什么都没有显示&#xff0c;只有author那里有回显在版上&#xff0c;所以尝试sstl&#xff0c;{{config}}找到密钥 扫目录发现有admin进入…

Python数学建模-2.5Pandas库介绍

2.5.1Pandas基本操作 Pandas是一个强大的Python数据分析库&#xff0c;它提供了快速、灵活且富有表现力的数据结构&#xff0c;设计初衷是为了处理关系型或标记型数据。Pandas的基本操作涵盖了数据的读取、处理、筛选、排序、分组、合并以及可视化等多个方面。 以下是一些Pan…

判断闰年(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int year 2000;//执行循环判断&#xff1b;while (year < 2010){//执行流程&#xff1b;//判断能否整除4&#xff1…

配置IPv4静态路由示例

配置IPv4静态路由示例 图1 配置IP静态路由组网图 组网需求配置思路操作步骤配置文件 组网需求 如图1所示&#xff0c;STA1、STA2和PC1属于不同网段&#xff0c;STA1在AP1中上线&#xff0c;STA2在AP2中上线&#xff0c;要求配置静态路由&#xff0c;使PC1与STA1和STA2能够互…