合并有序链表

合并两个有序链表，使其成为一个新的有序链表

1
2
3
4
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode temp = newHead;
        while(l1!=null&&l2!=null) {
        	if(l1.val<=l2.val) {
        		temp.next = l1;
        		l1 = l1.next;
        	}else if(l1.val > l2.val) {
        		temp.next = l2;
        		l2 = l2.next;
        	}
        	temp = temp.next;
        }
        //接下来有一个链表已经遍历到结尾，另一条可能还没有结束
        temp.next = (l1==null?l2:l1);
        return newHead.next;
    }
}

展开全文 >>

快速幂

pow(x,y)快速幂的实现形式

如果我们使用常规的想法去累成得到无疑时间复杂度很高，我们再进行对问题的分析，加入我们相求x^n的值，那我们只要知道x^1/2的值，继续递归知道我们知道x^1的值，那么我们在返回栈结果我们就可以的到我们想要的结果时间复杂度从n降到logn
解题细节：
首先y可能为负值，那么我们预处理一下，当y小于零时，令y=-y，x=1/x
其次我们要讨论n的奇偶性，当n为偶数时，那么x^n = half * half，当n为奇数时,那么x^n = half * half * x;其中half表示x^n的一半
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double myPow(double x, int n) {
        if(n<0) {
			n = -n;
			x = 1/x;
		}
		return fastPow(x, n);
    }
    public double fastPow(double x,int n) {
		if( n == 0) {
			return 1.0;
		}
		double half = fastPow(x,n/2);
		if(n%2 == 0) {
			return half*half;
		}else {
			return half*half*x;
		}
	}
}

展开全文 >>

反转字符串 

1
2
3
4
5
6
7
8
9
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void reverseString(char[] s) {
        RS(s, 0,s.length-1 );
    }
    public void RS(char[]s,int left,int right) {
		if(left>=right) {
			return;
		}
		char temp = s[left];
		s[left++] = s[right];
		s[right--] = temp;
		RS(s, left, right);
	}
}

展开全文 >>

二叉树最近公共祖先

二叉树最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树:root =[3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解题思路：
通过上述对公共祖先的解释，其实我们可以发现对于一个节点而言，如果这个点是p，q的最近公共祖先节点，我们大致可以分成三种情况：
1.p，q在root的子树中，那么p，q一定在root的右侧
2.p为root，且q在p的子树中
3.q为root，且p在q的子树中
我们通过后序遍历，从最深处向上遍历
递归解析：
1.首先结束条件：如果越过了p，q就返回null，如果root等于p，q那就返回p，q
2.递推工作：开启递归左子节点，返回值为left，开启递归右子节点，返回值为right
3.根据left和right的返回情况我们可以分成以下几点
·当left和right同时为空，说明p，q不在root的子树中，直接返回null
·当left和right同时不为空时，说明p，q在root的异侧，那么root就是p，q的最近公共祖先节点，所以返回root
·当left为空，right不为空时，说明此时，pq都不在root的左子树中，则直接返回root，此时可能有两种情况：p，q有一个在right中，那么我们返回的right指向p或q；p，q都在right中那么我们返回的就是最近公共父节点
·当right为空，left不为空时同上
我们通过图解来更好的理解这个含义
例一：找到7和8的最近公共祖先节点

例二：找到2和4的最近公共祖先节点

具体的代码实现：

1
2
3
4
5
6
7
8
9
10
11
public static TreeNode1 lowestCommonAncestor(TreeNode1 root, TreeNode1 p, TreeNode1 q) {
	      if(root == null||root == p || root ==q) {
	    	  return root;
	      }
	      TreeNode1 left = lowestCommonAncestor(root.left, p, q);
	      TreeNode1 right = lowestCommonAncestor(root.right, p, q);
	      if(left == null && right == null) return null;
	        if(left == null) return right; 
	        if(right == null) return left; 
	        return root; //当左右都不为空时
	  }

展开全文 >>

对称树

对称树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树[1,2,2,3,4,4,3] 是对称的。
    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

解题思路：
1.首先我们使用两个参数t1，t2来表示根节点的左右子树，我们宏观的去看待递归问题，我们找到要解决的问题单元：首先判断t1和t2节点的值是否相同，不相同直接返回false，如果相同接着判断：如果t1的左子树和t2的右子树相同，同时t1的右子树和t2的左子树相同那么我们就可以return true。
2.接着我们找到结束条件，如果t1和t2都是null，那肯定是对称的，如果一方是null另一方不是那么肯定不是对称的，那么我们就找到了结束条件
接下来是代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static boolean isSymmetric(TreeNode root) {
	     return dfs(root,root);
	}
	public static boolean dfs(TreeNode t1,TreeNode t2) {
		if(t1==null&&t2==null) {
			return true;
		}
		if(t1==null||t2==null) {
			return false;
		}
		boolean f1 = dfs(t1.left,t2.right);
		boolean f2 = dfs(t1.right,t2.left);
		return((t1.val==t2.val)&&f1&&f2);	
	}

展开全文 >>

二叉树的最大深度

二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明:叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度3

我们解决这个问题可以有两种思路，从上往下的解决，和从下往上的解决，对应着前序和后序两种不同的思路
1.从上往下解决问题：我们将问题宏观去看，就是找根节点左子树和右子树两者的最大高度，当我们向深处遍历一层，深度就+1，当左右两侧都到达最深处时返回两者最大值

1
2
3
4
5
6
7
8
9
10
11
private int answer;
private void maximum_depth(TreeNode root, int depth) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        answer = Math.max(answer, depth);
    }
    maximum_depth(root.left, depth + 1);
    maximum_depth(root.right, depth + 1);
}

