本想撸完迷宫去上个厕所，却憋了2个小时，解法倒是很简单，但是为啥特么总有傻X把入口堵死。那还走个🔨。不同路径一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）

前缀和

区间问题

等差数列划分如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列。最佳观光组合给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。返回一对观光景点能取得的最高分。等差数列划分解题思路定义等差数列 一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列 取数组第一，二个元素先求出公差，从数组下标2开始迭代，判断当前元素和前一个元素的差是否等于公差，若等于则计数，如果不是重新计算公差，然后计数器清零。每次计算总数代码实现func numberOfArithmeticSlices(nums []int) int { if len(nums)<3{ return 0 } tolerance:=nums[1]-nums[0] total,count:=0,0 for i:=2;i<len(nums);i++{ if nums[i]-nums[i-1]==tolerance{ total++ }else{ tolerance=nums[i]-nums[i-1] total=0; } count+=total } return count}最佳观光组合解题思路定义等差数列 观光组合的得分为 values[i] + values[j] + i - j 代码实现func maxScoreSightseeingPair(values []int) int { a,b,max:=0,1,0 for b<len(values) { pre:=values[a]+a-b max = MathMax(max,pre+values[b]) if values[b]>pre{ a=b } b++ } return max}func MathMax(a,b int)int{ if a>b{ return a } return b}

丑数给你一个整数n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。丑数 就是只包含质因数 2、3 和/或 5 的正整数。丑数 II给你一个整数 n，请你找出并返回第 n个 丑数 。丑数 就是只包含质因数2、3 和/或5 的正整数。丑数解题思路根据给定的题意 丑数 就是只包含质因数 2、3 和/或 5 的正整数。 ，第一个想到就是因式分解。一直做除法如果这个数除到最后等于1那么就是，如果不是那么就是非丑数代码实现迭代class Solution { public boolean isUgly(int n) { while(n>=1){ if (n%2==0){ n/=2; }else if(n%3==0){ n/=3; }else if(n%5==0){ n/=5; }else{ return n==1; } } return false; }}递归class Solution { public boolean isUgly(int n) { if (n==0){ return false; } if (n==1){ return true; } if (n%2==0){ return isUgly(n/2); }else if(n%3==0){ return isUgly(n/3); }else if(n%5==0){ return isUgly(n/5); } return false; }}丑数 II解题思路第一道题从数字n入手，一步步向下做除法，试探n是不是丑数。这里需要找到第n个丑数，代表我们的思维需要从下往上，从小的数值向大寻找。定义一个丑数数组，将所有的丑数三等分，定义a,b,c来标记分别标记被2，3，5整除的数据的下标从0开始，从1开始计算到n的丑数代码实现class Solution { public boolean isUgly(int n) { if (n==0){ return false; } if (n==1){ return true; } if (n%2==0){ return isUgly(n/2); }else if(n%3==0){ return isUgly(n/3); }else if(n%5==0){ return isUgly(n/5); } return false; }}

2022最大和打卡最大子数组和给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。环形子数组的最大和给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i],C[i+1], ..., C[j]，不存在 i <= k1,k2 <= j 其中 k1 % A.length = k2 % A.length）乘积最大子数组给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。乘积为正数的最长子数组长度给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。请你返回乘积为正数的最长子数组长度。最大子数组和思路针对连续数组的最大和而言，直观的想就是累加求和取最值的过程，如果数组所有的元素均是自然数，那么就是整个数组元素累加求和，如果元素中含有负数那么当前元素的最大和依赖于前一个元素的最大和，如果前一个元素的最大和是正数则累加，如果是负数，那么则比较前一个元素最大和和当前元素的大小代码func maxSubArray(nums []int) int { sum:=nums[0] for i:=1;i<len(nums);i++{ nums[i]=max(nums[i-1],0)+nums[i] sum=max(sum, nums[i]) } return sum}func max(a,b int)int{ if a>b{ return a } return b}环形子数组的最大和思路环形数组计算最大和 第一种情况来看 当整个数组都是自然数那么最大和就是整个元素的总和。如果含有负数，当负数在两边。那么就相当于绕圈了把整个环形数组展开可以理解为抛去负数的剩下数的最大和直接服用最大子数组和即可。如果含有负数，当负数在中间。就等于所有元素的和减去最小元素和就是整个数组的最大和如图所示的数组要计算最大和代码func maxSubarraySumCircular(nums []int) int { maxSum,arrSum,minSum,tMax,tMin:=nums[0],0,nums[0],0,0 for i:=0;i<len(nums);i++{arrSum+=nums[i] tMax,tMin=max(tMax+nums[i],nums[i]),min(tMin+nums[i],nums[i]) maxSum=max(maxSum,tMax)minSum=min(minSum, tMin) } if maxSum<0{return maxSum } return max(maxSum,arrSum-minSum)}func max(a,b int)int{ if a>b{ return a } return b}func min(a,b int)int{ if a>b{ return b } return a}乘积最大子数组思路如图所示的数组要求这数组中子数组乘积最大的是多少，要想知道到当前元素的最大乘积就等于前一个元素的最大乘积值和当前元素的乘积和前一个元素的最小乘积和当前元素的乘积和当前元素的值 反过来要想知道到当前元素的最小乘积就等于 前一个元素的最小乘积值和当前元素的乘积和前一个元素的最大乘积和当前元素的乘积和当前元素的值 所以得出状态转移方程代码func maxProduct(nums []int) int { max,min,ans:=nums[0],nums[0],nums[0] for i:=1;i<len(nums);i++{ mx:=max mn:=min max=Mathmax(mx*nums[i],Mathmax(nums[i],mn*nums[i])) min=Mathmin(mn*nums[i],Mathmin(nums[i],mx*nums[i])) ans=Mathmax(ans,max) } return ans}func Mathmax(a,b int)int{ if a>b { return a } return b}func Mathmin(a,b int)int{ if a<b { return a } return b}乘积为正数的最长子数组长度思路还是使用老图，懒得画图了，分析上述数组，乘积为正数的长度。如果当前元素是正数，正数长度加一，如果当前值是负数，正负长度累加交换 如果当前元素是零，那么正负长度归零，在每次遍历的时候比较最大的正数长度就是到当前元素乘积为正数的最大长度的值。定义两个遍历P,N来用于统计正数乘积和负数乘积的长度，V代表当前元素.P(i-1),N(i-1)分别代表前一个正数乘积和负数乘积的长度。代码func getMaxLen(nums []int) int { p,n:=0,0 if nums[0]>0{ p=1 } if nums[0]<0{ n=1 } ans:=p for i:=1;i<len(nums);i++{ if nums[i]>0{ p++ if n>0{ n++ }else{ n=0 } }else if nums[i]<0{ a,b:=p+1,0 if n>0{ b=n+1 } p,n=b,a }else{ p,n=0,0 } ans=MathMax(ans,p) } return ans }func MathMax(a,b int)int{ if a>b { return a } return b}

