基础算法示例和解法

发表于 2019-02-19 更新于 2019-04-23 分类于 java 阅读次数：

正文

最近发现自己基础算法方面还有些欠缺。虽然之前也看过数据结构、算法导论、计算机网络等等一些基础书籍，也都理解基础算法和数据结构，但因为没有每道都手写过，所以当真正去实现时还需要去查阅参考资料。由此，下定决心弥补这些不足。基础算法在工作中对业务理解、代码编写并没有非常显著的提升，但是个人觉得这些影响是潜在的，它会潜在的影响你的思考和解决方案。总之，基础夯实终归是没错的。

目前较为推荐的有牛客的剑指 offer、LeetCode 的 Top 100 Liked Questions。个人更推荐 LeetCode，但是牛客有手机 App，如果想在上下班路上刷一刷，可以选择牛客。我也是因此选择先刷牛客，下面是相关的题目和个人通过编译的答案，不定期更新，如答案中有错误之处烦请指出。

牛客

剑指 offer

链表

JZ6 从尾到头打印链表

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入 {1,2,3} 的链表，返回一个数组为 [3,2,1]

0 <= 链表长度 <= 10000

示例 1
输入: {1,2,3}
返回值: [3,2,1]
示例 2
输入: {67,0,24,58}
返回值: [58,24,0,67]

答案

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/

// 解法1:
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> result = new ArrayList<>();
        if (listNode == null) {
            return result;
        }
        Stack<ListNode> stack = new Stack();
        while (listNode != null) {
            stack.push(listNode);
            listNode = listNode.next;
        }
        while (!stack.empty()) {
            result.add(stack.pop().val);
        }
        return result;
    }
}

JZ24 反转链表

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

给定一个单链表的头结点 pHead，长度为 n，反转该链表后，返回新链表的表头。

数据范围: n≤1000
要求: 空间复杂度 O(1)，时间复杂度 O(n)。

如当输入链表 {1,2,3} 时，
经反转后，原链表变为 {3,2,1}，所以对应的输出为 {3,2,1}。

示例 1
输入: {1,2,3}
返回值: {3,2,1}
示例 2
输入: {}
返回值: {}
说明: 空链表则输出空

答案

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

JZ25 合并两个排序的链表

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

输入两个递增的链表，单个链表的长度为 n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: 0≤n≤1000，−1000≤ 节点值 ≤1000
要求: 空间复杂度 O(1)，时间复杂度 O(n)

如输入 {1,3,5},{2,4,6} 时，合并后的链表为 {1,2,3,4,5,6}，所以对应的输出为 {1,2,3,4,5,6}
输入 {-1,2,4},{1,3,4}时，合并后的链表为 {-1,1,2,3,4,4}，所以对应的输出为 {-1,1,2,3,4,4}

示例 1
输入: {1,3,5},{2,4,6}
返回值: {1,2,3,4,5,6}
示例 2
输入: {},{}
返回值: {}

答案

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode h = new ListNode(-1);
        ListNode cur = h;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null) cur.next = list1;
        if (list2 != null) cur.next = list2;
        return h.next;
    }
}

JZ52 两个链表的第一个公共结点

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

输入描述：
输入分为是 3 段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。后台会将这 3 个参数组装为两个链表，并将这两个链表对应的头节点传入到函数 FindFirstCommonNode 里面，用户得到的输入只有 pHead1 和 pHead2。

示例 1
输入: {1,2,3},{4,5},{6,7}
返回值: {6,7}
说明: 第一个参数 {1,2,3} 代表是第一个链表非公共部分，第二个参数 {4,5} 代表是第二个链表非公共部分，最后的 {6,7} 表示的是 2 个链表的公共部分。这 3 个参数最后在后台会组装成为 2 个两个无环的单链表，且是有公共节点的。
示例 2
输入: {1},{2,3},{}
返回值: {}
说明: 2 个链表没有公共节点 ,返回 null，后台打印 {}

答案

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

// 解法：使用两个指针N1,N2，一个从链表1的头节点开始遍历，我们记为N1，一个从链表2的头节点开始遍历，我们记为N2。
// 让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。
// 因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }
}

JZ23 链表中环的入口结点

时间限制: 1 秒
空间限制: 64M
知识点: 链表哈希双指针

描述

给一个长度为 n 链表，若其中包含环，请找出该链表的环的入口结点，否则，返回 null。

数据范围： n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)

输入描述：
输入分为 2 段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例 1
输入: {1,2},{3,4,5}
返回值: “null”
说明: 没有环，返回对应编程语言的空结点，后台程序会打印 “null”
示例 2
输入: {},{2}
返回值: 2
说明: 环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即 2

答案

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/

// 解法1: 用HashMap (不推荐)
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 使用set来记录出现的结点
        Set<ListNode> set = new HashSet<>();
        while (pHead != null) {
            // 当set中包含结点，说明第一次出现重复的结点，即环的入口结点
            if (set.contains(pHead)) {
                return pHead;
            }
            // set中加入未重复的结点
            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }
}


// 解法2: 用快慢指针
// 在环上的时候快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)-> N-1步。
// 所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 快慢指针
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast != null && fast.next != null) {
            // 快指针是满指针的两倍速度
            fast = fast.next.next;
            slow = slow.next;
            // 记录快慢指针第一次相遇的结点
            if (fast == slow) {
                break;
            }
        }
        // 若是快指针指向null，则不存在环
        if (fast == null || fast.next == null) {
            return null;
        }
        // 重新指向链表头部
        fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

JZ22 链表中倒数最后 k 个结点

时间限制: 1 秒
空间限制: 256M
知识点: 链表

描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第 k 个节点。
如果该链表长度小于 k，请返回一个长度为 0 的链表。

数据范围：0≤n≤10⁵，0≤a_i≤10⁹，0≤k≤10⁹

要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例 1
输入: {1,2,3,4,5},2
返回值: {4,5}
说明：返回倒数第 2 个节点 4，系统会打印后面所有的节点来比较。
示例 2
输入: {2},8
返回值: {}

答案

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

// 解法1: 双指针
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if (pHead == null || k <= 0) {
            return null;
        }
        ListNode cursor1 = pHead;
        ListNode cursor2 = pHead;
        for (int i = 0; i < k; i ++) {
            if (cursor1 == null) {
                return null;
            }
            cursor1 = cursor1.next;
        }
        while (cursor1 != null) {
            cursor1 = cursor1.next;
            cursor2 = cursor2.next;
        }
        return cursor2;
    }
}

// 解法2: 直接遍历
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if (pHead == null) {
            return null;
        }
        int i = 1;
        ListNode cursor = pHead;
        while ((cursor = cursor.next) != null) {
            i ++;
        }
        if (i < k) {
            return null;
        }
        cursor = pHead;
        for (int j = 0; j < i - k; j ++) {
            cursor = cursor.next;
        }
        return cursor;
    }
}

// 解法3: 用栈
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if (pHead == null || k == 0){
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        //链表节点压栈
        while (pHead != null) {
            stack.push(pHead);
            pHead = pHead.next;
        }
        // 判断栈的元素是否小于k
        if (stack.size() < k){
            return null;
        }
        //在出栈串成新的链表
        ListNode firstNode = stack.pop();
        while (--k > 0) {
            // 将出栈的元素重新连接成为链表
            ListNode temp = stack.pop();
            temp.next = firstNode;
            firstNode = temp;
        }
        return firstNode;
    }
}

JZ35 复杂链表的复制

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针 random 指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。下图是一个含有 5 个结点的复杂链表。图中实线箭头表示 next 指针，虚线箭头表示 random 指针。为简单起见，指向 null 的指针没有画出。

示例:
输入: {1,2,3,4,5,3,5,#,2,#}
输出: {1,2,3,4,5,3,5,#,2,#}
解析:我们将链表分为两段，前半部分 {1,2,3,4,5} 为 ListNode，后半部分 {3,5,#,2,#} 是随机指针域表示。
以上示例前半部分可以表示链表为的 ListNode:1->2->3->4->5
后半部分，3，5，#，2，# 分别的表示为 1 的位置指向 3，2 的位置指向 5，3 的位置指向 null，4 的位置指向 2，5 的位置指向 null
如下图:

示例 1
输入: {1,2,3,4,5,3,5,#,2,#}
返回值: {1,2,3,4,5,3,5,#,2,#}

答案

import java.util.*;
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/

// 解法1: 借助map构建
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode cur = pHead;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        while (cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}

// 解法2: 链表拼接、拆分
// 考虑构建 原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }

        // 克隆基础链表
        RandomListNode cur = pHead;
        while (cur != null) {
            RandomListNode clone = new RandomListNode(cur.label);
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }

        // 克隆随机链表
        cur = pHead;
        while (cur != null) {
            cur.next.random = cur.random != null ? cur.random.next : null;
            cur = cur.next.next;
        }

        // 拆分链表
        RandomListNode cloneHead = pHead.next;
        RandomListNode old = pHead;
        RandomListNode clone = cloneHead;
        while (old != null) {
            old.next = clone.next;
            if (old.next != null) {
                clone.next = old.next.next;
            }
            old = old.next;
            clone = clone.next;
        }

        return cloneHead;
    }
}

JZ76 删除链表中重复的结点

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

数据范围：链表长度满足 0≤n≤1000 ，链表中的值满足 1≤val≤1000

进阶：空间复杂度 O(n)，时间复杂度 O(n)

例如输入 {1,2,3,3,4,4,5} 时，对应的输出为 {1,2,5}

示例 1
输入: {1,2,3,3,4,4,5}
返回值: {1,2,5}
示例 2
输入: {1,1,1,8}
返回值: {8}

答案

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
// 解法1: 给链表前加上表头，删除所有重复的节点
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        //在链表前加一个表头
        ListNode res = new ListNode(0);
        res.next = pHead;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            }
            else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }
}

// 解法2: 用HashMap计数

JZ18 删除链表的节点

时间限制: 1 秒
空间限制: 64M
知识点: 链表

描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

1.此题对比原题有改动 2.题目保证链表中节点的值互不相同 3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

数据范围:
0<=链表节点值<=10000
0<=链表长度<=10000

示例 1
输入: {2,5,1,9},5
返回值: {2,1,9}
说明: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9
示例 2
输入: {2,5,1,9},1
返回值: {2,5,9}
说明: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 2 -> 5 -> 9

答案

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 解法: 添加头结点，找到对应节点后退出循环
public class Solution {
    public ListNode deleteNode (ListNode head, int val) {
        // write code here
        // 添加头结点
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while (cur != null) {
            if (cur.next != null && cur.next.val == val) {
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return res.next;
    }
}

树

JZ55 二叉树的深度

时间限制: 1 秒
空间限制: 64M
知识点: 树

描述

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

数据范围：节点的数量满足 0≤n≤100 ，节点上的值满足 0≤val≤100
进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例 1
输入: {1,2,3,4,5,#,6,#,#,7}
返回值: 4
示例 2
输入: {}
返回值: 0

答案

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 解法1: 递归
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
    }
}

JZ77 按之字形顺序打印二叉树

时间限制: 1 秒
空间限制: 64M
知识点: 栈树队列

描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0≤n≤1500,树上每个节点的 val 满足 ∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)
例如：
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是

[
[1],
[3,2],
[4,5]
]

示例 1
输入: {1,2,3,#,#,4,5}
返回值: [[1],[3,2],[4,5]]
示例 2
输入: {8,6,10,5,7,9,11}
返回值: [[8],[10,6],[5,7,9,11]]
示例 3
输入: {1,2,3,4,5}
返回值: [[1],[3,2],[4,5]]

答案

import java.util.*;
import java.util.ArrayList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 解法1: 用链表，一个链表记录当前层，一个链表记录下一层，也可用栈
// 注意: 每次都从后往前遍历，即可翻转，但是第一层节点右节点先入下一层，第二层左节点先，如此反复
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > result = new ArrayList();
        if (pRoot == null) {
            return result;
        }
        ArrayList<TreeNode> layer = new ArrayList<>();
        layer.add(pRoot);
        result.add(new ArrayList<Integer>() {{add(pRoot.val);}});
        while (layer.size() > 0) {
            ArrayList<TreeNode> nextLayer = new ArrayList<>();
            ArrayList<Integer> nextLayerValue = new ArrayList<>();
            if (result.size() % 2 == 1) {
                for (int i = layer.size() - 1; i >= 0; i --) {
                    TreeNode treeNode = layer.get(i);
                    addTreeNode(treeNode.right, nextLayer, nextLayerValue);
                    addTreeNode(treeNode.left, nextLayer, nextLayerValue);
                }
            } else {
                for (int i = layer.size() - 1; i >= 0; i --) {
                    TreeNode treeNode = layer.get(i);
                    addTreeNode(treeNode.left, nextLayer, nextLayerValue);
                    addTreeNode(treeNode.right, nextLayer, nextLayerValue);
                }
            }
            layer = nextLayer;
            if (nextLayerValue.size() > 0) {
                result.add(nextLayerValue);
            }
        }
        return result;
    }

    private void addTreeNode(TreeNode treeNode, ArrayList<TreeNode> nextLayer, ArrayList<Integer> nextLayerValue) {
        if (treeNode != null) {
            nextLayer.add(treeNode);
            nextLayerValue.add(treeNode.val);
        }
    }
}

JZ54 二叉搜索树的第 k 个节点

时间限制: 1 秒
空间限制: 64M
知识点: 树 dfs 递归

描述

给定一棵结点数为 n 二叉搜索树，请找出其中的第 k 小的 TreeNode 结点值。 1.返回第 k 小的节点值即可 2.不能查找的情况，如二叉树为空，则返回-1，或者 k 大于 n 等等，也返回-1 3.保证 n 个节点的值不一样

数据范围：0≤n≤1000，0≤k≤1000，树上每个结点的值满足 0≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)

如输入{5,3,7,2,4,6,8},3时。该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第 3 个结点的结点值为 4，故返回对应结点值为 4 的结点即可。

