JJXxXLL

理论基础什么是动态规划动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的， 在关于贪心算法，你该了解这些！ (opens new window)中我举了一个背包问题的例子。 例如：有$N$件物品和一个最多能背重量为 $W$ 的背包。第$i$件物品的重量是 $weight[i]$，得到的价值是 $value[i] $。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 动态规划中 $dp[j]$ 是由 $dp[j-weight[i]]$ 推导出来的，然后取$max(dp[j], dp[j - weight[i]] + value[i])$。 但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。 所以贪心解决不了动态规划的问题。 动态规划的解题步骤做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后， ...

01背包理论基础46. 携带研究材料（第六期模拟笔试） (kamacoder.com) 01 背包有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包：i 来表示物品、j表示背包容量。 定义：dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]) 考虑能不能放下 初始化：j=0时全为零；i=0时，j

GAT–Graph Attention Networks文献地址 GAT产生背景神经网络在图数据上的应用需求： 随着深度学习技术在图像、语音、自然语言处理等领域的成功应用，研究人员开始尝试将神经网络方法扩展到图结构数据上。图数据广泛存在于社交网络、生物网络、通信网络等实际应用中，处理这些数据需要专门的算法。 现有方法的局限性： 传统的图神经网络（Graph Neural Networks, GNN）和图卷积网络（Graph Convolutional Networks, GCN）在处理图结构数据时遇到了一些挑战，例如： 固定权重分配：GNN和GCN通常使用固定的权重或预定义的方法来处理邻居节点的重要性，难以灵活地处理不同邻居节点的重要性差异。 计算复杂度高：一些基于光谱的方法需要进行复杂的矩阵分解或逆操作，在大规模图数据上计算成本较高。 依赖全局图结构：许多方法需要预先知道整个图的结构，在处理从未见过的新图时存在局限性。 注意力机制的发展： 注意力机制在自然语言处理领域（如机器翻译）取得了显著的成功，它能够动态地为输入序列的不同部分分配不同的权重，显著提升了模型的性能和灵 ...

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS 基于图卷积网络的半监督分类 文献参考 引言（INTRODUCTION）我们考虑在图（如引文网络）中对节点（如文档）进行分类的问题，其中只有一小部分节点有标签。这一问题可以被框架化为基于图的半监督学习，其中标签信息通过某种形式的显式图正则化（如使用图拉普拉斯正则化项）在图上进行平滑。然而，这种假设可能会限制模型的容量，因为图边不一定编码节点相似性，还可能包含其他信息。 在本工作中，我们使用神经网络模型直接编码图结构，并对所有有标签的节点进行监督目标训练，从而避免在损失函数中显式的图正则化。通过条件化神经网络模型于图的邻接矩阵，我们的模型能够从监督损失中分布梯度信息，并能够学习有标签和无标签节点的表示。 我们的贡献有两方面。 首先，我们介绍了一种简单且行为良好的逐层传播规则，用于直接在图上操作的神经网络模型，并展示了其可以从频谱图卷积的一阶近似中得到动机。 其次，我们展示了这种图神经网络模型可以用于快速且可扩展的图中节点的半监督分类。在多个数据集上的实验表明，我 ...

A Comprehensive Survey on Graph Neural Networks 文献地址 摘要 传统深度学习任务中的数据通常在欧几里德空间中表示。然而越来越多的数据从非欧几里得域生成，并表示为具有复杂关系和对象之间相互依赖关系的图形。图数据的复杂性给现有的机器学习算法带来了重大挑战。 提出了新的分类方法，将最先进的GNN模型分为四类：递归图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）、图自动编码器（GAEs）和时空图神经网络（STGNNs）。 探讨了GNN在各种领域中的应用，如推荐系统、化学分子分析和引文网络分类。 总结了开源代码、基准数据集和模型评估方法。 提出了GNN领域的潜在研究方向，如模型深度、可扩展性、异质性和动态性等。 简介深度学习在欧几里得空间成功深度学习在图像分类、视频处理、语音识别和自然语言理解等领域的成功，这些领域的数据通常表示在欧几里得空间中。然而，越来越多的应用中，数据来自非欧几里得领域，并表示为图，这些图数据具有复杂的关系和依赖性。这种复杂性对现有的机器学习算法提出了重大挑战。 图数据的复杂性与欧几里得数据不同，图数据是非结构 ...

226.翻转二叉树 （优先掌握递归）题目链接思路：交换每个节点的左右子树即可，尝试使用递归法 递归法提示：递归三部曲 1.确定递归函数的参数和返回值 TreeNode* invertTree(TreeNode* root) 2.确定终止条件 if(root == NULL) return root; 3.确定单层递归的逻辑 123swap(root->left,root->right);intvertTree(root->left);invertTree(root->right); 代码如下： 123456789class Solution {public: TreeNode* invertTree(TreeNode* root){ if(root == NULL) return root; swap(root->left,root->right); intvertTree(root->left); invertTree(root->right); return r ...

二叉树的定义123456struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}}; 二叉树的递归遍历写递归需按照这三要素来写： 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 前序遍历： 123456void traversal(TreeNode* cur, vector<int>& vec) { ...

150. 逆波兰表达式求值题目链接状态：错一次错误原因：stoi不会使用 1234567891011121314151617181920212223242526272829class Solution {public: int evalRPN(vector<string>& tokens) { stack<int> st; int a, b; for (int i = 0; i < tokens.size(); i++) { if (!st.empty() && (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")) { b = st.top(); ...

介绍栈和队列是STL（C++标准库）里面的两个数据结构。 HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。 P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。 SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。 栈和队列也是SGI STL里面的数据结构 stack push(): 在栈顶添加一个元素。 pop(): 移除栈顶元素。 top(): 返回栈顶元素的引用，但不移除它。 empty():检查栈是否为空。 size(): 返回栈中元素的数量。 queue empty(): 检查队列是否为空。 size(): 返回队列中的元素数量。 front(): 返回队首元素的引用。 back(): 返回队尾元素的引用。 push(): 在队尾添加一个元素。 ...

151.翻转字符串里的单词题目链接状态：一遍过思路：使用栈，先进后出，除去空格 12345678910111213141516171819202122232425class Solution {public: string reverseWords(string s) { stack<string> stack; int n=s.size(); for(int i=0;i<n;i++){ string tmp; while(i<n&&s[i]!=' '){ tmp+=s[i++]; } if(tmp!=""){ stack.push(tmp); } } string ans = stac ...

344.反转字符串题目链接状态: 一遍过思路: 基础题 1234567891011class Solution {public: void reverseString(vector<char>& s) { int n=s.size(); for(int i=0;i<n/2;i++){ char tmp=s[i]; s[i]=s[n-i-1]; s[n-i-1]=tmp; } }}; 简洁版本 12345678class Solution {public: void reverseString(vector<char>& s) { for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) { swap(s[i],s[j]); ...