买卖股票 本文所讲解的内容与LeetCode122.买卖股票的最佳时机ll，这道题题意相同，阅读完本文后可以自行挑战一下 力扣链接 题目叙述： 给定一个长度为N的数组，数组中的第i个数字表示一个给定股票在第i天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉悠前的股票)。一次买入卖出合为一笔交易。 输入格式： 第一行包含整数N，表示天数。第二行包含N个不大于10000的正整数表示每天股票的价格。 输出格式 输出一个整数，表示最大利润。 输入样例1 6 715346 输出样例1 7 ...

LeetCode516.最长回文子序列 题目叙述： 力扣题目链接(opensnewwindow) 给你一个字符串s，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 示例1： 输入：s="bbbab" 输出：4 解释：一个可能的最长回文子序列为"bbbb"。 示例2： 输入：s="cbbd" 输出：2 解释：一个可能的最长回文子序列为"bb"。 提示： 1<=s.length<=1000 s仅由小写英文字母组成 动态规划思路 我们在上文中已经介绍了回文子串，那么我们可以沿用回文子串的思...

大盗阿福 本题与leetcode198题——打家劫舍的题意一模一样，阅读完本文以后可以尝试以下题目 力扣题目链接) 题目叙述： 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有N家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金? 输入格式 输入的第一行是一个整数T，表示一共有T组数据。 接下来的每组数据，第一行是一个整数N，表示一有N家店铺。 第二行是N个...

最长公共子串 阅读本文前可以先了解“动态规划方法论”，在我之前讲过的文章有讲过。 动态规划方法论 本文讲解的题与leetcode718.最长重复子数组，题意一模一样，阅读完本文以后可以去挑战这题。 力扣链接 题目叙述： 给定两个字符串，输出其最长公共子串的长度。 输入 ABACCB AACCAB 输出 3 解释 最长公共子串是ACC，其长度为3。 与最长公共子序列的区别 公共子串：字符必须是连续相等的 公共子序列：字符必须是相等的，可以不连续。 动态规划思路 只有当两个字符串中的字符连续相等的时候，公共子串的长度才不断增加，否则清零 因此，我们不难发现，公共子串问题其实是公共...

LeetCode674.最长连续递增序列 阅读本文之前，需要先了解“动态规划方法论”，这在我的文章以前有讲过 链接：动态规划方法论 本文之前也讲过一篇文章：最长递增子序列，这道题，阅读本文的同时可以与“最长递增子序列进行对比”，这样更能对比二者的区别！ LeetCode300.最长递增子序列Tomorrowland_D博客园(cnblogs.com) leetcode链接如下 力扣题目链接： 题目叙述 给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。 连续递增的子序列可以由两个下标l和r（l<r）确定，如果对于每个l<=i<r，都有nu...

最长公共子串 本文讲解的题与leetcode718.最长重复子数组，题意一模一样，阅读完本文以后可以去挑战这题。 力扣链接 题目叙述： 给定两个字符串，输出其最长公共子串的长度。 输入 ABACCB AACCAB 输出 3 解释 最长公共子串是ACC，其长度为3。 与最长公共子序列的区别 公共子串：字符必须是连续相等的 公共子序列：字符必须是相等的，可以不连续。 动态规划思路 只有当两个字符串中的字符连续相等的时候，公共子串的长度才不断增加，否则清零 因此，我们不难发现，公共子串问题其实是公共子序列问题的一个特殊情况 状态变量以及其含义 我们延续最长公共子序列的思路，可以使用...

