专门使用一个stack，记录每次操作所对应的最小值？ ---第二小元素的下一个元素在哪儿？--解决思路：专门使用一个stack 同步弹出！！ public class Solution { Stack<Integer> min=new Stack<>(); Stack<Integer> data=new Stack<>(); public void push(int node) { data.push(node); if(min.isEmpty()){ min.push(node); }else{ min.push(Math.min(min.pe...

设置边界，left,right,top,bottom，有效的条件是left<=right,top<=bottom. 每完成一行后，需要修改边界，然后再比较，so,++left;  /** * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字 * @param matrix 矩阵 * @return 顺时针的顺序依次打印出每一个数字 */ public ArrayList<Integer> printMatrix(int [][] matrix) { ArrayList<Integer> res=new ArrayList<>(); i...

终止条件：NULL,或者叶子节点。两个都不需要交换。 遍历到的节点有子节点，就交换它的两个子节点  /** * 操作给定的二叉树，将其变换为源二叉树的镜像。 * @param root 二叉树的镜像 */ public void Mirror(TreeNode root) { if (root==null){ return; } if(root.left==null&&root.right==null){ return; } TreeNode temp=root.left; root.left=root.right; root.right=temp; if(root.left!...

当根节点相等时，再去考虑剩余部分(left,right)。 对数的访问确保非空。 设置标志位，一旦找到，就不再继续。  /** * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） * @param root1 二叉树A * @param root2 二叉树B * @return 判断B是不是A的子结构 */ public boolean HasSubtree(TreeNode root1,TreeNode root2) { boolean res=false; if(root1!=null&&root2!=null){ if(root...

过程与归并排序相似。函数含义的理解：归并两个有序链表，并返回归并后的头结点(递归的理解，包括返回值)  确定头结点。 剩余部分通过递归来实现，确定了一个，剩余部分:list1.next;   /** * 输入两个单调递增的链表，输出两个链表合成后的链表， * 当然我们需要合成后的链表满足单调不减规则。 * @param list1 有序单链表1 * @param list2 有序单链表2 * @return 输出两个链表合成后的链表 */ public ListNode Merge(ListNode list1,ListNode list2) { if (list1==null){ retur...

初始化 pre=null,cur=head;  next=cur.next;//保存后继节点。 cur.next=pre;//翻转或逆序 pre=cur;//后移 cur=next;// 后移  /** * 输入一个链表，反转链表后，输出新链表的表头。 * @param head 链表 * @return 反转链表后的表头 */ public ListNode ReverseList(ListNode head) { if(head==null||head.next==null){ return head; } ListNode pre=null; ListNode cur=head; whi...

双指针，当相距k-1时，当后者到最后时，前者才恰好是倒数第k个元素。 最后一个元素的循环条件是cur.next!=null,而不是cur!=null. 链表访问(cur.next)全程要确保非空！  /** * 输入一个链表，输出该链表中倒数第k个结点。 * @param head 链表 * @param k 倒数第k * @return 输出该链表中倒数第k个结点。 */ public ListNode FindKthToTail(ListNode head,int k) { if(head==null||k<=0){ return null; } ListNode cur=head;...

使用额外的空间来保持稳定性。 先复制所有奇数，后复制所有偶数，最后回写！  public class Solution { public void reOrderArray(int [] array) { if(array==null|array.length==0){ return ; } int length=array.length; int[] aux=new int[length]; int k=0; for(int num:array){ if((num&1)==1){ aux[k++]=num; } } for(int num:array){ if((num&1)...

二分法 2的n次方，等价于2的n/2的平方，---快速幂算法的核心思想。 当指数为负数时，标记后，需要将指数变为整数。exp=-exp;  /** * 给定一个double类型的浮点数base和int类型的整数exponent。 * 求base的exponent次方。 保证base和exponent不同时为0 * @param base 浮点数base * @param exponent int类型的整数exponent * @return base的exponent次方 */ public double Power(double base, int exponent) { if(expone...

去除掉二进制最右边的一个1. n&(n-1)  /** * 输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。 * @param n 整数 * @return 1的个数 */ public int NumberOf1(int n) { int res=0; while(n!=0){ res++; n&=(n-1); } return res; }

初始状态单独枚举，符合公式的才进入循环。i=3;  /** * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ * @param target n个2*1的小矩形 * @return 方法总数 */ public int RectCover(int target) { if(target<=2){ return target; } int f1=1,f2=2; int fn=f1+f2; for(int i=3;i<=target;i++){ fn=f1+f2; f1=f2; f2=fn; } ...

数学法，跳与不跳。2^(n-1). 递归：f(n)=2f(n-1),初始条件：target==1,n=1;  /** * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。 * 求该青蛙跳上一个n级的台阶总共有多少种跳法。 * @param target n级 * @return 跳法总数 */ public int JumpFloorII(int target) { // f(n) = 2*f(n-1) if (target<=0){ return -1; }else if(target==1){ return 1; } return 2*JumpFloorII(tar...

初始条件需要独立枚举，n从3开始。  /** * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。 * 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 * @param target n级的台阶 * @return 跳法总数。 */ public int JumpFloor(int target) { if(target<=2){ return target; } int f1=1,f2=2; int fn=f1+f2; for(int i=3;i<=target;i++){ fn=f1+f2; f1=f2; f2=fn; } return fn; }

请注意控制循环次数，循环次数应该去除掉初始变量的次数。  /** * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项 * （从0开始，第0项为0，第1项是1）。 * n<=39 * @param n 整数n * @return 斐波那契数列的第n项 */ public int Fibonacci(int n) { if (n < 2) { return n; } int f1 = 0, f2 = 1; int fn = f1+f2; for (int i = 2; i <= n; i++) { fn = (f1 + f2)%1000000007;...