- 102. 二叉树的层序遍历">102. 二叉树的层序遍历
- 433. 最小基因变化">433. 最小基因变化
- 22. 括号生成">22. 括号生成
- 515. 在每个树行中找最大值">515. 在每个树行中找最大值
- 69. x 的平方根">69. x 的平方根
- 367. 有效的完全平方数">367. 有效的完全平方数
- 860. 柠檬水找零">860. 柠檬水找零
- 122. 买卖股票的最佳时机 II">122. 买卖股票的最佳时机 II
- 455. 分发饼干">455. 分发饼干
- 874. 模拟行走机器人">874. 模拟行走机器人
- 127. 单词接龙">127. 单词接龙
- 200. 岛屿数量">200. 岛屿数量
- 529. 扫雷游戏">529. 扫雷游戏
- 55. 跳跃游戏">55. 跳跃游戏
- 33. 搜索旋转排序数组">33. 搜索旋转排序数组
- 74. 搜索二维矩阵">74. 搜索二维矩阵
- 153. 寻找旋转排序数组中的最小值">153. 寻找旋转排序数组中的最小值
- 126. 单词接龙 II">126. 单词接龙 II
- 45. 跳跃游戏 II">45. 跳跃游戏 II
102. 二叉树的层序遍历
难度中等767收藏分享切换为英文接收动态反馈
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层序遍历结果:
[
[3],
[9,20],
[15,7]
]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//最终的结果
List<List<Integer>> result = new ArrayList<>();
//队列
Queue<TreeNode> queue = new ArrayDeque<>();
if(root!=null){
queue.add(root);
}
//队列不为空的情况下进行
while (!queue.isEmpty()){
//每一层节点的多少
int levelSize = queue.size();
//每一层的结果
List<Integer> levelResult = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
//出队
TreeNode levelNode = queue.poll();
//收割单层的每个节点
levelResult.add(levelNode.val);
if(levelNode.left!=null){
queue.add(levelNode.left);
}
if(levelNode.right!=null){
queue.add(levelNode.right);
}
}
//收割单层的节点
result.add(levelResult);
}
return result;
}
}
433. 最小基因变化
难度中等67收藏分享切换为英文接收动态反馈
一条基因序列由一个带有8个字符的字符串表示,其中每个字符都属于 "A"
, "C"
, "G"
, "T"
中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如,基因序列由"AACCGGTT"
变化至 "AACCGGTA"
即发生了一次基因变化。
与此同时,每一次基因变化的结果,都需要是一个合法的基因串,即该结果属于一个基因库。
现在给定3个参数 — start, end, bank,分别代表起始基因序列,目标基因序列及基因库,请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化,请返回 -1。
注意:
- 起始基因序列默认是合法的,但是它并不一定会出现在基因库中。
- 如果一个起始基因序列需要多次变化,那么它每一次变化之后的基因序列都必须是合法的。
假定起始基因序列与目标基因序列是不一样的。
示例 1:
start: “AACCGGTT”
end: “AACCGGTA”
bank: [“AACCGGTA”]
返回值: 1
示例 2:
start: “AACCGGTT”
end: “AAACGGTA”
bank: [“AACCGGTA”, “AACCGCTA”, “AAACGGTA”]
返回值: 2
示例 3:
start: “AAAAACCC”
end: “AACCCCCC”
bank: [“AAAACCCC”, “AAACCCCC”, “AACCCCCC”]
返回值: 3
22. 括号生成
难度中等1554收藏分享切换为英文接收动态反馈
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2:
输入:n = 1
输出:[“()”]
提示:
1 <= n <= 8
class Solution {
/**
* 括号生成
* @param n
* @return
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
_generate(0,0,"",n,result);
return result;
}
private void _generate(int left, int right, String s, int n, List<String> result) {
//终结者
if(left == n && right == n){
//收割当前的数据
result.add(s);
return;
}
//逻辑
//进入到下一层
if(left < n){
String s1 = s + "(";
_generate(left+1,right,s1 ,n,result);
}
if(right < left){
String s2 = s + ")";
_generate(left,right+1,s2,n,result);
}
//清理当前层
}
}
515. 在每个树行中找最大值
难度中等124收藏分享切换为英文接收动态反馈
您需要在二叉树的每一行中找到最大的值。
示例:
输入:
1<br /> / \<br /> 3 2<br /> / \ \ <br /> 5 3 9
输出: [1, 3, 9]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
//存储树的每行中的最大值
List<Integer> result = new ArrayList<>();
//用于遍历每层的队列
Queue<TreeNode> queue = new ArrayDeque<>();
//存储每一层中的最大值
int levelMax = Integer.MIN_VALUE;
if(root!=null){
queue.add(root);
}
//队列不为空的时候,进行
while (!queue.isEmpty()){
//拿到每层的数量
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
//取出数据
TreeNode pollNode = queue.poll();
//找到最大值
levelMax = Math.max(levelMax,pollNode.val);
if(pollNode.left != null){
queue.add(pollNode.left);
}
if(pollNode.right != null){
queue.add(pollNode.right);
}
}
//收割当前层的最大值
result.add(levelMax);
//恢复
levelMax = Integer.MIN_VALUE;
}
return result;
}
}
69. x 的平方根
难度简单589收藏分享切换为英文接收动态反馈
实现 int sqrt(int x)
函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。
367. 有效的完全平方数
难度简单190收藏分享切换为英文接收动态反馈
给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。
说明:不要使用任何内置的库函数,如 sqrt
。
示例 1:
输入:16
输出:True
示例 2:
输入:14
输出:False
860. 柠檬水找零
难度简单210收藏分享切换为英文接收动态反馈
在柠檬水摊上,每一杯柠檬水的售价为 5
美元。
顾客排队购买你的产品,(按账单 bills
支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5
美元、10
美元或 20
美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5
美元。
注意,一开始你手头没有任何零钱。
如果你能给每位顾客正确找零,返回 true
,否则返回 false
。
示例 1:
输入:[5,5,5,10,20]
输出:true
解释:
前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。
第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零,所以我们输出 true。
示例 2:
输入:[5,5,10]
输出:true
示例 3:
输入:[10,10]
输出:false
示例 4:
输入:[5,5,10,10,20]
输出:false
解释:
前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。
对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零,所以答案是 false。
提示:
0 <= bills.length <= 10000
bills[i]
不是5
就是10
或是20
122. 买卖股票的最佳时机 II
难度简单1089收藏分享切换为英文接收动态反馈
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
455. 分发饼干
难度简单301收藏分享切换为英文接收动态反馈
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i
,都有一个胃口值 g[i]
这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j
,都有一个尺寸 s[j]
。如果 s[j] >= g[i]
,我们可以将这个饼干 j
分配给孩子 i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示:
1 <= g.length <= 3 * 10
0 <= s.length <= 3 * 10
1 <= g[i], s[j] <= 2 - 1
874. 模拟行走机器人
难度简单122收藏分享切换为英文接收动态反馈
机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0)
处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands
:
-2
:向左转90
度-1
:向右转90
度1 <= x <= 9
:向前移动x
个单位长度
在网格上有一些格子被视为障碍物 obstacles
。第 i
个障碍物位于网格点 obstacles[i] = (x, y)
。
机器人无法走到障碍物上,它将会停留在障碍物的前一个网格方块上,但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点(坐标为整数)的最大欧式距离的平方。(即,如果距离为 5
,则返回 25
)
注意:
- 北表示
+Y
方向。 - 东表示
+X
方向。 - 南表示
-Y
方向。 西表示
-X
方向。
示例 1:
输入:commands = [4,-1,3], obstacles = []
输出:25
解释:
机器人开始位于 (0, 0):
1. 向北移动 4 个单位,到达 (0, 4)
2. 右转
3. 向东移动 3 个单位,到达 (3, 4)
距离原点最远的是 (3, 4) ,距离为 3 + 4 = 25
示例 2:
输入:commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出:65
解释:机器人开始位于 (0, 0):
1. 向北移动 4 个单位,到达 (0, 4)
2. 右转
3. 向东移动 1 个单位,然后被位于 (2, 4) 的障碍物阻挡,机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位,到达 (1, 8)
距离原点最远的是 (1, 8) ,距离为 1 + 8 = 65
提示:1 <= commands.length <= 10
commands[i]
is one of the values in the list[-2,-1,1,2,3,4,5,6,7,8,9]
.0 <= obstacles.length <= 10
-3 * 10 <= x, y <= 3 * 10
- 答案保证小于
2
127. 单词接龙
难度困难692收藏分享切换为英文接收动态反馈
字典 wordList
中从单词 beginWord
和 endWord
的 转换序列 是一个按下述规格形成的序列:
- 序列中第一个单词是
beginWord
。 - 序列中最后一个单词是
endWord
。 - 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典
wordList
中的单词。
给你两个单词 beginWord
和 endWord
和一个字典 wordList
,找到从 beginWord
到 endWord
的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0。
示例 1:
输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出:5
解释:一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
示例 2:
输入:beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出:0
解释:endWord “cog” 不在字典中,所以无法进行转换。
提示:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
、endWord
和wordList[i]
由小写英文字母组成beginWord != endWord
wordList
中的所有字符串 互不相同
200. 岛屿数量
难度中等971收藏分享切换为英文接收动态反馈
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出:1
示例 2:
输入:grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出:3
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
的值为'0'
或'1'
class Solution {
int count = 0;
int parent[] = null;
public int numIslands(char[][] grid) {
if(grid==null){
return 0;
}
if(grid.length==1 && grid[0][0]=='0'){
return count;
}
int m = grid.length;
int n = grid[0].length;
count = m;
parent = new int[count];
//初始化自己
for (int i = 0; i < count; i++) {
parent[i] = i;
}
//并查集操作
for (int i = 0; i < count; i++) {
for (int j = i+1; j < count; j++) {
//等于1说明相邻,都是岛屿
if(grid[i][j] == '1'){
union(parent,i,j);
}
}
}
//计算结果
int daoyuCount = 0;
for (int i = 0; i < count; i++) {
if(parent[i] == i){
daoyuCount++;
}
}
return daoyuCount;
}
private void union(int[] parent, int i, int j) {
int rootP = find(parent,i);
int rootQ = find(parent,j);
if(rootP == rootQ){
return;
}
parent[rootP] = rootQ;
}
private int find(int[] parent, int index) {
while (index != parent[index]){
parent[index] = parent[parent[index]];
index = parent[index];
}
return index;
}
}
529. 扫雷游戏
难度中等214收藏分享切换为英文接收动态反馈
让我们一起来玩扫雷游戏!
给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷,‘E’ 代表一个未挖出的空方块,‘B’ 代表没有相邻(上,下,左,右,和所有4个对角线)地雷的已挖出的空白方块,数字(’1’ 到 ‘8’)表示有多少地雷与这块已挖出的方块相邻,‘X’ 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中(’M’或者’E’)的下一个点击位置(行和列索引),根据以下规则,返回相应位置被点击后对应的面板:
- 如果一个地雷(’M’)被挖出,游戏就结束了- 把它改为 ‘X’。
- 如果一个没有相邻地雷的空方块(’E’)被挖出,修改它为(’B’),并且所有和其相邻的未挖出方块都应该被递归地揭露。
- 如果一个至少与一个地雷相邻的空方块(’E’)被挖出,修改它为数字(’1’到’8’),表示相邻地雷的数量。
如果在此次点击中,若无更多方块可被揭露,则返回面板。
示例 1:
输入: [[‘E’, ‘E’, ‘E’, ‘E’, ‘E’], [‘E’, ‘E’, ‘M’, ‘E’, ‘E’], [‘E’, ‘E’, ‘E’, ‘E’, ‘E’], [‘E’, ‘E’, ‘E’, ‘E’, ‘E’]] Click : [3,0] 输出: [[‘B’, ‘1’, ‘E’, ‘1’, ‘B’], [‘B’, ‘1’, ‘M’, ‘1’, ‘B’], [‘B’, ‘1’, ‘1’, ‘1’, ‘B’], [‘B’, ‘B’, ‘B’, ‘B’, ‘B’]] 解释:
示例 2:
输入: [[‘B’, ‘1’, ‘E’, ‘1’, ‘B’], [‘B’, ‘1’, ‘M’, ‘1’, ‘B’], [‘B’, ‘1’, ‘1’, ‘1’, ‘B’], [‘B’, ‘B’, ‘B’, ‘B’, ‘B’]] Click : [1,2] 输出: [[‘B’, ‘1’, ‘E’, ‘1’, ‘B’], [‘B’, ‘1’, ‘X’, ‘1’, ‘B’], [‘B’, ‘1’, ‘1’, ‘1’, ‘B’], [‘B’, ‘B’, ‘B’, ‘B’, ‘B’]] 解释:
注意:输入矩阵的宽和高的范围为 [1,50]。
- 点击的位置只能是未被挖出的方块 (‘M’ 或者 ‘E’),这也意味着面板至少包含一个可点击的方块。
- 输入面板不会是游戏结束的状态(即有地雷已被挖出)。
- 简单起见,未提及的规则在这个问题中可被忽略。例如,当游戏结束时你不需要挖出所有地雷,考虑所有你可能赢得游戏或标记方块的情况。
55. 跳跃游戏
难度中等1041收藏分享切换为英文接收动态反馈
给定一个非负整数数组 nums
,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
提示:
1 <= nums.length <= 3 * 10
0 <= nums[i] <= 10
33. 搜索旋转排序数组
难度中等1176收藏分享切换为英文接收动态反馈
升序排列的整数数组 nums
在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7]
经旋转后可能变为 [4,5,6,7,0,1,2]
)。
请你在数组中搜索 target
,如果数组中存在这个目标值,则返回它的索引,否则返回 -1
。
示例 1:
输入:nums = [4,5,6,7,0,1,2]
, target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2]
, target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums
中的每个值都 独一无二nums
肯定会在某个点上旋转-10^4 <= target <= 10^4
74. 搜索二维矩阵
难度中等314收藏分享切换为英文接收动态反馈
编写一个高效的算法来判断 m x n
矩阵中,是否存在一个目标值。该矩阵具有如下特性:
- 每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
示例 2:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10 <= matrix[i][j], target <= 10
153. 寻找旋转排序数组中的最小值
难度中等347收藏分享切换为英文接收动态反馈
假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如,数组 [0,1,2,4,5,6,7]
可能变为 [4,5,6,7,0,1,2]
。
请找出其中最小的元素。
示例 1:
输入:nums = [3,4,5,1,2]
输出:1
示例 2:
输入:nums = [4,5,6,7,0,1,2]
输出:0
示例 3:
输入:nums = [1]
输出:1
提示:
1 <= nums.length <= 5000
-5000 <= nums[i] <= 5000
nums
中的所有整数都是 唯一 的nums
原来是一个升序排序的数组,但在预先未知的某个点上进行了旋转
126. 单词接龙 II
难度困难392收藏分享切换为英文接收动态反馈
给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:
- 每次转换只能改变一个字母。
- 转换后得到的单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列,返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出:
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出: []
解释: endWord “cog” 不在字典中,所以不存在符合要求的转换序列。
45. 跳跃游戏 II
难度困难824收藏分享切换为英文接收动态反馈
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2
。
从下标为 0 跳到下标为 1 的位置,跳 1
步,然后跳 3
步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。