LeetCode 1517, 205, 124
1517. 查找拥有有效邮箱的用户
题目链接
表
- 表
Users的字段为user_id、name和mail。
要求
编写一个解决方案，以查找具有有效电子邮件的用户。
一个有效的电子邮件具有前缀名称和域，其中：
- 前缀 名称是一个字符串，可以包含字母（大写或小写），数字，下划线
'_'，点'.'和/或破折号'-'。前缀名称 必须 以字母开头。 - 域 为
'@leetcode.com'。
以任何顺序返回结果表。
知识点
regexp：正则表达式匹配。-：表示从某个字符到另一个字符。例如0-9表示字符0到9。[]：表示限制字符为中括号里面的字符。例如[0-9]表示限制字符为0到9中的一个，[a-zA-z-0-9]表示限制字符为0到9、a到z、A到Z中的一个。如果字符以单个字符的形式出现，没有被包含在中括号里面，例如leetcode，则表示匹配为leetcode的字符串。^：表示以某个字符开头。例如^[a-z]表示以小写字符a到z作为字符串的前缀。$：表示以某个字符结尾。例如com$表示以字符串com作为字符串的后缀。*：表示可以有多个(0个及以上)字符。例如[a-z]*表示字符串中有多个(0个及以上)小写字符a到z。转义：在正则表达式中，一些字符是有特殊含义的，比如.表示任意单个字符，如果想要匹配.则需要使用\\来将 表示任意单个字符的.转化为 表示单个.的\\.。但是，当这些特殊字符在在中括号[]中，不需要转义，例如可以这样使用[a-z.]，这表示限制字符为a到z、.中的一个。
思路
本题的重点在于书写正确的正则表达式，由于邮箱的前缀以字母开头，所以得限制开头^[a-zA-Z]；邮箱的前缀中其他字符为字母、数字、下划线、点、破折号中的任意一个，也不限制字符的个数，所以使用[a-zA-Z0-9_.-]*限制；邮箱的域为'@leetcode.com'，即得以'@leetcode.com'作为整个邮箱的结尾，其中的.为特殊字符，得转义，所以使用@leetcode\\.com$限制。
代码
select
user_id,
name,
mail
from
Users
where
mail regexp '^[a-zA-Z][a-zA-Z0-9_.-]*@leetcode\\.com$'
205. 同构字符串
题目链接
标签
哈希表 字符串
简单版
思路
本题各处都在暗示使用映射，即Map，可以使用两个字符映射sToT, tToS，它们分别表示从s到t的字符映射和从t到s到字符映射，遍历整个字符串，对于从t和s取出的相同索引的字符，如果不存在这两个字符的相互映射，则需要建立这两个字符的映射；如果这两个字符没有映射到对方，则此时就是不同构的情况，返回false。
为什么需要需要两个映射？因为如果只有一个映射，对于s = "badc", t = "baba"这种情况是没有办法的。
代码
class Solution {
public boolean isIsomorphic(String s, String t) {
char[] sC = s.toCharArray();
char[] tC = t.toCharArray();
Map<Character, Character> sToT = new HashMap<>(); // 从s到t的映射，key为s中的字符，value为t中的字符
Map<Character, Character> tToS = new HashMap<>(); // 从t到s的映射，key为t中的字符，value为s中的字符
for (int i = 0, j = 0; i < s.length(); i++, j++) {
char sKey = sC[i], tKey = tC[i]; // 从s和t中取出两个索引相同的字符
// 如果不存在映射，就建立映射
if (!sToT.containsKey(sKey)) {
sToT.put(sKey, tKey);
}
if (!tToS.containsKey(tKey)) {
tToS.put(tKey, sKey);
}
// 如果这两个字符没有映射到对方，则此时就是不同构的情况，返回false
if (sToT.get(sKey) != tKey || tToS.get(tKey) != sKey) {
return false;
}
}
return true;
}
}
优化版
思路
可以不使用字符到字符的映射，而是使用字符到索引的映射，想一想字符到字符的映射记录了什么？记录的是相同索引下另一个字符串的字符，那为什么不能直接记录索引呢？两个字符串都记录每个字符第一次出现的位置，然后在比较时比较这个字符第一次出现的位置，如果相同，则说明映射成功；否则s和t不是同构的，返回false。
当然，可以不建立这个映射，因为这样做代码就会很复杂，这时可以使用String的indexOf()方法来定位字符第一次出现的位置。
代码
class Solution {
public boolean isIsomorphic(String s, String t) {
for (int i = 0; i < s.length(); i++) {
if (s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))) {
return false;
}
}
return true;
}
}
124. 二叉树中的最大路径和
题目链接
标签
树 深度优先搜索 动态规划 二叉树
思路
对于每个节点来说，寻找路径无非就两种情况：以当前节点为路径的起始节点，要么往左子树延伸、要么往右子树延伸、要么不延伸形成的路径；以当前节点为中转节点，连接左子树和右子树（也有可能由于左子树或右子树的路径为负值而不连接）形成的路径。只需要在这几个值中取最大值，然后将递归方法外的最大值更新一下就行了。
代码
class Solution {
private int max = Integer.MIN_VALUE; // 记录路径的最大值
public int maxPathSum(TreeNode root) {
maxSum(root);
return max;
}
// 以本节点curr为路径的起始节点，寻找最长路径
private int maxSum(TreeNode curr) {
if (curr == null) { // 如果当前节点为null
return 0; // 则最长路径为0
}
int leftMax = maxSum(curr.left); // 在左子树中寻找 以左子节点为路径的起始节点的 最长路径
int rightMax = maxSum(curr.right); // 在右子树中寻找 以右子节点为路径的起始节点的 最长路径
int currMax = Math.max(Math.max(leftMax, rightMax), 0) + curr.val; // 以当前节点为路径的起始节点的 最长路径
int allMax = Math.max(curr.val + leftMax + rightMax, currMax); // 以当前节点为路径的起始节点 或 以当前节点为中转节点的 最长路径
max = Math.max(allMax, max); // 更新最长路径
return currMax; // 返回 以当前节点为路径的起始节点的 最长路径
}
}
原文地址：https://blog.csdn.net/qq_61350148/article/details/140168336
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！