下降路径问题931. 下降路径最小和给你一个n x n的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]输出：13解释：下面是两条和最小的下降路径，用加粗+斜体标注：[[2,1,3], [[2,1,3], [6,5,4], [6,5,4], [7,8,9]] [7,8,9]]解決这类问题我们可以自上而下的来解决问题：找当前层的最小值，那么就要把当前层的最小值的上方来按照对应的规则来递推前一层的最小值,如此类推 循环到最后一层,func minFallingPathSum(matrix [][]int) int { ans:=math.MaxInt32 for i:=1;i<len(matrix);i++{ for j:=0;j<len(matrix);j++{ if j==0{ matrix[i][j]+=min(matrix[i-1][0],matrix[i-1][j+1]) }else if j==len(matrix)-1{ matrix[i][j]+=min(matrix[i-1][j-1],matrix[i-1][j]) }else{ matrix[i][j]+=min(matrix[i-1][j+1],min(matrix[i-1][j-1],matrix[i-1][j])) } } } for i:=0;i<len(matrix);i++{ ans=min(ans,matrix[len(matrix)-1][i]) } return ans}func min(a,b int)int{ if a>b{ return b } return a}120. 三角形最小路径和给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标+ 1 的两个结点。也就是说，如果正位于当前行的下标 i，那么下一步可以移动到下一行的下标 i 或 i + 1 。输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出：11解释：如下面简图所示： 2 3 4 6 5 74 1 8 3自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。三角形下降也是同样的道理，只不过规则的选取变成了当前行 ↓ ↘ 那么我们从当前层往上找，难道就是取得 ↑ ↖func minimumTotal(triangle [][]int) int { if len(triangle)==0{ return 0 } if len(triangle)==1{ return triangle[0][0] } ans:=math.MaxInt32 for i:=1;i<len(triangle);i++{ for j:=0;j<=i;j++{ if j==0 { triangle[i][j]+=triangle[i-1][j] }else if j==i{ triangle[i][j]+=triangle[i-1][j-1] }else{ triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]) } } } for i:=0;i<len(triangle);i++{ ans=min(ans,triangle[len(triangle)-1][i]) } return ans}func min(a,b int)int{ if a>b{ return b } return a }

滑动窗口：用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最大/小值就是要求的结果。不断增加j使滑动窗口增大，直到窗口包含了T的所有元素

优先队列队列的数据结构我们都熟悉，先进先出,后进后出的数据结构，当我们提交若干个下载任务给某网盘，进行批量下载，所有的任务会被加入一个下载队列。在批量下载过程中下载器需要优秀下载耗时较短的任务，这样会加快整个下载任务的进度。显然这样的场景在现代计算机当中很常见，这种特殊的队列就是优先队列。

title: 数据结构和算法之树author: Moodtags:数据结构和算法categories:树date: 2020-03-20 22:18:00树二叉树二叉搜索树平衡二叉搜索树(AVL)AVL简介AVL实现平衡法则推演AVL生成AVL删除AVLAVL平衡代码实现代码实现public cla

八大排序算法

二分查找