2.从下往上解决问题：当我们找到最深处时，root==null，那么它的深度为0，这个时候我们可以得到其父节点的深度，然后逐层向上求出各个节点的深度

1
2
3
4
5
6
7
8
9
10
11
public static int postHeight(TreeNode root) {
		if(root == null) {
			return 0;
		}
		int left_h=postHeight(root.left);
		int right_h=postHeight(root.right);
		return Math.max(left_h, right_h)+1;
		
		//或者精简版
		return Math.max((root==null?0:postHeight(root.left),(root==null?0:postHeight(root.right))+1;
}

展开全文 >>

路径总和

路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
<!--more-->

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解题思路：我们将二叉树分为两个方向，遍历左子树和右子树看是否有路径为目标和，每当我们经过一个节点，就加上这个节点的值，当我们找到最后一个叶子节点时，我们判断是否sum为目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return dfs(root,0,sum);
    }
    public boolean dfs(TreeNode root,int sum,int target) {
		if(root == null) {
			return false;
		}
		sum += root.val;
		if(root.left == null && root.right ==null) {
			return sum==target;
		}
		return dfs(root.left,sum,target)||dfs(root.right,sum,target);
	}
}

展开全文 >>

恢复二叉树

恢复二叉树

如题所示，我们解决的问题是根据二叉树的遍历组合来还原这个二叉树，这个过程其实是复杂的，我们需要根据三种遍历方式的不同特性来确定这个二叉树，由于前序+后序遍历无法确定一颗唯一的二叉树，所以我们将着重介绍两种：前序+中序和后序+中序来还原二叉树.

接下来我将详细介绍后序+中序还原二叉树的过程

1
2
3
4
5
6
7
8
9
10
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

首先我们根据后序遍历的特点可知，最后一个元素就是数的根节点，根据中序遍历可知，根节点的左侧是左子树，右侧是右子树：


接下来解释一下下面会使用到的一些变量： 

1
2
3
4
int InStart  //接下来递归时我们使用到的中序遍历的左边界
int InEnd    //中序便利的右边界
int PostStart //后序遍历的左边界
int PostEnd  //后序遍历的有边界

接下来最重要的是边界的计算：

