# CodingInterviews

**Repository Path**: MoTuoCheRiJi/CodingInterviews

## Basic Information

- **Project Name**: CodingInterviews
- **Description**: 剑指offer
- **Primary Language**: Java
- **License**: MulanPSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-03-18
- **Last Updated**: 2021-05-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 每日一道算法题



## 数组



## 链表

### 1.合并两个排序的链表

 问题描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

```
示例1：
    输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4
```

****

```
限制：
	0 <= 链表长度 <= 1000
```

解题思路1：

1. 用虚拟头结点接受合并后的链表

2. 比较两个链表的当前值，将小的放入链表中

3. 最后将排空链表剩余部分挂上


代码实现：

```java
public class MergeTwoLists25 {

    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        ListNode h = new ListNode(-1);
        ListNode cur = h;

        while (l1!=null&&l2!=null){
            if (l1.val<l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1!=null) cur.next = l1;
        if(l2!=null) cur.next = l2;

        return h.next;
    }
}

```

### 2.链表中倒数第k个节点

问题描述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

```
示例：
    给定一个链表: 1->2->3->4->5, 和 k = 2.
    返回链表 4->5.
```

解题思路1：

1. 计算链表的长度len
2. 倒数第k个元素等于正数（len-k）
3. 循环遍历

代码实现：

```java
public class GetKthFromEnd22 {

    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }
   
    public ListNode getKthFromEnd(ListNode head, int k) {

        ListNode cur = head;
        int count = 0;

        while (cur!=null){
            count++;//算出链表的数量
            cur = cur.next;
        }
        ListNode cur1 = head;
        int len = count-k; //倒数第k个元素等于正数（len-k）
        for(int i=0;i<len;i++){
            cur1 = cur1.next;
        }
        return cur1;
    }
}


```

### 3.翻转链表

问题描述：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

```
示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL
```

 解题思路1：双指针迭代

1. 定义两个节点，一个存放当前节点cur
2. 另一个节点存放前一个节点pre
3. 每次迭代到当前节点cur，都将cur的next指向pre
4. pre和cur都前进一位
5. cur迭代完成后，pre就是最后一个节点了

代码实现：

```java
public class ReverseList24 {
    
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
    }

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;//前一个节点
        ListNode cur = head;//当前节点
        ListNode tmp = null;
        while (cur!=null){
            tmp = cur.next;//记录当前节点的下一个节点
            cur.next = pre;//然后将当前节点指向pre
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

```

​	

## 树

### 1.重建二叉树

问题描述：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    例如，给出
    
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树：
                   3
                  / \
                  9  20
                    /  \
                   15   7
                   
    限制：
    0 <= 节点个数 <= 5000
解题思路1：

1. 根据前序遍历的第一个节点确定根节点
2. 根据根节点在中序遍历的位置分割出左右两个子序列
3. 对左子树和右子树分别递归使用同样的方法求解

代码实现：

```java
import java.util.Arrays;

public class BuildTree {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0||inorder.length==0)
            return null;
        TreeNode root = new TreeNode(preorder[0]);
        for(int i=0;i<inorder.length;i++){
            if(preorder[0]==inorder[i]){
                root.left=buildTree(Arrays.copyOfRange(preorder,1,i+1),
                                    Arrays.copyOfRange(inorder,0,i));
				root.right=buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),
                     				Arrays.copyOfRange(inorder,i+1,inorder.length));
                break;
            }

        }
        return root;
    }
}

```

### 2.二叉树的镜像

问题描述：请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

          4	
        /   \
      2     7
     / \   / \
    1   3 6   9
    镜像输出：
    
         4
       /   \
      7     2
     / \   / \
    9   6 3   1
    
    示例 1：
    输入：root = [4,2,7,1,3,6,9]
    输出：[4,7,2,9,6,3,1]
    
    限制：
    0 <= 节点个数 <= 1000
解题思路：

1. 跟节点不为空的时候，交换左右两个子树的位置
2. 遍历完成整个操作

代码实现：

```java
/**
 * 二叉树的镜像
 */
public class MirrorTree {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null)
            return null;

       //左右子树交换位置
       TreeNode node = null;
       node = node.left;
       node.left = node.right;
       node.right = node;

       //递归完成
       mirrorTree(node.left);
       mirrorTree(node.right);

       return root;
    }
}
```

### 3.二叉树的深度

问题描述：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

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

    	 3
     	/ \
      9  20
        /  \
       15   7
         
    返回它的最大深度 3 
    
    提示：
    节点总数 <= 10000
解题思路1：递归实现

代码实现：

```java
public class MaxDepth {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public int maxDepth(TreeNode root) {

        if(root==null)
            return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}
```

解题思路2：用队列实现

1. 层序遍历二分搜索树
2. 在 层序遍历中，每次当队列中某一层节点出队完成后高度+1
3. 在出队之前记录队列中每一次的数量
4. 当次个数减到0的时候,则说明该层节点全部出队完成

代码实现：

```java
public class MaxDepth {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public int maxDepth2(TreeNode root) {
            if(root==null)
                return 0;

            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);

            int size = 0;
            int hight = 0;
            TreeNode node;
            while (!queue.isEmpty()){
                 queue.add(root);
                size = queue.size();//记录一下每一层的数量
                while(size!=0){
                    node= queue.remove();
                    if(node.left!=null) {queue.add(node.left);}
                    if(node.right!=null) {queue.add(node.right);}
                    size--;//当个数减为0时，高度加1
                }
                hight++;
            }
            return hight;
        }
}
```

### 4.平衡二叉树

问题描述：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

 

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    	3
       / \
      9  20
        /  \
       15   7
    返回 true 。
解题思路：递归判断左右子树的高度差是否大于1

代码实现：

```java
/**
 * 判断是否是平衡二叉树
 */
public class IsBalanced {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        if( Math.abs(TreeDepth(root.left)-Math.abs(TreeDepth(root.right)))>1)
            return false;

        return isBalanced(root.left)&&isBalanced(root.right);
    }
    /**
 	* 二叉树的深度
 	*/
    public int TreeDepth(TreeNode node){
        
        if(node==null)
            return 0;

        return Math.max(TreeDepth(node.left),TreeDepth(node.right))+1;
    }
}
```



## 图

问题描述：

解题思路：

代码实现：