Java每日一练(20230314)
JAVA 每日
2023-09-14 09:01:29 时间
目录
2. 重复的DNA序列 ★★
3. 二叉树中的最大路径和 ★★★
1. 字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s)
函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi
函数)。
函数 myAtoi(string s)
的算法如下:
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
- 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数(即,"123" -> 123, "0032" -> 32)。如果没有读入数字,则整数为
0
。必要时更改符号(从步骤 2 开始)。 - 如果整数数超过 32 位有符号整数范围
[−231, 231 − 1]
,需要截断这个整数,使其保持在这个范围内。具体来说,小于−231
的整数应该被固定为−231
,大于231 − 1
的整数应该被固定为231 − 1
。 - 返回整数作为最终结果。
注意:
- 本题中的空白字符只包括空格字符
' '
。 - 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。
示例 1:
输入:s = "42" 输出:42 解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。 第 1 步:"42"(当前没有读入字符,因为没有前导空格) 第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+') 第 3 步:"42"(读入 "42") 解析得到整数 42 。 由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。
示例 2:
输入:s = " -42" 输出:-42 解释: 第 1 步:" -42"(读入前导空格,但忽视掉) 第 2 步:" -42"(读入 '-' 字符,所以结果应该是负数) 第 3 步:" -42"(读入 "42") 解析得到整数 -42 。 由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。
示例 3:
输入:s = "4193 with words" 输出:4193 解释: 第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格) 第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+') 第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止) 解析得到整数 4193 。 由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。
示例 4:
输入:s = "words and 987" 输出:0 解释: 第 1 步:"words and 987"(当前没有读入字符,因为没有前导空格) 第 2 步:"words and 987"(当前没有读入字符,因为这里不存在 '-' 或者 '+') 第 3 步:"words and 987"(由于当前字符 'w' 不是一个数字,所以读入停止) 解析得到整数 0 ,因为没有读入任何数字。 由于 0 在范围 [-231, 231 - 1] 内,最终结果为 0 。
示例 5:
输入:s = "-91283472332" 输出:-2147483648 解释: 第 1 步:"-91283472332"(当前没有读入字符,因为没有前导空格) 第 2 步:"-91283472332"(读入 '-' 字符,所以结果应该是负数) 第 3 步:"-91283472332"(读入 "91283472332") 解析得到整数 -91283472332 。 由于 -91283472332 小于范围 [-2^31, 2^31 - 1] 的下界,最终结果被截断为 -2^31 = -2147483648 。
提示:
0 <= s.length <= 200
s
由英文字母(大写和小写)、数字(0-9
)、' '
、'+'
、'-'
和'.'
组成
代码:
class Solution {
public int myAtoi(String s) {
long y = 0;
int i = 0;
boolean w = false;
boolean sign = false;
int offset = 0;
char[] ints = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
while (i < s.length()) {
char c = s.charAt(i);
boolean isSign = false;
if (w == false && c != ' ') {
w = true;
if (c == '-') {
sign = true;
isSign = true;
}
if (c == '+') {
isSign = true;
}
}
if (w && (!isSign)) {
int v = Arrays.binarySearch(ints, c);
if (v < 0) {
break;
}
y = y * 10 + v;
if (y > 0x7FFFFFFF) {
y = 0x7FFFFFFF;
offset = 1;
break;
}
}
i++;
}
return sign ? -(int) (y + offset) : (int) y;
}
}
2. 重复的DNA序列
所有 DNA 都由一系列缩写为 'A'
,'C'
,'G'
和 'T'
的核苷酸组成,例如:"ACGAATTCCG"
。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串,目标子串的长度为 10,且在 DNA 字符串 s
中出现次数超过一次。
示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出:["AAAAACCCCC","CCCCCAAAAA"]
示例 2:
输入:s = "AAAAAAAAAAAAA" 输出:["AAAAAAAAAA"]
提示:
0 <= s.length <= 10^5
s[i]
为'A'
、'C'
、'G'
或'T'
代码:
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> set = new HashSet<>();
Set<String> help = new HashSet<>();
for (int i = 0; i <= s.length() - 10; i++) {
String cur = s.substring(i, i + 10);
if (!set.add(cur))
help.add(cur);
}
return new ArrayList<String>(help);
}
}
3. 二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root
,返回其 最大路径和 。
示例 1:
输入:root = [1,2,3] 输出:6 解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
输入:root = [-10,9,20,null,null,15,7] 输出:42 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
提示:
- 树中节点数目范围是
[1, 3 * 10^4]
-1000 <= Node.val <= 1000
代码: 递归法
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}
public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewpath);
return node.val + Math.max(leftGain, rightGain);
}
}
非递归法:
用栈来模拟递归过程,用哈希表存储每个节点的最大贡献值。首先将根节点入栈,然后在循环中不断弹出栈顶节点,如果该节点为空,我们将其最大贡献值设为0;如果该节点为叶子节点,将其最大贡献值设为节点值,并更新最大路径和;否则,计算左右子树的最大贡献值,并计算包含该节点的最大路径和,同样更新最大路径和,并将该节点的最大贡献值存入哈希表,同时将左右子节点入栈。最后返回最大路径和即可。
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
Map<TreeNode, Integer> map = new HashMap<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
map.put(node, 0);
continue;
}
if (node.left == null && node.right == null) {
map.put(node, node.val);
maxSum = Math.max(maxSum, node.val);
continue;
}
int leftGain = Math.max(map.getOrDefault(node.left, 0), 0);
int rightGain = Math.max(map.getOrDefault(node.right, 0), 0);
int priceNewpath = node.val + leftGain + rightGain;
maxSum = Math.max(maxSum, priceNewpath);
map.put(node, node.val + Math.max(leftGain, rightGain));
stack.push(node.left);
stack.push(node.right);
}
return maxSum;
}
}
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
| C/C++ 每日一练 专栏 |
| Python 每日一练 专栏 |
| Java 每日一练 专栏 |
![]() | Golang 每日一练 专栏 |
相关文章
- 编写一个C程序,运行时输出以下图形_java图形程序设计之图片显示
- java 对象转map,去掉null
- java分层打印二叉树_基于Java的二叉树层序遍历打印实现
- java 删除目录下所有文件_Java删除文件、目录及目录下所有文件的方法实例
- java数组的声明_Java数组定义常用方法[通俗易懂]
- Java实现友链管理的思路及demo
- 【开发经验】java socket编程详解
- java redis锁_Java中Redis锁的实现[通俗易懂]
- Java面向对象的三大特征以及理解
- gridbagconstraints什么意思_java rectangle
- java softreference_Java引用总结–StrongReference、SoftReference、WeakReference、PhantomReference…[通俗易懂]
- Think in Java之复用
- Java事件处理基础实例:处理按钮点击+捕获窗口事件+改变观感
- rocketmq长轮询原理_java长轮询
- java inputstream读取文件_java如何获取输入的数据
- 【错误记录】Android Studio 4.2.1 编译报错 ( 设置支持的 Java 和 Kotlin 版本 | java.lang.BootstrapMethodError )
- Java常用类及其常用方法详解编程语言
- 一个简单的绘制饼图的 Java Bean 实例详解编程语言
- Java中使用Redis实现分布式锁(javaredis锁)
- 安装安装JRE1.7:在Linux上开启Java之旅(jre1.7linux)
- 策略Java中Redis的过期策略实现(redisjava过期)
- 数据处理Java处理Redis过期数据的Best实践(redisjava过期)
- Java 核心系列教程
- 深入学习:Linux下Java环境建设与配置(linux下java环境)
- 使用Java连接SQL Server数据库,轻松实现数据交互(java连sqlserver)
- Java 开发提升Oracle数据库性能(java开发oracle)
- Java实现Redis计数器功能(redis计数 java)
- 基于java开发之系统托盘的应用