示例 1
输入: {5,3,7,2,4,6,8},3
返回值: 4
示例 2
输入: {},1
返回值: -1
说明: 当树是空

答案

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 解法1: 递归 用链表存储数据
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param proot TreeNode类
     * @param k int整型
     * @return int整型
     */
    public int KthNode(TreeNode proot, int k) {
        // write code here
        if (proot == null || k < 1) {
            return -1;
        }
        List<Integer> list = new LinkedList<>();
        addNode(list, proot);
        if (k > list.size()) {
            return -1;
        }
        return list.get(k - 1);
    }

    private void addNode(List<Integer> list, TreeNode curNode) {
        if (curNode == null) {
            return;
        }
        addNode(list, curNode.left);
        list.add(curNode.val);
        addNode(list, curNode.right);
    }
}

// 解法2: 递归 计数
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param proot TreeNode类
     * @param k int整型
     * @return int整型
     */
    public int KthNode(TreeNode proot, int k) {
        // write code here
        // 记录返回的节点
        TreeNode[] res = new TreeNode[] {null};
        // 记录中序遍历了多少个
        int[] count = new int[] {0};
        midOrder(res, count, proot, k);
        if (res[0] != null) {
            return res[0].val;
        }
        return -1;
    }

    private void midOrder(TreeNode[] res, int[] count, TreeNode curNode, int k) {
        //当遍历到节点为空或者超过k时，返回
        if (curNode == null || count[0] > k) {
            return;
        }
        midOrder(res, count, curNode.left, k);
        count[0] ++;
        // 只记录第k个
        if (count[0] == k) {
            res[0] = curNode;
        }
        midOrder(res, count, curNode.right, k);
    }
}

JZ7 重建二叉树

时间限制: 1 秒
空间限制: 64M
知识点: 树 dfs 数组

描述

给定节点数为 n 二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin 出现的元素均出现在 pre 里 4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围：n≤2000，节点的值 −10000≤val≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

示例 1
输入: [1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值: {1,2,3,4,#,5,6,#,7,#,#,8}
说明：返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
示例 2
输入: [1],[1]
返回值: {1}
示例 3
输入: [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值: {1,2,5,3,4,6,7}

答案

/**
 算法思想：
 1. 先序遍历第一个位置肯定是根节点node

 2. 中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组

 3. 先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组

 4. 把四个数组找出来，分左右递归调用即可
 */

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// 解法1：
// 每次直接拷贝出对应的四个数组，然后递归调用
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0 || pre.length != in.length){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
            }
        }
        return node;
    }
}

