题目描述(力扣): 什么是最优子结构 最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，可以通过子问题的最优解，推导出问题的最优解。要符合「最优子结构」，子问题间必须互相独立。 比如说，假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。 得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，「每门科目考到最高」这些子问题是互相独立，互不干扰的。 但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，不能同时达到满分，数学分数高，语文分数就会降低，反之亦然。 这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为「每门科目考到最高」的子问题并不独立，语文数学成绩户互相影响，无法同时最优，所以最优子结构被破坏。 思路: 题目说明了每种硬币数量无限，所以该问题具有最优子结构，可以用动态规划来解决。确定好用动态规划来解决后，先确定dp数组的意义，这里dp[i]存储的值就是总金额为i的最优解。接下来最重要的事情就是找到状态转移方程，dp[0] = 0，当amount大于0时，我们只需遍历给出的coins数组找到 dp[amount - coin_value] + 1 中的最小值即可(避免越界，需要先判断coin_value是否小于amount)，加一是因为要加上一个面值为coin_value的硬币。 代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX - 1); //初始化dp数组，初始值为INT_MAX - 1是因为后面有dp[i - value] + 1操作，需要避免整形溢出 dp[0] = 0; //已知的最优解 for(int i = 1; i <= amount; i++) { for(int value : coins) //遍历每种硬币 { if(i - value < 0) continue; //进行判断是为了避免越界 dp[i] = min(dp[i], dp[i - value] + 1); //找到总金额为 i 时的最优解 } } return dp[amount] == (INT_MAX - 1) ?

题目描述(力扣): 思路: 首先理解二叉树的直径指的是二叉树中任意两个节点之间的路径长度的最大值(最长直径不一定经过根节点)。想要找到二叉树的直径，就需要遍历每个节点，依次计算每个节点的左右子树深度之和，其中的最大值就是二叉树的直径。因为二叉树的直径大多数情况下就是根节点下的左右子树深度之和，但存在直径不经过根节点的情况，所以需要遍历每个节点，计算以该节点为根的二叉树的直径，然后取计算结果中的最大值。根据前面的分析，我们需要计算左右子树深度之和，这就需要左右子树的信息，所以选择后序遍历。 代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int diameterOfBinaryTree(TreeNode* root) { maxDepth(root); return maxDia; } int maxDepth(TreeNode* root) { if(root == nullptr) return 0; int lefth_h = maxDepth(root->left); int right_h = maxDepth(root->right); int Dia = lefth_h + right_h; //计算当前二叉树的直径 maxDia = max(maxDia, Dia); return lefth_h > right_h?

题目描述(力扣): 思路: 创造两个指针，分别指向大于x的链表和小于x的链表，然后依次遍历初始链表的每个节点进行判断将其添加到对应的新链表中，最后将两个链接进行连接后返回。 代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode *h1 = new ListNode(-1); //指向小于x的节点组成的链表的头节点 ListNode *h2 = new ListNode(-1); //指向大于x的节点组成的链表的头节点 ListNode *t1, *t2; //分别指向各自链表的尾结点 t1 = h1; t2 = h2; while(head !

代码 行内代码 格式：ˋ代码内容ˋ 块内代码 格式： 1 2 3 ˋˋˋmarkdown Sample text here ... ˋˋˋ 标题 格式： 1 2 3 4 # 一级标题 ## 二级标题 ... ###### 六级标题 水平线 格式： 1 2 3 4 水平线有三种实现方式: ___:三个连续的下划线 ---:三个连续的破折号 ***:三个连续的星号 换行 分行 格式：两个空格 + 回车 或 使用<br> 分段 格式：两个回车 强调 粗体 格式：**加粗的内容** 也可以选择需要加粗的内容后使用快捷键Ctrl + B 斜体 格式：*倾斜的内容* 或 _倾斜的内容_ 也可以选择需要加粗的内容后使用快捷键Ctrl + I 删除线 格式：~~倾斜的内容~~ 组合使用 1 2 3 4 _**加粗和斜体**_ ~~**删除线和加粗**~~ ~~_删除线和斜体_~~ ~~_**加粗，斜体和删除线**_~~ 引用 格式：> + 空格 + 引用的内容

Git概述 Git 是一款分布式的代码版本控制工具，Linux 之父 Linus 嫌弃当时主流的中心式的版本控制工具太难用还要花钱，就自己花两周时间开发出了 Git 的主体程序，一个月后就开始用Git来维护 Linux 的版本（给大佬跪了）。 常见的版本控制工具有：分布式版本控制工具和集中式版本控制工具 分布式版本控制工具： 工作原理： 分布式版本控制工具不依赖于单一的中央服务器，每个开发者都拥有完整的代码库的副本。开发者在本地工作副本上进行修改，并在本地进行提交、分支、合并等操作。开发者可以选择与其他开发者直接交换修改的内容，也可以将修改推送到共享的远程仓库中。 特点： 每个开发者都拥有完整的代码库的副本，可以在本地进行版本控制 具有更好的分支和合并功能，能够轻松地处理复杂的开发工作流程 典型的分布式版本控制工具有Git和Mercurial等 集中式版本控制工具： 工作原理： 集中式版本管理工具使用单一的中央服务器来存储所有版本的代码库。开发者在本地工作副本上进行修改，然后将修改后的内容提交到中央服务器。其他开发者通过从中央服务器检出代码库来获取最新的代码，并将他们的修改提交到同一个中央服务器上。 特点： 中央服务器是唯一的源头，所有的代码修改都需要提交到中央服务器 开发者在没有网络连接的情况下无法进行版本控制操作 典型的集中式版本管理工具包括Subversion（SVN）和Perforce等 Git的工作机制如下图所示: 工作区：开发人员在本地存放项目文件（代码）的地方 暂存区：是一个缓冲区域，用于临时存放即将提交到本地库的修改，开发者通过 git add 命令将工作区中的修改添加到暂存区，只有添加到暂存区的文件该会被提交到本地库中去 本地库：存放项目完整历史记录和版本信息的地方，开发者通过 git commit 命令将暂存区的内容提交到本地库，使用该命令后暂存区就会清空 远程库：用于存放项目的中央代码库（如GitHub），位于云端或其他服务器上。团队成员可以通过 git clone 操作从远程仓库克隆一个完整的 Git 仓库到本地。克隆操作会复制远程仓库的所有历史记录、分支、标签等信息，并在本地创建一个相同的仓库副本。通过 git push 用于将本地库推送到远程库， 通过 git pull 从远程库拉取最新的代码到本地库 Git安装 Windows下安装 先确定自己的电脑是64位操作系统还是32位的(按Win键，设置→系统→关于)，然后去Git官网下载对应的安装包，根据提示进行安装(详细安装过程请自行Google)。 注意： 安装路径中不要包含中文！ Ubuntu下安装 由于本人是Ubuntu下使用Git的，所以这里的步骤会写的详细点。 输入命令 sudo apt-get install git进行安装，输入 git version 检查是否安装成功 输入命令 ssh -T git@github.com 检查是否可以连接到GitHub，如果看到 则说明能够连接。 安装SSH keys（一定要在 ~/.