欢迎关注个人公众号：爱喝可可牛奶 LeetCode39.组合总和40.组合总和II131.分割回文串 LeetCode39.组合总和 分析 回溯可看成对二叉树节点进行组合枚举，分为横向和纵向 每次往sum添加新元素时，必须明确从can哪个位置开始，定义变量pos 返回条件sumtarget或sum>target;横向结束条件没有新元素可以添加了即pos<can.length; bt(can,sum,tar,pos){ if(sumtar)addreturn; if(sum>tar)posreturn; for(inti=pos;i<can.len;i){ sum+=c...

欢迎关注个人公众号：爱喝可可牛奶 LeetCode算法训练93.复原IP地址78.子集90.子集II LeetCode93.复原IP地址 分析 字符串全部由数字组成，ipv4每一段数字不能有前导0，且大小∈[0,255] 等价于将字符串进行分割，并判断分割后的数是否满足条件 插入一个点进行切割、判断是否满足条件、再插入、再判断，直到插入3个点，判断剩下的一段是否满足条件 代码 classSolution{ List<String>res=newArrayList<>(); publicList<String>restoreIpAddresses(Strin...

欢迎关注个人公众号：爱喝可可牛奶 LeetCode算法训练-回溯491.递增子序列46.全排列47.全排列II LeetCode491.递增子序列 分析 找出并返回所有数组中不同的递增子序列 绝对不能先升序绝对不能先升序绝对不能先升序这样会改变原有数组的结构 子序列中元素在数组中不一定相邻 只要叶子节点，也就是path，一满足条件，直接加入res 注意去重used[]数组只针对当前节点的后序节点要在回溯函数中定义画回溯树一看便知 代码 classSolution{ privateLinkedList<Integer>path=newLinkedList<>(); p...

欢迎关注个人公众号：爱喝可可牛奶 LeetCode算法训练-回溯总结 适用问题 组合问题：N个数里面按一定规则找出k个数的集合 排列问题：N个数按一定规则全排列，有几种排列方式 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个N个数的集合里有多少符合条件的子集 棋盘问题：N皇后，解数独等等 通用模板 result存放结果集 path某个符合条件的结果 voidbacktracking(参数){ if(终止条件){ result.add(path); return; } for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){ 处理节点; backtracking(...

欢迎关注个人公众号：爱喝可可牛奶 LeetCode算法训练-贪心算法455.分发饼干376.摆动序列53.最大子序和 前置知识 贪心算法核心是找局部最优解，通过局部最优推导出全局最优 LeetCode455.分发饼干 分析 要求：把饼干分给孩子，并返回分了多少个孩子 局部最优：小饼干分给胃口小的 代码 classSolution{ publicintfindContentChildren(int[]g,int[]s){ Arrays.sort(g); Arrays.sort(s); inti=0,j=0; intnum=0; while(i<g.length&&j<...

欢迎关注个人公众号：爱喝可可牛奶 LeetCode算法训练-动态规划 理论知识 动态规划当前状态是由前一个状态推导出来的，而贪心没有状态的转移 动态规划需要借助dp数组，可能是一维也可能是二维的 首先要明确dp数组是用来干什么的，下标对应什么 状态如何转移？也就是理清递推公式 dp数组如何初始化 如何遍历 举个栗子模拟推导一遍 LeetCode509.斐波那契数 分析 F(n)=F(n1)+F(n2)，其中n>1 代码 classSolution{ publicintfib(intn){ if(n<=1)returnn; int[]dp=newint[n+1]; dp[0]=0...