// 解法2：
// 传递原数组、以及数组中对应的开始位置和长度，然后递归调用
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return reConstructBinaryTree(pre, in, 0, 0, pre.length);
    }

    /**
     * 每次都传递原数组的引用，不需要进行数组拷贝，但是要注意：
     *   先序和中序开始的位置是不一样的
     * @param pre 原先序数组
     * @param in 原中序数组
     * @param preBeginIndex 先序数组中开始的索引
     * @param inBeginIndex 中序数组中开始的索引
     * @param length 本次要重建的长度
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in,
                                          int preBeginIndex, int inBeginIndex, int length) {
        // 判断是否越界，以及本次长度是否为0
        if (preBeginIndex < 0 || preBeginIndex + length > pre.length
                || inBeginIndex < 0 || inBeginIndex + length > pre.length || length <= 0) {
            return null;
        }

        // 先序遍历第一个位置肯定是根节点node
        TreeNode root = new TreeNode(pre[preBeginIndex]);
        int rootIndex = preBeginIndex;
        // 左子树的长度
        int leftLength = 0;
        for (int i = inBeginIndex; i < inBeginIndex + length; i ++) {
            if (pre[preBeginIndex] == in[i]) {
                rootIndex = i;
                leftLength = i - inBeginIndex;
                break;
            }
        }
        // 右子树的长度
        int rightLength = length - leftLength - 1;
        root.left = reConstructBinaryTree(pre, in, preBeginIndex + 1, inBeginIndex, leftLength);
        root.right = reConstructBinaryTree(pre, in, preBeginIndex + leftLength + 1, rootIndex + 1, rightLength);
        return root;
    }
}

JZ26 树的子结构

时间限制: 1 秒
空间限制: 64M
知识点: 二叉树树

描述

输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。（我们约定空树不是任意一个树的子结构）
假如给定 A 为{8,8,7,9,2,#,#,#,#,4,7}，B 为{8,9,2}，2 个树的结构如下，可以看出 B 是 A 的子结构

数据范围:
0 <= A 的节点个数 <= 10000
0 <= B 的节点个数 <= 10000

示例 1
输入: {8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
返回值: true
示例 2
输入: {1,2,3,4,5},{2,4}
返回值: true
示例 3
输入: {1,2,3},{3,1}
返回值: false

答案

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 解法1: 双遍历 先遍历A，在每个节点都去去对比B是否是子树
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }

        // 遍历A
        return traverse(root1, root2);
    }

    public boolean traverse(TreeNode root1,TreeNode root2) {
        // A的该节点是空
        if (root1 == null) {
            return false;
        }
        // 和B对比
        if (compare(root1, root2)) {
            return true;
        } else {
            // 遍历A的左右子树
            return traverse(root1.left, root2) || traverse(root1.right, root2);
        }
    }

    private boolean compare(TreeNode root1, TreeNode root2) {
        if (root1 != null) {
            if (root2 == null) {
                return true;
            } else if (root1.val != root2.val) {
                return false;
            } else {
                return compare(root1.left, root2.left) && compare(root1.right, root2.right);
            }
        } else {
            if (root2 == null) {
                return true;
            } else {
                return false;
            }
        }
    }
}

JZ27 二叉树的镜像

时间限制: 1 秒
空间限制: 64M
知识点:

描述

操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 0≤n≤1000 ，二叉树每个节点的值 0≤val≤1000
要求：空间复杂度 O(n)。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n)

比如：
源二叉树

镜像二叉树

示例 1
输入: {8,6,10,5,7,9,11}
返回值: {8,10,6,11,9,7,5}
说明: 如题面所示
示例 2
输入: {}
返回值: {}

答案

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 解法1: 先交换左右子节点，然后遍历子节点交换子节点的左右子节点
public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return null;
        }

        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

// 解法2: 见下图
// 算法流程：一层一层进栈并交换左右节点
public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot == null) return null;
        // 构建辅助栈
        Stack<TreeNode> stack = new Stack<>();
        // 根节点入栈
        stack.add(pRoot);
        while(!stack.isEmpty()) {
            // 节点出栈
            TreeNode node = stack.pop();
            // 根节点的左右子树入栈
            if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            // 左右子树交换
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return pRoot;
    }
}

解法 2

JZ32 从上往下打印二叉树

时间限制: 1 秒
空间限制: 64M
知识点: 队列树

描述

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印 8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

数据范围:
0<=节点总数<=1000
-1000<=节点值<=1000

示例 1
输入: {8,6,10,#,#,2,1}
返回值: [8,6,10,2,1]
示例 2
输入: {5,4,#,3,#,2,#,1}
返回值: [5,4,3,2,1]

答案

import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 解法1: 层次遍历
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        // 返回列表
        ArrayList<Integer> result = new ArrayList<>();
        // 暂存当前层节点
        List<TreeNode> layer = new LinkedList<>();
        layer.add(root);
        while (layer.size() > 0) {
            // 创建当前层缓存
            List<TreeNode> tmp = layer;
            // 新建下一层
            layer = new LinkedList<>();
            for (TreeNode node : tmp) {
                if (node != null) {
                    result.add(node.val);
                    layer.add(node.left);
                    layer.add(node.right);
                }
            }
        }
        return result;
    }
}

JZ33 二叉搜索树的后序遍历序列

时间限制: 1 秒
空间限制: 64M
知识点: 栈树

描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

数据范围：节点数量 0≤n≤1000 ，节点上的值满足 1≤val≤10⁵，保证节点上的值各不相同
要求：空间复杂度 O(n) ，时间时间复杂度 O(n^2)

提示： 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历 4.参考下面的二叉搜索树，示例 1

示例 1
输入: [1,3,2]
返回值: true
说明: 是上图的后序遍历，返回 true
示例 2
输入: [3,1,2]
返回值: false
说明: 不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列，因为最后的 2 一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是 [3,1,2] 的组合都不能满足这些情况，故返回 false
示例 3
输入: [5,7,6,9,11,10,8]
返回值: true

答案

import java.util.*;
// 解法1: 将一个序列划分为3段, 左子树+右子树+根，然后遍历
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int length = sequence.length;
        if (sequence.length <= 0) {
            return false;
        }

        return verify(sequence, 0, length - 1);
    }

    public boolean verify(int[] sequence, int l, int r) {
        // 子树只有一个节点
        if (l >= r) {
            return true;
        }
        // 子树根节点
        int root = sequence[r];

        // 划分右子树
        int j = r - 1;
        while (j >= 0 && sequence[j] > root) {
            j --;
        }

        // 检查左子树是否存在大于根节点的数
        for (int i = l; i <= j; i ++) {
            if (sequence[i] > root) {
                return false;
            }
        }

        return verify(sequence, l, j) && verify(sequence, j + 1, r - 1);
    }
}

JZ82 二叉树中和为某一值的路径(一)

时间限制: 1 秒
空间限制: 64M
知识点: 树 dfs

描述

给定一个二叉树 root 和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为 n

例如：
给出如下的二叉树，sum=22，

返回 true，因为存在一条路径 5→4→11→2 的节点值之和为 22

数据范围： 1.树上的节点数满足 0≤n≤10000 2.每个节点的值都满足 ∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(树的高度)，时间复杂度 O(n)

示例 1
输入: {5,4,8,1,11,#,9,#,#,2,7},22
返回值: true
示例 2
输入: {1,2},0
返回值: false
示例 3
输入: {1,2},3
返回值: true
示例 4
输入: {},0
返回值: false

答案

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
// 解法1: 递归 加法
public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return false;
        }
        return hasPathSum(root, sum, root.val);
    }

    public boolean hasPathSum (TreeNode root, int sum, int res) {
        // 左右子节点都为空才是叶子节点
        if (root.left == null && root.right == null) {
            if (res == sum) {
                return true;
            } else {
                return false;
            }
        } else {
            boolean left = false;
            boolean right = false;
            if (root.left != null) {
                left = hasPathSum(root.left, sum, res + root.left.val);
            }
            if (root.right != null) {
                right = hasPathSum(root.right, sum, res + root.right.val);
            }
            return left || right;
        }
    }
}

// 解法2: 递归 减法
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        //空节点找不到路径
        if (root == null)
            return false;
        //叶子节点，且路径和为sum
        if (root.left == null && root.right == null && sum - root.val == 0)
            return true;
        //递归进入子节点
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

JZ34 二叉树中和为某一值的路径(二)

时间限制: 1 秒
空间限制: 64M
知识点: 树

描述

输入一颗二叉树的根节点 root 和一个整数 expectNumber，找出二叉树中结点值的和为 expectNumber 的所有路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为 n

如二叉树 root 为 {10,5,12,4,7}, expectNumber 为 22

则合法路径有 [[10,5,7],[10,12]]

数据范围:
树中节点总数在范围 [0, 5000] 内
-1000 <= 节点值 <= 1000
-1000 <= expectNumber <= 1000

示例 1
输入: {10,5,12,4,7},22
返回值: [[10,5,7],[10,12]]
说明: 返回 [[10,12],[10,5,7]] 也是对的
示例 2
输入: {10,5,12,4,7},15
返回值: []
示例 3
输入: {2,3},0
返回值: []
示例 4
输入: {1,3,4},7
返回值: []

答案

import java.util.*;
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 解法1: 深度优先搜索 加法
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        ArrayList<Integer> path = new ArrayList<>();
        path.add(root.val);
        findPath(root, expectNumber, root.val, path, result);
        return result;
    }

    private void findPath(TreeNode root, int expectNumber, int sum,
                          ArrayList<Integer> path,
                          ArrayList<ArrayList<Integer>> result) {
        if (root.left == null && root.right == null && sum == expectNumber) {
            result.add(new ArrayList<>(path));
            return;
        }

        if (root.left != null) {
            path.add(root.left.val);
            findPath(root.left, expectNumber, sum + root.left.val, path, result);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            findPath(root.right, expectNumber, sum + root.right.val, path, result);
            path.remove(path.size() - 1);
        }
    }
}

// 解法2: 深度优先搜索 减法
import java.util.*;
public class Solution {
    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        dfs(root, expectNumber);
        return ret;
    }

    private void dfs(TreeNode root, int number) {
        // 处理树为空
        if (root == null) return;
        // 路径更新
        path.add(root.val);
        // number更新
        number -= root.val;
        // 如果递归当前节点为叶子节点且该条路径的值已经达到了expectNumber，则更新ret
        if(root.left == null && root.right == null && number == 0) {
            ret.add(new ArrayList<>(path));
        }
        // 左右子树递归
        dfs(root.left, number);
        dfs(root.right, number);
        path.removeLast();
    }
}

JZ36 二叉搜索树与双向链表

时间限制: 1 秒
空间限制: 64M
知识点: 分治

描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000
要求：空间复杂度 O(1)（即在原树上操作），时间复杂度 O(n)

注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的 TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述：
二叉树的根节点

返回值描述：
双向链表的其中一个头节点。

示例 1
输入: {10,6,14,4,8,12,16}
返回值: From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明: 输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例 2
输入: {5,4,#,3,#,2,#,1}
返回值: From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明:

树的形状如上图

答案

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 方法1: 递归中序遍历
public class Solution {
    //返回的第一个指针，即为最小值，先定为null
    public TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            //中序递归，叶子为空则返回
            return null;
        }
        //首先递归到最左最小值
        Convert(pRootOfTree.left);
        //找到最小值，初始化head与pre
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            //当前节点与上一节点建立连接，将pre设置为当前值
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

// 方法2: 非递归中序遍历 （栈）
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null)
            return null;
        //设置栈用于遍历
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode head = null;
        TreeNode pre = null;
        //确认第一个遍历到最左，即为首位
        boolean isFirst = true;
        while (pRootOfTree != null || !s.isEmpty()) {
            //直到没有左节点
            while (pRootOfTree != null) {
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = s.pop();
            //最左元素即表头
            if (isFirst) {
                head = pRootOfTree;
                pre = head;
                isFirst = false;
            //当前节点与上一节点建立连接，将pre设置为当前值
            } else {
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }
}

JZ79 判断是不是平衡二叉树

时间限制: 1 秒
空间限制: 64M
知识点: 树 dfs

描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
样例解释：

样例二叉树如图，为一颗平衡二叉树
注：我们约定空树是平衡二叉树。

数据范围：n≤100,树上节点的 val 值满足 0≤n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

输入描述：
输入一棵二叉树的根节点

返回值描述：
输出一个布尔类型的值

示例 1
输入: {1,2,3,4,5,6,7}
返回值: true
示例 2
输入: {}
返回值: true

答案

// 方法1: 递归
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) {
            return true;
        }

        return Math.abs(treeDepth(root.left) - treeDepth(root.right)) <= 1
            && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    public int treeDepth(TreeNode root) {
        if (root == null)
            return 0;
        int l = treeDepth(root.left);
        int r = treeDepth(root.right);
        return Math.max(l, r) + 1;
    }
}

JZ8 二叉树的下一个结点

时间限制: 1 秒
空间限制: 64M
知识点: 树

描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的 next 指针。

示例:
输入: {8,6,10,5,7,9,11},8
返回: 9
解析: 这个组装传入的子树根节点，其实就是整颗树，中序遍历 {5,6,7,8,9,10,11}，根节点 8 的下一个节点就是 9，应该返回 {9,10,11}，后台只打印子树的下一个节点，所以只会打印 9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

数据范围：节点数满足 1≤n≤50 ，节点上的值满足 1≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例 1
输入: {8,6,10,5,7,9,11},8
返回值: 9
示例 2
输入: {8,6,10,5,7,9,11},6
返回值: 7
示例 3
输入: {1,2,#,#,3,#,4},4
返回值: 1
示例 4
输入: {5},5
返回值: “null”
说明: 不存在，后台打印”null”

答案

import java.util.*;
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
// 解法1: 递归中序遍历
public class Solution {
    ArrayList<TreeLinkNode> nodes = new ArrayList<>();
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 获取根节点
        TreeLinkNode root = pNode;
        while(root.next != null) root = root.next;

        // 中序遍历打造nodes
        InOrder(root);

        // 进行匹配
        int n = nodes.size();
        for(int i = 0; i < n - 1; i++) {
            TreeLinkNode cur = nodes.get(i);
            if(pNode == cur) {
                return nodes.get(i+1);
            }
        }
        return null;
    }

    // 中序遍历
    void InOrder(TreeLinkNode root) {
        if(root != null) {
            InOrder(root.left);
            nodes.add(root);
            InOrder(root.right);
        }
    }
}

JZ28 对称的二叉树

时间限制: 1 秒
空间限制: 64M
知识点: 树

描述

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：
下面这棵二叉树是对称的

下面这棵二叉树不对称

数据范围：节点数满足 0≤n≤1000，节点上的值满足 ∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
备注：
你可以用递归和迭代两种方法解决这个问题

示例 1
输入: {1,2,2,3,4,4,3}
返回值: true
示例 2
输入: {8,6,9,5,7,7,5}
返回值: false

答案

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        return recursion(pRoot.left, pRoot.right);
    }

    boolean recursion(TreeNode root1, TreeNode root2) {
        // 可以两个都为空
        if (root1 == null && root2 == null) {
            return true;
        }
        // 只有一个为空或者节点值不同，必定不对称
        if (root1 == null  || root2 == null || root1.val != root2.val) {
            return false;
        }
        // 每层对应的节点进入递归比较
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }
}

JZ78 把二叉树打印成多行

时间限制: 1 秒
空间限制: 64M
知识点: 树广度优先搜索(BFS)

描述

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。
例如：
给定的二叉树是 {1,2,3,#,#,4,5}

该二叉树多行打印层序遍历的结果是

[
[1],
[2,3],
[4,5]
]

数据范围：二叉树的节点数 0≤n≤1000，0≤val≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
输入描述：
给定一个二叉树的根节点

示例 1
输入: {1,2,3,#,#,4,5}
返回值: [[1],[2,3],[4,5]]
示例 2
输入: {8,6,10,5,7,9,11}
返回值: [[8],[6,10],[5,7,9,11]]
示例 3
输入: {1,2,3,4,5}
返回值: [[1],[2,3],[4,5]]
示例 4
输入: {}
返回值: []

答案

import java.util.*;
import java.util.ArrayList;


/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
// 解法: 用ArrayList做缓存
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        if (pRoot == null) {
            return res;
        }

        ArrayList<TreeNode> layer = new ArrayList<>();
        layer.add(pRoot);
        while(layer.size() > 0) {
            ArrayList<Integer> values = new ArrayList<>();
            ArrayList<TreeNode> tmp = new ArrayList<>();
            for (TreeNode node : layer) {
                values.add(node.val);
                if (node.left != null) {
                    tmp.add(node.left);
                }
                if (node.right != null) {
                    tmp.add(node.right);
                }
            }
            res.add(values);
            layer = tmp;
        }
        return res;
    }
}

JZ37 序列化二叉树

时间限制: 1 秒
空间限制: 64M
知识点: 队列树

描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果 str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数 Serialize 转化) 如上的二叉树转为 "{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize) 将 "{1,2,3,#,#,6,7}" 构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数 n≤100，树上每个节点的值满足 0≤val≤150
要求：序列化和反序列化都是空间复杂度 O(n)，时间复杂度 O(n)

示例 1
输入: {1,2,3,#,#,6,7}
返回值: {1,2,3,#,#,6,7}
说明: 如题面图
示例 2
输入: {8,6,10,5,7,9,11}
返回值: {8,6,10,5,7,9,11}

答案

// 解法: 前序遍历
import java.util.*;
public class Solution {
    //序列的下标
    public int index = 0;
    //处理序列化的功能函数（递归）
    private void SerializeFunction(TreeNode root, StringBuilder str){
        //如果节点为空，表示左子节点或右子节点为空，用#表示
        if(root == null){
            str.append('#');
            return;
        }
        //根节点
        str.append(root.val).append('!');
        //左子树
        SerializeFunction(root.left, str);
        //右子树
        SerializeFunction(root.right, str);
    }

    public String Serialize(TreeNode root) {
        //处理空树
        if(root == null)
            return "#";
        StringBuilder res = new StringBuilder();
        SerializeFunction(root, res);
        //把str转换成char
        return res.toString();
    }
    //处理反序列化的功能函数（递归）
    private TreeNode DeserializeFunction(String str){
        //到达叶节点时，构建完毕，返回继续构建父节点
        //空节点
        if(str.charAt(index) == '#'){
            index++;
            return null;
        }
        //数字转换
        int val = 0;
        //遇到分隔符或者结尾
        while(str.charAt(index) != '!' && index != str.length()){
            val = val * 10 + ((str.charAt(index)) - '0');
            index++;
        }
        TreeNode root = new TreeNode(val);
        //序列到底了，构建完成
        if(index == str.length())
            return root;
        else
            index++;
        //反序列化与序列化一致，都是前序
        root.left = DeserializeFunction(str);
        root.right = DeserializeFunction(str);
        return root;
    }

    public TreeNode Deserialize(String str) {
        //空序列对应空树
        if(str == "#")
            return null;
        TreeNode res = DeserializeFunction(str);
        return res;
    }
}

JZ84 二叉树中和为某一值的路径(三)

时间限制: 1 秒
空间限制: 64M
知识点: 树

描述

给定一个二叉树 root 和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。 1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点 2.总节点数目为 n 3.保证最后返回的路径个数在整形范围内(即路径个数小于 2³¹-1)

数据范围:
0<=n<=1000
-10^9<=节点值<=10^9

假如二叉树 root 为 {1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有 3 条路径符合要求

示例 1
输入: {1,2,3,4,5,4,3,#,#,-1},6
返回值: 3
说明: 如图所示，有 3 条路径符合
示例 2
输入: {0,1},1
返回值: 2
示例 3
输入: {1,#,2,#,3},3
返回值: 2

答案

// 解法: dfs算法
import java.util.*;
public class Solution {
    private int res = 0;

    // 以每个节点作为根查询路径
    public int FindPath (TreeNode root, int sum) {
        // write code here
        // 为空则返回
        if (root == null) {
            return res;
        }
        // 查询以某节点为根的路径数
        dfs(root, sum);
        // 以其子节点为新根
        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return res;
    }

    // dfs查询以某节点为根的路径数
    private void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        // 符合目标值
        if (sum == root.val) {
            res ++;
        }
        // 节点值可以为负数，所以进入子节点继续寻找
        dfs(root.left, sum - root.val);
        dfs(root.right, sum - root.val);
    }
}

JZ86 在二叉树中找到两个节点的最近公共祖先

时间限制: 1 秒
空间限制: 64M
知识点: 树

描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的 val 值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 1≤n≤10^5, 节点值 val 满足区间 [0,n)
要求：时间复杂度 O(n)

注：本题保证二叉树中每个节点的 val 值均不相同。

如当输入 {3,5,1,6,2,0,8,#,#,7,4},5,1 时，二叉树 {3,5,1,6,2,0,8,#,#,7,4} 如下图所示：

所以节点值为 5 和节点值为 1 的节点的最近公共祖先节点的节点值为 3，所以对应的输出为 3。
节点本身可以视为自己的祖先

示例 1
输入: {3,5,1,6,2,0,8,#,#,7,4},5,1
返回值: 3
示例 2
输入: {3,5,1,6,2,0,8,#,#,7,4},2,7
返回值: 2

答案

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
// 解法: dfs遍历回溯找到两个目标值的路径，再进行路径对比
public class Solution {
    // 记录是否找到o的路径
    private boolean flag = false;

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        ArrayList<Integer> path1 = new ArrayList<>();
        ArrayList<Integer> path2 = new ArrayList<>();
        // 求根节点到o1的路径
        dfs(root, path1, o1);
        // 重置flag
        flag = false;
        // 求根节点到o2的路径
        dfs(root, path2, o2);

        int res = 0;
        // 比较路径，找到最后一个相同点
        for (int i = 0; i < path1.size() && i < path2.size(); i ++) {
            int x = path1.get(i);
            int y = path2.get(i);
            if (x == y) {
                res = x;
            } else {
                break;
            }
        }
        return res;
    }

    private void dfs(TreeNode root, List<Integer> path, int o) {
        if (flag || root == null) {
            return;
        }
        path.add(root.val);
        // 节点的值都不同，可以直接用值比较
        if (root.val == o) {
            flag = true;
            return;
        }
        // dfs遍历查找
        dfs(root.left, path, o);
        dfs(root.right, path, o);
        // 找到
        if (flag) {
            return;
        }
        // 回溯
        path.remove(path.size() - 1);
    }
}

JZ68 二叉搜索树的最近公共祖先

时间限制: 1 秒
空间限制: 64M
知识点: 树递归

描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

对于该题的最近的公共祖先定义:对于有根树 T 的两个节点 p、q，最近公共祖先 LCA(T,p,q)表示一个节点 x，满足 x 是 p 和 q 的祖先且 x 的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

数据范围:
3<=节点总数<=10000
0<=节点值<=10000

如果给定以下搜索二叉树: {7,1,12,0,4,11,14,#,#,3,5}，如下图:

示例 1
输入: {7,1,12,0,4,11,14,#,#,3,5},1,12
返回值: 7
说明: 节点 1 和节点 12 的最近公共祖先是 7
示例 2
输入: {7,1,12,0,4,11,14,#,#,3,5},12,11
返回值: 12
说明: 因为一个节点也可以是它自己的祖先.所以输出 12

答案

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 利用二叉搜索树的性质向下查找即可
public class Solution {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        TreeNode cur = root;
        while(cur != null) {
            if (p < cur.val && q < cur.val) {
                cur = cur.left;
            } else if (p > cur.val && q > cur.val) {
                cur = cur.right;
            } else {
                break;
            }
        }
        return cur.val;
    }
}

队列 & 栈

JZ9 用两个栈实现队列

时间限制: 1 秒
空间限制: 64M
知识点: 栈

描述

用两个栈来实现一个队列，使用 n 个元素来完成 n 次在队列尾部插入整数(push)和 n 次在队列头部删除整数(pop)的功能。队列中的元素为 int 类型。保证操作合法，即保证 pop 操作时队列内已有元素。

数据范围： n≤1000
要求：存储 n 个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)

示例 1

输入: ["PSH1","PSH2","POP","POP"]
返回值: 1,2
说明:
“PSH1”:代表将 1 插入队列尾部
“PSH2”:代表将 2 插入队列尾部
“POP”:代表删除一个元素，先进先出=>返回 1
“POP”:代表删除一个元素，先进先出=>返回 2

示例 2
输入: ["PSH2","POP","PSH1","POP"]
返回值: 2,1

答案

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

JZ30 包含 min 函数的栈

时间限制: 1 秒
空间限制: 64M
知识点: 栈

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：
push(value):将 value 压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

数据范围：操作数量满足 0≤n≤300，输入的元素满足 ∣val∣≤10000
进阶：栈的各个操作的时间复杂度是 O(1)，空间复杂度是 O(n)

示例:
输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出: -1,2,1,-1
解析:
“PSH-1”表示将-1 压入栈中，栈中元素为-1
“PSH2”表示将 2 压入栈中，栈中元素为 2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
“TOP”表示获取栈顶元素==>返回 2
“POP”表示弹出栈顶元素，弹出 2，栈中元素为-1
“PSH1”表示将 1 压入栈中，栈中元素为 1，-1
“TOP”表示获取栈顶元素==>返回 1
“MIN”表示获取此时栈中最小元素==>返回-1

示例 1
输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值: -1,2,1,-1

答案

import java.util.Stack;
// 解法: 维护一个非严格对应的降序最小栈
public class Solution {
    // 用于栈的push 与 pop
    Stack<Integer> s1 = new Stack<Integer>();
    // 用于存储最小min
    Stack<Integer> s2 = new Stack<Integer>();


    public void push(int node) {
        s1.push(node);
        // 空或者新元素小于等于最小值，则入栈
        if (s2.isEmpty() || node <= s2.peek()) {
            s2.push(node);
        }
    }

    public void pop() {
        int v = s1.pop();
        if (s2.peek() == v) {
            s2.pop();
        }
    }

    public int top() {
        return s1.peek();
    }

    public int min() {
        return s2.peek();
    }
}

JZ31 栈的压入、弹出序列

时间限制: 1 秒
空间限制: 64M
知识点: 栈

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

0 <= pushV.length == popV.length <=1000
-1000 <= pushV[i] <= 1000
pushV 的所有数字均不相同

示例 1
输入: [1,2,3,4,5],[4,5,3,2,1]
返回值: true
说明: 可以通过
push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到 [4,5,3,2,1] 这个序列，返回 true
示例 2
输入: [1,2,3,4,5],[4,3,5,1,2]
返回值: false
说明: 由于是 [1,2,3,4,5] 的压入顺序，[4,3,5,1,2] 的弹出顺序，要求 4，3，5 必须在 1，2 前弹出，且 1，2 不能弹出，但是这样压入的顺序，1 又不能在 2 之前弹出，所以无法形成的，返回 false

答案

import java.util.*;
// 解法: 辅助栈模拟出入栈
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int n = pushA.length;
        // 辅助栈
        Stack<Integer> s = new Stack<>();
        // 遍历入栈的下标
        int j = 0;
        // 遍历出栈的数组
        for (int i = 0; i < n; i ++) {
            // 入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.isEmpty() || s.peek() != popA[i])) {
                s.push(pushA[j]);
                j ++;
            }
            // 栈顶等于出栈数组
            if (s.peek() == popA[i]) {
                s.pop();
            } else {
                return false;
            }
        }
        return true;
    }
}

JZ73 翻转单词序列

时间限制: 1 秒
空间限制: 64M
知识点: 字符串双指针

描述

牛客最近来了一个新员工 Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事 Cat 对 Fish 写的内容颇感兴趣，有一天他向 Fish 借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat 对一一的翻转这些单词顺序可不在行，你能帮助他么？

数据范围：1≤n≤100
进阶：空间复杂度 O(n)，时间复杂度 O(n)，保证没有只包含空格的字符串

示例 1
输入: “nowcoder. a am I”
返回值: “I am a nowcoder.”
示例 2
输入: “”
返回值: “”

答案

import java.util.*;
public class Solution {
    public String ReverseSentence(String str) {
        int n = str.length();
        char[] cs = str.toCharArray();
        // 翻转句子
        reverse(cs, 0, n - 1);
        // 翻转每个单词
        for(int i = 0; i < n; i ++) {
            int j = i + 1;
            // 以空格为界找到一个单词
            while(j < n && cs[i] != ' ' && cs[j] != ' ') {
                j ++;
            }
            // 将单词翻转
            reverse(cs, i, j - 1);
            i = j;
        }
        return new String(cs);
    }

    private void reverse(char[] cs, int l, int r) {
        while(l < r) {
            swap(cs, l ++, r --);
        }
    }

    private void swap(char[] cs, int l, int r) {
        char tmp = cs[l];
        cs[l] = cs[r];
        cs[r] = tmp;
    }
}

JZ59 滑动窗口的最大值

时间限制: 1 秒
空间限制: 64M
知识点: 堆双指针队列

描述

给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

例如，如果输入数组 {2,3,4,2,6,2,5,1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4,4,6,6,6,5}；针对数组 {2,3,4,2,6,2,5,1} 的滑动窗口有以下 6 个：{[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

数据范围：1≤size≤n≤10000，数组中每个元素的值满足 ∣val∣≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)

示例 1
输入: [2,3,4,2,6,2,5,1],3
返回值: [4,4,6,6,6,5]
示例 2
输入: [9,10,9,-7,-3,8,2,-6],5
返回值: [10,10,9,8]
示例 3
输入: [1,2,3,4],3
返回值: [3,4]

答案

import java.util.*;
// 解法1: 依次移动窗口
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (size <= 0) {
            return res;
        }
        int maxIndex = -1;
        for (int i = 0; i <= num.length - size; i ++) {
            int r = i + size - 1;
            if (i > maxIndex) {
                maxIndex = findMax(num, i, r);
            } else if (num[r] >= num[maxIndex]) {
                maxIndex = r;
            }
            res.add(num[maxIndex]);
        }
        return res;
    }

    private int findMax(int[] num, int l, int r) {
        int minIndex = l;
        for (int i = l + 1; i <= r; i ++) {
            if (num[i] >= num[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }
}

// 解法2: 用双向队列记递减序列
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        // 这里本不需要这个判断，但是提供的用例和题目中的条件不符
        if (size <= 0 || size > num.length) {
            return res;
        }
        // 双向队列
        ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
        // 遍历第一个窗口
        for (int i = 0; i < size; i ++) {
            addMaxDeque(num, dq, i);
        }
        // 遍历后续元素
        for (int i = 0; i <= num.length - size; i ++) {
            int r = i + size - 1;
            while (!dq.isEmpty() && i > dq.peekFirst()) {
                dq.pollFirst();
            }
            addMaxDeque(num, dq, r);
            res.add(num[dq.peekFirst()]);
        }
        return res;
    }

    private void addMaxDeque(int[] num, ArrayDeque<Integer> dq, int i) {
        while (!dq.isEmpty() && num[dq.peekLast()] <= num[i]) {
            dq.pollLast();
        }
        dq.add(i);
    }
}

搜索算法

JZ53 数字在升序数组中出现的次数

时间限制: 1 秒
空间限制: 64M
知识点: 数组二分

描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)

示例 1
输入: [1,2,3,3,3,3,4,5],3
返回值: 4
示例 2
输入: [1,3,4,5],6
返回值: 0

答案

// 解法1: 二分法
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int index = getIndex(array, k, 0, array.length - 1);
        if (index == -1) {
            return 0;
        }
        int num = 1;
        for (int i = index + 1; i < array.length && array[i] == array[index]; i ++) {
            num ++;
        }
        for (int i = index - 1; i >= 0 && array[i] == array[index]; i --) {
            num ++;
        }
        return num;
    }

    private int getIndex(int[] array, int k, int l, int r) {
        if (l > r) {
            return -1;
        }
        int mid = (r - l) / 2 + l;
        if (array[mid] == k) {
            return mid;
        } else if (array[mid] > k) {
            return getIndex(array, k, l, mid - 1);
        } else {
            return getIndex(array, k, mid + 1, r);
        }
    }
}

// 解法2: 二分法查找目标值加减0.5的数
public class Solution {
    //二分查找
    private int bisearch(int[] data, double k){
        int left = 0;
        int right = data.length - 1;
        //二分左右界
        while(left <= right){
            int mid = (left + right) / 2;
            if(data[mid] < k)
                left = mid + 1;
            else if(data[mid] > k)
                right = mid - 1;
        }
        return left;
    }
    public int GetNumberOfK(int [] array , int k) {
        //分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k
        return bisearch(array, k + 0.5) - bisearch(array, k - 0.5);
    }
}

JZ4 二维数组中的查找

时间限制: 1 秒空间限制: 64M
本题知识点: 数组
题目描述
在一个二维数组 array 中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。
给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤500 ，矩阵中的值满足 0≤val≤10⁹
进阶：空间复杂度 O(1)，时间复杂度 O(n+m)

示例 1
输入: 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值: true
说明：存在 7，返回 true
示例 2
输入: 1,[[2]]
返回值: false
示例 3
输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
说明：不存在 3，返回 false

答案:

public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int row = rows - 1;
        int col = 0;
        while(row >= 0 && col < cols) {
            if (array[row][col] > target) {
                row --;
            } else if (array[row][col] < target) {
                col ++;
            } else {
                return true;
            }
        }
        return false;
    }
}

JZ11 旋转数组的最小数字

时间限制: 1 秒
空间限制: 64M
知识点: 二分

描述

有一个长度为 n 的非降序数组，比如 [1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了 [3,4,5,1,2]，或者 [4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000
要求：空间复杂度：O(1)，时间复杂度：O(logn)

示例 1
输入: [3,4,5,1,2]
返回值: 1
示例 2
输入: [3,100,200,3]
返回值: 3

答案

// 情况1，arr[mid] > target：4 5 6 1 2 3
// arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first ... mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1...last]区间,所以 first = mid + 1

// 情况2，arr[mid] < target:5 6 1 2 3 4
// arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = mid;

// 情况3，arr[mid] == target:
// 如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
// 如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
// 所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。

import java.util.*;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        return solution2(array);
    }

    public int solution1(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        return Arrays.stream(array).min().getAsInt();
    }

    public int solution2(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        int first = 0;
        int last = array.length - 1;
        while (first < last) {
            // 提前退出
            if (array[first] < array[last]) {
                return array[first];
            }
            int mid = (last - first) / 2 + first;
            if (array[mid] > array[last]) {
                first = mid + 1;
            } else if (array[mid] < array[last]) {
                last = mid;
            } else {
                last --;
            }
        }
        return array[first];
    }
}

JZ38 字符串的排列

时间限制: 1 秒
空间限制: 64M
知识点: 字符串递归

描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串 ABC,则输出由字符 A,B,C 所能排列出来的所有字符串 ABC,ACB,BAC,BCA,CBA 和 CAB。

数据范围：n < 10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
输入描述：
输入一个字符串,长度不超过 10,字符只包括大小写字母。

示例 1
输入: “ab”
返回值: ["ab","ba"]
说明: 返回 ["ba","ab"] 也是正确的
示例 2
输入: “aab”
返回值: ["aab","aba","baa"]
示例 3
输入: “abc”
返回值: ["abc","acb","bac","bca","cab","cba"]
示例 4
输入: “”
返回值: []

答案

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> res = new ArrayList<>();
       if (str == null || str.length() == 0) {
           return res;
       }
       // 转换数组
       char[] charStr = str.toCharArray();
       // 按字典序排序
       Arrays.sort(charStr);
       // 标记每个位置的字符是否被使用过
       boolean[] vis = new boolean[str.length()];
       Arrays.fill(vis, false);
       StringBuilder tmp = new StringBuilder();
       // 递归获取
       recursion(res, charStr, tmp, vis);
       return res;
    }

    public void recursion(ArrayList<String> res, char[] str, StringBuilder tmp, boolean[] vis) {
        // 临时字符串满了加入输出
        if (tmp.length() == str.length) {
            res.add(new String(tmp));
            return;
        }
        // 遍历所有元素选取一个加入
        for (int i = 0; i < str.length; i ++) {
            // 如果该元素已经被加入了，则不需要再加入了
            // 当前的元素str[i]与同一层的前一个元素str[i-1]相同
            if  (vis[i] || (i > 0 && str[i - 1] == str[i] && !vis[i - 1])) {
                continue;
            }
            // 标记为使用过
            vis[i] = true;
            // 加入临时字符串
            tmp.append(str[i]);
            recursion(res, str, tmp, vis);
            // 回溯
            vis[i] = false;
            tmp.deleteCharAt(tmp.length() - 1);
        }
    }
}

JZ44 数字序列中某一位的数字

时间限制: 1 秒
空间限制: 64M
知识点: 模拟

描述

数字以 0123456789101112131415… 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。

数据范围：0<=n<=10^9

示例 1
输入: 0
返回值: 0
示例 2
输入: 2
返回值: 2
示例 3
输入: 10
返回值: 1
示例 4
输入: 13
返回值: 1

答案

import java.util.*;
// 解法: 位数减法
// 找规律:
// 小于10的数字一位数，1～9，共9个数字，9位；
// 小于100的数字两位数，10～99，共90个数字，180位；
// 小于1000的数字三位数，100～999，共900个数字，2700位；
// ......
public class Solution {
    public int findNthDigit (int n) {
        // write code here
        // 记录n是几位数
        int digit = 1;
        // 记录当前位数区间的起始数字: 1,10,100...
        long start = 1;
        // 记录当前区间之前总共有多少位数字
        long sum = 9;
        // 将n定位在某个位数的区间中
        while(n > sum) {
            n -= sum;
            start *= 10;
            digit ++;
            sum = 9 * start * digit;
        }
        // 定位n在哪个数字上
        String num = "" + (start + (n - 1) / digit);
        // 定位n在数字的哪一位上
        int index = (n - 1) % digit;
        return (int)(num.charAt(index)) - (int)('0');
    }
}

动态规划

JZ42 连续子数组的最大和

时间限制: 1 秒
空间限制: 64M
知识点: 动态规划贪心

描述

输入一个长度为 n 的整型数组 array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为 1。求所有子数组的和的最大值。
数据范围:

1 2	1 <= n <= 2 * 10^5 -100 <= a[i] <= 100

要求:时间复杂度为 O(n)，空间复杂度为 O(n)
进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

示例 1
输入: [1,-2,3,10,-4,7,2,-5]
返回值: 18
说明: 经分析可知，输入数组的子数组 [3,10,-4,7,2] 可以求得最大和为 18
示例 2
输入: [2]
返回值: 2
示例 3
输入: [-10]
返回值: -10

答案

// 解法: 动态规划，列出状态转移方程
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int lastMax = array[0];
        int max = lastMax;
        for (int i = 1; i < array.length; i ++) {
            lastMax = Math.max(lastMax + array[i], array[i]);
            if (lastMax > max) {
                max = lastMax;
            }
        }
        return max;
    }
}

JZ85 连续子数组的最大和(二)

时间限制: 1 秒
空间限制: 64M
知识点: 贪心动态规划数组双指针

描述

输入一个长度为 n 的整型数组 array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。

子数组是连续的，比如 [1,3,5,7,9] 的子数组有 [1,3]，[3,5,7] 等等，但是 [1,3,7] 不是子数组
如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
该题定义的子数组的最小长度为 1，不存在为空的子数组，即不存在[]是某个数组的子数组
返回的数组不计入空间复杂度计算

数据范围:

1 2	1<=n<=10^5 -100 <= a[i] <= 100

要求:时间复杂度 O(n)，空间复杂度 O(n)
进阶:时间复杂度 O(n)，空间复杂度 O(1)

示例 1
输入: [1,-2,3,10,-4,7,2,-5]
返回值: [3,10,-4,7,2]
说明: 经分析可知，输入数组的子数组 [3,10,-4,7,2] 可以求得最大和为 18，故返回 [3,10,-4,7,2]
示例 2
输入: [1]
返回值: [1]
示例 3
输入: [1,2,-3,4,-1,1,-3,2]
返回值: [1,2,-3,4,-1,1]
说明: 经分析可知，最大子数组的和为 4，有 [4],[4,-1,1],[1,2,-3,4],[1,2,-3,4,-1,1]，故返回其中长度最长的 [1,2,-3,4,-1,1]
示例 4
输入: [-2,-1]
返回值: [-1]
说明: 子数组最小长度为 1，故返回 [-1]

答案

import java.util.*;
// 解法: 动态规划，列出状态转移方程，记录对应状态即可
public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int lastMax = array[0];
        int max = lastMax;
        int lastStartIndex = 0;
        int startIndex = 0;
        int maxIndex = 0;
        for (int i = 1; i < array.length; i ++) {
            int num = array[i];
            // 求最长子串，所以这里是>=
            if (lastMax + num >= num) {
                lastMax += num;
            } else {
                lastMax = num;
                lastStartIndex = i;
            }
            // 求最长子串，所以这里是>=
            if (lastMax >= max) {
                max = lastMax;
                startIndex = lastStartIndex;
                maxIndex = i;
            }
        }
        return Arrays.copyOfRange(array, startIndex, maxIndex + 1);
    }
}

JZ69 跳台阶

时间限制: 1 秒
空间限制: 64M
知识点: 递归动态规划记忆化搜索

描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40
要求：时间复杂度：O(n)，空间复杂度：O(1)

示例 1
输入: 2
返回值: 2
说明: 青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为 2
示例 2
输入: 7
返回值: 21

答案

public class Solution {
    public int jumpFloor(int target) {
        if (target <= 1) {
            return target;
        }
        int c = 1;
        int a = 1;
        int b = 1;
        for (int i = 2; i <= target; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

JZ10 斐波那契数列

时间限制: 1 秒
空间限制: 64M
知识点: 数组动态规划记忆化搜索快速幂递归

描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn) 的解法

示例 1
输入: 4
返回值: 3
示例 2
输入: 1
返回值: 1
示例 3
输入: 2
返回值: 1

答案

public class Solution {
    public int Fibonacci(int n) {
        return solution1(n);
    }

    public int solution1(int n) {
        if (n <= 1) {
            return n;
        }
        int c = 0;
        int a = 0;
        int b = 1;
        for(int i = 2; i <= n; i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public int solution2(int n) {
        int ans[] = new int[n + 1];
        ans[0] = 0;
        ans[1] = 1;
        for(int i=2;i<=n;i++){
            ans[i] = ans[i-1] + ans[i-2];
        }
        return ans[n];
    }

    public int solution3(int n) {
        if (n <= 1) {
            return n;
        }
        return solution2(n - 2) + solution2(n - 1);
    }
}

JZ19 正则表达式匹配

时间限制: 1 秒
空间限制: 64M
知识点: 字符串动态规划递归

描述

请实现一个函数用来匹配包括’.’和’‘的正则表达式。 1.模式中的字符’.’表示任意一个字符 2.模式中的字符’‘表示它前面的字符可以出现任意次（包含 0 次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

数据范围:
1.str 只包含从 a-z 的小写字母。
2.pattern 只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘‘。 3. 0≤str.length≤26 4. 0≤pattern.length≤26

示例 1
输入: “aaa”,”aa”
返回值: true
说明: 中间的可以出现任意次的 a，所以可以出现 1 次 a，能匹配上
示例 2
输入: “aad”,”cad”
返回值: true
说明: 因为这里 c 为 0 个，a 被重复一次， _ 表示零个或多个 a。因此可以匹配字符串 “aad”。
示例 3
输入: “a”,”.“
返回值: true
说明: “.“ 表示可匹配零个或多个（’_’）任意字符（’.’）
示例 4
输入: “aaab”,”aaa*c”
返回值: false

答案

import java.util.*;
import java.util.regex.*;
// 解法1: java中的正则匹配
public class Solution {
    public boolean match (String str, String pattern) {
        // write code here
        return Pattern.matches(pattern, str);
    }
}
// 解法2: 动态规划
// 具体做法：
// step 1：设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）
// step 2： （初始条件） 首先，毋庸置疑，两个空串是直接匹配，因此dp[0][0]=truedp[0][0]=truedp[0][0]=true。然后我们假设str字符串为空，那么pattern要怎么才能匹配空串呢？答案是利用'*'字符出现0次的特性。遍历pattern字符串，如果遇到'*'意味着它前面的字符可以出现0次，要想匹配空串也只能出现0，那就相当于考虑再前一个字符是否能匹配，因此dp[0][i]=dp[0][i−2]dp[0][i] = dp[0][i - 2]dp[0][i]=dp[0][i−2]。
// step 3： （状态转移） 然后分别遍历str与pattern的每个长度，开始寻找状态转移。首先考虑字符不为'*'的简单情况，只要遍历到的两个字符相等，或是pattern串中为'.'即可匹配，因此最后一位匹配，即查看二者各自前一位是否能完成匹配，即dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i−1][j−1]。然后考虑'*'出现的情况：
// 1. pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]：即pattern前一位能够多匹配一位，可以用'*'让它多出现一次或是不出现，因此有转移方程: dp[i][j] = dp[i - 1][j] || dp[i][j - 2]
// 2. 不满足上述条件，只能不匹配，让前一个字符出现0次，dp[i][j] = dp[i][j - 2].
// 原答案: https://blog.nowcoder.net/n/a3d770a390da4683aa6e6a9020d59945
public class Solution {
    public boolean match (String str, String pattern) {
        // write code here
        int n1 = str.length();
        int n2 = pattern.length();
        // dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        // 遍历str每个长度
        for (int i = 0; i <= n1; i ++) {
            // 遍历pattern每个长度
            for (int j = 0; j <= n2; j ++) {
                // 空正则的情况
                if (j == 0) {
                    dp[i][j] = i == 0 ? true : false;
                // 非空的情况下 星号、点号、字符
                } else {
                    // 当前字符不为*，用.去匹配或者字符直接相同
                    if (pattern.charAt(j - 1) != '*') {
                        if (i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    // 当前字符是*
                    } else {
                        if (j >= 2) {
                            dp[i][j] |= dp[i][j - 2];
                        }
                        // 若是前一位为.或者前一位可以与这个数字匹配
                        if (i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')) {
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }
        return dp[n1][n2];
    }
}

JZ71 跳台阶扩展问题

时间限制: 1 秒
空间限制: 64M
知识点: 动态规划递归记忆化搜索

描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶(n 为正整数)总共有多少种跳法。

数据范围：1≤n≤20
进阶：空间复杂度 O(1) ，时间复杂度 O(1)

示例 1
输入: 3
返回值: 4
示例 2
输入: 1
返回值: 1

答案

// 解题思路：
// 设f[i] 表示 当前跳道第 i 个台阶的方法数。那么f[n]就是所求答案。
// 假设现在已经跳到了第 n 个台阶，那么前一步可以从哪些台阶到达呢？
// 如果上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]
// 如果上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]
// 。。。
// 如果上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。已知跳到 第0个台阶的方法数为f[0]
// 那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + ... + f[0]
// 显然初始条件f[0] = f[1] = 1
// 所以我们就可以先求f[2]，然后f[3]...f[n-1]， 最后f[n]

// 解法1：
public class Solution {
    public int jumpFloorII(int n) {
        if (n == 0 || n == 1) return 1;
        int[] f = new int[n+1];
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; ++ i) {
            for (int j = 0; j < i; ++ j) {
                f[i] += f[j];
            }
        }
        return f[n];
    }
}
// 解法2：
// 对于方法一中的：f[n] = f[n-1] + f[n-2] + ... + f[0]
// 那么f[n-1] 为多少呢？
// f[n-1] = f[n-2] + f[n-3] + ... + f[0]
// 所以一合并，f[n] = 2*f[n-1]，初始条件f[0] = f[1] = 1
// 所以可以采用递归，记忆化递归，动态规划，递推。
public class Solution {
    public int jumpFloorII(int n) {
        if (n == 0 || n == 1) return 1;
        int a = 1;
        int b = 1;
        for (int i = 2; i <= n; ++ i) {
            b = a << 1; //  口诀：左移乘2，右移除2
            a = b;
        }
        return b;
    }
};
// 解法3：
// 这时候，你会发现一个规律：
// f[0] = f[1] = 1
// f[2] = 2 = 2<<0 = 1<<1
// f[3] = 4 = 2<<1 = 1<<2
// f[4] = 8 = 2<<2 = 1<<3
public class Solution {
    public int jumpFloorII(int n) {
         if (n == 0 || n == 1) return 1;
         return 1 << (n - 1);
    }
};

JZ70 矩形覆盖

时间限制: 1 秒
空间限制: 64M
知识点: 递归动态规划

描述

我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

数据范围：0≤n≤38
进阶：空间复杂度 O(1)，时间复杂度 O(n)

注意：约定 n == 0 时，输出 0

比如 n=3 时，2*3 的矩形块有 3 种不同的覆盖方法(从同一个方向看):

示例 1
输入: 0
返回值: 0
示例 2
输入: 1
返回值: 1
示例 3
输入: 4
返回值: 5

答案

// 解题思路：
// 因为小矩形长宽是2*1，所以每次新增加的一列，如果竖着放对应的情况与 target 为 n-1 时相同；如果横着放，对应的情况与 target 为 n-2 时相同。所以：f[n] = f[n-1] + f[n-2]
public class Solution {
    public int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int c = 0;
        int a = 1;
        int b = 2;
        for (int i = 3; i <= target; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

JZ63 买卖股票的最好时机(一)

时间限制: 1 秒
空间限制: 64M
知识点: 动态规划贪心

描述

假设你有一个数组 prices，长度为 n，其中 prices[i] 是股票在第 i 天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天 2.如果不能获取到任何利润，请返回 0 3.假设买入卖出均无手续费

数据范围： 0≤n≤10^5, 0≤val≤10^4

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例 1
输入: [8,9,2,5,4,7,1]
返回值: 5
说明: 在第 3 天(股票价格 = 2)的时候买入，在第 6 天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第 2 天买入，第 3 天卖出，这样就亏损 7 了；同时，你也不能在买入前卖出股票。
示例 2
输入: [2,4,1]
返回值: 2
示例 3
输入: [3,2,1]
返回值: 0

答案

import java.util.*;
// 解法: 动态规划
public class Solution {
    public int maxProfit (int[] prices) {
        // write code here
        int n = prices.length;
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2];
        //第一天不持股，总收益为0
        dp[0][0] = 0;
        //第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0];
        //遍历后续每天，状态转移
        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0];
    }
}

JZ47 礼物的最大价值

时间限制: 1 秒
空间限制: 64M
知识点: 动态规划数组

描述

在一个 m * n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输入这样的一个二维数组，

[
[1,3,1],
[1,5,1],
[4,2,1]
]

那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为 12

1 2	0<grid.length≤200 0<grid[0].length≤200

示例 1
输入: [[1,3,1],[1,5,1],[4,2,1]]
返回值: 12

答案

import java.util.*;
// 动态规划
public class Solution {
    public int maxValue (int[][] grid) {
        // write code here
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row + 1][col + 1];
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                // 取左边或者上面最大值加上当前格子的值
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]) + grid[i][j];
            }
        }
        return dp[row][col];
    }
}

JZ48 最长不含重复字符的子字符串

时间限制: 1 秒
空间限制: 64M
知识点: 字符串哈希双指针

描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
数据范围:
s.length≤40000

示例 1
输入: “abcabcbb”
返回值: 3
说明: 因为无重复字符的最长子串是”abc”，所以其长度为 3。
示例 2
输入: “bbbbb”
返回值: 1
说明: 因为无重复字符的最长子串是”b”，所以其长度为 1。
示例 3
输入: “pwwkew”
返回值: 3
说明: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

答案

import java.util.*;
// 解法1: 双指针
public class Solution {
    public int lengthOfLongestSubstring (String s) {
        // write code here
        // 哈希表记录窗口内非重复的字符
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        // 设置窗口左右边界
        char[] cs = s.toCharArray();
        for (int left = 0, right = 0; right < cs.length; right ++) {
            // 窗口右移进入哈希表统计出现次数
            map.merge(cs[right], 1, Integer::sum);
            // 出现次数大于1，则窗口内有重复
            while (map.get(cs[right]) > 1) {
                // 窗口左移，同时减去该字符的出现次数
                map.merge(cs[left ++], -1, Integer::sum);
            }
            // 维护子串长度最大值
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

// 解法2: 动态规划
public class Solution {
    public int lengthOfLongestSubstring (String s) {
        // 哈希表记录窗口内非重复的字符及其下标
        HashMap<Character, Integer> mp = new HashMap<>();
        int res = 0;
        // dp[i]表示以下标i结尾的字符串最长不含重复子串的长度
        int[] dp = new int[s.length() + 1];
        for(int i = 1; i <= s.length(); i++){
            dp[i] = 1;
            // 哈希表中没有，说明不重复
            if(!mp.containsKey(s.charAt(i - 1)))
                //前一个加1
                dp[i] = dp[i - 1] + 1;
            // 遇到重复字符
            else
                dp[i] = Math.min(dp[i - 1] + 1, i - mp.get(s.charAt(i - 1)));
            // 加入哈希表
            mp.put(s.charAt(i - 1), i);
            // 维护最大值
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

JZ46 把数字翻译成字符串

时间限制: 1 秒
空间限制: 64M
知识点: 动态规划

描述

有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0<n≤90
进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例 1
输入: “12”
返回值: 2
说明: 2 种可能的译码结果（”ab” 或”l”）
示例 2
输入: “31717126241541717”
返回值: 192
说明: 192 种可能的译码结果

答案

import java.util.*;
// 解法: 动态规划，需要考虑无法编译的情况
public class Solution {
    public int solve (String nums) {
        // write code here
        // 排除0
        if (nums.equals("0")) {
            return 0;
        }
        int[] dp = new int[nums.length() + 1];
        // 辅助数组初始化为1
        Arrays.fill(dp, 1);
        for (int i = 2; i <= nums.length(); i ++) {
            // 当0的前面部署1或2时，无法译码，0种
            if (nums.charAt(i - 1) == '0' && nums.charAt(i - 2) != '1' && nums.charAt(i - 2) != '2') {
                return 0;
            }
            // 在11-19，21-26之间的情况
            else if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0')
                || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' && nums.charAt(i - 1) < '7')) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[nums.length()];
    }
}

回溯

JZ12 矩阵中的路径

时间限制: 1 秒
空间限制: 64M
知识点: dfs

描述

请设计一个函数，用来判断在一个 n 乘 m 的矩阵中是否存在一条包含某长度为 len 的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如
a b c e
s f c s
a d e e
矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符 b 占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
数据范围：0≤n,m≤20, 1≤len≤25

示例 1
输入: [[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值: true
示例 2
输入: [[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"
返回值:false

答案

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        int row = matrix.length;
        if (row <= 0) {
            return false;
        }
        int col = matrix[0].length;
        if (col <= 0) {
            return false;
        }
        for (int i = 0; i < matrix.length; i ++) {
            for (int j = 0; j < matrix[0].length; j ++) {
                // 记录回溯路径
                boolean[][] path = new boolean[row][col];
                boolean find = findPath(matrix, word, path, 0, i, j);
                if (find) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean findPath(char[][] matrix, String word, boolean[][] path, int start, int i, int j) {
        // 如果已满足则返回
        if (start >= word.length()) {
            return true;
        }
        // 判断边界
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
            return false;
        }
        char c = word.charAt(start);
        // 判断边界
        if (path[i][j] || matrix[i][j] != c) {
            return false;
        }
        path[i][j] = true;
        // 试探往前走
        boolean find = findPath(matrix, word, path, start + 1, i, j - 1)
                || findPath(matrix, word, path, start + 1, i, j + 1)
                || findPath(matrix, word, path, start + 1, i - 1, j)
                || findPath(matrix, word, path, start + 1, i + 1, j);
        // 不满足的时候回退
        if (!find) {
            path[i][j] = false;
        }
        return find;
    }
}

JZ13 机器人的运动范围

时间限制: 1 秒
空间限制: 64M
知识点: 递归

描述

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

数据范围：0≤threshold≤15, 1≤rows,cols≤100

进阶：空间复杂度 O(nm) , 时间复杂度 O(nm)

示例 1
输入: 1,2,3
返回值: 3
示例 2
输入: 0,1,3
返回值: 1
示例 3
输入: 10,1,100
返回值: 29
说明: [0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的
示例 4
输入: 5,10,10
返回值: 21

答案

public class Solution {
    private int count = 0;
    private int[][] dxy = new int[][] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] path = new boolean[rows][cols];
        dfs(threshold, rows, cols, path, 0, 0);
        return count;
    }

    private void dfs(int theshold, int rows, int cols, boolean[][] path, int i, int j) {
        // 判断边界
        if (i < 0 || i >= rows || j < 0 || j >= cols) {
            return;
        }
        // 判断是否走过
        if (path[i][j]) {
            return;
        }
        // 判断是否能进入该格子
        if (!canEnter(theshold, i, j)) {
            return;
        }
        // 更新 path, 并往下走
        path[i][j] = true;
        count ++;
        for (int k = 0; k < 4; k ++) {
            dfs(theshold, rows, cols, path, i + dxy[k][0], j + dxy[k][1]);
        }
    }

    private boolean canEnter(int theshold, int row, int col) {
        return getBitSum(row) + getBitSum(col) <= theshold;
    }

    private int getBitSum(int num) {
        int res = 0;
        while (num > 0) {
            res += num % 10;
            num /= 10;
        }
        return res;
    }
}

排序

JZ3 数组中重复的数字

时间限制: 1 秒
空间限制: 64M
知识点: 数组

描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000
进阶：时间复杂度 O(n) ，空间复杂度 O(n)

示例 1
输入: [2,3,1,0,2,5,3]
返回值: 2
说明: 2或3都是对的

答案

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        Map<Integer, Integer> tmp = new HashMap<>();
        for (int num : numbers) {
            int count = tmp.merge(num, 1, Integer::sum);
            if (count > 1) {
                return num;
            }
        }
        return -1;
    }
}

JZ51 数组中的逆序对

时间限制: 1 秒
空间限制: 64M
知识点: 数组

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P mod 1000000007

数据范围：对于 50% 的数据, size≤10^4
对于 100% 的数据, size≤10^5
数组中所有数字的值满足 0≤val≤10^9

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

输入描述：题目保证输入的数组中没有的相同的数字

示例 1
输入: [1,2,3,4,5,6,7,0]
返回值: 7
示例 2
输入: [1,2,3]
返回值: 0

答案

public class Solution {
    int count = 0;

    public int InversePairs(int[] array) {
        // 长度小于2则无逆序对
        if (array.length < 2)
            return 0;
        // 进入归并
        mergeSort(array, 0, array.length - 1);
        return count;
    }

    public void mergeSort(int[] array, int left, int right) {
        // 找分割点
        int mid = left + (right - left) / 2;
        if (left < right) {
            // 左子数组
            mergeSort(array, left, mid);
            // 右子数组
            mergeSort(array, mid + 1, right);
            // 并
            merge(array, left, mid, right);
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr = new int[right - left + 1];
        // 临时数组的下标起点
        int c = 0;
        // 保存在原数组的起点下标值
        int s = left;
        // 左子数组的起始指针
        int l = left;
        // 右子数组的起始指针
        int r = mid + 1;
        while (l <= mid && r <= right) {
            // 当左子数组的当前元素小的时候，跳过，无逆序对
            if (array[l] <= array[r]) {
                // 放入临时数组
                // 临时数组下标+1
                // 左子数组指针右移
                arr[c++] = array[l++];
            } else { // 否则，此时存在逆序对
                // 放入临时数组
                // 临时数组+1
                // 右子数组的指针右移
                arr[c++] = array[r++];
                // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
                count += mid + 1 - l;
                count %= 1000000007;
            }
        }

        // 左子数组还有元素时，全部放入临时数组
        while (l <= mid)
            arr[c++] = array[l++];
        // 右子数组还有元素时，全部放入临时数组
        while (r <= right)
            arr[c++] = array[r++];
        // 将临时数组中的元素放入到原数组的指定位置
        for (int num : arr) {
            array[s++] = num;
        }
    }
}

// 解法2 暴力解法
public class Solution {
    public int InversePairs2(int [] array) {
        long res = 0;
        int length = array.length;
        for (int start = length - 2; start >= 0; start --) {
            int dp = 0;
            for (int i = start + 1; i < length; i ++) {
                if (array[start] > array[i]) {
                    dp ++;
                }
            }
            res += dp;
        }
        return (int) (res % 1000000007);
    }
}

JZ40 最小的K个数

时间限制: 1 秒
空间限制: 64M
知识点: 堆排序分治

描述

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0≤k,n≤10000，数组中每个数的大小 0≤val≤1000
要求：空间复杂度 O(n) ，时间复杂度 O(nlogk)

示例 1
输入: [4,5,1,6,2,7,3,8],4
返回值: [1,2,3,4]
说明: 返回最小的4个数即可，返回 [1,3,2,4] 也可以
示例 2
输入: [1],0
返回值: []
示例 3
输入: [0,1,2,1,2],3
返回值: [0,1,1]

答案

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((n1, n2) -> n2 - n1);
        for (int num : input) {
            queue.offer(num);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return new ArrayList<>(queue);
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k <= 0) {
            return new ArrayList<>();
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((n1, n2) -> n2 - n1);
        for (int num : input) {
            if (queue.size() < k) {
                queue.offer(num);
            } else if (num < queue.peek()) {
                queue.poll();
                queue.offer(num);
            }
        }
        return new ArrayList<>(queue);
    }
}

JZ41 数据流中的中位数

时间限制: 1 秒
空间限制: 64M
知识点: 排序堆

描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 1≤n≤1000, 大小满足 1≤val≤1000
进阶：空间复杂度 O(n), 时间复杂度 O(nlogn)

示例 1
输入: [5,2,3,4,1,6,7,0,8]
返回值: “5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 “
说明: 数据流里面不断吐出的是5,2,3…,则得到的平均数分别为5,(5+2)/2,3…
示例 2
输入: [1,1,1]
返回值: “1.00 1.00 1.00 “

答案

// 解法1
// 插入排序法
import java.util.*;
public class Solution {
    private List<Integer> val = new ArrayList<Integer>();

    public void Insert(Integer num) {
        int i = 0;
        // 遍历找到插入点
        for (; i < val.size(); i++) {
            if (num <= val.get(i)) {
                break;
            }
        }
        // 插入相应位置
        val.add(i, num);
    }

    public Double GetMedian() {
        int n = val.size();
        if (n % 2 == 1) {
            // 奇数个数字
            return (double) val.get(n / 2);
        } else {
            // 偶数个数字
            return (val.get(n / 2) + val.get(n / 2 - 1)) / 2.0;
        }
    }
}


// 解法2
// 堆排序
import java.util.*;
public class Solution {
    // 小顶堆，元素数值都比大顶堆大
    private PriorityQueue<Integer> max = new PriorityQueue<>();
    // 大顶堆，元素数值较小 
    private PriorityQueue<Integer> min = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1)); 
    // 维护两个堆，取两个堆顶部即与中位数相关
    public void Insert(Integer num) {
        // 先加入较小部分
        min.offer(num);
        // 将较小部分的最大值取出，送入到较大部分
        max.offer(min.poll());  
        // 平衡两个堆的数量
        if (min.size() < max.size()) {
            min.offer(max.poll());
        }
    }

    public Double GetMedian() {
        if (min.size() > max.size()) {
            //奇数个
            return (double) min.peek();
        } else {
            //偶数个
            return (double) (min.peek() + max.peek()) / 2;
        }
    }
}

答案

import java.util.*;
public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        // 首先对所有数字进行异或运算，得到两个只出现一次的数字的异或结果
        int xorResult = 0;
        for (int num : array) {
            xorResult ^= num;
        }

        // 找到异或结果中第一个为 1 的位，该位表示两个只出现一次的数字在该位上不同
        int bit = 1;
        while ((bit & xorResult) == 0) {
            bit <<= 1;
        }

        // 根据该位是否为 1，将原数组分成两个子数组
        int a = 0, b = 0;
        for (int num : array) {
            if ((num & bit) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        // 按非降序排列
        return a < b ? new int[] {a, b} : new int[] {b, a};
    }
}

JZ64 求1+2+3+…+n

时间限制: 1 秒
空间限制: 64M
知识点: 基础数学

描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

数据范围： 0<n≤200
进阶：空间复杂度 O(1) ，时间复杂度 O(n)

示例 1
输入: 5
返回值: 15
示例 2
输入: 1
返回值: 1

答案

public class Solution {
    public int Sum_Solution(int n) {
        // 通过与运算判断n是否为正数，以结束递归
        boolean flag = (n > 1) && ((n += Sum_Solution(n - 1)) > 0);
        return n;
    }
}

模拟

JZ29 顺时针打印矩阵

时间限制: 1 秒
空间限制: 64M
知识点: 数组

描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：

[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]

则依次打印出数字
[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
数据范围:
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

示例 1
输入: [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
返回值: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
示例 2
输入: [[1,2,3,1],[4,5,6,1],[4,5,6,1]]
返回值: [1,2,3,1,1,1,6,5,4,4,5,6]

答案

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        // 排除空矩阵
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList<>();
        }
        // 矩阵总行数
        int m = matrix.length;
        // 矩阵总列数
        int n = matrix[0].length;
        // 四个边界
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        // 结果集
        ArrayList<Integer> res = new ArrayList<>();
        while (left <= right && top <= bottom) {
            // 打印上边界
            for (int j = left; j <= right; j++) {
                res.add(matrix[top][j]);
            }
            // 打印右边界
            for (int i = top + 1; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            // 判断是否需要打印下边界和左边界
            if (left < right && top < bottom) {
                // 打印下边界
                for (int j = right - 1; j >= left; j--) {
                    res.add(matrix[bottom][j]);
                }
                // 打印左边界
                for (int i = bottom - 1; i > top; i--) {
                    res.add(matrix[i][left]);
                }
            }
            // 扩展边界
            left++;
            right--;
            top++;
            bottom--;
        }
        return res;
    }
}

JZ61 扑克牌顺子

时间限制: 1 秒
空间限制: 64M
知识点: 模拟

描述

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：

A为1，J为11，Q为12，K为13，A不能视为14
大、小王为 0，0可以看作任意牌
如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

要求：空间复杂度 O(1)，时间复杂度 O(nlogn)，本题也有时间复杂度 O(n) 的解法
输入描述：
输入五张扑克牌的值
返回值描述：
五张扑克牌能否组成顺子。

示例 1
输入: [6,0,2,0,4]
返回值: true
说明: 中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4] 这样这五张牌在 [2,6] 区间连续，输出true
示例 2
输入: [0,3,2,6,4]
返回值: true
示例 3
输入: [1,0,0,1,0]
返回值: false
示例 4
输入: [13,12,11,0,1]
返回值: false

答案

import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        Arrays.sort(numbers);
        int n = numbers.length;
        int min = numbers[0];
        int max = numbers[n - 1];
        int p = 0;
        while (min == 0 && p < n) {
            p ++;
            min = numbers[p];
        }
        int zeroNum = p;
        int gap = max - min - (n - p) + 1;
        int last = min;
        for (int i = p + 1; i < n; i++) {
            if (numbers[i] == last) {
                return false;
            }
            last = numbers[i];
        }
        return zeroNum >= gap;
    }
}

JZ67 把字符串转换成整数(atoi)

时间限制: 1 秒
空间限制: 64M
知识点: 字符串

描述

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:

若干空格
（可选）一个符号字符（’+’ 或 ‘-‘）
数字，字母，符号，空格组成的字符串表达式
若干空格

转换算法如下:

去掉无用的前导空格
第一个非空字符为+或者-号时，作为该整数的正负号，如果没有符号，默认为正数
判断整数的有效部分：
1. 确定符号位之后，与之后面尽可能多的连续数字组合起来成为有效整数数字，如果没有有效的整数部分，那么直接返回0
2. 将字符串前面的整数部分取出，后面可能会存在存在多余的字符(字母，符号，空格等)，这些字符可以被忽略，它们对于函数不应该造成影响
3. 整数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231的整数应该被调整为 −231 ，大于 231 − 1 的整数应该被调整为 231 − 1
去掉无用的后导空格

数据范围:
1.0 <=字符串长度<= 100
2.字符串由英文字母（大写和小写）、数字（0-9）、’ ‘、’+’、’-‘ 和 ‘.’ 组成

示例 1
输入: “82”
返回值: 82
示例 2
输入: “ -12 “
返回值: -12
说明: 去掉前后的空格，为-12
示例 3
输入: “4396 clearlove”
返回值: 4396
说明: 6后面的字符不属于有效的整数部分，去除，但是返回前面提取的有效部分
示例 4
输入: “clearlove 4396”
返回值: 0
示例 5
输入: “-987654321111”
返回值: -2147483648

答案

import java.util.*;
public class Solution {
    public int StrToInt(String str) {
        // 处理空字符串的情况
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        int index = 0;
        int sign = 1; // 符号，默认为正数
        int result = 0;
        
        // 跳过前导空格
        while (index < str.length() && str.charAt(index) == ' ') {
            index++;
        }
        
        // 判断符号位
        if (index < str.length() && (str.charAt(index) == '+' || str.charAt(index) == '-')) {
            sign = (str.charAt(index) == '-') ? -1 : 1;
            index++;
        }
        
        // 逐个字符转换为数字，并计算结果
        while (index < str.length()) {
            char c = str.charAt(index);
            // 判断是否为合法数字字符
            if (c < '0' || c > '9') {
                break; // 非法字符，跳出循环
            }
            // 计算当前位的数字
            int digit = c - '0';
            
            // 判断是否溢出
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            
            // 更新结果
            result = result * 10 + digit;
            index++;
        }
        
        return result * sign;
    }
}

JZ20 表示数值的字符串

时间限制: 1 秒
空间限制: 64M
知识点: 字符串

描述

请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。

科学计数法的数字(按顺序）可以分成以下几个部分:

若干空格
一个整数或者小数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数(可正可负)
若干空格

小数（按顺序）可以分成以下几个部分：

若干空格
（可选）一个符号字符（’+’ 或 ‘-‘）
可能是以下描述格式之一:
1. 至少一位数字，后面跟着一个点 ‘.’
2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
3. 一个点 ‘.’ ，后面跟着至少一位数字
若干空格

整数（按顺序）可以分成以下几个部分：

若干空格
（可选）一个符号字符（’+’ 或 ‘-‘)
至少一位数字
若干空格

例如，字符串 ["+100","5e2","-123","3.1416","-1E-16"] 都表示数值。
但是 ["12e","1a3.14","1.2.3","+-5","12e+4.3"] 都不是数值。

提示:
1.1 <= str.length <= 25
2.str 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-‘ ，空格 ‘ ‘ 或者点 ‘.’ 。
3.如果怀疑用例是不是能表示为数值的，可以使用python的print(float(str))去查看
进阶：时间复杂度 O(n) ，空间复杂度 O(n)

示例 1
输入: “123.45e+6”
返回值: true
示例 2
输入: “1.2.3”
返回值: false
说明:
示例 3
输入: “.”
返回值: false
示例 4
输入: “ .2 “
返回值: true

答案

/**
 * 解法1: 正则表达式
 */
