合作: root121toor@gmail.com ~关注我 带你看更多精品技术和面试必备 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组...[4,-1,2,1] 的和最大，为 6。
前言 本文是《剑指Offer》系列（JavaScript版）的第一篇，题目是“连续子数组的最大和或最小和”。 话不多说，开始“打怪”修炼......一、理解题目 以“连续子数组的最大和”为例，相当于我们在数组中，计算连续的子数组的和，找寻最大值。...二、解决方案 连续子数组的最大和 这道面试题有几种解决方案呢？可能在很多个同学的脑海里会出现这样的一种方案： 1....连续子数组的最小和 “连续子数组的最小和” 这个需求的实现原理和“连续子数组的最大和”的实现基本是一致的，唯一的区别点为：当sum的值 > 0为正数时，累加就无意义了，需要重新赋值为当前值。...我们来看下代码的实现 /** * getLeastSumOfSubArray() * @description 获取连续子数组的最小和 * @param Array arr 指定的数组 * @returns
2021-07-16：三个无重叠子数组的最大和。给定数组 nums 由正整数组成，找到三个互不重叠的子数组的最大和。每个子数组的长度为k，我们要使这3*k个项的和最大化。...返回每个区间起始索引的列表（索引从 0 开始）。如果有多个结果，返回字典序最小的一个。 ? 福大大 答案2021-07-16： 时间紧，见代码。 代码用golang编写。...} } a := 0 b := 0 c := 0 max = 0 for i := k; i < N-2*k+1; i++ { // 中间一块的起始点
数据结构与算法 基本算法思想 动态规划 贪心算法 回溯算法 分治算法 枚举算法 算法基础 时间复杂度 空间复杂度 最大复杂度 平均复杂度 基础数据结构 数组 动态数组 树状数组 矩阵 栈与队列 栈 队列...邻接矩阵 邻接表 关键路径 最小生成树 最短路径 拓扑排序 常见算法 十大排序算法 简单排序: 插入排序 选择排序 冒泡排序 分治排序: 快速排序 : 注意轴的选取方式 归并排序 分配排序:...桶排序 基数排序 树状排序: 堆排序 计数排序 希尔排序 图论算法 图的表示: 邻接矩阵 邻接表 遍历算法: 深度搜索 广度搜索 查找算法: 二分查找 散列表查找 树结构查找 最短路径算法:...贪心算法 启发式搜索算法: A*寻路算法 地图着色算法 N皇后问题 最优加工算法 旅行商问题 动态规划 树形DP: 01背包问题 线性DP: 最长公共子序列 最长公共子串 区间DP: 矩阵最大值...矩阵最大和 矩阵最大积 数位DP: 数字游戏 状态压缩DP: 旅行商 字符串匹配算法 正则表达式 暴力匹配算法 模式匹配: KMP Boyer-Moore Trie 流相关算法 最大流: 最短增广路
返回击败全部 n 个对手需要训练的 最少 小时数目。 题解 随着比赛的进行，我们的经验和能量都会发生变化。我们要战胜对手需要保证经验和能量都超过它们，我们需要找到能够保证一命通关的最小数值。...其中一个思路是二分，我们在0和int32之间二分初始的能量和经验，找到满足条件的最小答案。 当然还有更好的做法，就是直接挑战所有选手。如果当前挑战不成功，我们记录下来当前距离挑战成功所需要的点数。...K 大和 给你一个整数数组 nums 和一个 正 整数 k 。...你可以选择数组的任一 子序列 并且对其全部元素求和。 数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复） 返回数组的 第 k 大和 。...那么最大的子序列就是包含所有元素的子序列，最小的子序列就是空集。我们观察一下可以发现，最大和最小的情况是相反的。比如[1, 2, 3]，最大的子序列是[1, 2, 3]。
例如： 数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11（16 - 5） 分析： 看到这个题目，很多人的第一反应是找到这个数组的最大值和最小值，然后觉得最大值减去最小值就是最终的结果...； （2）被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值； （3）被减数在第一个子数组中，是第一个子数组的最大值；减数在第二个子数组中，是第二个子数组的最小值。...在前面提到的三种情况中，得到第一个子数组的最大值和第二子数组的最小值不是一件难事，但如何得到两个子数组中的数对之差的最大值？...如何求连续子数组最大之和，见前一篇博客数组中最大和的子数组，在此直接给出参考代码： // 解法2： 转化求解子数组的最大和问题 int MaxDiff(int array[], unsigned int...第二种方法需要一个长度为n-1的辅助数组，因此其空间复杂度是O(n)。 第三种方法则没有额外的时间、空间开销，并且它的代码是最简洁的，因此这是最值得推荐的一种解法。 源码
以下是一些可以确定需要滑动窗口的方式： 问题输入是线性数据结构，例如链表，数组或字符串 要求你找到最长/最短的子字符串，子数组或所需的值 你将滑动窗口模式用于以下常见问题： 大小为" K"的最大总和子数组...在许多情况下，两个指针可以帮助你找到具有更好空间或运行时复杂性的解决方案。 确定何时使用"两指针"方法的方法： 在处理排序数组（或链接列表）并且需要找到一组满足某些约束的元素时，它将遇到一些问题。...数组中的元素集是一对，三元组甚至是子数组 以下是具有两个指针模式的一些问题： 平方排序数组（简单） 总计为零的三元组（中） 比较包含退格键的字符串（中） 3、快速指针或慢速指针 快速和慢速指针方法，也称为...它们将是涉及编号在给定范围内的排序数组的问题 如果问题要求你在排序/旋转数组中查找缺失/重复/最小的数字 具有循环排序模式的问题： 查找丢失的号码（简单） 查找最小的遗漏正数（中） 6、就地反转链表 在很多问题中...如何识别K-way合并模式： 该问题将出现排序的数组，列表或矩阵 如果问题要求你合并排序列表，请在排序列表中找到最小的元素。
注意连通分量的概念，它强调: 要是子图； 子图要是连通的； 连通子图含有极大顶点数； 具有极大顶点数的连通子图包含依附于这些顶点的所有边。...当在E中选择一条具有最小权值的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则重新选择一条权值最小的边 c....遍历与结点1相连的所有结点，找到距离最近的一个，把这个结点标记为访问过，并更新最短路径 b. 遍历最短路径包含的点相连的节点，找到距离最近的加入最短路径，并且标记为访问过 c....打印顶点 */ EnQueue(&Q,j); /* 将找到的此顶点入队列 */ } } } } } } 对于邻接表的广度优先遍历，代码与邻接矩阵差异不大...Dijkstra 算法 文字解释枯燥无味，我选择看图：（求解节点“1”到其他所有节点的最短路径） 这是我能找到的最容易理解的图了，其他图文讲的讳莫如深，我不喜欢。
欢迎 点赞✍评论⭐收藏前言数据结构是一种组织和存储数据的方式，它涉及如何在计算机中存储和访问数据的方法和技术。数据结构可以用来解决不同类型的问题，包括搜索、排序、插入和删除等操作。...一、完整数据结构1.线性结构线性表栈和队列串2.数组、矩阵和广义表3.树树和二叉树的定义二叉树的性质与存储结构二叉树的遍历线索二叉树最优二叉树(哈夫曼树)树和森林4.图图的定义和存储图的遍历深度优先搜索广度优先搜索生成树和最小生成树拓扑结构和关键路径...图的表示方法有多种，包括邻接矩阵和邻接表。邻接矩阵是一个二维数组，用于表示节点之间的连接关系。邻接表则是一个链表数组，用于表示每个节点的邻接节点。...常见的查找算法包括线性查找、二分查找、哈希查找等。线性查找：线性查找是最简单的查找算法，逐个遍历数据集合中的元素，直到找到目标元素或者遍历完所有元素。时间复杂度为O(n)。...选择排序（Selection Sort）：每次从待排序的元素中选择最小（或最大）的元素，放到已排序部分的末尾，直到所有元素都排好序。
普里姆（Prim）算法 基本思想： 设G=(V, E)是具有n个顶点的连通网， T=(U, TE)是G的最小生成树， T的初始状态为U={u0}（u0∈V），TE={ }， 重复执行下述操作：...如何判断一条边所依附的两个顶点在同一个连通分两中(并查集) 定义Parent[i]数组。...数据结构 : 图的存储结构：邻接矩阵存储结构 数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。...数组path[n]：path[i]是一个字符串，表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为vvi；否则置path[i]空串。...数组s[n]：存放源点和已经找到最短路径的终点，其初态为只有一个源点v。 迪杰斯特拉算法的主要步骤如下： (1) g为用邻接矩阵表示的带权图。
问题描述 n个村庄间架设通信线路，每个村庄间的距离不同，如何架设最节省开销？...这个问题中，村庄可以抽象成节点，村庄之间的距离抽象成带权值的边，要求最节约的架设方案其实就是求如何使用最少的边、最小的权值和将图中所有的节点连接起来。...这就是一个最小代价生成树的问题，可以用Prim算法或kruskal算法解决。 PS1：无向连通图的生成树是一个极小连通子图。 PS2：生成树是图的一个子图，包括所有的顶点和最少的边（n-1条边）。...图的邻接表示法 边节点 ? 一个边节点有一条边 和 一个终止节点组成。...在lowcost数组中找到那个权值最小，且不在生成树中的边的节点，将它加入生成树中： 3.1. 遍历lowcost，找出最小值； 3.2.
目录 一.课本知识点 1.图的定义和术语 2.图的存储结构 a.邻接矩阵(数组)表示 b. 邻接表表示 c. 十字链表 d....路径： 路径长度： 回路（环）： 简单路径： 简单回路（简单环）： 子图： 连通图： 连通分量： 强连通图：有向图 强连通分量：的极大强连通子图。...在图的邻接表中如何进行DFS？...辅助数组dist[n]为各终点当前找到的最短路径的长度，初始值为： dist[i]＝A[v0 ,i] //即邻接矩阵中第v0行的权值 （2）选择u，使得...用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2) ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。 15.
父节点（Parent） 一个节点的直接上级节点称为父节点。 兄弟节点（Sibling） 具有相同父节点的节点互为兄弟节点。 叶节点（Leaf） 没有子节点的节点称为叶节点或终端节点。...1.2 树的特点和性质 树（Tree）作为一种常见的数据结构，具有以下特点和性质： 特点与性质 解释 非线性结构 树是一种非线性的数据结构，与线性结构（如数组和链表）相对。...邻接矩阵适用于稠密图，其中边的数量相对节点的数量较多。 邻接表（Adjacency List）： 邻接表是一种使用链表或数组的列表来表示图的方式。对于每个节点，维护一个与之相邻节点的列表。...通过创建一个邻接表来表示图的连接关系，并使用一个visited数组和队列来辅助遍历。...图的最小生成树算法主要用于找到一个连通图的最小生成树，即连接图中所有节点的边的集合，且边的权重之和最小。
从所有的顶点 u∈U 和顶点 v∈V-U 的带权边中选出具有最小权值的边（u,v），将顶点 v 加入集合 U 中，将边（u,v）加入集合 T 中。如此不断地重复直到 U=V 时，最小生成树构造完毕。...在所有 u 为集合 U 中顶点、 v 为集合 V-U 中顶点的边(u,v)中寻找具有最小权值的边，寻找到的边是(A,D)，权值为 20，把顶点 B 加入到集合U 中，把边(A,D)加入到集合 T 中，如图...在所有 u 为集合 U 中顶点、v 为集合 V-U 中顶点的边(u,v)中寻找具有最小权值的边，寻找到的边是(D,E)，权值为 10，把顶点 E 加入到集合 U 中，把边(D,E)加入到集合 T 中，如图...另外，为了表示某顶点的最短路径是否已经找到，在算法中设了一个一维数组 final,如果 final[i]为 true,则表示已经找到第 i 个顶点的最短路径。 i 是该顶点在邻接矩阵中的序号。...例如，很多工程都可分为若干个具有独立性的子工程，我们把这些子工程称为“活动”。每个活动之间有时存在一定的先决条件关系，即在时间上有着一定的相互制约的关系。
A. 5 B. 6 C. 7 D. 8 本题共 1.5 分 第 9 题 6 个顶点的连通图的最小生成树，其边数为（ ）。...O(n2) 本题共 1.5 分 第 11 题 具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运 算的时间复杂度均为（ ）。 A. Θ(n2) B. Θ(e2) C....）给定一个长度为 n（3 ≤ n ≤ 1000）的整数序列，要求从中选出两个 连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。...用邻接矩阵的 形式给出每条边的边长，要求输出以结点 0 为起点出发，到各结点的最短路径长度。...使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最 短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻 的结点的 dist
强调： *要是子图； *子图要是连通的； *连通子图含有极大顶点数； *具有极大顶点数的连通子图包含依附于这些顶点的所有边。 2.从Vi到Vj和从Vi到Vj都存在路径，则称G是强连通图。...2.图的五种不同的存储结构： （1）邻接矩阵：图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。...（2）邻接表：数组与链表相结合的存储方法称为邻接表。 *邻接表的处理方法是这样： 1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。...另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。...比较：深度优先遍历更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。 六（最小生成树） 我们把构造连通网的最小代价生成树称为最小生成树。
题目 描述 给定一个整数数组，找到一个具有最小和的子数组。返回其最大和。 注意事项：子数组最少包含一个数字。...样例 给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6 解答 思路 双重循环，以每个元素作为起点向后计算子数组的和，找到最大的和。
、最简单的链表； 链表的节点（Node）： 完整的链表： 链表的优点：新增节点、删除节点快； 在链表中新增一个元素： 在单向链表中，新增一个元素最多只会影响上一个节点，比在数组中的新增效率要高的多； 在链表中删除一个元素...： 链表的缺点： 1）查询速度慢，查询从头部开始一直查询到尾部，如果元素刚好是在最尾部那么查询效率势必非常低； 2）链表相对于数组多了一个指针域的开销，内存相对占用会比较大； 总结：数据量较小，需要频繁增加...，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。...，通过key和value来映射到散列表中的一个位置，这样就可以很快找到集合中的对应元素。...，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。
如果连通图是一个网络，图的边上带权，则其生成树中的边也带权。那么称该网络中所有带权生成树中权值总和最小的生成树为最小生成树，也叫作最小代价生成树。...一个具有n个顶点的图G可定义一个数组vertex[n]，将该图顶点的数据信息分别存放在对应的数组元素上，也就是将顶点 v_i 的数据信息存放在vertex[i]中。...有了邻接矩阵我们就可以对数组vertex中的顶点元素进行操作。 如果通过邻接矩阵表示具有n个顶点的图，则需要占用n×n个存储单元保存顶点之间边的信息，所以空间复杂度为 O(n^2) 。...具体来讲，要为图中每个顶点分别建立一个链表，具有n个顶点的图的邻接表包含n个链表。 每个链表前面设置一个头节点，称为顶点节点。...在该类中包含了一个VNode类的数组，用来存放每个顶点的信息，包括顶点中的数据和该顶点指向边链表的指针。 图的创建 下面介绍如何用createGraph()函数创建一个图。
最大子数组和【中等】 给你一个整数数组nums请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。...分析下 以第2个元素作为子数组尾元素 的最大和？...综上分析，以第2个元素作为子数组尾元素的最大和 就是在：以第1个元素作为数组尾元素最大和 + 第2个元素，第2个元素 中选一个较大的。...如果再加入第3个元素，以第3个元素作为子数组尾元素的最大和选择同理也是：第3个元素，第3个元素+以第2个元素作为子数组尾元素的最大和中选一个较大的。...依次类推第n个元素 a[n] 作为子数组尾元素的最大和 s[n]，用公式来说就是： s[n] = Max( a[n] , s[n-1] + a[n] ) 所谓整个数组的最大和的连续子数组，无非是在 第
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