1.左子树的中序数组左边界：Instart，有边界是rootIndex-1
2.左子树的后序数组左边界：PostStart，右边界：PostStart+（rootIndex-1-Instart+1）-1
3.右子树的中序数组左边界：rootIndex+1，右边界InEnd
4.右子树的中序数组左边界：：PostStart+rootIndex-Instart，右边界：PostEnd-1
所以接下来代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class InAndPost {
	int[] postArr;
	Map<Integer,Integer> map = new HashMap<>();//利用hash表快速找到根节点在中序数组中的位置
	public static void main(String[] args) {
		// TODO 自动生成的方法存根

	}
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		postArr = postorder;
		for(int i=0;i<inorder.length;i++) {
			map.put(inorder[i], i);
		}
		return buildTrees(0, inorder.length-1, 0, postArr.length-1);
    }
	public TreeNode buildTrees(int InStart,int InEnd,int PostStart,int PostEnd) {
		if(InStart>InEnd||PostStart>PostEnd) {
			return null;
		}
		int root = postArr[PostEnd];
		int rootIndex = map.get(root);
		TreeNode node = new TreeNode(root);
		node.left = buildTrees(InStart, rootIndex-1, PostStart, PostStart+rootIndex-InStart-1);
		node.right = buildTrees(rootIndex+1, InEnd, PostStart+rootIndex-InStart, PostEnd-1);
		return node;
	}

}

接下来是前序+中序:

其实大部分和前者的思路一致，最主要是边界的求法不同
中序遍历中，我们知道左子树：[inorder_start,index-1], 右子树：[index+1, inorder_end]
在前序遍历中，左子树起始位置为pre_start+1,左子树一共有(index-1 - inorder_start)个，因此左子树：[pre_start+1, pre_start+1 + (index-1 - inorder_start)]
右子树起始位置为左子树终止位置+1，终止位置为pre_end，因此右子树：[ pre_start+1 + (index-1 - inorder_start) + 1, pre_end]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int[] postArr;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postArr = postorder;
		for(int i=0;i<inorder.length;i++) {
			map.put(inorder[i], i);
		}
		return buildTrees(0, inorder.length-1, 0, postArr.length-1);
    }
    public TreeNode buildTrees(int InStart,int InEnd,int PostStart,int PostEnd) {
		if(InStart>InEnd||PostStart>PostEnd) {
			return null;
		}
		int root = postArr[PostEnd];
		int rootIndex = map.get(root);
		TreeNode node = new TreeNode(root);
		node.left = buildTrees(InStart, rootIndex-1, PostStart, PostStart+rootIndex-InStart-1);
		node.right = buildTrees(rootIndex+1, InEnd, PostStart+rootIndex-InStart, PostEnd-1);
		return node;
	}

}

展开全文 >>

目标和

目标和LeetCodeT494

此题可以用dfs和dp两种方案解决，此处先给出dfs的解法
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号+和-。对于数组中的任意一个整数，你都可以从+或-中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

1
2
3
4
5
6
7
8
9
10

解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

解题思路：以题目可知，我们将起点设为nums[0]，sum设为0，我们遍历令sum+nums[i]和sum-num[i]两种方案来实现添加符号，简单的暴力求解代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int count;
    public int findTargetSumWays(int[] nums, int S) {
        dfs(nums, 0, 0, S);
		return count;
    }
    public void dfs(int nums[],int i,int sum,int target) {
		if( i == nums.length ) {
			if(sum == target) {
				count++; 
			}
			return;
		}else {
			dfs(nums, i+1, sum+nums[i], target);
			dfs(nums, i+1, sum-nums[i], target);
		}
	}
}

展开全文 >>

盒子模型

盒子模型:

基本组成部分

水平布局：

元素在其父元素中水平位置由以下几个属性共同决定，从外到内依次为：margin-left,border-left,padding-left,width,padding-right,border-right,margin-right,且其综合必须等于父元素的内容区的宽度.
当不满足时浏览器会自动帮我们填充，填充规则如下：
1.当七个中没有auto情况下，自动调整margin-right来使等式满足
2.七个值中，width，margin-left，margin-right三个值可设为auto
2.1当某一个值为auto时，则自动调整这个auto的值
2.2如果宽度和一个外边距设为auto，宽度会调整为最大，设置的auto外边距会自动为0
2.3如果三个为auto，外边距都是0
2.4两个边距为auto，宽度固定，则元素居中处理

垂直布局：

垂直布局相对较为简单，默认情况下父元素的高度由内容决定。
我们注意一种特殊情况：当子元素在父元素中排列，如果子元素的大小超过了父元素则会造成溢出的情况，我们要在父元素中定义overflow属性来处理溢出的部分。 

1
2
3
4
overflow:visiable//默认值，超出部分不做处理
overflow:hidden//裁剪，超出的部分会直接被裁减
overflow:scroll//生成下右两侧滚动条，不管是否需要
overflow:hidden//根据需要生成滚动条