import java.util.*;
import java.util.regex.Pattern;
public class Solution {
    public boolean isNumeric (String str) {
        // ^ 表示开头 $ 表示结尾  java中两个\\ 代表一个\
        // * 零次或多次匹配前面的字符或子表达式
        // ？零次或一次匹配前面的字符或子表达式
        // + 一次或多次匹配前面的字符或子表达式
        // [] 字符集。匹配包含的任一字符
        // (?: )匹配 pattern 但不捕获该匹配的子表达式，即它是一个非捕获匹配
        String p = "^[+-]?(\\d*\\.\\d+|\\d+(\\.\\d*)?)(?:[eE][+-]?\\d+)?$";
        return Pattern.matches(p, str.trim());
    }
}

/**
 * 解法2
 * 通过定义状态和状态转移规则，逐个字符地检查字符串是否符合数值的规则。
 */
import java.util.*;
public class Solution {
    public boolean isNumeric(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        
        char[] cs = str.toCharArray();
        int index = 0;
        int len = cs.length;
        
        // 跳过前导空格
        while (index < len && cs[index] == ' ') {
            index++;
        }
        
        // 判断符号位
        if (index < len && (cs[index] == '+' || cs[index] == '-')) {
            index++;
        }
        
        boolean isNum = false;
        
        // 处理数字部分
        while (index < len && Character.isDigit(cs[index])) {
            index++;
            isNum = true;
        }
        
        // 处理小数部分
        if (index < len && cs[index] == '.') {
            index++;
            
            // 小数点后面可以没有数字
            while (index < len && Character.isDigit(cs[index])) {
                index++;
                isNum = true;
            }
        }
        
        // 处理指数部分
        if (isNum && index < len && (cs[index] == 'e' || cs[index] == 'E')) {
            index++;
            
            // 指数部分可以有符号位
            if (index < len && (cs[index] == '+' || cs[index] == '-')) {
                index++;
            }
            
            // 指数部分必须有数字
            if (index < len && Character.isDigit(cs[index])) {
                while (index < len && Character.isDigit(cs[index])) {
                    index++;
                }
            } else {
                return false;
            }
        }
        
        // 跳过尾部空格
        while (index < len && cs[index] == ' ') {
            index++;
        }
        
        return isNum && index == len;
    }
}

