入门的动态规划问题： public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int len = array.length; int[] dp = new int[len]; int max = array[0]; dp[0] = array[0]; for(int i = 1; i < len; i++) { int newMax = dp[i - 1] + array[i]; if(newMax > array[i]) { dp[i] = newMax; } else { dp[i]...

本质上还是斐波那契数组 public class Solution { public int rectCover(int n) { if (n <= 2) return n; int a1 = 1; int a2 = 2; int ret = 0; for (int i = 3; i <= n; i++) { ret = a1 + a2; a1 = a2; a2 = ret; } return ret; } }

O(n)时间复杂度O(1)空间复杂度  一趟遍历，O(1)的空间消耗，意味着就地处理。 超过一半，意味着出现的次数多于  public class Solution { public int MoreThanHalfNum_Solution(int [] a) { int cand = a[0]; int times = 1; for (int i = 1; i < a.length; i++) { if (times == 0) { cand = a[i]; // 放弃上一个候选，重新选取 times = 1; } else if (a[i] == cand) { times++; /...

双栈实现 import java.util.Stack; public class Solution { private Stack<Integer> stack1 = new Stack<>(); private Stack<Integer> stack2 = new Stack<>(); public void push(int node) { if (stack1.isEmpty()) { stack2.push(node); } else if (node < stack2.peek()) { stack2.push(node); ...

解法一、自上而下 这种解法每次都要去计算当前节点的高度，而计算高度的时候又要递归以当前节点为根的树，存在大量的重复计算。 import java.lang.*; public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if(root == null){ return true; } int leftHeight = getHeight(root.left); int rightHeight = getHeight(root.right); if(Math.abs(leftHeight - right...

这个题目是对每个节点的左右子节点进行交换，实质上就是如何遍历树的所有节点，正好复习一遍树的遍历。 树的结构 /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ 解法一、递归后序遍历 public class Solution { public TreeNode Mirror (TreeNode root) { if (root == null) r...

二叉树的结构： /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ 递归解法，某一个结点的高度等于其左右子树高度中较大者加1，本题叶子节点的高度为1，因此空节点的高度为0。 public class Solution { public int TreeDepth(TreeNode root) { if (root == null) return 0; // 递归终止条件 int...

链表结构： /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ 解法一、常规思路  public class Solution { public ListNode Merge(ListNode l1, ListNode l2) { ListNode head = new ListNode(0), p = head; // head头结点，避免找不到链表头 while (l1 != null && l2 != null) { if (...

先说这个题目的问题，这个题目没有明确的说明台阶n的取值范围，  没有说明台阶n的下限，没有定义f(0)的取值而且没有对应的测试案例，导致f(0)返回任何值都能通过 没有定义台阶n的上限，这个题目最终是求2的指数级结果，虽然通过参数和返回值的类型可以判断取值范围，但是从严谨的角度还是应该说明一下。  因此这是题目的瑕疵。 但是如果题目给定义了f(0)的值，那么n=0这个案例又是送分的，所以我们姑且认为题目的n取值是正整数，f(0)是我们解题时自己定义的值，与答案无关，我们怎么便于解题怎么定义，直观的看，f(0)似乎取1比较便于理解。 此时： f[n] = f[n-1] + f[n-2] + .....