力扣题目训练(15)

news/2024/4/23 4:12:13

2024年2月8日力扣题目训练

  • 2024年2月8日力扣题目训练
    • 507. 完美数
    • 520. 检测大写字母
    • 521. 最长特殊序列 Ⅰ
    • 221. 最大正方形
    • 237. 删除链表中的节点
    • 115. 不同的子序列

2024年2月8日力扣题目训练

2024年2月8日第十五天编程训练,今天主要是进行一些题训练,包括简单题3道、中等题2道和困难题1道。惰性太强现在才完成,不过之后我会认真完成的。

507. 完美数

链接: 完美数
难度: 简单
题目:
题目描述

运行示例:
运行示例

思路:
这道题是求因子,我从1~n遍历找到其正因子,然后求和判断是否为完美数。
代码:

class Solution {
public:bool checkPerfectNumber(int num) {int sum = 0;int i = num-1;while(i){if(num%i == 0) sum+=i;i--;}return sum == num;}
};

520. 检测大写字母

链接: 检测大写字母
难度: 简单
题目:
题目描述

运行示例:
运行示例

思路:
这道题是单次扫描,看每一个字母是否满足题意即可。
代码:

class Solution {
public:bool detectCapitalUse(string word) {int low = 0;int up = 0, bup = 0;for(int i = 0; i < word.size(); i++){if(word[i]>='A' && word[i] <= 'Z'){if(low != 0) return false;up++;if( i == 0) bup++;}else{if(up != bup) return false;low++;}}return true;}
};

521. 最长特殊序列 Ⅰ

链接: 最长特殊序列
难度: 简单
题目:
题目描述

运行示例:
运行示例

思路:
这道题要注意题目中的独有两个字,s1 = ‘ab’,s2 = ‘a’,因为ab是s1独有,所以最长子序列为ab,s1 = ‘ab’, s2 = ‘ab’, 因为ab是两个串都有,ab排除,a也是两个串都有,排除,b也是两个串都有,排除。所以最长特殊序列不存在,返回-1通过以上分析,我们可以得出结论,如果:两个串相等(不仅长度相等,内容也相等),那么他们的最长特殊序列不存在。返回-1
如果两个串长度不一样,那么长的串 永远也不可能是 短串的子序列,即len(s1) > len(s2),则最长特殊序列为s1,返回长度大的数 。
代码:

class Solution {
public:int findLUSlength(string a, string b) {if(a == b) return -1;return max(a.size(),b.size());}
};

221. 最大正方形

链接: 最大正方形
难度: 中等
题目:
题目描述

运行示例:
运行示例

思路:
这道题涉及状态以及连续一般都是利用动态规划解决。dp(i,j)表示以 (i,j)为右下角,且只包含 1 的正方形的边长最大值。如果该位置的值是 1,则 dp(i,j)的值由其上方、左方和左上方的三个相邻位置的 dp值决定。
代码:

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();if(n == 0 || m == 0) return 0;int maxSize = 0;vector<vector<int>> dp(n,vector<int>(m));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(matrix[i][j] == '1'){if(i == 0 || j == 0){dp[i][j] = 1;}else{dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;}maxSize = max(maxSize,dp[i][j]);}}}return maxSize*maxSize;}
};

237. 删除链表中的节点

链接: 删除链表中的节点
难度: 中等
题目:
题目描述

运行示例:
运行示例

思路:
这道题是删除当前节点,既然我们不知道之前节点,那我们可以将其复制为下一个节点,然后删除下一个节点即可。
代码:

class Solution {
public:void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;}
};

115. 不同的子序列

链接: 子序列
难度: 困难
题目:
题目描述

运行示例:
运行示例

思路:
这种题我感觉要用动态规划但是具体怎么用还是不太会。
官方解法如下
在这里插入图片描述
在这里插入图片描述

代码:

class Solution {
public:int numDistinct(string s, string t) {int m = s.size(),n = t.size();if(m < n) return 0;vector<vector<unsigned long long>> dp(m+1,vector<unsigned long long>(n+1));for(int i = 0; i <= m; i++){dp[i][n] = 1;}for(int i = m - 1; i >= 0; i--){char sChar = s[i];for (int j = n - 1; j >= 0; j--){char tChar = t[j];if(sChar == tChar) dp[i][j] = dp[i+1][j+1]+dp[i+1][j];else dp[i][j] = dp[i+1][j];}}return dp[0][0];}
};

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

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

相关文章

开关电源电路主要元器件基础知识详解

在学习电子电路过程中&#xff0c;电源我们无法绕开的一个重要部分&#xff0c;很多时候&#xff0c;故障就出现在电源部分&#xff0c;特别是开关电源。开关电源电路主要是由熔断器、热敏电阻器、互感滤波器、桥式整流电路、滤波电容器、开关振荡集成电路、开关变压器、光耦合…

微服务学习Day4

文章目录 初始MQ同步通讯和异步通讯MQ常见技术介绍 RabbitMQ快速入门入门案例 SpringAMQP介绍例子WorkQueue模型exchange交换机消息转换器 初始MQ 同步通讯和异步通讯 MQ常见技术介绍 RabbitMQ快速入门 入门案例 SpringAMQP 介绍 例子 WorkQueue模型 exchange交换机 消息转换…

Ubuntu忘记登录密码重置步骤

Ubuntu忘记登录密码重置步骤 1.开机界面长按shitf键&#xff0c;进入grub&#xff0c;并选择Advanced options for ubuntu&#xff0c;按下回车 2.选择一个较新版本的recovery mode&#xff0c;按下回车 3.会跑一些数据&#xff0c;等待跑完后会出现下面的界面&#xff0c;选择…

【Linux】---Linux下基本指令(2)

目录 一、指令详细介绍1.1 cat 指令1.2 echo 指令1.3 more 指令1.4 less 指令1.5 head 指令1.6 tail 指令1.7 date 指令1.8 cal 指令1.9 find 指令1.10 grep 指令1.11 zip/unzip 指令1.12 tar 指令1.13 uname –r 指令&#xff1a; 一、指令详细介绍 1.1 cat 指令 语法&#…

CSS之BFC

BFC概念 BFC&#xff08;Block Formatting Context&#xff09;即块级格式化上下文&#xff0c;是Web页面的可视CSS渲染的一部分。它是一个独立的渲染区域&#xff0c;让其中的元素在布局上与外部的元素互不影响。简单来说&#xff0c;BFC提供了一个环境&#xff0c;允许内部的…

【刷题记录】合并两个有序数组、移除元素

本系列博客为个人刷题思路分享&#xff0c;有需要借鉴即可。 1.题目链接&#xff1a; T1&#xff1a;LINK T2&#xff1a;LINK 2.详解思路&#xff1a; T1: 思路1&#xff1a;弄个新数组&#xff0c;比较两个数组中的值&#xff0c;哪个小就把哪个值放到新数组中。 分析1&a…