答案

// 解法1
// https://blog.nowcoder.net/n/70f76c242e4b4c0ab0aa25ed64eb3b79
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count = 0, bitNum = 1, high = n / 10, cur = n % 10, low = 0;
        // cur遍历n每一数位
        while (cur != 0 || high != 0) {
            if (cur < 1) {
                // case 1: cur == 0
                // cur=0时，高位需要减去一位用于低位进行计算
                // 相当于 count = (high - 1) * bitNum + (99 + 1)
                count += high * bitNum;
            } else if (cur == 1) {
                // case 2: cur == 1
                // 相当于高位+低位计算结果，即(high * bitNum) + (low + 1)
                count += high * bitNum + low + 1;
            } else {
                // case3: cur > 1
                // 相对于cur=0的情况，就不需要高位减去一位来计算低位的结果数了
                // 相当于(high * bitNum) + (低位数结果数)
                count += (high + 1) * bitNum;
            }
            // low、cur、high都像左偏移一个位
            // bitNum表示cur的数位
            low += cur * bitNum;
            cur = high % 10;
            high = high / 10;
            bitNum = bitNum * 10;
        }
        return count;
    }
}

JZ45 把数组排成最小的数

时间限制: 1 秒
空间限制: 64M
知识点: 数组贪心排序

描述

