每次压完栈之后，就可能匹配出栈，如果可以出栈，就一直出栈直到为空 如果最后一次压栈出栈之后，栈还不为空，则不匹配 一开始的代码： import java.util.*; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { int in = 0, out = 0; Stack<Integer> stack = new Stack(); while(in < pushA.length || !stack.empty()...

给一个初始节点赋给root，构建的链表连接在其后，返回时返回root.next 两条链哪个小链接哪个节点，被链接的链后移，直到一条链为空，另一条链直接接在最后 public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode root = new ListNode(-1), node = root; // 直到一条链为空 while(list1 != null && list2 != null){ ...

利用三个对象来反转链表的步骤 先用now保存当前头部再使用head指向本次反转的头部再将end(尾部)的下一位定位到下次反转的头部最后进行本次反转 public class Solution { public ListNode ReverseList(ListNode head) { if(head == null || head.next == null) { return head; } // 翻转 ListNode end = head, now; while(end....

暴力方法每次只乘一次base，考虑将exponent化成二进制，base每次平方，来进行结果的增长 public class Solution { public double Power(double base, int exponent) { double result = 1.0; if(exponent < 0) { exponent = -exponent; base = 1 / base; } // 二进制缩减 while(exponent ...

逐位计算1个数 有两种思路，一种右移n，每次与1进行与运算；另一种是左移1，每次与n进行与运算，由于n为负数时右移会填充1，所以选择左移1的思路public class Solution { public int NumberOf1(int n) { int ans = 0; int mark = 1; while(mark != 0) { // 判断某位是否为1 if((mark & n) != 0) { ans++; } // 左移一...

设铺第n个砖块可能的方法数为f(n) 铺每个砖块可以横着铺（占两格，f(n-2)），也可以竖着铺（只占一格，f(n-1)），即f(n) = f(n-1) + f(n-2) public class Solution { public int RectCover(int target) { // 排除初始情况 if(target <= 1) return target; // 给出初始数据进行计算 int first = 1, second = 2; while(target-- > 2) {...

前序遍历为{根节点，{左孩子树}，{右孩子树}}，中序遍历为{{左孩子树}，根节点，{右孩子树}} 可以从前序遍历拿出根节点（首位）确定中序遍历数组的根节点位置，从而划分左右子树在两序遍历数组的范围，接下来就是左右子树的构建过程，即将一个大问题分割成了相同类型但规模更小的子问题，直接递归解决。 public class Solution { public TreeNode reConstructBinaryTree(int[] pre, int[] in) { return reConstructBinaryTreeRec(pre, 0, pre.length - 1...

递归 设跳到n层的方法数为f(n)，则f(n) = f(n - 1) + f(n - 2) public class Solution { public int JumpFloor(int target) { if(target <= 1) return 1; return JumpFloor(target - 2) + JumpFloor(target - 1); } }动态规划 设跳到n层的方法数为f(n)，则f(n) = f(n - 1) + f(n - 2) 每次只需要使用到前两层方法数，所以只需要两个变量保存 public...

二叉排序树找第K小值，则中序遍历到第k个时可满足需求 import java.util.*; public class Solution { TreeNode KthNode(TreeNode pRoot, int k) { if(k == 0) { return null; } Stack stack = new Stack(); TreeNode node = pRoot; // 中序遍历 while(node != null || !stack.isEmpty...

目标数组的i对应元素是原数组不包括i元素的乘积，即B[i] = (A[0]*...*A[i-1]) * (A[i+1]*...*A[n-1])，即左侧乘以右侧 可以用一次正循环计算左侧乘积，再来一次逆循环计算右侧乘积的同时计算B[i] public class Solution { public int[] multiply(int[] A) { int[] B = new int[A.length]; // 计算i左侧乘积存入B B[0] = 1; for(int i = 1; i < A.length; i++...

加法可以分为不包含进位的加法（异或）和进位（与操作再左移） 每次计算不包含进位的加法和进位，如果无进位，则不包含进位的加法计算出来的就是结果，如果有进位，则将不包含进位的加法算出来的而结果和进位算作两个数再相加 public class Solution { public int Add(int num1,int num2) { int sum = 0, carry = -1; // 如果进位为0则sum计算值是正确的 while(carry != 0) { // 没有进位的加法 sum ...

判断是否为平衡二叉树：节点为空，左右孩子深度差不超过1，且左右孩子也必须平衡（通过计算深度） 函数不可单纯计算深度，还需判断平衡，设置一个不可逆负值为非平衡，则可实现需求 public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return treeDepthRec(root) != -2; } // 判断树的深度，返回-1则不平衡 public int treeDepthRec(TreeNode root) { if(root =...

递归 当前节点深度为左右孩子的最大深度 + 1 public class Solution { public int TreeDepth(TreeNode root) { if(root == null) { return 0; } return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1; } } 非递归 层次遍历树，每一层+1 import java.util.*; public class Solution { public int Tree...

求最大连续子数组和 可以转化为 求以每一个元素结尾的最大子数组和的最大值，而以当前元素结尾的最大子数组和可以由以上一个元素结尾的最大子数组和求得，则可使用动态规划qiuj 设n为当前遍历元素下标，e为当前元素，f(n)为以当前元素结尾的子数组和最大值，则f(n) = MAX(f(n - 1) + e, e)，则最大子数组和为计算出的f(n)的最大值 public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int nowSum = 0, maxSum = Integer.MI...