垂直方向外边距的重叠：

兄弟元素间相邻垂直外边距会取两者的较大值，不会进行叠加。
父子元素之间，相邻垂直外边距子元素会传递给父元素（上外边距），当你想要子元素与父元素之间设置外边距时，若两条边重合则会同步移动，解决：通过在相邻外边距设置边框，使其分开

水平方向外边距的重叠：

此时，水平方向的外边距将会相加，不会取最大值，不会造成外边距的重叠

行内元素的盒子模型：

1.首先行内元素时不支持设置高度和宽度的，默认时内容决定，无法修改。
2.行内元素是可以设置边框边距的，有可能会发生重叠，但不会影响垂直方向上的布局
3.当我们需要对行内元素设置宽高时我们可以设置display属性，将行内元素转换为块元素

1
2
3
4
display : inline//行内元素
display : block// 块元素
display : inline-block//即可以设置宽高，也不会独占一行
display : none//不再显示

盒子的大小：

默认情况下，盒子的可见框是有内容区，内边距，边框共同决定的
我们通过设置box-sizing来改变，可选值有content-box和border-box

1
2
box-sizing : content-box//此时width和height来设置内容区的大小，边框边距会增大盒子大小
box-sizing : border-box//此时宽高来设置整个盒子的大小，width和height为内容区和内边距边框的总大小

轮廓和圆角：

1.outline用来设置元素的轮廓线，用法和border一样，不同的是，轮廓线不会影响布局，可能造成重叠
2.阴影：box-shadow设置阴影效果，默认在元素正下方，不可见，通过设置偏移量来设置偏移效果，格式为box-shadow:xxx xxx xxx xxx 水平偏移量，竖直偏移量，模糊效果，颜色
3.圆角：border-radius:border-top-left-radius,同理类推，可得到四个角的圆角，可以设置曲率半径，当border-radius设置为50%，图形会变成圆形

浮动：

通过浮动可以使一个元素向其父元素的左侧或右侧移动，可以用来设置水平布局
设置float属性：none，默认值不一定，left向左移动，right向右移动。
设置float后的元素脱离文档流：
1.块元素不会再独占一行
2.块元素高度和宽度默认为内容的大小，文档流中，宽度默认为父元素的大小，高度默认为内容大小
3.行内元素脱离之后就会变成浮动的块元素
其中在设置float属性后，在移动过程中，同为float属性的元素移动时不会发生覆盖，将会形成对齐效果

高度塌陷问题：

在布局中父元素的高度默认是被子元素撑开的，当子元素浮动后，其完全脱离文档流，子元素从文档流中脱离将会无法撑起父元素的高度导致父元素高度丢失，丢失后以下元素会自动上移造成页面的混乱，这就叫做高度塌陷的问题。
解决的方案通常有两种，第一将父元素高度定死，但这种做法会造成元素大小无法根据内容变化，可能有大部分留白或者溢出的现象，所以通常不提倡这种做法，那么另一种解决方案设置BFC
那么什么是BFC？
BFC块级格式化区域环境：开启后该元素会变成一个独立的布局区域。
1.开启后BFC的元素不会被浮动元素覆盖
2.开启后BFC的元素和父元素外边距不会重叠（可用来解决上面的垂直方向外边距重叠问题）
3.开启后BFC的元素可以包含浮动的子元素（用来解决高度塌陷问题）
BFC开启的方法：
1.将元素设为浮动
2.将元素设为行内块元素
3.设置overflow将默认值改掉

clear属性：

如果我们不希望某个元素因为其他元素浮动而改变位置，可以通过clear属性来清除浮动元素对当前元素的影响。可选值：left，right，both 

1
2
3
clear：left//清楚左侧浮动元素对当前元素的影响
clear：right//清楚右侧浮动元素对当前元素的影响
clear：both//清楚两侧中影响最大的那个

用after伪类解决高度塌陷问题：

为了解决同时解决高度塌陷和外边距重叠问题，我们有一个模板,clearfix为要修改的类名

1
2
3
4
5
6
.clearfix::before,
.clearfix::after{
    content:'';
    display:table;
    clear:both
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

蛙广志<br><br>总要变强<br>