如何在网站源码做授权,西双版纳网站制作公司,提供企业网站建设公司,重庆招标建设信息网站LeetCode100题总结 前言LeetCode100题总结题型梳理双指针11. 盛最多水的容器234.回文链表75.颜色分类206.反转链表142.环形链表215.三数之和 滑动窗口3. 无重复字符的最长子串209. 长度最小的子数组438. 找到字符串中所有字母异位词 广搜102. 二叉树的层序遍历200. 岛屿数量617… LeetCode100题总结 前言LeetCode100题总结题型梳理双指针11. 盛最多水的容器234.回文链表75.颜色分类206.反转链表142.环形链表215.三数之和 滑动窗口3. 无重复字符的最长子串209. 长度最小的子数组438. 找到字符串中所有字母异位词 广搜102. 二叉树的层序遍历200. 岛屿数量617.合并二叉树 深搜104.二叉树的最大深度543.二叉树的直径111. 二叉树的最小深度110.平衡二叉树226.翻转二叉树 回溯39.组合总和77.组合46.全排列79.单词搜索22.括号生成17.电话号码的字母组合 排序二分704.二分查找35.搜索插入位置 动态规划基础题目509.斐波那契数70.爬楼梯746.使用最小花费爬楼梯62.不同路径63.不同路径2343.整数拆分96.不同的二叉搜索树343.整数拆分96.不同的二叉搜索树 前言
这是陈旧已久的草稿2022-10-20 00:07:01发布一下
这个是我的同学自己写的算法记录我看了一看。 当时准备寒假实习后面也没有找到。
现在2024-5-12 22:06:18发布到[LeetCode]专栏中。
LeetCode100题总结
题型梳理 双指针
思想应对一组数据的走向有两种变化方案向左或向右
通过不断改变左右边界来去最优解。
类型题目解决方案 找到适合使用双指针的遍历点 找到适合题目的最优解方案的底层逻辑。
难点在于如何找到合适的底层逻辑很多结果数据的处理很棘手。
11. 盛最多水的容器
这个题的底层逻辑判断左移还是右移使得容量变大从底层逻辑来看纯纯数学问题。
我的想法用假设发生的结果来决定接下来真实发生什么
题目想法用真实发生的结果来决定接下路真实发生什么
我的逻辑用假设发生的结果来决定接下来真实发生什么题解的逻辑用真实发生的结果来决定接下路真实发生什么我的问题切入点先判断左移、右移、同时移的影响来决定接下来如何处理左右指针题解的问题切入点根据已知的两个指针所指结果只改变两指针中数组值小的。缺点我考虑的情况要有6种而且假设移动的写法得保证数组不能越界。很难处理没写出来。优点题解设计很巧妙也比较难想这个问题的思考角度需要较深的数学水平。 暴力解法On^2 /*
思路暴力解法
两层遍历依次算出对应的面具area。比较选出最大的返回*/class Solution {public int maxArea(int[] height) {int fro,last,area;fro0;area0;lastheight.length;for (int i0;iheight.length;i){for (int ji1;jheight.length;j){areaMath.max(area,Math.min(height[i],height[j])*(j-i));}}return area;}
}双指针解法我的 /*影响水体积的因素有 所选数组的长度 所选数组所能决定的高度数组的长度是第一时间好确定的改变长度的方式有两种左边界1 or 右边界—1因为存在这两种变化所以采用双指针的思想。不断去找适合本题的指针移动逻辑 采用对的方法找到每个题的逻辑ac*/public int maxArea(int[] height) {int nheight.length;int left0;int rightn-1;//用dp0dp2/dp1来帮助实现比较逻辑int dp0,dp1,dp2;dp0Math.min(height[left],height[right]);int areadp0*(right-left);if(n2)return area;while(left!right){//6种情况//abc//area(height,left1,right),area(height,left,right-1),area(height,left1,right-1)if (left1nright-10area(height,left1,right)max3(area(height,left1,right),area(height,left,right-1),area(height,left1,right-1))){left;areaMath.max(area,area(height,left1,right));}else if (left1nright-10area(height,left,right-1)max3(area(height,left1,right),area(height,left,right-1),area(height,left1,right-1))){right--;areaMath.max(area,area(height,left,right-1));}else if (left1nright-10area(height,left1,right-1)max3(area(height,left1,right),area(height,left,right-1),area(height,left1,right-1))){left;right--;areaMath.max(area,area(height,left1,right-1));}elseleft;}return area;}private int area(int []h,int l,int r){return (r-l)*(Math.min(h[l],h[r]));}//三数最大值private int max3(int a,int b,int c){if (ab){if (ca)return c;elsereturn a;}return b;}public static void main(String[] args) {int a[]{2,3,4,5,18,17,6};int bnew Solution().maxArea(a);System.out.println(b);}
}双指针On /*
思路
如何看待这个问题
可以将我们要计算的数字公式转化为直观的物理意义-面积控制这个几何图形面积的因素有两个底、高
我们可以用两个指针来底因素左指针指向最左右指针指向最右。
通过控制指针的移动来直接改变底间接改变高那该如何控制这个指针走向。
分析可得
假设我们的左指针移动了那么我们的底肯定小了如果这时候高返回小了那就没有移动的必要了这样只让area越来越小。
所以可以确定的一点是指针移动势必会让底变小想尽快找到答案就必须让高适当增高
那我们该如何控制高的问题呢
本题而言高这个因素是由最小的hight决定的那明确了这个点好办了
我们通过简单的判断高的问题来控制左右指针的走向指针发生移动之后就可以通过计算面积取对应的最大值来进行下一步的判断了
当整个循环走完的时候就我们的问题找出答案的时候。*/
public class Demo01 {public int maxArea(int[] height) {int f,l,area;f0;area0;lheight.length-1;while (fl){//Math.min(height[f],height[l])表示几何图形的高areaMath.max(area,Math.min(height[f],height[l])*(l-f));if(height[f]height[l]){f;}else l--;}
// for (int i0;iheight.length;i)
// {
// for (int ji1;jheight.length;j)
// {
// areaMath.max(area,Math.min(height[i],height[j])
// *(j-i));
// }
// }return area;}public static void main(String[] args) {int []a{1,8,6,2,5,4,8,3,7};Demo01 demo01 new Demo01();demo01.maxArea(a);System.out.println(demo01.maxArea(a));}}总结 感觉这个移动有点博弈论的味了每次都移动自己最差的一边虽然可能变得更差但是总比不动或者减小强动最差的部分可能找到更好的结果但是动另一边总会更差或者不变兄弟们这不是题这是人生逃离舒适圈234.回文链表 双指针切入点数组的双指针遍历 本题的应用逻辑将链表转化成双指针变成了常见的双指针遍历问题。 双指针 public boolean isPalindrome(ListNode head) {ListInteger listnew ArrayList();while (head!null){list.add(head.val);headhead.next;}int nlist.size();int front0;int lastn-1;while (frontlast){if (list.get(front)!list.get(last))return false;front;last--;}return true;}75.颜色分类 也叫荷兰国旗问题 -Dijkstra提出的 冒泡排序 时间复杂度On^2 //插入排序public void sortColors(int[] nums) {int temp0;for (int i0;inums.length;i){for (int j0;jnums.length-1;j){if (nums[j]nums[j1]){tempnums[j1];nums[j1]nums[j];nums[j]temp;}}}}两次单指针 时间复杂度为O(n)在遍历外部加一个指针遍历中进行交换如果交换指针递增。 逻辑先让0放在数组的前面再让1放在0的后面。 //两次单指针public void sortColors(int[] nums){int ptr0;int temp0;for (int i0;inums.length;i){if (nums[i]0){tempnums[i];nums[i]nums[ptr];nums[ptr]temp;ptr;}}for (int i0;inums.length;i){if (nums[i]1){tempnums[i];nums[i]nums[ptr];nums[ptr]temp;ptr;}}}双指针 需要开辟一个新的数组空间复杂度为On 本质上还是是将0放在前面2放在后面 public static void sortColors(int[] nums){int b[]new int[nums.length];for (int i 0; i nums.length; i) {b[i]1;}int front0;int backnums.length-1;for (int i0;inums.length;i){if (nums[i]0) {b[front] 0;front;}if (nums[i]2) {b[back] 2;back--;}}for (int i0;inums.length;i){nums[i]b[i];}}206.反转链表 栈 利用栈先进后出的特性这处理前后反序的问题。 class Solution {public ListNode reverseList(ListNode head) {StackListNode stacknew StackListNode();ListNode tophead,tail,pre;while(top!null){stack.push(top);toptop.next;}if (stack.isEmpty())return null;tailstack.pop();pretail;while (true){if (!stack.empty()) {pre.next stack.pop();pre pre.next;}else break;}pre.nextnull;return tail;}
} 迭代 创建一个前驱结点pre
迭代过程记录一个后继结点n
让当前结点指向前驱结点让当前结点变成后继结点。public static ListNode reverseList1(ListNode head) {if(headnull)return null;ListNode prenull;ListNode curhead;while(cur!null){ListNode ncur.next;cur.nextpre;precur;if (nnull)return cur;curn;}return cur;}递归 和迭代的思想一样能迭代的一般都能递归写出来练练手。 public static ListNode reverseList(ListNode head){ListNode prenull;ListNode curhead;return method(pre,cur);}private static ListNode method(ListNode pre,ListNode cur){if (cur.nextnull) {cur.nextpre;return cur;}ListNode nextnodecur.next;cur.nextpre;return method(pre,nextnode);}142.环形链表2 用栈写 时间复杂度O(n^2) 空间复杂度O(n) public ListNode detectCycle(ListNode head) {StackListNode stacknew Stack();while (head!null){if (stack.contains(head))return head;elsestack.add(head);headhead.next;}return null;}双指针方法 了解一下思路得了这个问题是采用了快慢指针的模型通过两次相遇来确定进入环的入口。开扩一下思路就好。 哈希时间优话空间复杂 这个比较实在栈的时间复杂度是On^2可以用哈希优化成O(n) public ListNode detectCycle(ListNode head) {SetListNode setnew HashSet();while (head!null){if (set.contains(head))return head;elseset.add(head);headhead.next;}return null;}15.三数之和 这个题目跟两数之和有点像介于三数和为0 遍历第一个数只需要找到接下来范围内两数和为-绝对值第一个数即可。 双指针 对于两数之和部分用双指针能使时间复杂度从O(n^3降到O(n方) ListListInteger resnew ArrayList();public ListListInteger threeSum(int[] nums) {if (nums.length3)return null;Arrays.sort(nums);if (nums[0]0)return res;for (int i0;inums.length-2;i){int begini1;int endnums.length-1;while (beginend){if (nums[begin]nums[end]Math.abs(nums[i]))begin;else if (nums[begin]nums[end]Math.abs(nums[i]))end--;else if (nums[begin]nums[end]Math.abs(nums[i])){ListInteger listnew ArrayList();list.add(nums[i]);list.add(nums[begin]);list.add(nums[end]);Collections.sort(list);if (!res.contains(list))res.add(list);begin;end--;}}}return res;}解法分析
难度在于如何去除重复解。
这种处理是采用排序数组再检验是否res集中是否存在这样的数组。
大大影响实际复杂度。数组排序O(N logN),遍历数组O(n),双指针遍历O(n)优化方向
既然找到了慢的原因是处理重复结果导致的那就从这个方向开始优化
我是从数组生成的时候进行筛选的如果从源头筛选就能优化很多时间。双指针优化版 2030ms到18ms的巨大飞跃 从重复的原因角度出发处理了两个点即第一次遍历时重复情况第二次双指针出现重复。大大减少时间负担 优化部分 //第一次遍历到大于0的就不用继续走了.if(nums[i]0)return res;
//如果有连着两个 直接用一个if(i 0 nums[i] nums[i-1])//优化了如果连着挨着的一样那就跳过。while (beginendnums[begin1]nums[begin])begin;while (beginendnums[end-1]nums[end])end--;优化完整版 ListListInteger resnew ArrayList();public ListListInteger threeSum(int[] nums) {if (nums.length3)return null;Arrays.sort(nums);if (nums[0]0)return res;for (int i0;inums.length;i){if(nums[i]0)return res; //如果有连着两个0直接用一个if(i 0 nums[i] nums[i-1])continue;int begini1;int endnums.length-1;while (beginend){if (nums[begin]nums[end]Math.abs(nums[i]))begin;else if (nums[begin]nums[end]Math.abs(nums[i]))end--;else if (nums[begin]nums[end]Math.abs(nums[i])){ListInteger listnew ArrayList();list.add(nums[i]);list.add(nums[begin]);list.add(nums[end]);res.add(list);//优化了如果连着挨着的一样那就跳过。while (beginendnums[begin1]nums[begin])begin;while (beginendnums[end-1]nums[end])end--;begin;end--;}}}return res;}滑动窗口 其实就是一个队列,比如例题中的 abcabcbb进入这个队列窗口为 abc 满足题目要求当再进入 a队列变成了 abca这时候不满足要求。所以我们要移动这个队列 3. 无重复字符的最长子串 暴力解法 时间复杂度On方 空间复杂度On 超时 public int lengthOfLongestSubstring(String s) {int count0;for (int i0; is.length();){SetCharacter setnew HashSet();for (int j0;js.length();j)if (!set.contains(s.charAt(j)))set.add(s.charAt(j));else {countcountset.size()? count:set.size();break;}}return count;}双指针 减少了从头遍历的情况时间上优化了不少但还有优化的空间这里面的left指针没怎么用上。 public int lengthOfLongestSubstring(String s) {int left,right;left0;right0;int count0;ListCharacter listnew ArrayList();while (leftrightrights.length()left0){if (!list.contains(s.charAt(right))) {while (true) {if (rights.length()!list.contains(s.charAt(right))) {list.add(s.charAt(right));right;//right越界问题}else {countMath.max(count,list.size());break;}}}else {while (list.contains(s.charAt(right))){list.remove(0);}left;}}return count;}双指针优化版 while (list.contains(s.charAt(right))){ list.remove(0); } 优化开始的地方这个采用删除想要数组的索引之前的元素然后统计数组个数的策略来返回最大值。 改为用hashmap来存储索引和字符用字符来确定索引从而确定左指针的值 public int lengthOfLongestSubstring(String s) {int left,right;left0;right0;int count0;MapCharacter,Integer mapnew HashMap();ListCharacter listnew ArrayList();for (int i 0; i s.length() ; i) {if (!map.containsKey(s.charAt(i))) {map.put(s.charAt(i), i);//right越界问题}else{leftMath.max(map.get(s.charAt(i))1,left);map.put(s.charAt(i), i);}countMath.max(i-left1,count);}return count;}209. 长度最小的子数组 做懂了第三题再做类似的题有种酣畅淋漓的感觉。贼爽。 滑动窗口 public int minSubArrayLen(int target, int[] nums) {int left0;int lenInteger.MAX_VALUE;int sum0;for (int i0;inums.length;i){sumnums[i];while (sumtarget){lenMath.min(len,i-left1);sum-nums[left];leftleft1;}}lenlenInteger.MAX_VALUE? 0:len;return len;}438. 找到字符串中所有字母异位词 标准长度的滑动窗口比较简单难点在于处理是否是异位词这个点如果能想到分割子串、排序、再比较的方式就更简单了 就是排序比较的过程加长了时间复杂度。 滑动窗口 public ListInteger findAnagrams(String s, String p) {ListInteger list new ArrayList();if (s.length()p.length())return list;if (p.length()0)return list;int np.length();char[] spp.toCharArray();Arrays.sort(sp);for (int i0;is.length()-p.length();i){char[] sss.substring(i,in).toCharArray();Arrays.sort(ss);if (xiangdeng(ss,sp)) list.add(i);}return list;}public boolean xiangdeng(char[] a,char[] b){boolean ftrue;for (int i0;ib.length;i){if (a[i]!b[i])return false;} return f;}广搜 按照数据结构中广搜的定义bfs也是遍历的一种思想核心策略采用当前节点能走的全都走。 102. 二叉树的层序遍历 bfs 这里有一行错误代码i queue.size() 。 错误原因循环体内容要操作queue的size动态变化的size不适合做循环判断条件 /*
102. 二叉树的层序遍历思路
这个题跟基础的算法层序遍历很像基础算法可以用层序遍历但区别于层序遍历我们
缺少对返回值ListListInteger这个条件的控制直接不分组的sout无法满足这个题的需求。针对这个需求有以下实现思路
1.通过进队列的时候我们放入list集合可以用类似于之前的后序遍历采用双栈我想用一个队列
加一个栈队列来控制层序遍历栈来控制加入list但是每写出来。
2.可以通过栈当前数量来加入我们肯定要加入集合中但是加入几个是个问题获取队列的长度来
代表我们加入集合的个数。每次加完一个集合都代表栈对应着更新一次。同步对应。很巧妙的设计。*/
public ListListInteger levelOrder(TreeNode root) {ListListInteger resnew ArrayList();if (rootnull)return res;QueueTreeNode queuenew LinkedList();queue.add(root);while (!queue.isEmpty()){ListInteger listnew ArrayList();int countqueue.size();for (int i 0; icount ; i) {TreeNode nodequeue.poll();list.add(node.val);if (node.left!null)queue.add(node.left);if (node.right!null)queue.add(node.right);}res.add(list);}return res;}200. 岛屿数量 bfs和递归结合分为两组逻辑进入逻辑和递归逻辑 递归逻辑这片岛为1的全变成2 进入逻辑遍历到当前为1的情况进入递归让这片都为2 计数 bfs递归 /*
200. 岛屿数量
输入grid [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]
]
输出1
思路遍历岛这个二维数组如果当前数为1则进入感染函数并将岛个数1
感染函数其实就是一个递归标注的过程它会将所有相连的1都标注成2。
为什么要标注这样就避免了遍历过程中的重复计数的情况一个岛所有的1都变成了2后
遍历的时候就不会重复遍历了。*/public static int numIslands(char[][] grid) {int rowgrid.length;int columngrid[0].length;int sum0;for (int i0;irow;i){for (int j0;jcolumn;j){//进入递归的逻辑if (grid[i][j]1){digui(grid,i,j);sum;}}}return sum;}public static void digui(char[][] grid,int i,int j){//终止条件if (i0||igrid.length||j0||jgrid[0].length){return;}if(grid[i][j]!1)return;if (grid[i][j]1)grid[i][j]2;digui(grid,i-1,j);digui(grid,i1,j);digui(grid,i,j-1);digui(grid,i,j1);}617.合并二叉树 递归实现 递归创造新的节点确定好每一步的返回值即可。 出现了好多次空参报错都是因为返回点没有找好。 public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {TreeNode ressum(root1,root2);return res;}public TreeNode sum(TreeNode root1, TreeNode root2){TreeNode resnull;//终止条件if (root1nullroot2null)return null;if (root1nullroot2!null){res root2;}if (root2nullroot1!null){resroot1;}if (root1!nullroot2!null) {res new TreeNode(root1.valroot2.val);res.leftsum(root1.left,root2.left);res.rightsum(root1.right,root2.right);}return res;}迭代bfs 想把每一步的操作结果都体现在root1树上迭代需要我们的数据结构-队列来支持跟层序遍历的思路一样对于每一步进队列和出队列的情况加上我们的逻辑限制就能解决本题。 哪体现了bfs思想呢 本身在二叉树的遍历思想上层序遍历本身也是一种能走就全走的思想只不过这个能走是横向的在同一层的都进入队列。 某种意义上来讲二叉树的遍历都可以归类为bfs或dfs前中后三序遍历可看做是dfs层序遍历可看成bfs public TreeNode mergeTrees(TreeNode root1, TreeNode root2){//挺美观的条件判断处理学习一手if (root1null||root2null)return root1null ?root2:root1;QueueTreeNode queuenew LinkedList();queue.add(root1);queue.add(root2);while (queue.size()0){TreeNode r1queue.poll();TreeNode r2queue.poll();r1.valr2.val;if (r1.left!nullr2.left!null){queue.add(r1.left);queue.add(r2.left);}//隐藏了一步逻辑就是当右子树为空r1还等于原值不用写出来if (r1.leftnull)r1.leftr2.left;if (r1.right!nullr2.right!null){queue.add(r1.right);queue.add(r2.right);}if (r1.rightnull)r1.rightr2.right;}return root1;}深搜
104.二叉树的最大深度 dfs递归 思想很简单只要能走就一走到底不能走的情况用我们的递归终止条件控制返回深度即可。 public int maxDepth(TreeNode root) {int ansdepth(root);return ans;}public int depth(TreeNode node){if (nodenull)return 0;return Math.max(depth(node.left),depth(node.right))1;}bfs递归 /*
104. 二叉树的最大深度
用了广度优选感觉这个题用广度优先不如深度优先好深度优先能减少一些时间复杂度*/
public class Solution {public int maxDepth(TreeNode root) {QueueTreeNode queuenew LinkedList();ListListInteger anew ArrayListListInteger();if (rootnull)return 0;queue.add(root);TreeNode noderoot;int max0;while (!queue.isEmpty()) {ListInteger bnew ArrayList();int countqueue.size();max;for (int i0;icount;i){node queue.poll();b.add(node.val);if (node.left ! null)queue.add(node.left);if (node.right ! null)queue.add(node.right);}a.add(b);}return max;}
}543.二叉树的直径 这题第二次做又有了一个新理解的点就是用一个全局变量dfs的过程去记录我想要的结果避免了dfs求深度之后再遍历二叉树拿值的情况。 特殊情况 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cotXebxO-1666195548221)(C:\Users\Onlylove\AppData\Roaming\Typora\typora-user-images\image-20220726220506903.png)] 错误写法 以为只需要根节点的深度-1和左右子树深度和比较取max就可以 其实最大值不一定出现了 public int diameterOfBinaryTree(TreeNode root) {int cdepth(root.right)depth(root.left);int bdepth(root)-1;return Math.max(b,c);}public int depth(TreeNode node){if (nodenull)return 0;return Math.max(depth(node.left),depth(node.right))1;}dfs /*
543.二叉树的直径
深度优先搜索
1.递归函数的三个关键点退出条件、递归内容、相似条件。
2.树的定义深度
3.树的直径定义树中任意两节点最短路径的最大值
4.两节点间路径的定义他们之间边的数目两叶子节点之间路径祖先节点左右儿子的深度和*/int ans;public int diameterOfBinaryTree(TreeNode root) {ans1;depth(root);return ans-1;}public int depth(TreeNode node){if (nodenull)return 0;int ldepth(node.left);int rdepth(node.right);ansMath.max(ans,lr1);//记录每一步能走的最大值避免出现最大值不在根节点子树的情况。return Math.max(l,r)1;}111. 二叉树的最小深度 dfs递归 时间On空间On /*
111. 二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
1.写出结束条件
2.不要把树复杂化就当做树是三个节点根节点左子节点右子节点
3.只考虑当前做什么不用考虑下次应该做什么
4.每次调用应该返回什么*/
public int minDepth(TreeNode root) {int ans0;if (rootnull)return ans;ansdepth(root);return ans;}public int depth(TreeNode node){if (node.leftnullnode.rightnull)return 1;else if (node.leftnullnode.right!null)return depth(node.right)1;else if (node.rightnullnode.left!null)return depth(node.left)1;elsereturn Math.min(depth(node.left),depth(node.right))1;}110.平衡二叉树 dfs递归 这是一个双重遍历问题用深搜求树的深度再用遍历帮助我们求一下是否满足条件。 public boolean isBalanced(TreeNode root) {if (rootnull)return true;if (Math.abs(depth(root.right)-depth(root.left))1)return false;return isBalanced(root.right)isBalanced(root.left);}//求深度public int depth(TreeNode node){if (nodenull)return 0;return Math.max(depth(node.left),depth(node.right))1;}dfs迭代 时间On 空间On 这段代码是第一次写的求深度这步写的比较蠢 整体思路还是层序遍历dfs求深度 /*
110. 平衡二叉树
高度叶子节点到根节点的最长距离
不可能从叶子到根反向寻找只能是从根向下寻找
用递归能少写个栈
他说每个结点那还得再遍历一下二叉树
递归部分
1.结束条件当前节点为叶子节点
2.递归内容: 计数且进入下一次比较*/
public class Solution2 {int h0;boolean ftrue;public boolean isBalanced(TreeNode root) {QueueTreeNode queuenew LinkedList();if (rootnull)return true;TreeNode curroot;queue.add(cur);while (!queue.isEmpty()) {curqueue.poll();if (cur.left!null)queue.add(cur.left);if (cur.right!null)queue.add(cur.right);fok(cur);if (ffalse) {break;}}return f;}//求高度的函数public int high(TreeNode node){if (nodenull)return 0;if (node.leftnullnode.rightnull)h1;if (node.left!nullnode.rightnull)hhigh(node.left)1;if (node.right!nullnode.leftnull)hhigh(node.right)1;if (node.right!nullnode.left!null)hMath.max(high(node.left),high(node.right))1;return h;}public boolean ok(TreeNode node){if (Math.abs(high(node.left)-high(node.right))1)return false;elsereturn true;}
}226.翻转二叉树 dfs递归 时间On 空间On 在我能走的基础上一直深搜交换左右两边的值操作写好递归终止条件即可。 public TreeNode invertTree(TreeNode root) {change(root);return root;}private void change(TreeNode node){TreeNode curnode;if (nodenull)return;else if (node.leftnullnode.right!null){node.leftnode.right;node.rightnull;}else if (node.rightnullnode.left!null){node.rightnode.left;node.leftnull;}else {curnode.right;node.rightnode.left;node.leftcur;}change(node.left);change(node.right);}回溯 回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。 遍历阶段伪代码 for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果
}递归部分伪代码 void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}可能遇到的结果处理 res.add(new ArrayList(list));39.组合总和 回溯树 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lgTXnaDx-1666195548223)(F:\截图\IMG_20220729_222638.jpg)] 回溯 /*
39. 组合总和
核心三步骤回溯22 23凑list.add(candidates[i]);back(candidates,list,target-candidates[i],i);list.remove(list.size()-1);
剪枝if (candidates[start]target)//上来就大于目标值直接不用考虑return;if(i 0 candidates[i] candidates[i-1]) continue; 连续元素重复了直接跳过一个//[2,2,3,5]*/
public class Solution3 {ListListInteger resnew ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {ListInteger listnew ArrayList();Arrays.sort(candidates);back(candidates,list,target,0);return res;}public void back(int[] candidates, ListInteger list,int target,int start){if (target0){res.add(new ArrayList(list));return;}for (int istart;icandidates.length;i){if (candidates[start]target)return;//[2] [2,2] [2,2,3] [7]list.add(candidates[i]);/*tar:5,start:1[2,2] back3 [2,3] back2*/back(candidates,list,target-candidates[i],i);//[]list.remove(list.size()-1);}}
}77.组合 回溯 我的思路是先将n转化为平时操作的数组在for遍历上扩宽集合在backtracking上深入集合 判断条件 长度 剪枝角度 要放的必须比之前的得大小的话一定已经放过了为了避免重复 时间173ms ListListInteger resnew ArrayList();public ListListInteger combine(int n, int k) {int [] anew int[n];for (int i0;in;i){a[i]i1;}ListInteger listnew ArrayList();backtracking(a,list,k);return res;}void backtracking(int []nums,ListInteger list,int k){//递归终止条件if (list.size()k){{ res.add(new ArrayList(list));return;}}for (int i0;inums.length;i){//剪枝操作if (list.size()!0nums[i]list.get(list.size()-1))continue;//深度和宽度的逻辑实现list.add(nums[i]);backtracking(nums,list,k);list.remove(list.size()-1);}}优化版 既然上面都已经想到了剪枝操作那可以从产生条件上就避免剪枝情况的出现因为我放进入的数组必然是递增的。 时间17ms ListListInteger resnew ArrayList();public ListListInteger combine(int n, int k) {int [] anew int[n];for (int i0;in;i){a[i]i1;}ListInteger listnew ArrayList();backtracking(a,list,k,0);return res;}void backtracking(int []nums,ListInteger list,int k,int start){//递归终止条件if (list.size()k){{ res.add(new ArrayList(list));return;}}for (int istart;inums.length;i){//剪枝操作// if (list.size()!0nums[i]list.get(list.size()-1))// continue;//深度和宽度的逻辑实现list.add(nums[i]);backtracking(nums,list,k,i1);list.remove(list.size()-1);}}优化版plus 仔细想想这题还有能优化的地方从遍历的次数来减少是一个很好的出发点。 如果从1开始k3那我们只需要遍历到4就OK了没有必要再去遍历5、6、7…这样的数据了 时间1ms inums.length-(k-list.size())完整版 ListListInteger resnew ArrayList();public ListListInteger combine(int n, int k) {int [] anew int[n];for (int i0;in;i){a[i]i1;}ListInteger listnew ArrayList();backtracking(a,list,k,0);return res;}void backtracking(int []nums,ListInteger list,int k,int start){//递归终止条件if (list.size()k){{ res.add(new ArrayList(list));return;}}for (int istart;inums.length-(k-list.size());i){//剪枝操作// if (list.size()!0nums[i]list.get(list.size()-1))// continue;//深度和宽度的逻辑实现list.add(nums[i]);backtracking(nums,list,k,i1);list.remove(list.size()-1);}}46.全排列 回溯 避免重复数据遍历一下是否已经存在nums[i] if(list.contains(nums[i]))continue;ListListInteger resnew ArrayList();public ListListInteger permute(int[] nums) {ListInteger listnew ArrayList();backtracking(nums,list);return res;}void backtracking(int []nums,ListInteger list){if (list.size()nums.length){res.add(new ArrayList(list));return;}for (int i0;inums.length;i){if(list.contains(nums[i]))continue;list.add(nums[i]);backtracking(nums,list);list.remove(list.size()-1);}}79.单词搜索 dfs错误写法 看题目想到的是dfs正常的dfs写完发现面对abcb这样的样例无法通过于是采用了跟LeetCode200题一样的策略将已经遍历过的字符设为一个不相干的来避免下次再遍历到。 改进之后 发现 [[“C”,“A”,“A”],[“A”,“A”,“A”],[“B”,“C”,“D”]] “AAB” 这个测试是致命的也就说用dfs就无法解决这样的情况 public boolean exist(char[][] board, String word) {int mboard.length;int nboard[0].length;for (int i0;im;i){for (int j0;jn;j){if (board[i][j]word.charAt(0)dfs(board,word,0,i,j))return true;}}return false;}boolean dfs(char[][] board, String word,int start,int i,int j){boolean flagfalse;if (i0||iboard.length||j0||jboard[0].length)return true;if (board[i][j]!(word.charAt(start))){return false;}board[i][j]0;flagtrue;return flag(dfs(board,word,start1,i1,j)||dfs(board,word,start1,i-1,j)||dfs(board,word,start1,i,j-1)||dfs(board,word,start1,i,j1));}回溯 用一个二维Boolean数组来表示当前节点走没走没走过之后再撤销一下。 /*** 回溯法相比于DFS多了一步『撤销修改节点状态』*/private boolean find; // 定义为成员变量方便以下两个成员方法使用和修改public boolean exist(char[][] board, String word) {if (board null) return false;int m board.length, n board[0].length;boolean[][] visited new boolean[m][n];find false;for (int i 0; i m; i){for (int j 0; j n; j){backtracking(i, j, board, word, visited, 0); // 从左上角开始遍历棋盘每个格子}}return find;}/*** i,j,board棋盘格及当前元素的坐标* word: 要搜索的目标单词* visited记录当前格子是否已被访问过* pos: 记录目标单词的字符索引只有棋盘格字符和pos指向的字符一致时才* 有机会继续搜索接下来的字符如果pos已经过了目标单词的尾部了那么便说明找到目标单词了*/public void backtracking(int i, int j, char[][] board, String word,boolean[][] visited, int pos){// 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了if(i0 || i board.length || j0 || j board[0].length || visited[i][j] ||find || board[i][j]!word.charAt(pos)) return;if(pos word.length()-1){find true;return;}visited[i][j] true; // 修改当前节点状态backtracking(i1, j, board, word, visited, pos1); // 遍历子节点backtracking(i-1, j, board, word, visited, pos1);backtracking(i, j1, board, word, visited, pos1);backtracking(i, j-1, board, word, visited, pos1);visited[i][j] false; // 撤销修改}
22.括号生成 对检验函数的处理思路 模拟了我们正常人脑检验括号时采用的消去法即一个左括号和一个右括号能抵消统计左右括号的个数保证左括号的个数不小于右括号的个数即可。 字符串数据的处理 不能用Stringbuffer因为stringbuffer的处理是连续的不能返回一个新的集合处理。 回溯 ListString resnew ArrayListString();public ListString generateParenthesis(int n) {
// ListString listnew ArrayList();backtracking(new char[2*n],0,res);return res;}boolean check(char []a){ int count0;for (int i 0; i a.length ; i) {if (a[i]()count;elsecount--;if (count0)return false;}return (count0);}void backtracking(char [] current,int pos,ListString result){if (pos current.length) {if (check(current)) {result.add(new String(current));}} else {current[pos] (;backtracking(current, pos 1, result);current[pos] );backtracking(current, pos 1, result);}}17.电话号码的字母组合 回溯 数据的处理需要花时间想想回溯的部分还是比较基础的 先采用hashmap集合来将我们要用的abc这样的字符放进去 看来stringbuffer也能删除只是我没用对。deleteCharAt才是真正的删除函数 static MapCharacter,String mapnew HashMap();StringBuffer sbnew StringBuffer();ListString resnew ArrayList();public ListString letterCombinations(String digits) {map.put(2,abc);map.put(3,def);map.put(4,ghi);map.put(5,jkl);map.put(6,mno);map.put(7,pqrs);map.put(8,tuv);map.put(9,wxyz);int ndigits.length();backtracking(digits,0);return res;}void backtracking(String digits,int index){if (sb.length()digits.length()){res.add(sb.toString());return;}String valmap.get(digits.charAt(index));for (char ch:val.toCharArray()) {sb.append(ch);backtracking(digits,index1);sb.deleteCharAt(sb.length()-1);}}排序
二分 前提我数组必须是已经升序的 时间复杂度O logn 模板 public int searchInsert(int[] nums, int target) {int left 0, right nums.length - 1; // 注意while(left right) { // 注意int mid (left right) / 2; // 注意if(nums[mid] target) { // 注意// 相关逻辑} else if(nums[mid] target) {left mid 1; // 注意} else {right mid - 1; // 注意}}// 相关返回值return 0;}704.二分查找 解法 public int search(int[] nums, int target) {int left0;int rightnums.length-1;while(leftright){int mid(leftright)/2;if (targetnums[mid])return mid;else if (targetnums[mid]){leftmid1;}else {rightmid-1;}}return -1;}35.搜索插入位置 二分 public int searchInsert(int[] nums, int target) {int left0;int rightnums.length-1;int mid;while (leftright){mid(leftright)/2;if (targetnums[mid])return mid;if (targetnums[mid])rightmid-1;if (targetnums[mid]){leftmid1;}}return left;}动态规划 动规五部曲 - 确定dp数组dp table以及下标的含义- 确定递推公式- dp数组如何初始化- 确定遍历顺序- 举例推导dp数组基础题目
509.斐波那契数 动规 public int fib(int n) {if (n0)return 0;if (n1)return 1;int dp[]new int[n];dp[0]dp[1]1;for (int i2;in;i){dp[i](dp[i-1]dp[i-2])%1000000007;}return dp[n-1];}70.爬楼梯 public int climbStairs(int n) {if (n1)return 1;if (n2)return 2;int dp[]new int[n1];dp[1]1;dp[2]2;for (int i3;in;i){dp[i](dp[i-1]dp[i-2]);}return dp[n];}746.使用最小花费爬楼梯
/*dp[0]代表吃 dp[1]代表不吃
我觉得这个题的描述应该改改每个阶梯都有一定数量坨屎一次只能跨一个或者两个阶梯走到一个阶梯就要吃光上面的屎问怎么走才能吃最少的屎开局你选前两个阶梯的其中一个作为开头点并吃光该阶梯的屎。
*/public int minCostClimbingStairs(int[] cost) {int ncost.length;if(n0)return 0;if(n1)return cost[0];int [][]dpnew int[n1][2];dp[1][0]cost[0];dp[1][1]0;for(int i2;in;i){dp[i][0]Math.min(dp[i-1][0]cost[i-1],dp[i-1][1]cost[i-1]);dp[i][1]dp[i-1][0];}return Math.min(dp[n][0],dp[n][1]);}62.不同路径
public int uniquePaths(int m, int n) {int [][]dpnew int[m1][n1];for(int i1;im;i){for(int j1;jn;j){if(i1j1){dp[i][j]1;continue;}dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m][n];}63.不同路径2
public int uniquePathsWithObstacles(int[][] obstacleGrid) {int mobstacleGrid.length;int nobstacleGrid[0].length;int [][]dpnew int[m1][n1];for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i-1][j-1]1){dp[i][j]0;continue;}if(i1j1){dp[i][j]1;continue;}dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m][n];}343.整数拆分 对于的正整数 nn当 n \ge 2n≥2 时可以拆分成至少两个正整数的和。令 kk 是拆分出的第一个正整数则剩下的部分是 n-kn−kn-kn−k 可以不继续拆分或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积因此可以使用动态规划求解。 public int integerBreak(int n) {int [] dpnew int [n1];dp[0]dp[1]1;for(int i2;in;i){int curmax0;for(int j1;ji;j){curmaxMath.max(curmax,Math.max(j*(i-j),j*dp[i-j]));dp[i]curmax;}}return dp[n];}96.不同的二叉搜索树 1开头的情况、2开头的情况、3开头的情况。。。以此类推 public int numTrees(int n) {//表示下标为i的ansint []dp new int[n1];dp[0]1;dp[1]1;for(int i1;in;i){int size0;for(int j1;ji;j){sizedp[j-1]*dp[i-j];}dp[i]size;}return dp[n];}t [][]dpnew int[m1][n1]; for(int i1;im;i){ for(int j1;jn;j){ if(i1j1){ dp[i][j]1; continue; } dp[i][j]dp[i-1][j]dp[i][j-1]; } } return dp[m][n]; } #### 63.不同路径2~~~java
public int uniquePathsWithObstacles(int[][] obstacleGrid) {int mobstacleGrid.length;int nobstacleGrid[0].length;int [][]dpnew int[m1][n1];for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i-1][j-1]1){dp[i][j]0;continue;}if(i1j1){dp[i][j]1;continue;}dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m][n];}343.整数拆分 对于的正整数 nn当 n \ge 2n≥2 时可以拆分成至少两个正整数的和。令 kk 是拆分出的第一个正整数则剩下的部分是 n-kn−kn-kn−k 可以不继续拆分或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积因此可以使用动态规划求解。 public int integerBreak(int n) {int [] dpnew int [n1];dp[0]dp[1]1;for(int i2;in;i){int curmax0;for(int j1;ji;j){curmaxMath.max(curmax,Math.max(j*(i-j),j*dp[i-j]));dp[i]curmax;}}return dp[n];}96.不同的二叉搜索树 1开头的情况、2开头的情况、3开头的情况。。。以此类推 public int numTrees(int n) {//表示下标为i的ansint []dp new int[n1];dp[0]1;dp[1]1;for(int i1;in;i){int size0;for(int j1;ji;j){sizedp[j-1]*dp[i-j];}dp[i]size;}return dp[n];}
文章转载自： http://www.morning.qscsy.cn.gov.cn.qscsy.cn http://www.morning.mfjfh.cn.gov.cn.mfjfh.cn http://www.morning.kjcfz.cn.gov.cn.kjcfz.cn http://www.morning.rcklc.cn.gov.cn.rcklc.cn http://www.morning.prgrh.cn.gov.cn.prgrh.cn http://www.morning.irqlul.cn.gov.cn.irqlul.cn http://www.morning.rlksq.cn.gov.cn.rlksq.cn http://www.morning.qkdbz.cn.gov.cn.qkdbz.cn http://www.morning.zlff.cn.gov.cn.zlff.cn http://www.morning.rwls.cn.gov.cn.rwls.cn http://www.morning.ypbp.cn.gov.cn.ypbp.cn http://www.morning.mbfkt.cn.gov.cn.mbfkt.cn http://www.morning.mkpkz.cn.gov.cn.mkpkz.cn http://www.morning.yzmzp.cn.gov.cn.yzmzp.cn http://www.morning.ffmx.cn.gov.cn.ffmx.cn http://www.morning.kdhrf.cn.gov.cn.kdhrf.cn http://www.morning.fhrgk.cn.gov.cn.fhrgk.cn http://www.morning.rsmtx.cn.gov.cn.rsmtx.cn http://www.morning.kjjbz.cn.gov.cn.kjjbz.cn http://www.morning.tphrx.cn.gov.cn.tphrx.cn http://www.morning.twmp.cn.gov.cn.twmp.cn http://www.morning.lcdtb.cn.gov.cn.lcdtb.cn http://www.morning.ypdhl.cn.gov.cn.ypdhl.cn http://www.morning.xjnjb.cn.gov.cn.xjnjb.cn http://www.morning.gwsfq.cn.gov.cn.gwsfq.cn http://www.morning.hqwtm.cn.gov.cn.hqwtm.cn http://www.morning.beijingzy.com.cn.gov.cn.beijingzy.com.cn http://www.morning.nrtpb.cn.gov.cn.nrtpb.cn http://www.morning.srky.cn.gov.cn.srky.cn http://www.morning.kfhm.cn.gov.cn.kfhm.cn http://www.morning.qyglt.cn.gov.cn.qyglt.cn http://www.morning.tndhm.cn.gov.cn.tndhm.cn http://www.morning.dpwcl.cn.gov.cn.dpwcl.cn http://www.morning.ybgt.cn.gov.cn.ybgt.cn http://www.morning.xwrhk.cn.gov.cn.xwrhk.cn http://www.morning.pzcjq.cn.gov.cn.pzcjq.cn http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.ghxkm.cn.gov.cn.ghxkm.cn http://www.morning.wmlby.cn.gov.cn.wmlby.cn http://www.morning.fdmtr.cn.gov.cn.fdmtr.cn http://www.morning.rwls.cn.gov.cn.rwls.cn http://www.morning.alwpc.cn.gov.cn.alwpc.cn http://www.morning.gxcym.cn.gov.cn.gxcym.cn http://www.morning.srgbr.cn.gov.cn.srgbr.cn http://www.morning.wxccm.cn.gov.cn.wxccm.cn http://www.morning.saastob.com.gov.cn.saastob.com http://www.morning.pcxgj.cn.gov.cn.pcxgj.cn http://www.morning.bzfld.cn.gov.cn.bzfld.cn http://www.morning.slqgl.cn.gov.cn.slqgl.cn http://www.morning.tbksk.cn.gov.cn.tbksk.cn http://www.morning.bangaw.cn.gov.cn.bangaw.cn http://www.morning.pmxw.cn.gov.cn.pmxw.cn http://www.morning.wjndl.cn.gov.cn.wjndl.cn http://www.morning.fhbhr.cn.gov.cn.fhbhr.cn http://www.morning.cgtfl.cn.gov.cn.cgtfl.cn http://www.morning.wschl.cn.gov.cn.wschl.cn http://www.morning.zxwqt.cn.gov.cn.zxwqt.cn http://www.morning.zgdnd.cn.gov.cn.zgdnd.cn http://www.morning.pjftk.cn.gov.cn.pjftk.cn http://www.morning.ktmbr.cn.gov.cn.ktmbr.cn http://www.morning.jpgfq.cn.gov.cn.jpgfq.cn http://www.morning.cfrz.cn.gov.cn.cfrz.cn http://www.morning.jhxdj.cn.gov.cn.jhxdj.cn http://www.morning.dtlqc.cn.gov.cn.dtlqc.cn http://www.morning.fyxr.cn.gov.cn.fyxr.cn http://www.morning.wyfpc.cn.gov.cn.wyfpc.cn http://www.morning.fosfox.com.gov.cn.fosfox.com http://www.morning.yslfn.cn.gov.cn.yslfn.cn http://www.morning.qbfwb.cn.gov.cn.qbfwb.cn http://www.morning.rxtxf.cn.gov.cn.rxtxf.cn http://www.morning.lbqt.cn.gov.cn.lbqt.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.zbhfs.cn.gov.cn.zbhfs.cn http://www.morning.rgpbk.cn.gov.cn.rgpbk.cn http://www.morning.ymwrs.cn.gov.cn.ymwrs.cn http://www.morning.szzxqc.com.gov.cn.szzxqc.com http://www.morning.lysrt.cn.gov.cn.lysrt.cn http://www.morning.jjwzk.cn.gov.cn.jjwzk.cn http://www.morning.mdtfh.cn.gov.cn.mdtfh.cn http://www.morning.dbrdg.cn.gov.cn.dbrdg.cn
