Leetcode刷题总结-3.二叉树篇

Leetcode刷题总结二叉树刷题心得、总结文章目录Leetcode刷题总结前言一、二叉树刷题思路二、美团面试题2.1 第十套卷面试题2.2 第九套卷面试题三、华为研发工程师编程题四、华为2016研发工程师编程题前言二叉树有两种主要的形式满二叉树和完全二叉树满二叉树上只有度为0和2的节点完全二叉树的定义是在除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置通俗点说就是没填满的都在最后一层而且是从左向右没填满的都是在右边 当然还有几种比较特殊的二叉树二叉搜素树二叉搜索树是一个有序树左子树的节点的值均小于根节点的值右子树的节点的值均大于根节点的值同时左右子树也是搜索树满足左小右大的性质、平衡二叉搜索树AVL是在为二叉搜素树的基础上左右两个子树的高度差的绝对值不超过1而且左右子树都是平衡二叉树。一、二叉树刷题思路Notes首先来说一说递归三部曲这是卡尔总结的我只是学习到了做个记录下面来看1确定递归函数的参数和返回值2确定终止条件3确定单层逻辑力扣 144、94、145 题 二叉树的前、中、后序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/、 https://leetcode.cn/problems/binary-tree-inorder-traversal/、https://leetcode.cn/problems/binary-tree-postorder-traversal/思路这三道题都是比较简单的题二叉树的前、中、后序遍历我们按照递归三部曲来看一看首先递归函数的给定参数一定是根节点root和需要的结果存储的数组返回值是结果存储的数组如果当前遍历的节点为空时就终止单层的逻辑分别为前、中、后序遍历顺序前序遍历就是数组先存储当前节点的值、遍历左子树、遍历右子树中序遍历就是数组先遍历左子树、再存储当前节点的值、遍历右子树后序遍历就是数组先遍历左子树、遍历右子树、最后存储当前节点的值。力扣 102 题 二叉树的层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/思路题目描述中给你二叉树的根节点 root 让你返回其节点值的层序遍历层序遍历需要借用队列去实现我这里记录自己使用非递归方法的层序遍历思路如果给的不是空树就先把根节点进队进队后记录此时的size大小用该size去pop队列中的节点把节点值存储到数组中pop节点的同时把左右子树的节点入队列每次size出队列完成后就把该数组存到一个新数组中同时记录此时队列的大小该大小就是这一层的节点的个数队列变空了就说明遍历完了二叉树最后返回新数组即可。力扣 226 题 翻转二叉树 https://leetcode.cn/problems/invert-binary-tree/思路题目描述中给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点这道题的思路也是十分巧妙的使用递归去翻转每一层的节点递归的参数为当前的节点返回的是根节点、当前节点为空的时候就终止递归、单层的递归逻辑就是先反转当前节点的左右节点然后递归去反转当前节点的左右节点的孩子节点。力扣 101 题 对称二叉树https://leetcode.cn/problems/symmetric-tree/submissions/思路题目描述中给你一个二叉树的根节点 root 检查它是否轴对称这道题的思路就是用迭代法去遍历这棵二叉树首先是树为空就天然对称返回true就可以了如果树不为空就把它的左右孩子节点入队列在循环中检查左右孩子节点的值是否相同如果相同就放入左孩子的左节点、右孩子的右节点、左孩子的右节点、右孩子的左节点这样入队列的目的是每次出队列的两个节点都是我们要检验值是否相同的节点也就是对称的节点如果两个对称节点都为空也是对称的就继续往下走需要加一个判断处理这种情况。力扣 104、111 题 二叉树的最大深度、二叉树的最小深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/、https://leetcode.cn/problems/minimum-depth-of-binary-tree/submissions/思路二叉树的最大深度、最小深度本质上都是二叉树的层序遍历只是最大深度的在每一层遍历的时候都加1而且队列不为空就一直层序遍历二叉树而最小深度的在层序遍历的时候都加1但是只要当前节点为叶子结点左右孩子都为空就返回深度结束遍历这就是二者的差别都是只需在层序遍历的代码上加上记录深度最小深度多加一个判断条件。力扣 222 题 完全二叉树的节点个数https://leetcode.cn/problems/maximum-depth-of-binary-tree/、https://leetcode.cn/problems/minimum-depth-of-binary-tree/submissions/思路题目描述中给你一棵完全二叉树的根节点 root 让你求该树的节点个数这道题的思路也是比较简单的因为求该树的节点个数就是用层序遍历的代码只需要在每次往队列中加节点的时候用一个变量每次加1最后返回这个变量就可以啦。力扣 110 题 平衡二叉树https://leetcode.cn/problems/maximum-depth-of-binary-tree/、https://leetcode.cn/problems/minimum-depth-of-binary-tree/submissions/思路题目描述中给你一个二叉树让你判断它是否是高度平衡的二叉树这道题目求的是高度注意高度和深度不是同一个东西高度是从该节点到叶子节点的最长简单路径边的条数深度是从该节点到根节点的最长简单路径边的条数既然是求高度就只能用后序遍历了用递归去做来看递归三部曲1递归函数给定的参数的当前节点返回值是当前节点作为根节点的子树的高度2终止条件就是当前节点的左右子树高度差超过13单层的逻辑就是先求左子树的高度再求右子树的高度看两者高度差是否超过1超过1返回-1没超过就计算当前树的高度。力扣 257 题 二叉树的所有路径https://leetcode.cn/problems/binary-tree-paths/思路题目描述中给你一个二叉树的根节点 root 按任意顺序 返回所有从根节点到叶子节点的路径叶子节点 是指没有子节点的节点既然求的是叶子节点到根节点的路径所以必须用后序遍历这样回溯返回的才是从叶子结点返回的直到根节点正常来说递归实现后序遍历应该先递归左右子树但是本题如果先递归左右子树后把值放入path中会使最后的叶子结点没有放入路径里所以应该先把值放入path里再递归左右子树递归的终止条件是当前节点为叶子结点那么我们就需要收获结果了把path里的数字变成字符同时在后面拼接上题目要求的字符串拼接完成一个path后把它放入result中如此往复直到所有结果放入result中。力扣 404 题 左叶子之和https://leetcode.cn/problems/sum-of-left-leaves/思路题目描述中给定二叉树的根节点 root 让你返回所有左叶子之和这道题目仍然可以用递归来做既然是要求所有左叶子之和那么就需要找到所有的左叶子但是本题有一个特殊的地方在于你怎么知道这个叶子结点是不是父节点的左子树呢所以本题的递归不能遍历到叶子结点只能遍历到叶子结点的父节点这样才能判断这个叶子结点是不是父节点的左子树什么时候去收获结果呢那就是遍历到左子树的时候判断该节点的左子树不为空且该节点的左节点为叶子结点就去收获结果遍历完左子树就遍历右子树两者的结果加起来得到最终的结果。力扣 69 题 x 的平方根 https://leetcode.cn/problems/sqrtx/思路题目描述中给你一个非负整数 x 计算并返回 x 的 算术平方根 由于返回类型是整数结果只保留 整数部分 小数部分将被舍去 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 这道题的思路就是牛顿迭代法使用f(x)的一阶泰勒展开式去近似f(x)然后去计算x得到x的计算公式为x0.5*(xa/x)得到计算公式后去计算每次迭代求出的值和上次的差值是否很小如果差值很小就说明我们得到结果了对它取整返回即可。力扣 513 题 找树左下角的值 https://leetcode.cn/problems/find-bottom-left-tree-value/思路题目描述中给定一个二叉树的 根节点 root让你找出该二叉树的 最底层最左边节点的值假设二叉树中至少有一个节点这道题用层序遍历的思路就可以解决但是需要加上一个判断在每层进行遍历的时候都把每层最左边的节点的值赋值给result这样每层最左边的值一直覆盖result最后的值一定是最后一层的最左边节点的值也就是我们要找的答案。力扣 112 题 路径总和https://leetcode.cn/problems/path-sum/思路题目描述中给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 判断该树中是否存在 根节点到叶子节点的路径这条路径上所有节点值相加等于目标和 targetSum 如果存在返回 true 否则返回 false 这道题和二叉树的所有路径类似而且不需要对路径的节点的值做转变转变为字符串只需要把每个路径的节点的值相加放入result数组中再遍历这个数组看是否有与target相同的值没有就返回false有就返回true。力扣 106 题 从中序与后序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/思路题目描述中给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗二叉树这道题有点难度需要递归的切分中序遍历和后序遍历必须先切分中序遍历再切分后序遍历去构建二叉树实现的过程就是首先找到根节点其实找到它在中序遍历中的下标索引其次就开始切分中序遍历、后序遍历得到左子树的中序遍历、后序遍历和右子树的中序遍历、后序遍历最后递归的切分左子树的中序遍历、后序遍历和右子树的中序遍历、后序遍历构建出了一颗二叉树。力扣 654 题 最大二叉树 https://leetcode.cn/problems/maximum-binary-tree/思路题目描述中给定一个不重复的整数数组 nums 最大二叉树可以用下面的算法从 nums递归地构建:创建一个根节点其值为 nums 中的最大值递归地在最大值 左边 的 子数组前缀上构建左子树递归地在最大值右边的子数组后缀上构建右子树这道题的思路很明显是使用递归首先递归的终止条件是数组大小为1的时候就返回该节点因为要递归的构建左右子树所以首先需要遍历整个数组找到最大值以及下标定义变量的时候最大值为第一个数下标为0定义一个节点节点的值为该最大值然后因为我们递归终止条件是为一个节点所以构建左右子树的过程中需要判断左右子树是否为空如果最大值的下标大于0说明左边子树不为空那就构建左子树如果最大值的下标小于数组的大小说明右子树不为空那就构建右子树最后返回根节点即可。力扣 700 题 二叉搜索树中的搜索 https://leetcode.cn/problems/search-in-a-binary-search-tree/思路题目描述中给定二叉搜索树BST的根节点 root 和一个整数值 val你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在则返回null 二叉搜索树是左子树的值都小于根节点、右子树的值都大于根节点的树二叉树的搜索这道题目的思路就是用递归用递归三部曲来分析递归的传递参数就是当前的节点和要寻找的值返回参数是等于要找的等于特定的值的节点或者返回空节点当前节点为空节点是终止条件说明已经到叶子结点了需要向上返回了或者已经找到要找的节点单层的逻辑是递归在节点的左子树和右子树寻找等于特定的值的节点最后返回结果即可。力扣 98 题 验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree/思路题目描述中给你一个二叉树的根节点 root 让你判断其是否是一个有效的二叉搜索树这道题很有意思如果给你一个数组让你判断数组是否单调递增肯定都会但是给你一个二叉树让你判断其是否是一个有效的二叉搜索树确蒙圈了其实我还是对二叉树的遍历方式不是特别懂这道题用中序遍历就可以得到一个单调递增的数组了所以这道题有两个思路一是把中序遍历得到的结果存到一个数组中然后判断数组是否单调递增即可二是双指针 用一个节点记录上一个遍历过的节点如果上一个节点的值大于等于当前节点的值这棵树就不是二叉搜索树返回false否则就更新pre指针继续进行遍历最后左右子树得到的结果综合最终的返回结果。力扣 530 题 二叉搜索树的最小绝对差 https://leetcode.cn/problems/minimum-absolute-difference-in-bst/思路题目描述中给你一个二叉搜索树的根节点 root 返回树中任意两不同节点值之间的最小差值差值是一个正数其数值等于两值之差的绝对值这道题如果验证二叉搜索树会了这道题就很简单继续用中序遍历得到数组遍历数组得到两个相邻的值的差取最小的即可。力扣 501 题 二叉搜索树中的众数 https://leetcode.cn/problems/find-mode-in-binary-search-tree/思路题目描述中给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有众数如果树中有不止一个众数可以按任意顺序返回怎么找众数呢这道题仍然是用中序遍历但是难点在于怎么把众数找出来也就是中在处理中的逻辑中我们仍然用双指针两个指针指向的节点的值一样那就计数值加1否则计数值就重新赋为1第一次进循环的时候直接计数值赋为1即可为了找到众数需要一个计数值和一个最大值用来记录计数值中最大的值的变量每次把计数值等于最大值的放入存放结果的数组中如果计数值大于最大值那就更新最大值同时把结果集清空把当前的节点的值再重新放入结果集中核心就是滚动更新pre指针、结果集、最大值最终得到结果。力扣 617 题 合并二叉树 https://leetcode.cn/problems/merge-two-binary-trees/思路题目描述中给你两棵二叉树让你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠你需要将这两棵树合并成一棵新二叉树合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点返回合并后的二叉树这道题目是比较简单的来看递归三部曲递归的参数是当前的两颗树的节点返回值是合并后树的根节点当一棵树对应的位置节点为空的时候就可以终止递归返回另一棵树的该节点即可单层的逻辑就是根节点的值等于两个树对应节点值相加然后在左子树上合并在右子树上合并最后返回根节点。力扣 700题 二叉搜索树中的搜索 https://leetcode.cn/problems/search-in-a-binary-search-tree/思路题目描述中给定二叉搜索树BST的根节点 root 和一个整数值 val你需要在 BST 中找到节点值等于 val 的节点返回以该节点为根的子树。 如果节点不存在则返回 null 在二叉搜索树中找节点值用后序遍历来遍历二叉树来看递归三部曲的步骤递归的参数是当前的节点和要寻找的节点值返回值是找到的节点当前节点为空或者当前的节点等于要寻找的节点值就返回该节点单层递归的逻辑就是判断当前节点值和要寻找的节点值的大小关系然后向左子树或右子树继续寻找。力扣 98题 验证二叉搜索树https://leetcode.cn/problems/validate-binary-search-tree/思路题目描述中给你一个二叉树的根节点 root 让你判断其是否是一个有效的二叉搜索树判断是否为一个有效的二叉搜索树有一个很容易犯错的地方我自己就犯错了就是递归的去遍历树判断当前节点的左孩子小于节点值右孩子大于节点值这样的问题在于不能验证根节点的左子树值是否均小于根节点也不能验证根节点的右子树值是否均大于根节点所以就会出错判断错误正确的做法是用两个节点的值循环比较其中cur节点就是依次后续遍历的节点pre节点是上一个cur节点这样遍历只要pre节点的值一直小于cur节点即可。力扣 530题 二叉搜索树的最小绝对差https://leetcode.cn/problems/minimum-absolute-difference-in-bst/思路题目描述中给你一个二叉搜索树的根节点 root 让你返回树中任意两不同节点值之间的最小差值 差值是一个正数其数值等于两值之差的绝对值这道题思路很简单把二叉搜索树的后序遍历结果放到数组中循环找相邻两个数的最小差值即可。力扣 235 题 二叉搜索树的最近公共祖先https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/思路题目描述中给定一个二叉搜索树, 让你找到该树中两个指定节点的最近公共祖先递归三部曲递归参数是当前的节点和要寻找的两个节点值返回值是两个节点的最近公共祖先如果遍历到空节点或者找到了其中一个节点值就返回单层的逻辑是向左子树寻找、向右子树寻找如果两个子树返回值都不为空那就返回左右子树的最近公共祖先。力扣 701 题 二叉搜索树中的插入操作https://leetcode.cn/problems/insert-into-a-binary-search-tree/思路题目描述中给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树返回插入后二叉搜索树的根节点输入数据保证 新值和原始二叉搜索树中的任意节点值都不同递归三部曲递归的参数为当前的节点和要插入树中的值 value返回值为新的节点当遍历到空节点的时候证明已经找到合适的位置了定义节点把节点返回给上一层即可单层递归的逻辑是遍历左子树、遍历右子树最后返回根节点即可。力扣 450 题 删除二叉搜索树中的节点https://leetcode.cn/problems/delete-node-in-a-bst/思路题目描述中给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变返回二叉搜索树有可能被更新的根节点的引用这道题目要处理几种情况一是要删除节点左子树、右子树都为空二是左子树为空、右子树不为空三是左子树不为空、右子树为空四是左子树、右子树都为不为空第一种情况直接返回空节点第二种情况返回右孩子的节点第三种情况返回左孩子的节点第四种情况麻烦一点需要先在该节点的左孩子上一直找右孩子直到右孩子的孩子为空此时把该节点的右孩子的子树放到这里来返回左孩子即可。这是对找到节点的操作相当于终止条件下面就是单层逻辑的执行向左子树寻找、右子树寻找最后返回根节点。力扣 669 题 修剪二叉搜索树https://leetcode.cn/problems/trim-a-binary-search-tree/思路题目描述中给你二叉搜索树的根节点 root 同时给定最小边界low和最大边界 high让你通过修剪二叉搜索树使得所有节点的值在[low, high]中修剪树不应该改变保留在树中的元素的相对结构递归三部曲递归的参数是当前的节点、节点的值的上界和下界返回值是根节点当遍历到空节点的时候就终止单层递归的逻辑就是当前节点值小于下界那就去当前节点的右子树寻找合适的节点并返回节点当前节点值大于下上界那就去当前节点的左子树寻找合适的节点并返回节点最终返回根节点即可。力扣 108 题 将有序数组转换为二叉搜索树https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/思路题目描述中给你一个整数数组 nums 其中元素已经按升序排列让你将其转换为高度平衡的二叉搜索树递归三部曲递归的参数是数组和数组的左、右下标返回值是根节点当左下标大于右下标没有值了就终止单层的逻辑首先是处理中间节点也就是根节点第的逻辑左、右下标相加除以2得到中间值的下标然后定义一个节点把节点值赋为刚才的中间值然后左下标到中间下标之前的递归去分割中间下标到右下标的递归去分割最后返回根节点。力扣 538 题 把二叉搜索树转换为累加树https://leetcode.cn/problems/convert-bst-to-greater-tree/思路题目描述中给出二叉 搜索树的根节点该树的节点值各不相同让你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和因为是从右子树累加到根节点再从根节点累加到左子树这样执行的来看递归三部曲递归参数是当前遍历的节点返回值根节点当遍历到根节点的时候就终止递归遍历右子树、然后当前节点的值等于前节点的值加上它的右子树的值也就是上一层递归节点的值、遍历左子树最终返回根节点即可。Notes这里记录上一层遍历的节点的值用一个变量定义在函数之前然后在加上节点的值语句后把当前节点的值赋值给该变量即可。二、美团面试题2.1 第十套卷面试题1输入第一行仅包含三个正整数n,x,y分别表示参赛的人数和晋级淘汰人数区间(1n50000,1x,yn)输入第二行包含n个整数中间用空格隔开表示从1号选手到n号选手的成绩(1|a_i|1000)。晋级和淘汰的人数均在[x,y]之间显然这个m有可能是不存在的也有可能存在多个m如果不存在请你输出-1如果存在多个请你输出符合条件的最低的分数线。思路这道题我没做出来看了网上别人的解答才明白思路就是既然晋级和淘汰的人数均要在[x,y]之间首先来判断n是否满足条件也就是n2xn2y因为n一旦不符合这个条件那么晋级和淘汰的人数就不符合条件了直接输出-1即可满足条件的情况下题目说了要分数线要最低那就是晋级的人数在满足条件的情况下尽可能多因此需要淘汰的人数应该在y和n-x中取最小值这样可以限制晋级人数不会超过y然后输出淘汰人中最高的分数即可。这里需要对分数进行排序题目说了晋级的人数都大于m所以要输出的是淘汰人中最高的分数在数组中找到对应的下标索引找到后输出它即可。2我们称一个长度为n的序列为正则序列当且仅当该序列是一个由1~n组成的排列即该序列由n个正整数组成取值在[1,n]范围且不存在重复的数同时正则序列不要求排序有一天小团得到了一个长度为n的任意序列s他需要在有限次操作内将这个序列变成一个正则序列每次操作他可以任选序列中的一个数字并将该数字加一或者减一。请问他最少用多少次操作可以把这个序列变成正则序列输入第一行仅包含一个正整数n表示任意序列的长度。(1n20000)输入第二行包含n个整数表示给出的序列每个数的绝对值都小于10000。输出仅包含一个整数表示最少的操作数量。思路首先对给定的n个整数排序刚开始我还被题目说的正则序列不要求排序迷惑了我以为这个数组不需要排序但是你不排序的话怎么知道你对每个数操作在1-n范围内后没有重复的数呢所以只能先排序把每个数操作到1-n的大小内这样的话操作次数才是最少的后面就很简单了把每个数的操作次数加起来就得到结果了。2.2 第九套卷面试题1小团的蛋糕铺长期霸占着美团APP中“蛋糕奶茶”栏目的首位因此总会吸引各路食客前来探店。小团一天最多可以烤n个蛋糕每个蛋糕有一个正整数的重量。早上糕点铺已经做好了m个蛋糕。现在有一个顾客要来买两个蛋糕他希望买这一天糕点铺烤好的最重的和最轻的蛋糕并且希望这两个蛋糕的重量恰好为a和b。剩余的n-m个蛋糕可以现烤请问小团能否满足他的要求输入描述输入包含多组数据每组数据两行。每组数据的第一行包含4个整数n,m,a,b空格隔开。这里不保证a和b的大小关系。接下来一行m个数空格隔开代表烤好的蛋糕重量。输出描述对于每一组数据如果可以办到顾客的要求输出YES否则输出NO。思路要买的蛋糕必须是当天最重的和最轻的因此就需要分几种情况讨论1已经做好的均小于a或者均大于b2已经做好的都在a-b之间3已经做好的包含了要的a或b或者a和b都有根据情况我们把做好的蛋糕计数为小于a、等于a、大于a小于b、等于b、大于b分别按照每种情况讨论即可。比如都在a-b之间就需要判断还没做的蛋糕数目大于等于2那就可以满足顾客要求小于2就不能满足。2小团是综艺节目的策划他为某个游戏环节设计了一种晋级规则已知在这个游戏环节中每个人最后都会得到一个分数score_i显而易见的是游戏很有可能出现同分的情况小团计划该环节晋级人数为x人则将所有人的分数从高到低排序所有分数大于等于第x个人的分数且得分不为0的人都可以晋级。请你求出本环节的实际晋级人数。显然这个数字可能是0如果所有人的得分都是0则没有人满足晋级条件。输入描述输入第一行包含两个正整数n和x分别表示参加本环节的人数和小团指定的x。输入第二行包含n个整数每个整数表示一位选手的得分。输出描述输出仅包含一个整数表示实际晋级人数。思路首先从高到低排序分数然后遍历这个分数如果大于等于x而且不为0那么晋级人数加1最后输出晋级人数。3小美请小团吃回转寿司。转盘上有N盘寿司围成一圈第1盘与第2盘相邻第2盘与第3盘相邻…第N-1盘与第N盘相邻第N盘与第1盘相邻。小团认为第i盘寿司的美味值为A[i]可能是负值如果小团讨厌这盘寿司。现在小团要在转盘上选出连续的若干盘寿司使得这些寿司的美味值之和最大允许不选任何寿司此时美味值总和为0。输入描述第一行输入一个整数T1T10表示数据组数。每组数据占两行第一行输入一个整数N1N10^5第二行输入N个由空格隔开的整数表示A[1]到A[N]-104A[i]104。输出描述每组数据输出占一行输出一个整数表示连续若干盘寿司的美味值之和的最大值。思路这道题的思路也是比较巧妙的首先如果第一个数为负数那么其实连成环和不连求出来的一样那么我们按照正常求连续子数组的最大和即可但是如果第一个数不为负而且连续子数组的最大和包含首尾元素那么就需要去计算所有数加起来的和再去计算连续子数组的最小和两者相减就得到了结果因为最小子数组和最大子数组一定是互补的所以去掉最小的和之后就是最大的啦。三、华为研发工程师编程题1汽水瓶某商店规定三个空汽水瓶可以换一瓶汽水允许向老板借空汽水瓶但是必须要归还。小张手上有n个空汽水瓶她想知道自己最多可以喝到多少瓶汽水输入描述输入文件最多包含 10 组测试数据每个数据占一行仅包含一个正整数 n 1n100 表示小张手上的空汽水瓶数。n0 表示输入结束你的程序不应当处理这一行输出描述对于每组测试数据输出一行表示最多可以喝的汽水瓶数。如果一瓶也喝不到输出0思路这道题目很简单可以借空汽水瓶的意思就是两个瓶子就可以喝一瓶汽水因为借一个空瓶子获得一瓶汽水后喝完再还给他即可所以输入整除2输出即可。2明明生成了N个1到500之间的随机整数请你删去其中重复的数字即相同的数字只保留一个把其余相同的数去掉然后再把这些数从小到大排序按照排好的顺序输出输入描述第一行先输入随机整数的个数 N接下来的 N 行每行输入一个整数代表明明生成的随机数输出描述输出多行表示输入数据处理后的结果思路把输入的数字放入集合中set然后用auto类型auto x : s把结果输出即可。3十六进制转换十进制写出一个程序接受一个十六进制的数输出该数值的十进制表示输入描述输入一个十六进制的数值字符串输出描述输出该数值的十进制字符串。不同组的测试用例用\n隔开思路从低位开始把字符与‘0’或者A作差后A作差要加10得到的数乘以16的第几位减一的次方然后累加之后输出即可。四、华为2016研发工程师编程题1有一个数组 a[N] 顺序存放 0 ~ N-1 要求每隔两个数删掉一个数到末尾时循环至开头继续进行求最后一个被删掉的数的原始下标位置,以 8 个数 (N7) 为例 : 01234567 0 - 1 - 2 (删除) - 3 - 4 - 5 (删除) - 6 - 7 - 0 (删除),如此循环直到最后一个数被删除;输入描述每组数据为一行一个整数n(小于等于1000)为数组成员数输出描述一行输出最后一个被删掉的数的原始下标位置思路这道题目是经典的约瑟夫环的问题每隔两个元素循环删除一个元素思路是通过对数组的大小取余实现循环删除的元素要设置标志表示已经删除了再遇到的话直接跳过继续当操作的次数没有到达数组的大小时继续操作同时每次操作记录删除的元素下标这么做的目的是删除完元素后直接输出这个下标就是要求的结果。intmain(){intn;while(cinn){intcountSizen;intcount0;inti0;intlastIndex0;vectorintnums(n,0);for(inti0;in;i){nums[i]i;}while(countSize!0){if(nums[i]!DELFLAG){if(countSTEP){lastIndexi;nums[i]DELFLAG;count0;countSize--;}}i(i1)%n;}coutlastIndexendl;}}2输入一个字符串求出该字符串包含的字符集合按照字母输入的顺序输出;输入描述每组数据输入一个字符串字符串最大长度为100且只包含字母不可能为空串区分大小写;输出描述每组数据一行按字符串原有的字符顺序输出字符集合即重复出现并靠后的字母不输出;思路这道题的收获在于怎么读取多行字符要用getline(cin,str)读取用之前读取整数的方式不可取会把所有行的字符串读到一个字符串里然后通过集合进行去重要加入集合的元素就是不重复的元素因此就把它添加到要输出的字符号串中最后输出字符串即可。intmain(){string input;while(getline(cin,input)){if(input.empty())break;string result;unordered_setcharuniqueChars;for(autoch:input){if(uniqueChars.find(ch)uniqueChars.end()){uniqueChars.insert(ch);resultch;}}coutresultendl;}}