时间复杂度为O(1)的思路 想要控制时间复杂度在O(1)则需要在原矩阵上操作 寻找规律：分析顺时针旋转后位置的变化，得到： mat[i][j]->m[j][n-1-i] 构造出坐标转移方程：f(i,j)=(j,n-1-i) 设f_next0=(i,j) 继续推导： f_next1=f(i,j)=(j,n-1-i) f_next2=f(j,n-1-i)=(n-1-i,n-1-j) f_next3=f(n-1-i,n-1-j)=(n-1-j,i) f_next4=f(n-1-j,i)=(i,j) 发现规律，周期为4，意味着每四个结点一组交换位置即达到旋转效果 为了避免重复旋转，...

思路 题目要求get和set都是O(1),所以要快速地查找和插入/删除 利用java.util中的LinkedHashMap实现，该类型结合了哈希表和链表的优点 import java.util.*; import java.util.ArrayList; import java.util.LinkedHashMap; public class Solution { /** * lru design * @param operators int整型二维数组 the ops * @param k int整型 the k * @return i...

思路 层次遍历，遍历结果内部没有空即为完全二叉树 判断为空可以用如下方法： 第一次遇到null，设置res为true，假设一个完全二叉树的有效节点已经遍历结束，只剩空结点 继续遍历如果遇到非空结点，则假设不成立，直接返回false 否则直至结束都是空结点，则假设成立，返回res，即true 代码 public class Solution { public boolean isCompleteTree (TreeNode root) { return levelOrder(root); } public boolean levelOrder(...

思路 二叉树题目逃不过遍历框架，我们需要确定的在遍历过程中需要做什么以及在何时做 同步遍历两棵二叉树，保证每次遍历的点为相互对应的（我们以覆盖树1为例） 合并二叉树有如下情形： 两结点均不为空：结点值相加，覆盖树1结点；继续遍历 树1结点为空，树2结点不为空：因为我们约定了覆盖树1，所以应当将树2结点及其子树一起移动到树1对应位置（这里需要记录树1空结点的父节点以及该空结点是左孩子还是右孩子）；继续遍历 树1结点不为空，树2结点为空：不需要做什么，继续遍历即可 两结点均为空：同样不需要做什么，继续便利即可 遍历时，为了记录当前树1结点的父节点及左/右，我们在遍历函数的参数中维护这两个值...

思路 遍历二叉树 维护一个变量res，res的值为从根节点到当前结点路径中结点值的和 遍历到当前节点时令res加上结点值，再遍历左右子树 当遇到叶子节点时，判断res是否等于sum 若等于则设置r为true 若不等于则继续遍历 当前结点遍历结束后令res减去结点值 代码 public class Solution { int res=0; boolean r=false; public boolean hasPathSum (TreeNode root, int sum) { if(root==null) return false; ...

思路 下文均以nex代表当前遍历结点，now为初始时nex的上一结点 处理头部重复结点（注意头部可能有多个重复结点） 当head和head.next的val相等时：找到不相等的值或者now.next为null 若为值不相等，则令nex为新头节点，继续循环判断 若为null（此时值相等），说明所有结点都为重复值，则返回null 处理非头部重复结点 用las记录now的上一个结点，nex遍历，找到与now不相等的值或者nex为null 若值不相等且now与nex相邻，说明此处无重复元素、更新las、now、nex位置，继续循环判断 若值不相等且now与nex不相邻，说明从now...

思路 创建双指针：now和nex，初始nex=now.nex nex开始遍历链表，跳出条件为 nex为空 nex.val与now.val不相等 遍历暂停时的处理 先判断若nex与val的值不相等，则说明找到了now的下一个结点为nex，令now.next=nex,now和nex均向后移动一格，nex继续遍历。 再判断若nex为空（此时nex和val的值相等），则说明nex遍历过的点均需要删除，直接令now.next=null，返回头结点 代码 public class Solution { public ListNode deleteDuplicates (ListNo...

思路 每次看两个，隔一个指向一个 注意分类讨论以及链表指向的关系 public class Solution { public ListNode oddEvenList (ListNode head) { if(head==null||head.next==null) return head; ListNode now=head; ListNode now2=head.next; ListNode head2=now2; while(now2.next!=null&&now2.next...

思路 得到反向的链表 依次比较两链表结点值是否相同，有不相同则返回false；直到最后都没有不相同则返回true 注意 得到反向链表而不是将原链表反向，需要copy一份出来 public class Solution { public boolean isPail (ListNode head) { if(head==null) return true; ListNode rev=reverseList(copyList(head)); while(head!=null){ if(head.val!=rev.v...

把链表转换为数组 将数组排序 把数组转换为链表 public class Solution { public ListNode sortInList (ListNode head) { if(head.next==null) return head; ListNode h1=head; ArrayList<Integer> tar=linkListToIntArray(head); int i=tar.size(); while(--i>=0...

一道思路大家都懂的麻烦题 思路 将两个列表反转 对应位相加，再加上上一位的进位值，计算当前位的值与进位 根据链表长度分类讨论（我在这里遍历时覆盖了head1链表） 两链表长度相同：遍历结束时判断进位是否为0，若不为0则生成新结点接在链表后面 链表1长度大于链表2：链表2遍历结束时，继续遍历链表1，计算公式为链表1结点值+进位值；链表1遍历结束时根据进位是否为0决定是否需要生成新结点。 链表1长度小于链表2：链表1遍历结束时，令链表1最后一个结点指向此时链表2下一个结点，计算公式为链表2结点值+进位值；链表2遍历结束时根据进位是否为0决定是否需要生成新结点。 反转链表1得到结果 优化...

分析依次合并和两两合并需要合并的次数 如图:

前置知识 需要先了解找倒数第k个结点的方法 这里附上“BM8-链表中倒数最后k个结点”的题解：附图解 思路 （以下用k代表n） 找到倒数第k+1个结点：now 将倒数第k+1个结点指向倒数第k-1个结点，即now.next=now.next.next 将倒数第k个结点赋值为null 边界条件讨论 如果k=链表长度，则为删除第一个结点，倒数第k+1个结点为null，则返回倒数第k-1个结点 如果k大于链表长度（不可能出现，题目保证n有效） 如果k=1，则删除最后一个结点，此种边界情况可归并到普通思路中。 符号说明 now用于遍历链表（迭代器） last用于记录now的上一个结点 box...

为了便于演示，假设k=3，链表如下 k<=链表长度 维护一个长度为k的链表数组temp，对链表进行遍历，把遍历到的结点按序放入该数组中，当下标i指向数组最后一个位置时，存入当前结点后将令i指向数组首部位置。 当遍历到链表末尾（空结点时），temp中最早存入的结点即为倒数第k个结点。 因为temp长度为k，所存放的结点为最近k步遍历到的结点，故遍历结束时temp中存储的为链表最后k个结点。 那么最早存入的就是最倒数第k个结点。 这里也可以把temp理解为一个环形数组，头尾相接，最新的结点会覆盖最旧的结点（下标指向的位置）； 下标一直向后移动，指向待覆盖的结点。 当链表到末尾时，下标指向...