力扣题目训练（15）

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];}
};