重建二叉树
public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
if (pre == null || vin == null || pre.length != vin.length) {
return null;
}
return build(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
}
private TreeNode build(int[] pre, int pre_start, int pre_end, int[] vin, int vin_start, int vin_end) {
if (pre_start > pre_end || vin_start > vin_end) {
return null;
}
TreeNode root = new TreeNode(pre[pre_start]);
for (int j = vin_start; j <= vin_end; j++) {
if (pre[pre_start] == vin[j]) {
root.left = build(pre, pre_start + 1, pre_start+ j - vin_start, vin, vin_start, j - 1);
root.right = build(pre,pre_start+ j - vin_start + 1, pre_end, vin, j + 1, vin_end);
break;
}
}
return root;
}
输出斐波那契数列的第 n 项。
斐波那契数列
【剪枝将重复的叶子树用Map集合过滤】
Map跳台阶map = new HashMap<>();//过滤 public int Fibonacci(int n) { if (n == 0 || n == 1) { return n; } int pre =0;//找n-1 if (map.containsKey(n-1)){ pre = map.get(n-1); }else { pre = Fibonacci(n-1); map.put(n-1,pre); } int ppre =0;//找n-2 if (map.containsKey(n-2)){ ppre =map.get(n-2); }else { ppre = Fibonacci(n-2); map.put(n-2,ppre); } return ppre+pre; }
题目:青蛙跳台阶
DP动态规划
public static int jumpFloor(int target) {
if (target == 0){
return 0;
}
if (target <= 2){
return target;
}
int[] dp = new int[target + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= target; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target];
}
二进制中1的个数
牛客原题
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {
int x = n - 1;
n = n & x;
count++;
}
return count;
}
合并两个排序的链表
方法一:创建虚拟头节点对两个链表拼接
方法二:递归实现方法一
合并两个排序的 链表
ListNode dummyHead =new ListNode(0);
ListNode tail =dummyHead;
public ListNode Merge(ListNode list1, ListNode list2) {
build(list1,list2);
return dummyHead.next;
}
private void build(ListNode list1, ListNode list2) {
if (list1 == null && list2 == null){
return;
}
if (list1 == null) {
tail.next =list2;
return;
}
if (list2 == null) {
tail.next = list1;
return;
}
if (list1.val < list2.val){
tail.next = list1;
list1 = list1.next;
}else {
tail.next = list2;
list2 =list2.next;
}
tail = tail.next;
build(list1,list2);
}
树的子结构
[空树不为子结构的情况]牛客原题
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}
Boolean isSame = false;
if (root1.val == root2.val) {
isSame = isSameChild(root1, root2);//判断子树是否相同
}
if (!isSame) {//当前头节点不是,在左子树找
isSame = HasSubtree(root1.left, root2);
}
if (!isSame) {//左子树没有在右子树找
isSame = HasSubtree(root1.right, root2);
}
return isSame;
}
private Boolean isSameChild(TreeNode root1, TreeNode root2) {
if (root2 == null) {//树2遍历结束都没找到不一样的返回真
return true;
}
if (root1 == null) {//树2都没走完,树1走完了返回假
return false;
}
if (root1.val != root2.val) {//判断根节点
return false;
}
return isSameChild(root1.left, root2.left) && isSameChild(root1.right, root2.right);//判断左右子树
}