输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组 [3，32，321] ，则打印出这三个数字能排成的最小数字为321323。

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

数据范围:
0<=len(numbers)<=100

示例 1
输入: [11,3]
返回值: “113”
示例 2
输入: []
返回值: “”
示例 3
输入: [3,32,321]
返回值: “321323”

答案

import java.util.*;
public class Solution {
    public String PrintMinNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        
        // 将数字转换为字符串数组
        String[] nums = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            nums[i] = String.valueOf(numbers[i]);
        }
        
        // 自定义比较规则
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                String order1 = s1 + s2;
                String order2 = s2 + s1;
                return order1.compareTo(order2);
            }
        };
        
        // 使用自定义比较规则对字符串数组进行排序
        Arrays.sort(nums, comparator);
        
        // 拼接排序结果
        StringBuilder sb = new StringBuilder();
        for (String num : nums) {
            sb.append(num);
        }
        
        return sb.toString();
    }
}

JZ49 丑数

时间限制: 1 秒
空间限制: 64M
知识点: 基础数学二分

描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围： 0≤n≤2000
要求：空间复杂度 O(n) ，时间复杂度 O(n)

示例 1
输入: 7
返回值: 8

答案

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        // 1 2 3 4 5 6 8
        if (index <= 6) {
            return index;
        }
        // 三个变量，用于指向arr中存放的最大丑数下标，也是 2 3 5 乘的次数
        int i2 = 0, i3 = 0, i5 = 0;
        int[] res = new int[index];
        // 第一个丑数为 1
        res[0] = 1;

        for (int i = 1; i < index; i++) {
            // 得到下一个丑数，三者中最小的
            res[i] = Math.min(res[i2] * 2, Math.min(res[i3] * 3, res[i5] * 5));
            // 第一次是 2、3、5比较，得到最小的是2
            // 第二次是 4、3、5比较，为什么是4了呢？因为上次2已经乘了一次了，所以接下去可以放的丑数在4、3、5之间
            // 所以开头的三个指针就是来的
            if (res[i] == res[i2] * 2)
                i2++;
            if (res[i] == res[i3] * 3)
                i3++;
            if (res[i] == res[i5] * 5)
                i5++;
        }
        return res[index - 1];
    }
}

