算法小记（持续学习）

算法小记过程长逐步往下写文章主要是写个人算法所想作为做完之后的思考总结非最好答案。关注官方答案可以去力扣查看560. 和为 K 的子数组 - 力扣LeetCode更详细的解答可以看推荐题解560. 和为 K 的子数组 - 力扣灵山茶艾府核心思想前缀和 哈希表空间换时间适用场景子数组和问题特别是包含负数时过程最初连续、非空能否用滑动窗口滑动窗口原数组有单调性如果均为正那么右指针往右移动必定增大左指针往右必定减小有了负数就打乱了这个顺序破坏了连续排序那不是打乱了原本顺序不能保证连续性前缀和可以很好解决区间和、子串、子数组的问题要怎么写一开始想着开一个数组然后得到每次前缀和的值然后进行判断是否等于K。前缀和定义s[0]0,s[i]nums[0]nums[1]⋯nums[i−1]。注意s是一个长为n1 的数组第一个数是 0。但是有个问题这样很多情况都忽略了这时存储键值对的哈希表就有用了通过记录当前前缀和的值在表中判断s[j]−ks[i]**这个s[i]在表中是否存在有的话就加上表中存在这个值的次数Sum(i,j)Prefix[j]−Prefix[i−1]k也就是Prefix[i−1]Prefix[j]−k最后得出结果代码classSolution{publicintsubarraySum(int[]nums,intk){// Map: key 前缀和的值, value 这个值出现过多少次MapInteger,IntegerprefixSumnewHashMap();// 初始化前缀和为0的情况出现过1次为了处理从数组开头就开始的子数组prefixSum.put(0,1);intcurrentSum0;// 当前位置的前缀和intres0;// 结果计数for(intnum:nums){currentSumnum;// 计算当前前缀和// 核心逻辑查找是否存在前缀和 currentSum - k// 如果存在说明找到了 res 次数 个符合条件的子数组if(prefixSum.containsKey(currentSum-k)){resprefixSum.get(currentSum-k);}// 将当前前缀和存入哈希表供后面的位置查找// getOrDefault: 如果之前没出现过就是0出现过就1prefixSum.put(currentSum,prefixSum.getOrDefault(currentSum,0)1);}returnres;}}206. 反转链表 - 力扣LeetCode详细题解可看灵山茶艾府怎么想如果是一维数组那么确实可以通过双指针去换。不同在于链表是两两联系通过三指针进行操作一个当前节点一个是当前节点的pre还有个是当前节点的next交换节点你必须直到当前节点的前后节点是谁要不然换不了怎么写因为是需要反转。反转反转就是当前节点cur反过来连接pre,然后pre变成当前节点被移到旧cur的节点位置了然后cur继续往下走一个节点注意链表更新next的时候一定要搞清楚谁的next是谁要不然很容易连错code1.这是迭代法/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */classSolution{publicListNodereverseList(ListNodehead){ListNodecurhead;ListNodeprenull;// 反转后原头节点的 next 应为 nullwhile(cur!null){ListNodenextcur.next;// 1. 临时保存下一个节点cur.nextpre;// 2. 反转指针precur;// 3. pre 后移curnext;// 4. cur 后移}returnpre;// 循环结束时pre 指向原链表的最后一个节点即新链表的头节点}}2.递归法本质上差不多只不过我们没有用while循环而是通过递归实现指针移动classSolution{publicListNodereverseList(ListNodehead){// 1. 递归终止条件空链表或只有一个节点if(headnull||head.nextnull){returnhead;}// 2. 递归反转剩余部分newHead 始终是原链表的最后一个节点ListNodenewHeadreverseList(head.next);// 3. 关键操作让下一个节点指向自己head.next.nexthead;// 4. 断开自己原来的指向防止成环head.nextnull;returnnewHead;}}总结特性迭代法递归法核心操作三指针循环移动递归到底回溯时反转空间复杂度O(1)O(n) (系统栈空间)易理解度直观需理解回溯推荐指数面试首选理解原理92. 反转链表 II - 力扣LeetCode详细可看灵山茶艾府怎么看看到题目可以发现本质差不多但是是在规定的[left,right]范围内进行反转。然后除了要关注反转链表题目中的反转以外还需要关注以下几点怎么找到left和right节点反转以后怎么把反转后的链表段跟剩余的节点相连注意题目中left和right的值不是节点值而是节点的序号怎么写那么反转节点还是可以仿照上面的例题去写然后寻找left和right节点的时候也是需要找到它们的前一个节点同时记录left和right节点1.切断然后切断要反转的与不用反转节点联系。断开pre与left的连接断开right与successor后继节点的连接。**2.反转**调用标准的“反转链表 I”函数**3.拼接**反转后一定是pre.nextrightNode.Next;leftNode.nextsuccessor这样才能重新连接上同时Java 是值传递。函数内部反转后必须返回新的头节点即原来的尾节点rightNode外部才能拿到反转后的链表头进行拼接。code/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */classSolution{publicListNodereverseBetween(ListNodehead,intleft,intright){// 1. 虚拟头节点处理 left1 的情况ListNodedummynewListNode(-1);dummy.nexthead;// 2. 找到 left 的前驱节点ListNodepredummy;for(inti0;ileft-1;i){prepre.next;}// 3. 找到 right 节点ListNoderightNodepre;for(inti0;iright-left1;i){rightNoderightNode.next;}// 4. 截取链表 (切断前后连接)ListNodeleftNodepre.next;// 待反转部分的头ListNodesuccessorrightNode.next;// 待反转部分的后继pre.nextnull;// 断开前驱rightNode.nextnull;// 断开后继 (关键防止反转过头)// 5. 反转截取的链表并获取新头// 注意这里必须接住返回值因为反转后头尾互换了ListNodenewHeadreverseNode(leftNode);// 6. 拼接回原链表pre.nextnewHead;// 前驱连新头leftNode.nextsuccessor;// 旧头(现尾)连后继returndummy.next;}// 标准的反转链表函数 (迭代法)privateListNodereverseNode(ListNodehead){ListNodeprenull;ListNodecurhead;while(cur!null){ListNodenextcur.next;cur.nextpre;precur;curnext;}returnpre;// 返回新头节点}}总结时间复杂度 O(N)。虽然我们分成了几步但本质上pre走了 NN步反转过程走了 R−L 步总体还是线性时间。空间复杂度 O(1) 。我们没有使用额外的数组或递归栈reverseNode是迭代的只是用了几个指针变量。102. 二叉树的层序遍历 - 力扣如何理解题目要求层序遍历也就是每层进行输出。但是如何分层怎么做1.创建列表根据输出格式我们需要一个ListListInteger存储结果以及每层临时的ListInteger。2.使用队列实现层级遍历观察输出3 先被处理接着是 9 和 20。这体现了先进先出FIFO的特性因此我们使用队列Queue而非栈。 栈是后进先出LIFO适用于 DFS队列是先进先出FIFO适用于 BFS层序遍历。3.控制每层的边界关键技巧在每轮 while 循环开始时记录当前队列的大小n这代表当前层的节点数。然后只处理这n个节点就能自然分层。code/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicListListIntegerlevelOrder(TreeNoderoot){if(rootnull){returnnewArrayList();}ListListIntegeransnewArrayList();QueueTreeNodeqnewLinkedList();q.add(root);while(!q.isEmpty()){intnq.size();ListIntegerlistnewArrayList();while(n--0){TreeNodenodeq.poll();list.add(node.val);if(node.left!null)q.add(node.left);if(node.right!null)q.add(node.right);}ans.add(list);}returnans;}}总结时间复杂度为O(n)105. 从前序与中序遍历序列构造二叉树 - 力扣怎么看从题目来看是通过两个遍历方式确定一个二叉树。那就要知道前序和中序遍历的特点前序前序遍历的第一个元素是当前子树的根节点中序根节点在整个中序遍历的中间元素元素左边是左子树的节点右边是右子树的节点怎么做首先需要在中序遍历里找到根节点的位置。前序遍历中第2个元素到根节点位置是该根节点的左子树同理前序遍历中的根节点以后的节点是右子树。中序遍历从第一个元素到该根节点的所有节点是左子树根节点以后的节点是右子树。同时因为根节点的左右子树也包含根节点和左右子树这就要通过递归进行注此解法便于理解但存在重复拷贝数组和线性查找的开销。实际可优化为使用哈希表 索引范围将时间复杂度降至 O(n)。code/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */classSolution{publicTreeNodebuildTree(int[]preorder,int[]inorder){intnpreorder.length;if(n0)returnnull;intleftfind(preorder[0],inorder);intpre1[]Arrays.copyOfRange(preorder,1,left1);intpre2[]Arrays.copyOfRange(preorder,left1,n);intin1[]Arrays.copyOfRange(inorder,0,left);intin2[]Arrays.copyOfRange(inorder,left1,n);TreeNodelbuildTree(pre1,in1);TreeNoderbuildTree(pre2,in2);returnnewTreeNode(preorder[0],l,r);}privateintfind(intx,int[]a){for(inti0;;i){if(a[i]x){returni;}}}}目前时间复杂度为O(n²)后续添加复杂度为O(n)的解法。。。最后在持续学习中如有问题还请指出