LeetCode300.最长递增子序列 力扣题目链接(opensnewwindow) 给你一个整数数组nums，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。 示例1： 输入：nums=[10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是[2,3,7,101]，因此长度为4。 示例2： 输入：nums=[0,1,0,3,2,3] 输出：4 示例3： 输入：nums=[7,7,7,7,7,7,7] 输出：1 提示： 1...

最长公共子序列 本文讲解的题与leetcode1143.最长公共子序列这题一样，阅读完可以挑战一下。 力扣题目链接 题目叙述： 给定两个字符串，输出其最长公共子序列，并输出它的长度 输入： ADABEC和DBDCA 输出： DBC 3 解释 最长公共子序列是DBC，其长度为3 动态规划思路： 我们这题先构建一个模型，我们使用两个指针i,j，分别用于遍历a字符串，b字符串。如图所示： 然后我们可以设想一个状态变量，也就是一个函数。一个关于两个变量相关的函数，这在代码中体现为二维数组f。 然后f[i][j]表示什么呢？表示序列a[1,2,3....i]和b[1,2,3....j]的...

编辑距离 本题与力扣72.编辑距离题意一样，阅读完本文可以尝试leetcode72.力扣题目链接 题目叙述 输入两个字符串a，b。输出从字符串a修改到字符串b时的编辑距离 输入 NOTV LOVER 输出 4 题目解释： 动态规划思路 这个问题显然是一个最优解问题，我们可以考虑动态规划的思路，那么我们使用动态规划的思路，要想得到最优解问题，那么我们必须要先考虑子问题。 子问题：我们先考虑a[1,2...i]到b[1,2....j]的编辑距离 状态变量的含义 设立一个dp数组，作为我们的状态变量 dp[i][j]表示以从a[1...i]到b[1....j]的编辑距离 递推公...

使用next_permutation函数非常简单，以下是具体的步骤和注意事项： 步骤： 包含头文件：确保包含<algorithm>头文件，因为next_permutation函数位于这个头文件中。include<algorithm> 准备容器：next_permutation可以用于处理任何支持随机访问迭代器的容器，比如vector或string。vector<int>nums={3,1,4}; 如果处理的是字符串，可以这样：stringstr="abc"; 排序（可选）：为了生成按照字典序排列的下一个排列，通常需要先对容器进行排序。sort(nums...

LeetCode39.组合总和 题目叙述： 给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。 candidates中的数字可以无限制重复被选取。 说明： 所有数字（包括target）都是正整数。 解集不能包含重复的组合。 示例1： 输入：candidates=[2,3,6,7],target=7, 所求解集为：[[7],[2,2,3]] 示例2： 输入：candidates=[2,3,5],target=8, 所求解集为：[[2,2,2,2],[2,3,3],[3,5]] 思路： 题目中提到同一...

回溯算法的理解： 回溯算法可以理解为一颗树形结构，即一颗n叉树，当遍历到叶子节点的时候，我们就到达了递归的终点，此时我们应该往上走。 回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。 回溯法的效率 回溯法的性能如何呢，回溯并不是什么高效的算法，虽然它很难理解，但是它的本质是枚举出所有情况。 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。 那么既然回溯法并不高效为...

4.组合总和lll（LeetCode216） 题目叙述： 找出所有相加之和为n的k个数的组合，且满足下列条件： 只使用数字1到9 每个数字最多使用一次 返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。 示例1: 输入:k=3,n=7 输出:[[1,2,4]] 解释: 1+2+4=7 没有其他符合的组合了。 示例2: 输入:k=3,n=9 输出:[[1,2,6],[1,3,5],[2,3,4]] 解释: 1+2+6=9 1+3+5=9 2+3+4=9 没有其他符合的组合了。 示例3: 输入:k=4,n=1 输出:[] 解释:不存在有效的组合。 在[1,...

[USACO05NOV]奶牛玩杂技 题目背景 FarmerJohn养了\(N\)头牛，她们已经按\(1\simN\)依次编上了号。FJ所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的）。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起，比如说，第一头牛站在第二头的身上，同时第二头牛又站在第三头牛的身上...最底下的是第\(N\)头牛。 题目描述 每头牛都有自己的体重以及力量，编号为\(i\)的奶牛的体重为\(W_i\)，力量为\(S_i\)。 ...

堆（Heap）的基本概念 堆是一种完全二叉树（CompleteBinaryTree），其性质使得堆可以高效地支持以下操作： 插入（Insert）：将一个新元素加入到堆中。 删除最大/最小元素（DeleteMax/Min）：移除并返回堆中的最大（大根堆）或最小（小根堆）元素。 获取最大/最小元素（GetMax/Min）：返回堆中的最大（大根堆）或最小（小根堆）元素。 大根堆（Max-Heap） 特性： 每个节点的值都大于或等于其子节点的值。 根节点是堆中最大的元素。 插入操作： 将新元素插入到树的最底层的最后位置（保持完全二叉树的性质）。 进行“上浮”操作，将新元素逐步与其父节点交换，...

P1223排队接水 题目描述 有\(n\)个人在一个水龙头前排队接水，假如每个人接水的时间为\(T_i\)，请编程找出这\(n\)个人排队的一种顺序，使得\(n\)个人的平均等待时间最小。 输入格式 第一行为一个整数\(n\)。 第二行\(n\)个整数，第\(i\)个整数\(T_i\)表示第\(i\)个人的接水时间\(T_i\)。 输出格式 输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。 样例1 样例输入1 10 56121991000234335599812 样例输出1 32781496105 291.90 提示 ...

[USACO1.3]修理牛棚BarnRepair 题目描述 在一个月黑风高的暴风雨夜，FarmerJohn的牛棚的屋顶、门被吹飞了好在许多牛正在度假，所以牛棚没有住满。 牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。有些牛棚里有牛，有些没有。所有的牛棚有相同的宽度。宽度为1 自门遗失以后，FarmerJohn必须尽快在牛棚之前竖立起新的木板。他的新木材供应商将会供应他任何他想要的长度，但是吝啬的供应商只能提供有限数目的木板。FarmerJohn想将他购买的木板总长度减到最少。 给出\(m,s,c\)，表示木板最大的数目、牛棚的总数、牛的总数；以及每头牛所在牛棚的编号，请算出拦住所有有牛的牛...

排序 1.冒泡排序 voidbubblesort1(intarr,unsignedintlen) { //长度小于2就不用排序了 if(len<2)return; for(inti=0;i<len1;i){ for(intj=0;j<len1i;j){ if(arr[j]>arr[j+1]) swap(arr[j+1],arr[j]); } } } //冒泡排序使用递归的方法实现 voidbubblesort2(intarr,unsignedintlen) { if(len<2)return; for(inti=0;i<...

题目链接：P1067[NOIP2009普及组]多项式输出 题目叙述： [NOIP2009普及组]多项式输出 题目描述 一元n次多项式可用如下的表达式表示： 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。 多项式中只包含系数不为0的项。 如果多项式n次项系数为正，则多项式开头不出+号，如果多项式n次项系数为负，则多项式以号开头。 对于不是最高次的项，以+号或者号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0次的项，其系数的绝对值为1，则无需输出1）。如果x的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b为x的指数...

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 题目叙述： 给你一个整数数组nums和一个整数k，按以下方法修改该数组： 选择某个下标i并将nums[i]替换为-nums[i]。重复这个过程恰好k次。可以多次选择同一个下标i。 以这种方式修改数组后，返回数组可能的最大和。 示例1： 输入：nums=[4,2,3],k=1输出：5解释：选择下标1，nums变为[4,-2,3]。 示例2： 输入：nums=[3,-1,0,2],k=3输出：6解释：选择下标(1,2,2)，n...