JZ74 和为S的连续正数序列

时间限制: 1 秒
空间限制: 64M
知识点: 穷举

描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

数据范围： 0<n≤100
进阶：时间复杂度 O(n)
返回值描述：
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

示例 1
输入: 9
返回值: [[2,3,4],[4,5]]
示例 2
输入: 0
返回值: []

答案

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        // 返回结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 回溯窗口
        LinkedList<Integer> track = new LinkedList<>();
        int nSum = 0;
        for (int i = 1; i <= sum / 2 + 3; i++) {
            if (nSum == sum && track.size() > 1) { // 满足条件
                res.add(new ArrayList<>(track));
            } else if (nSum > sum) { // 需要回溯窗口
                while (nSum >= sum) {
                    int num = track.removeFirst();
                    nSum -= num;
                    if (nSum == sum && track.size() > 1) { // 回溯之后满足条件
                        res.add(new ArrayList<>(track));
                    }
                }
            }
            // 把当前数加到窗口
            track.add(i);
            nSum += i;
        }
        return res;
    }
}

JZ57 和为S的两个数字

时间限制: 1 秒
空间限制: 64M
知识点: 数学数组双指针

描述

输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围: 0≤len(array)≤10^5, 1≤array[i]≤10^6

示例 1
输入: [1,2,4,7,11,15],15
返回值: [4,11]
说明: 返回 [4,11] 或者 [11,4] 都是可以的
示例 2
输入: [1,5,11],10
返回值: []
说明: 不存在，返回空数组
示例 3
输入: [1,2,3,4],5
返回值: [1,4]
说明: 返回 [1,4],[4,1],[2,3],[3,2] 都是可以的
示例 4
输入: [1,2,2,4],4
返回值: [2,2]

答案

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList<>();
        if (array.length <= 1 || sum < 1) {
            return res;
        }
        // 双指针
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int leftNum = array[left];
            int rightNum = array[right];
            int nSum = leftNum + rightNum;
            if (nSum == sum) {
                res.add(leftNum);
                res.add(rightNum);
                break;
            } else if (nSum > sum) {
                right --;
            } else {
                left ++;
            }
        }
        return res;
    }
}

JZ58 左旋转字符串

时间限制: 1 秒
空间限制: 64M
知识点: 字符串

描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”

数据范围：输入的字符串长度满足 0≤len≤100, 0≤n≤100
进阶：空间复杂度 O(n) ，时间复杂度 O(n)

示例 1
输入: “abcXYZdef”,3
返回值: “XYZdefabc”
示例 2
输入: “aab”,10
返回值: “aba”

答案

public class Solution {
    public String LeftRotateString(String str,int n) {
        // 不需要位移
        if (str == null || str.length() <= 1) {
            return str;
        }
        // 需要位移的数量
        int rotateNum = n % str.length();
        // 不需要位移
        if (rotateNum == 0) {
            return str;
        }
        return str.substring(rotateNum) + str.substring(0, rotateNum);
    }
}

JZ62 孩子们的游戏(圆圈中最后剩下的数)

时间限制: 1 秒
空间限制: 64M
知识点: 基础数学

描述

每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0… m-1报数….这样下去….直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

数据范围： 1≤m≤10000
要求：空间复杂度 O(1)，时间复杂度 O(n)

