大佬教程收集整理的这篇文章主要介绍了2021-08-24 力扣刷题笔记，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 toi 抵达 pricei。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
示例 1：
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200示例 2：
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500今天的每日一题是我不熟悉的图论的问题，根据三宫姐姐的思路使用Bellman Ford + 邻接矩阵来解题，那么这个Bellman Ford是什么呢
Bellman-Ford 算法是用来处理单源最短路径的一种算法，它可以处理Dijkstra算法处理不了的图中权值有负值的情况。
它的主要思想是对所有的边进行n - 1轮的松弛操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含 n - 1 条边。也就是说在所有的边经历第1轮松弛操作后，得到的是原点最多经过一条边到达其他顶点的最短距离；在所有的边经历第2轮松弛操作后，得到的是原点最多经过两条边到达其他顶点的最短距离；在所有的边经历第3轮松弛操作后，得到的是原点最多经过三条边到达其他顶点的最短距离，依次类推，在所有的边经历第n - 1轮松弛操作后，得到的是原点最多经过 n - 1条边也就是除了它本身之外的所有边到达其他顶点的最短距离。
松弛操作是指如果原点s到某个顶点v的距离大于原点s到某个顶点u的距离加上u到v的距离，那就把原点s到某个顶点v的距离置为原点s到某个顶点u的距离加上u到v的距离。数字形式为Distance(v) > Distance(u) + w(u, v)，其中Distance(v)代表原点到v的距离，w(u, v)代表u到v的距离。
因此Bellman-Ford 算法的核心代码为
int src;// 原点
int[][] edges;// 使用邻接矩阵存储所有边的权重
int[] distance;// 存储原点到其余点的距离估值；
Arrays.fill(distance, INF); // 初始化原点到其他点的距离为无限大
distance[src] = 0;// 初始化原点到原点的距离为0；
for(int i = 0; i < n; i++){ // n 为顶点的个数, 因此i为某个顶点
for(int j = 0; j < n; j++){
// edges[i][j] 为 i 到 j 的一条边；
// 松弛操作
if(distance[i] > distance[j] + edges[i][j];)
distance[i] = distance[j] + edges[i][j];
}
}代码实现
class Solution {
int n = 110; // 最多为100个顶点
int INF = 0x3f3f3f3f; // 无穷大量
int[][] edge = new int[n][n]; // 存储边的权重的邻接矩阵
int[] dist = new int[n]; // 存储原点到顶点的距离
int n; // n个顶点
int s; // 原点
int t; // 目的地
int k; // 最多经历k - 1个中转站，也就是最多经历k条边
public int findCheapestPrice(int _n, int[][] flights, int _src, int _dst, int _k) {
n = _n;
s = _src;
t = _dst;
k = _k + 1;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
edge[i][j] = i == j ? 0 : INF; // 初始化所有的边为无穷
}
}
for(int[] f : flights){// 将题目中给的条件放到邻接矩阵中 flights = [[起点,终点,权重],[1,2,100],[0,2,500]]
int src = f[0]; // 起点
int dst = f[1]; // 终点
int wight = f[2]; // 权重（距离）
edge[src][dst] = f[wigth];
}
int ans = bf(); // 执行Bellman Ford算法，得到最短距离
return ans > INF / 2 ? -1 : ans; // 如果不存在这样的边则返回-1
}
int bf() {
Arrarys.fill(dist, INF); // 初始化原点到其他顶点的距离为INF
dist[s] = 0; // 初始化原点到原点的距离为0
for(int limit = 0; limit < k; limit++){// 限制最多经历k条边
int[] clone = dist.clone(); // 保存每轮松弛操作的结果
for(int i = 0; i < n; i++){// 遍历n个顶点
for(int j = 0; j < n; j++){// 遍历所有的边
dist[i] = Math.min(dist[i], clone[j] + edge[i][j]); // 松弛操作；
}
}
return dist[t]; // 返回原点到目的地的最短距离
}
}给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
Tree 1 Tree 2
1 2
/ /
3 2 1 3
/
5 4 7
输出:
合并后的树:
3
/
4 5
/
5 4 7简单的深度优先搜索，合并就完事了
代码实现
/**
* 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 TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null || root2 == null)
return root1 == null ? root2 : root1;
dfs(root1, root2);
return root1;
}
TreeNode dfs(TreeNode root1, TreeNode root2){
if(root1 == null || root2 == null)
return root1 == null ? root2 : root1;
root1.val = root1.val + root2.val;
root1.left = dfs(root1.left, root2.left);
root1.right = dfs(root1.right, root2.right);
return root1;
}
}给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。广度优先搜索，使用一个队列来存储每一层的节点，然后将节点进行链接
代码实现
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.add(root); // 将根节点放入队列中
while(!queue.isEmpty()){ // 逐层遍历
int size = queue.size(); // 保存一下当前队列的长度，因为下面会将队列中的结点弹出，所以要提前保存
for(int i = 0; i < size; i++){ // 遍历队列中的节点
if(i < size - 1){ // 链接
Node node = queue.poll();
node.next = queue.peek();
}
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return root;
}
}类似深度优先搜索的递归，将当前节点的左右子节点链接，不会解释，看代码结合图理解吧
实现代码
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
return root;
}
Node dfs(Node root){
if(root == null) return null;
Node left = root.left;
Node right = root.right;
while(left != null){ // 链接并且换节点
left.next = right; // 同一个父节点的两个节点
left = left.right; // 到了隔壁节点了
right = right.left;
}
dfs(root.left);
dfs(root.right);
return root;
}
}以上是大佬教程为你收集整理的2021-08-24 力扣刷题笔记全部内容，希望文章能够帮你解决2021-08-24 力扣刷题笔记所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。