示例 1
输入: 5,3
返回值: 3
示例 2
输入: 2,3
返回值: 1
说明: 有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友，0号小朋友出圈，1号小朋友得到礼物
示例 3
输入: 10,17
返回值: 2

答案

public int LastRemaining_Solution(int n, int m) {
    if (n <= 0 || m <= 0) {
        return -1;
    }

    int lastRemaining = 0;
    for (int i = 2; i <= n; i++) {
        lastRemaining = (lastRemaining + m) % i;
    }

    return lastRemaining;
}

JZ75 字符流中第一个不重复的字符

时间限制: 1 秒
空间限制: 64M
知识点: 字符串

描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g” 。当从该字符流中读出前六个字符 “google” 时，第一个只出现一次的字符是”l”。

数据范围：字符串长度满足 1≤n≤1000 ，字符串中出现的字符一定在 ASCII 码内。
进阶：空间复杂度 O(n) ，时间复杂度 O(n)

后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数

string caseout = “”;
1.读入测试用例字符串casein
2.如果对应语言有Init()函数的话，执行Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
4.输出caseout，进行比较。

返回值描述：
如果当前字符流没有存在出现一次的字符，返回#字符。

示例 1
输入: “google”
返回值: “ggg#ll”
示例 2
输入: “abcdee”
返回值: “aaaaaa”

答案

// 解法： 哈希表+队列
import java.util.*;
public class Solution {
    Map<Character, Integer> chCountMap = new HashMap<>();
    LinkedList<Character> singleList = new LinkedList<>();
    //Insert one char from stringstream
    public void Insert(char ch) {
        int count = chCountMap.merge(ch, 1, Integer::sum);
        if (count == 1) {
            singleList.add(ch);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        while (singleList.size() > 0) {
            char ch = singleList.getFirst();
            if (chCountMap.get(ch) == 1) {
                return ch;
            }
            singleList.removeFirst();
        }
        return '#';
    }
}

JZ14 剪绳子

时间限制: 1 秒
空间限制: 64M
知识点: 基础数学

描述

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

数据范围： 2≤n≤60
进阶：空间复杂度 O(1) ，时间复杂度 O(n)
输入描述：
输入一个数n，意义见题面。
返回值描述：
输出答案。

示例 1
输入: 8
返回值: 18
说明: 8 = 2 +3 +3 , 233=18
示例 2
输入: 2
返回值: 1
说明: m>1，所以切成两段长度是1的绳子

答案

public class Solution {
    public int cutRope(int target) {
        // 处理特殊情况
        if (target <= 1) {
            return 0;
        }

        // 创建一个数组用于存储子问题的最优解
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 1;

        // 计算子问题的最优解
        for (int i = 2; i <= target; i++) {
            // 将绳子剪成 j 和 i-j 两段
            for (int j = 1; j <= i / 2; j++) {
                // 计算剪成两段后的长度乘积 (要注意长度为 1-3 的时候不分的乘积更大)
                int product = Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]);
                // 更新最优解
                dp[i] = Math.max(dp[i], product);
            }
        }
        return dp[target];
    }
}

JZ81 调整数组顺序使奇数位于偶数前面(二)

时间限制: 1 秒
空间限制: 64M
知识点: 数组排序

描述

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

数据范围： 0≤n≤50000，数组中每个数的值 0≤val≤10000
要求：时间复杂度 O(n)，空间复杂度 O(1)

示例 1
输入: [1,2,3,4]
返回值: [1,3,2,4]
说明: [3,1,2,4] 或者 [3,1,4,2] 也是正确答案
示例 2
输入: [1,3,5,6,7]
返回值: [1,3,5,7,6]
说明: [3,1,5,7,6] 等也是正确答案
示例 3
输入: [1,4,4,3]
返回值: [1,3,4,4]

答案

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo (int[] array) {
        // write code here
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            while (left < right && isOddNum(array[left])) {
                left++;
            }
            while (left < right && !isOddNum(array[right])) {
                right--;
            }
            if (left < right) {
                int tmp = array[left];
                array[left] = array[right];
                array[right] = tmp;
            }
        }
        return array;
    }

    private boolean isOddNum(int num) {
        return num % 2 == 1;
    }
}

JZ83 剪绳子（进阶版）

时间限制: 1 秒
空间限制: 64M
知识点: 基础数学快速幂

描述

由于答案过大，请对 998244353 取模。

数据范围： 2≤n≤10^14

进阶：空间复杂度 O(1) ，时间复杂度 O(logn)

示例 1
输入: 4
返回值: 4
说明: 拆分成 2 个长度为 2 的绳子，2 * 2 = 4
示例 2
输入: 5
返回值: 6
说明: 剪成一个长度为 2 的绳子和一个长度为 3 的绳子，答案为2*3=6
示例 3
输入: 874520
返回值: 908070737

答案

import java.util.*;
public class Solution {
    private long mod = 998244353;
    public long cutRope (long number) {
        // 不超过3直接计算
        if (number <= 3)
            return number - 1;
        // 能整除3
        if (number % 3 == 0)
            return pow(3, number / 3);
        // 最后剩余1
        else if (number % 3 == 1)
            // 4*3^{n-1}
            return fast(pow(3, number / 3 - 1), 4);
        // 最后剩余2
        else
            // 2*3^n
            return fast(pow(3, number / 3), 2);
    }

    // 快速幂
    long pow(long x, long y) {
        long res = 1;
        while (y != 0) {
            // 可以再往上乘一个
            if ((y & 1L) != 0)
                res = fast(res, x);
            // 叠加
            x = fast(x, x);
            // 减少乘次数
            y = y >> 1;
        }
        return res;
    }

    // 快速乘法
    private long fast(long x, long y) {
        long res = 0;
        x %= mod;
        y %= mod;
        while (y != 0) {
            if ((y & 1L) != 0) {
                // 加法代替乘法，防止越界
                res += x;
                if (res >= mod)
                    res -= mod;
            }
            y = y >> 1;
            x = x << 1;
            if (x >= mod)
                x -= mod;
        }
        return res;
    }
}

JZ17 打印从1到最大的n位数

时间限制: 1 秒
空间限制: 64M
知识点: 数组

描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

用返回一个整数列表来代替打印
n 为正整数，0 < n <= 5

示例 1
输入: 1
返回值: [1,2,3,4,5,6,7,8,9]

答案

import java.util.*;
public class Solution {
    public int[] printNumbers (int n) {
        int end = 1;
        for (int i = 1; i <= n; i++) {
            end *= 10;
        }
        int[] res = new int[end - 1];
        for (int i = 1; i < end; i++) {
            res[i - 1] = i;
        }
        return res;
    }
}

华为机试

较难

HJ3 明明的随机数

时间限制: 1 秒
空间限制: 32M
知识点: 数组

描述
明明生成了 N 个 1 到 500 之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

数据范围： 1≤n≤1000，输入的数字大小满足 1≤val≤500

输入描述：
第一行先输入随机整数的个数 N 。接下来的 N 行每行输入一个整数，代表明明生成的随机数。具体格式可以参考下面的”示例”。

输出描述：
输出多行，表示输入数据处理后的结果

示例 1
输入:
3
2
2
1
返回值:
1
2
说明:
输入解释：
第一个数字是 3，也即这个小样例的 N=3，说明用计算机生成了 3 个 1 到 500 之间的随机整数，接下来每行一个随机数字，共 3 行，也即这 3 个随机数字为：
2
2
1
所以样例的输出为：
1
2

答案

// 解法1
import java.util.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Set<Integer> numSet = new HashSet<>();
        for (int i = 0; i < n; i ++) {
            numSet.add(sc.nextInt());
        }

        List<Integer> numList = numSet.stream().sorted().collect(Collectors.toList());
        numList.forEach(num -> {
            System.out.println(num);
        });
    }
}

// 解法2
import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //获取个数
        int num = sc.nextInt();
        //创建TreeSet进行去重排序
        TreeSet set = new TreeSet();
        //输入
        for(int i =0 ; i < num ;i++){
            set.add(sc.nextInt());
        }

        //输出
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

困难

HJ28 素数伴侣

时间限制: 1 秒
空间限制: 32M
知识点: 查找排序

描述

题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如 2 和 5、6 和 13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有 4 个正整数：2，5，6，13，如果将 5 和 6 分为一组中只能得到一组“素数伴侣”，而将 2 和 5、6 和 13 编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。

数据范围：1≤n≤100，输入的数据大小满足 2≤val≤30000

输入描述：
输入说明
1 输入一个正偶数 n
2 输入 n 个整数

输出描述：
求得的“最佳方案”组成“素数伴侣”的对数。

示例 1
输入: 4
2 5 6 13
返回值: 2
示例 2
输入: 2
3 6
返回值: 0
示例 3
输入: 2
3 6
返回值: 0

答案

import java.util.*;

public class Main {

    // 小技巧！！！素数不是偶数，那么和是素数的话就是奇数+偶数
    // 那么可以分成两堆,一堆偶数，一堆奇数
    // 匈牙利算法，先到先得，能让就让
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            // 标准输入
            int n = sc.nextInt();
            // 用于记录输入的n个整数
            int[] arr=new int[n];
            // 用于存储所有的奇数
            ArrayList<Integer> odds = new ArrayList<>();
            // 用于存储所有的偶数
            ArrayList<Integer> evens = new ArrayList<>();
            for (int i = 0; i < n; i ++) {
                int num = sc.nextInt();
                if ((num & 1) == 1) {
                    odds.add(num);
                } else {
                    evens.add(num);
                }
            }

            // 下标对应偶数的下标，值对应这个偶数的伴侣
            int[] evenMatch = new int[evens.size()];
            // 记录伴侣的对数
            int count = 0;
            for (int i = 0; i < odds.size(); i ++) {
                // 用于标记对应的偶数是否查找过
                boolean[] evenUsed = new boolean[evens.size()];
                // 如果匹配上，则计数加1
                if (find(odds.get(i), evens, evenMatch, evenUsed)) {
                    count ++;
                }
            }
            System.out.println(count);
        }
    }

    // 判断奇数x能否找到伴侣
    private static boolean find(int odd, ArrayList<Integer> evens, int[] evenMatch, boolean[] evenUsed) {
        for (int i = 0; i < evens.size(); i ++) {
            // 该位置偶数能与x组成素数伴侣，并且没被访问过
            if (isPrime(odd + evens.get(i)) && !evenUsed[i]) {
                evenUsed[i] = true;
                // 如果第i个偶数没有伴侣，或者第i个偶数原来有伴侣，并且该伴侣能够重新找到伴侣的话(这里有递归调用)
                // 则奇数x可以设置为第i个偶数的伴侣
                // 这里采用了匈牙利算法，能让则让
                if (evenMatch[i] == 0 || find(evenMatch[i], evens, evenMatch, evenUsed)) {
                    evenMatch[i] = odd;
                    return true;
                }
            }
        }

        // 遍历完偶数都没有可以与传入奇数做伴侣的，该奇数只能孤独终老了
        return false;
    }

    // 判断是否是素数
    private static boolean isPrime(int num) {
        if (num == 1) return false;
        for (int i = 2; i * i <= num; i ++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

HJ44 Sudoku

时间限制: 1 秒
空间限制: 32M
知识点: 思维基础数学搜索

描述
问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据 9X9 盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个 3X3 粗线宫内的数字均含 1-9，并且不重复。

数据范围：输入一个 9*9 的矩阵

输入描述：
包含已知数字的 9X9 盘面数组 [空缺位以数字 0 表示]

输出描述：
完整的 9X9 盘面数组

示例 1
输入:
0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1
返回值:
5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

答案

// 从左上角开始去遍历这个数独。
// 对于没有填入的格子（即格子数值为0），我们去枚举1～9每个数字填入，然后根据数独的性质（同行、同列、同一个九宫格不能有相同数字）去判断填入。
// 如果可以成功填完所有格子那么就是找到了答案。找到答案后可以用一个bool变量，然后注意在回溯的地方根据这个变量及时的return，防止已经找到答案后又回溯为0。
// 对于初始化就有值的格子，我们往右走（列数值加一），那么因为一行只有9个，所以当列走到头的时候，列的值变成0，行的值加1（其实就是换到了下一行的开头）。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            // 初始化数独
            int[][] sd = new int[9][9];
            for (int i = 0; i < 9; i ++) {
                for (int j = 0; j < 9; j ++) {
                    sd[i][j] = sc.nextInt();
                }
            }

            // 填充数独
            dfs(sd, 0, 0);

            // 打印数独
            for (int i = 0; i < 9; i ++) {
                for (int j = 0; j < 9; j ++) {
                    System.out.print(sd[i][j]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }

    public static boolean dfs(int[][] sd, int i, int j) {
        if (j == 9) {
            i ++;
            j = 0;
        }
        if (i == 9 && j == 0) {
            return true;
        }
        if (sd[i][j] == 0) {
            for (int k = 1; k <= 9; k ++) {
                // check后满足
                if (check(sd, i, j, k)) {
                    sd[i][j] = k;
                    // 已经找到答案了，直接return
                    if (dfs(sd, i, j + 1)) {
                        return true;
                    }
                    // 没找到答案，回溯
                    sd[i][j] = 0;
                }
            }
            return false;
        } else {
            return dfs(sd, i, j + 1);
        }
    }

    public static boolean check(int[][] sd, int i, int j, int val) {
        // 同行
        for (int k = 0; k < 9; k ++) {
            if (sd[i][k] == val) {
                return false;
            }
        }
        // 同列
        for (int k = 0; k < 9; k ++) {
            if (sd[k][j] == val) {
                return false;
            }
        }

        // 同九宫格
        // 九宫格行的起点
        int limitRow = i / 3 * 3;
        // 九宫格列的起点
        int limitCol = j / 3 * 3;
        for(int k = limitRow; k < limitRow + 3; k ++) {
            for(int l = limitCol; l < limitCol + 3; l ++) {
                if(sd[k][l] == val) {
                    return false;
                }
            }
        }
        return true;
    }
}