开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 牛客网剑指offer——Java题解 -> 正文阅读

[数据结构与算法]牛客网剑指offer——Java题解

剑指offer

JZ1 二维数组中的查找

题目描述

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[

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

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

0 <= array.length <= 500
0 <= array[0].length <= 500
解题思路

双指针，从右上角或者左下角开始查找，逐行排查

代码

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

JZ2 替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路

通过StringBuilder的append重新拼接字符串

代码

public class Solution {
    public String replaceSpace (String s) {
        if(s == null || s.length() == 0)
            return s;
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            sb.append(' ' == s.charAt(i) ? "%20" : s.charAt(i));
        }
        return sb.toString();
    }
}

JZ3 从尾到头打印链表

题目描述

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

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000
解题思路
1. 使用栈实现
2. 使用ArrayList的特性

代码

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<ListNode> stack = new Stack();
        ListNode tmp = listNode;
        while(tmp != null){
            stack.push(tmp);
            tmp = tmp.next;
        }
        while(!stack.isEmpty()){
            list.add(stack.pop().val);
        }
        return list;
    }
}

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = listNode;
        while(tmp != null){
            list.add(0,tmp.val);
            tmp = tmp.next;
        }
        return list;
    }
}

JZ4 重建二叉树

题目描述

给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

1.0 <= pre.length <= 2000

2.vin.length == pre.length

3.-10000 <= pre[i], vin[i] <= 10000

4.pre 和 vin 均无重复元素

5.vin出现的元素均出现在 pre里

6.只需要返回根结点，系统会自动输出整颗树做答案对比
解题思路

递归（传入子数组的边界索引）

代码

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre,int[] vin) {
        TreeNode root = null;
        if(pre == null || pre.length == 0)
            return root;
        return Tree(root,pre,0,pre.length - 1,vin,0,vin.length - 1);
    }
    
    public TreeNode Tree(TreeNode root,int[] pre,int pl,int pr,int[] vin,int vl,int vr){
        if(pl > pr || vl > vr)
            return null;
        int rootVal = pre[pl];
        int index = 0;
        while(index <= vr && rootVal != vin[index]){
            index++;
        }
        root = new TreeNode(rootVal);
        root.left = Tree(root,pre,pl+1,pl + index - vl,vin,vl,index - 1);
        root.right = Tree(root,pre,pl + index - vl + 1,pr,vin,index + 1,vr);
        return root;
    }
}

JZ5 用两个栈实现队列

题目描述

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

示例:

输入:

[“PSH1”,“PSH2”,“POP”,“POP”]

返回:

1,2

解析:

“PSH1”:代表将1插入队列尾部

“PSH2”:代表将2插入队列尾部

"POP“:代表删除一个元素，先进先出=>返回1

"POP“:代表删除一个元素，先进先出=>返回2
解题思路
1. push：将元素全push到栈1
2. pop：栈1的元素都是相反的，出栈时需要将栈1的元素全部置入栈2，此时栈2的所有元素顺序都是符合先进先出的，所以出栈的操作步骤如下
  1. 当栈2为空时，先将栈1的元素全部移入栈2，再将栈2的栈顶出栈
  2. 栈2不为空，直接将栈2的栈顶出栈

代码

//时间复杂度： O(n)， 空间复杂度： O(n)
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.isEmpty())
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        return stack2.pop();
    }
}

JZ6 旋转数组中的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路

这种二分查找难就难在，arr[mid]跟谁比.
我们的目的是：当进行一次比较时，一定能够确定答案在mid的某一侧。一次比较为 arr[mid]跟谁比的问题。
一般的比较原则有：
- 如果有目标值target，那么直接让arr[mid] 和 target 比较即可。
- 如果没有目标值，一般可以考虑端点
这里我们把target 看作是右端点，来进行分析，那就要分析以下三种情况，看是否可以达到上述的目标。
1. 情况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. 情况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. 情况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;慢慢缩少区间，同时也不会错过答案。

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if(array.length == 0)
            return 0;
        int left = 0;
        int right = array.length - 1;
        if(array[left] >= array[right]){
            while (left < right) {
                int mid = (left + right) / 2;
                if (array[mid] > array[right]) {
                    left = mid + 1;
                }else if(array[mid] < array[right]){
                    right = mid;
                }else {
                    right--;
                }
            }
        }
        return array[left];
    }
}

JZ7 斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
解题思路
1. 递归
2. 基于动态规划思想，记录第n-1和n-2项，相加可得结果

代码

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 0){
            return 0;
        }else if(n <= 2){
            return 1;
        }else {
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }
}

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public int Fibonacci(int n) {
        if(n <= 0)
            return 0;
        if(n < 3)
            return 1;
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i = 2;i < n;i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

JZ8 跳台阶

题目描述

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

因为一次只能跳1或2级，所以可以得到公式，跳n级那么最后一步只能剩1或2级，所以n级的跳法=跳n-1级+跳n-2级，类比斐波那契数列

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public int jumpFloor(int target) {
        if(target < 3)
            return target;
        int a = 1;
        int b = 2;
        int c = 0;
        for(int i = 2;i < target;i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

JZ9 跳台阶扩展问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
解题思路
- 这是一道可以递归，记忆化递归，动态规划，递推思想的题目。
  跳1级：毫无疑问就1种跳法 j1 = 1
  跳2级：可以分为先跳1级剩1级、跳2级两种情况，第一种情况先跳1级剩1级，那么跳法就为跳1级的跳法。 j2 = j1 + 1
  跳3级：可以分为先跳1级2级、先跳2级剩1级、和跳3级三种情况，第一种情况先跳1级剩2级，那么跳法就为跳2级的跳法, 第二种情况先跳2级剩1级，那么跳法就为跳1级的跳法. j3 = j2 + j1 + 1
- 依此类推。。。。。。。。。。
  跳4级：j4 = j3 + j2 + j1 + 1
  跳5级：j5 = j4 + j3 + j2 + j2 + j1
- 公式优化
  跳1级：j1 = 1 ------->j1 = 2^0
  跳2级：j2 = j1 + 1 -------> j2 = j1 + j1 -------> j2 = 2 * j1 ------->j2 = 2^1
  跳3级：j3 = j2 + j1 + 1 ------->j3 = j2 + j2 -------> j3 =2 * j2 ------->j3 = 2^2
  跳4级：j4 = j3 + j2 + j1 + 1 -------> j4 = j3 + j3 -------> j4 =2 * j3 ------->j4 = 2^3
  跳n级：jn = jn-1 + jn-2 + … + j3 + j2 + j1 + 1 ------->jn = jn-1 + jn-1 ------->jn =2 * jn-1 ------->5 = 2^n-1

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public int jumpFloorII(int target) {
        return 1 << (target - 1);
    }
}

JZ10 矩阵覆盖

题目描述

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

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：
解题思路：其实等同于跳台阶(一次只能跳1或2级)问题

对于很多递归问题，我们都可以通过归纳总结来找出他们的规律：
当n=1时，way=1(横或竖)
当n=2时，way=2(全横或全竖)
当n=3时，way=3(全竖&横横竖&竖横横)
当n=4时，way=5(全竖&竖横横竖&竖竖横横&横横竖竖&横横横横)
当n=5时，way=8(全竖&竖横横竖竖&竖横横横横&竖竖横横竖&竖竖竖横横&横横竖竖竖&横横横横竖&横横竖横横)
…
n=(n-1)+(n-2);
于是问题有转换成了之前的斐波那契数列问题了，依旧时同样的方法求解

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public int rectCover(int target) {
        if(target < 3)
            return target;
        int a = 1;
        int b = 2;
        int c = 0;
        for(int i = 2;i < target;i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

JZ11 二进制中1的个数

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
解题思路

直接将整数看成二进制，然后采用移位的方法。注意移位时要使用无符号右移，想知道原因请点这里

代码

//时间复杂度 O(logn)， 空间复杂度 O(1)
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            count += (n & 1);
            n >>>= 1;
        }
        return count;
    }
}

JZ12 数值的整次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。
解题思路
1. 次方数等于0：直接返回1.0
2. 次方数小于0，将base置为1/base，再将次方数乘-1，转为正数次方计算

代码

//时间复杂度 O(n)， 空间复杂度 O(1)
public class Solution {
    public double Power(double base, int exponent) {
        if(exponent == 0)
            return 1.0;
        if(exponent < 0){
            base = 1 / base;
            exponent *= -1;
        }
        double res = base;
        for(int i = exponent;i > 1;i--){
            res *= base;
        }   
        return res;
    }
}

JZ13 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变
解题思路

额外空间辅助，使用队列

代码

//时间复杂度 O(n)， 空间复杂度 O(n)
public class Solution {
    public int[] reOrderArray (int[] array) {
        Queue<Integer> ji = new LinkedList();
        Queue<Integer> ou = new LinkedList();
        for(int i = 0;i<array.length;i++){
            if(array[i] % 2 == 1){
                ji.offer(array[i]);
            }else {
                ou.offer(array[i]);
            }
        }
        int i = 0;
        while(!ji.isEmpty()){
            array[i++] = ji.poll();
        }
        while(!ou.isEmpty()){
            array[i++] = ou.poll();
        }
        return array;
    }
}

JZ14 链表中倒数第k个节点

题目描述

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。
解题思路

双指针，快指针先走k-1步，再和慢指针同步走，快指针走到链表尾部则，慢指针指向倒数第k个

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null)
            return pHead;
        if(k <= 0)
            return null;
        ListNode quick = pHead;
        ListNode slow = null;
        while(quick != null && k > 1){
            quick = quick.next;
            k--;
        }
        if(quick != null){
            slow = pHead;
            while(quick.next != null){
                quick = quick.next;
                slow = slow.next;
            }
        }
        return slow;
    }
}

JZ15 反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。
解题思路

迭代，两个指针，一个遍历链表，一个链新链表

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode tmp = cur;
            cur = cur.next;
            tmp.next = pre;
            pre = tmp;
        }
        return pre;
    }
}

JZ16 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路

双指针：迭代

代码

//时间复杂度： O(m+n)， 空间复杂度： O(1)  
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode res = new ListNode(-1);
        ListNode list = res;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                list.next = list1;
                list1 = list1.next;
            }else{
                list.next = list2;
                list2 = list2.next;
            }
            list = list.next;
        }
        list.next = list1 == null ? list2 : list1;
        return res.next;
    }
}

JZ17 树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路

递归：若根节点相等，利用递归比较他们的子树是否相等，若根节点不相等，则利用递归分别在左右子树中查找

代码

//时间复杂度： O(n)， 空间复杂度： O(n)  
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null)
            return false;
        return isEqualsTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    
    public boolean isEqualsTree(TreeNode root1,TreeNode root2){
        if(root2 == null)
            return true;
        if(root1 == null || root1.val != root2.val)
            return false;
        return isEqualsTree(root1.left,root2.left) && isEqualsTree(root1.right,root2.right);
    }
}

JZ18 二叉树的镜像

题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。

比如：    源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

解题思路

使用递归交换每个节点的左右子树位置

代码

//时间复杂度： O(n)， 空间复杂度： O(n)  
public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null)
            return pRoot;
        swap(pRoot);
        pRoot.left = Mirror(pRoot.left);
        pRoot.right = Mirror(pRoot.right);
        return pRoot;
    }
    
    public void swap(TreeNode pRoot){
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
    }
}

JZ19 顺时针打印矩阵

题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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]
```
解题思路

模拟遍历过程

代码

//时间复杂度： O(n)， 空间复杂度： O(n)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int[][] array) {
        ArrayList<Integer> list = new ArrayList<>();
        int up = 0;
        int down = array.length - 1;
        int left = 0;
        int right = array[0].length - 1;
        if(down == -1 || right == -1)
            return list;
        while(up <= down && left <= right){
            for(int i = left;i <= right;i++){
                list.add(array[up][i]);
            }
            up++;
            for(int j = up;j <= down;j++){
                list.add(array[j][right]);
            }
            right--;
            //防止重复打印，解决奇数行列的问题
            if(up > down || left > right)
                break;
            for(int i = right;i >= left;i--){
                list.add(array[down][i]);
            }
            down--;
            for(int j = down;j >= up;j--){
                list.add(array[j][left]);
            }
            left++;
        }
        return list;
    }
}

JZ20 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数及 pop函数的时间复杂度都是 O(1)

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

示例:

输入: [“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

"PSH-1"表示将1压入栈中，栈中元素为1，-1

"TOP"表示获取栈顶元素==>返回1

“MIN”表示获取此时栈中最小元素==>返回-1
解题思路

维护一个最小值栈

代码

//时间复杂度： O(n)， 空间复杂度： O(n)
import java.util.Stack;

public class Solution {
    private Stack<Integer> minStack = new Stack<>();
    private Stack<Integer> stack = new Stack<>();
    
    public void push(int node) {
        stack.push(node);
        if(minStack.isEmpty() || minStack.peek() >= node){
            minStack.push(node);
        }
    }
    
    public void pop() {
        int node = stack.pop();
        if(node == minStack.peek())
            minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

JZ21 栈的压入、弹出序列

题目描述

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

用栈来压入弹出元素，相等则出栈

代码

//时间复杂度： O(n)， 空间复杂度： O(n)
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] push,int [] pop) {
        if(push.length == 0 || pop.length == 0)
            return false;
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for(int i = 0;i < push.length;i++){
            stack.push(push[i]);
            while(!stack.isEmpty() && stack.peek() == pop[index]){
                stack.pop();
                index++;
            }
        }
        return index == pop.length ? true : false;
    }
}

JZ22 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解题思路

借助队列实现
1. 出队列，打印当前队列首节点
2. 再判断左右子节点是否存在，存在进入队列

代码

//时间复杂度： O(n)， 空间复杂度： O(n)
import java.util.*;

public class Solution {
    public ArrayList<Integer>  PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            list.add(tmp.val);
            if(tmp.left != null)
                queue.offer(tmp.left);
            if(tmp.right != null)
                queue.offer(tmp.right);
        }
        return list;
    }
}

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

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）
解题思路
- 二叉搜索树：右子树的所有节点 > 根节点 > 左子树的所有节点
递归，判断当前树，再判断左右子树

逻辑：
1. 找到根节点的左子树根节点：比根节点小的节点就是左子树根节点
2. 判断左孩子节点下的所有节点是否小于根节点，全部小于则递归判断左，右子树

代码

//时间复杂度： O(n)， 空间复杂度： O(n)
public class Solution {
    public boolean VerifySquenceOfBST(int[] sequence) {
        if(sequence.length == 0)
            return false;
        return isBST(sequence,0,sequence.length - 1);
    }
    
    public boolean isBST(int[] array,int left,int right){
        //只剩一个节点，必然是二叉搜索树
        if(left >= right)
            return true;
        int i = right;
        //找到左子树根节点
        while(i >= left && array[right] <= array[i]){
            i--;
        }
        //判断左子树的所有节点是否小于根节点
        for(int j = i;j >= left;j--){
            if(array[j] > array[right])
                return false;
        }
        return isBST(array,left,i) && isBST(array,i + 1,right - 1);
    }
}

JZ24 二叉树中和为某一值的路径

题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解题思路

模拟二叉树的递归先序遍历

代码

import java.util.ArrayList;

public class Solution {
    private ArrayList<ArrayList<Integer>> listALL = new ArrayList<>();
    private ArrayList<Integer> list = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null || root.val > target)
            return listALL;
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null){
            //添加路径
            listALL.add(new ArrayList(list));
        }
        FindPath(root.left,target);
        FindPath(root.right,target);
        //左右子树查找完，回退
        list.remove(list.size() - 1);
        return listALL;
    }
}

JZ25 复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针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

如下图:
解题思路

借助HashMap，建立新链表的映射关系，key为原链表，value为新链表

代码

import java.util.HashMap;

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null)
            return null;
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        //构造新链表的节点
        while(cur != null){
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        RandomListNode tmp;
        //新链表节点的关系映射
        while(cur != null){
            tmp = map.get(cur);
            tmp.next = map.get(cur.next);
            tmp.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}

JZ26 二叉搜索树与双向链表

题目描述

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

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出或者处理，示例中输出里面的英文，比如"From left to right are:"这样的，程序会根据你的返回值自动打印输出

示例:

输入: {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;

解析:

输入就是一棵二叉树，如上图，输出的时候会将这个双向链表从左到右输出，以及

从右到左输出，确保答案的正确
解题思路
1. 非递归：利用栈辅助，链表的关系模型为：左孩子<->根<->右孩子，根又是根双亲节点的左孩子或由孩子
2. 递归：定义一个链表的尾节点，递归处理左右子树，最后返回链表的头节点

代码

import java.util.*;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null || (pRootOfTree.left == null && pRootOfTree.right == null))
            return pRootOfTree;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = pRootOfTree;
        while(cur != null || !stack.isEmpty()){
            //将当前节点的左子树全部入栈
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //拿到链表的next
            cur = stack.pop();
            if(pre == null){
                //记录链表首部
                pRootOfTree = cur;
            }else{
                //更新指针指向
                pre.right = cur;
                cur.left = pre;
            }
            //更新前驱节点
            pre = cur;
            //链表的下一个节点等于cur = cur.next
            cur = cur.right;
        }
        return pRootOfTree;
    }
}

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        //双向链表的尾节点
        TreeNode lastList = convertNode(pRootOfTree,null);
        TreeNode head = pRootOfTree;
        //寻找双向链表的头节点
        while(head != null && head.left != null){
            head = head.left;
        }
        return head;
    }
    
    public TreeNode convertNode(TreeNode root,TreeNode lastList){
        if(root == null)
            return root;
        TreeNode cur = root;
        //处理左子树
        if(cur.left != null){
            lastList = convertNode(cur.left,lastList);
        }
        //更新尾节点和新节点的连接关系
        cur.left = lastList;
        if(lastList != null){
            lastList.right = cur;
        }
        //更新链表的尾节点
        lastList = cur;
        //处理右子树
        if(cur.right != null){
            lastList = convertNode(cur.right,lastList);
        }
        return lastList;
    } 
}

JZ27 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
解题思路

将当前位置的字符和前一个字符位置交换，递归。详细思路参考

代码

import java.util.*;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList();
        backtrack(0,res,str.toCharArray());
        Collections.sort(res);
        return res;
    }

    public void backtrack(int left,ArrayList<String> res,char[] chars){
        if(left == chars.length - 1){
            res.add(String.valueOf(chars));
        }
        for(int i = left;i < chars.length;i++){
            if(i == left || chars[i] != chars[left]){
                swap(chars,left,i);
                backtrack(left + 1,res,chars);
                swap(chars,left,i);
            }
        }
    }

    public void swap(char[] c, int a,int b) {
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}

JZ28 数组中超过次数一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000，0<=数组元素<=10000
解题思路
1. 借助Map：将数存入map，值作为key，出现次数为value
2. 加入数组中存在众数，那么众数一定大于数组的长度的一半。
  思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

代码

import java.util.HashMap;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length == 1)
            return array[0];
        HashMap<Integer,Integer> map = new HashMap();
        for(int i = 0;i < array.length;i++){
            int key = array[i];
            if(map.containsKey(key)){
                int val = map.get(key) + 1;
                if(val > array.length/2)
                    return key;
                map.put(key,val);
            }else{
                map.put(key,1);
            }
        }
        return -1;
    }
}

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length < 2)
            return array[0];
        int count = 1;
        int cond = array[0];
        int tmp;
        for(int i = 1;i < array.length;i++){
            tmp = array[i];
            if(tmp == cond){
                count++;
            }else{
                if(--count == 0){
                    cond = tmp;
                    count++;
                }
            }
        }
        return cond;
    }
}

JZ29 最小的K个数

题目描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
- 0 <= k <= input.length <= 10000
- 0 <= input[i] <= 10000
解题思路

基于快排的划分思想，划分出前k小

代码

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(input.length < k){
           return list;
        }
        fastSort(input,0,input.length - 1);
        for(int i = 0;i < k;i++){
            list.add(input[i]);
        }
        return list;
    }
    
    public static void fastSort(int[] array,int start,int tail) {
		if(start >= tail) {
			return;
		}
		//将第一个元素作为比较元素，从第二个开始到最后一个执行快速排序算法
		int begin = start;
		int end = tail;
		int key = array[start];
		while(begin < end) {
			while(array[end] >= key && begin < end) {
				end = end - 1;
			}
			while(array[begin] <= key && begin < end) {
				begin = begin + 1;
			}
			if(end > begin) {
				int temp = array[begin];
				array[begin] = array[end];
				array[end] = temp;
			}
		}
		array[start] = array[begin];
		array[begin] = key;
		fastSort(array,start,begin - 1);
		fastSort(array,begin + 1,tail);
	}
}

JZ30 连续子数组的最大和

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
解题思路
1. 更新子数组和
2. 更新最大子数组和

代码

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int nowSum = array[0];
        int maxSum = nowSum;
        for(int i = 1;i < array.length;i++){
            //更新子数组和
            nowSum = Math.max(nowSum + array[i],array[i]);
            //更新最大子数组和
            maxSum = Math.max(nowSum,maxSum);
        }
        return maxSum;
    }
}

JZ31 整数中1出现的次数

题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数
例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次
解题思路
1. 将1~n拼接成一个字符串，遍历字符串统计1的个数
2. 数学思路总结公式

代码

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        if(n < 0) return 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 1;i <= n;i++)
            sb.append(i);
        for(char a : sb.toString().toCharArray())
            if(a == '1') res++;
        return res;
    }
}

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i = 1; i <= n; i *= 10){
            int a = n / i; // 高位
            int b = n % i; // 低位
            count += (a+8) / 10 * i;
            if(a % 10 == 1){
                count += b + 1;
            }
        }
        return count;
    }
}

JZ32 把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路

代码

import java.util.*;

public class Solution {
    public String PrintMinNumber(int[] numbers) {
        int len = numbers.length;
        if(len<1) 
            return "";
        String[] strs = new String[len];
        for(int i = 0; i < len; i++){
            strs[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(strs,new Comparator<String>(){
            @Override
            public int compare(String s1, String s2) {
                return (s1 + s2).compareTo(s2 + s1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(String s : strs){
            sb.append(s);
        }
        return sb.toString();
    }
}

JZ33 丑数

题目描述

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

有了上面的定义我们就可以知道，丑数的形式就是
所以我们可以定义一个数组res，存储第n个丑数。
因为我们要将丑数按从小到大的顺序排序，所以我们就得将对应的丑数放在对应的下标位置，小的放前面。
因为最小的丑数就是1，所以我们初始化res[0]=1，那么接下来的一个丑数是什么呢？我们自己知道是2。
但是我们能不能有一个格式，去将得到接下来的丑数是谁呢？
这个时候上面我们的出来的丑数的格式就起作用了，丑数的形式无非就是这样
所以我们就将res[n]去乘以 2、3、5，然后比较出最小的那个，就是我们当前的下一个丑数了。

代码

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0)
            return 0;
        int[] arr = new int[index];
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        arr[0] = 1;
        for(int j = 1;j<index;j++){
            arr[j] = Math.min(Math.min(arr[p2]*2,arr[p3]*3),arr[p5]*5);
            if(arr[j] == arr[p2]*2) p2++;
            if(arr[j] == arr[p3]*3) p3++;
            if(arr[j] == arr[p5]*5) p5++;
        }
        
        return arr[index-1];
    }
}

JZ34 第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
解题思路

利用HashMap 保存字符和出现次数

代码

import java.util.HashMap;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        HashMap<Character,Integer> map = new HashMap<>();
        for(char s : str.toCharArray()){
            if(map.get(s) == null){
                 map.put(s,1);
            }else{
                 map.put(s,map.get(s)+1);
            }
        }
        
        for(int i = 0;i < str.length();i++){
            if(map.get(str.charAt(i)) == 1){
                 return i;
            }
        }
        return -1;
    }
}

JZ35 数组中的逆序对

题目描述

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

对于50%的数据,size<=10^4
对于100%的数据,size<=10^5
解题思路

本质是归并排序，在比较时加入全局变量 count 进行记录逆序对的个数，若data[left] >= data[index] ，则 count 值为 mid + 1- leftIndex

代码

public class Solution {
    int count = 0;

    public int InversePairs(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        mergeSort(array,0,array.length - 1);
        return count;
    }
    
    void mergeSort(int[] array,int left,int right){
        if(left < right){
            int mid = (left + right) >> 1;
            mergeSort(array,left,mid);
            mergeSort(array,mid+1,right);
            merge(array,left,mid,right);
        }
    }
    
    void merge(int[] array,int left,int mid,int right){
        int[] tmp = new int[right - left + 1];
        int i = 0;
        int leftIndex = left;
        int rightIndex = mid + 1;
        
        while(leftIndex <= mid && rightIndex <= right){
            if(array[leftIndex] <= array[rightIndex]){
                tmp[i++] = array[leftIndex++];
            }else{
                tmp[i++] = array[rightIndex++];
                //逆序对统计
                count = (count + mid + 1 - leftIndex) % 1000000007;
            }
        }
        
        while(leftIndex <= mid){
            tmp[i++] = array[leftIndex++];
        }
        
        while(rightIndex <= right){
            tmp[i++] = array[rightIndex++];
        }
        
        for(int n : tmp){
            array[left++] = n;
        }
    }
}

JZ36 两个链表的第一个公共节点

题目描述

输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
解题思路
1. 借助栈将节点置入栈中，从后开始找出不同节点，不同节点的next为第一个共同节点
2. 让N1和N2一起遍历，当N1先走完链表1的尽头的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。

代码

//方法2
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         ListNode n1 = pHead1;
         ListNode n2 = pHead2;
         while(n1 != n2){
             n1 = n1 == null ? pHead2 : n1.next;
             n2 = n2 == null ? pHead1 : n2.next;
         }
        return n1;
    }
}

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

题目描述

统计一个数字在升序数组中出现的次数。
解题思路

使用二分查找，找到值后向左和向右去统计次数，而后返回

代码

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array == null || array.length == 0)
           return 0;
       return BinarySearch(array,0,array.length - 1,k);
    }
    
    public int BinarySearch(int[] arr,int left,int right,int k){
        int res = 0;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(k == arr[mid]){
                int i = mid;
                while(i < arr.length && k == arr[i++]) res++;
                i = mid - 1;
                while(i >= 0 && k == arr[i--]) res++;
                break;
            }else if(k > arr[mid]){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return res;
    }
}

JZ38 二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
解题思路
1. 对树进行层次遍历，每遍历一层则层数加一
2. 利用递归遍历分别返回左右子树深度

代码

import java.util.*;

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            depth++;
            for(int i = 0;i < size ; i++){
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return depth;
    }
}

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(TreeDepth(root.left),TreeDepth(root.right)) + 1;
    }
}

JZ39 平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

注：我们约定空树是平衡二叉树。
解题思路

计算当前左右子树最大深度差，判断当前二叉树是否是平衡二叉树，递归判断左右子树

代码

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) return true;
        return (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) && 
            IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);

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

JZ40 数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解题思路
1. 遍历数组将值置入list，置入时进行判断，已存在则不置入且将值删除，不存在则置入，最后list只剩2个元素
2. 两个相同的数异或后为 0，一个数和 0 异或还是它本身，将所有数异或后即得到 A、 B 异或的结果，然后求得 1 在该数最右边出现的 index，然后判断每个数右移 index 后是不是 1。

代码

import java.util.LinkedList;

public class Solution {
    public static int[] FindNumsAppearOnce (int[] array) {        
        if(array == null || array.length <= 2)
            return res;
        int[] res = new int[2];
        LinkedList<Integer> list = new LinkedList<>();
        for (int tmp : array) {
            if (list.contains(tmp)) {
                list.remove(Integer.valueOf(tmp));
            }else {
                list.add(tmp);
            }
        }
        int a = list.getFirst();
        int b = list.getLast();
        res[0] = Math.min(a, b);
        res[1] = Math.max(a, b);
        return res;
    }
}

public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        if(array.length <= 2)
            return array;
        int[] result = new int[2];
        int temp = 0;
        for (int value : array) {
            temp ^= value;
        }
        int count = 1;
        while(temp>>1 != 1){
            count++;
        }
        for (int value : array) {
            int tmp = (value >> count) & 1;
            if (tmp == 0) {
                result[0] ^= value;
            } else {
                result[1] ^= value;
            }
        }
        return result;
    }
}

JZ41 和为S的连续正数序列

题目描述

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

滑动窗口，通过动态改变窗口大小，判断窗口中的值是否符合要求

步骤：
1. 初始化，i=1,j=1, 表示窗口大小为0
2. 如果窗口中值的和小于目标值sum，表示需要扩大窗口，j += 1
3. 否则，如果狂口值和大于目标值sum，表示需要缩小窗口，i += 1
4. 否则，等于目标值，存结果，缩小窗口，继续进行步骤2,3,4

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>>  FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(sum <= 2)
            return res;
        int left = 1;
        int right = 1;
        int end = sum >> 1;
        while(left <= end){
            int tmp = ((left + right)*(right - left+1)) >> 1;
            if(tmp < sum){
                right++;
            }else if(tmp > sum){
                left++;
            }else{
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = left;i <= right;i++){
                    list.add(new Integer(i));
                }
                res.add(list);
                right++;
            }
        }
        return res;
    }
}

JZ42 和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。
解题思路

双指针，步骤：
1. 初始化：指针i指向数组首，指针j指向数组尾部
2. 如果arr[l] + arr[r] == sum , 说明是可能解
3. 否则如果arr[l] + arr[r] > sum, 说明和太大，所以–r
4. 否则如果arr[l] + arr[r] < sum, 说明和太小，所以++l

代码

//时间复杂度： O(n)， 空间复杂度： O(1)
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] arr,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        if(arr.length == 0 || sum < arr[0])
            return list;
        int l = 0;
        int r = arr.length - 1;
        while(l < r){
            int tmp = arr[l] + arr[r];
            if(tmp == sum){
                list.add(arr[l]);
                list.add( arr[r]);
                break;
            }else if(tmp < sum){
                l++;
            }else{
                r--;
            }
        }
        return list;
    }
}

JZ43 左旋转字符串

题目描述

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

拼接字符串

代码

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str == null || str.length() == 0 || n <= 0)
            return str;
        return str.substring(n) + str.substring(0,n);
    }
}

JZ44 反转单词序列

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
解题思路
1. Java库函数
2. 双指针 + StringBuilder
  
  从字符串的最后面开始，将每个单词拼接在新字符串上
3. 两次反转 + 栈
  
  先反转字符串，再反转每个单词

代码

public class Solution {
    public String ReverseSentence(String str) {
        StringBuffer sb = new StringBuffer("");
        if(str.length() <= 0 || str.trim().equals("")){//需要将多个空格的情况考虑进来
            return str;
        }
        String[] strSet = str.split(" ");//将一个字符串分成多个后，装数组里，效率低
        int length = strSet.length;
        for(int i = length-1; i > 0 ;i--){
            sb.append(strSet[i]+" ");//从尾部添加就可以保证顺序颠倒了
        }
        sb.append(strSet[0]);//写在外面是因为最后一个添加的不用添加空格了。
        return sb.toString();
    }
}

双指针

public class Solution {
    public String ReverseSentence(String str) {
        if(str == null || str.length() == 0)    return str;
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        int left = str.length() - 1;
        int right = left;
        while(right >= 0){
            while(left >= 0 && str.charAt(left) != ' ')    left--;
            sb.append(chars,left + 1,right - left);
            sb.append(' ');
            right = --left;
        }
        sb.deleteCharAt(sb.length() - 1);
        str = sb.toString();
        return str;
    }
}

两次反转 + 栈

import java.util.Stack;

public class Solution {
    public String ReverseSentence(String str) {
        if(str==null||str.length()==0)
            return str;
        StringBuilder res=new StringBuilder();
        String[] tmp = str.split(" ");
        if(tmp.length==0)
            return str;
        Stack<String>sx=new Stack<>();
        for(int i=0;i<tmp.length-1;i++) {//tmp.length-1是保障第一个字符串进栈不需要再进栈“ ”
            sx.push(tmp[i]);
            sx.push(" ");
        }
        sx.push(tmp[tmp.length-1]);
        while(!sx.isEmpty()) {
            res.append(sx.pop());
        }
        return res.toString();
    }
}

JZ45 扑克牌顺子

题目描述

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
  例如：给出数据[6,0,2,0,4]
  中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
  这样这五张牌在[2,6]区间连续，输出true
  数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
解题思路

用数组记录五张扑克牌，将数组调整为有序的，若 0 出现的次数>=顺子的差值，即为顺子

代码

import java.util.Arrays;
public class Solution {
    public boolean IsContinuous(int [] num) {
        if(num.length < 5)
            return false;
        int count = 0;
        int diff = 0;
        Arrays.sort(num);
        for(int i = 0;i < num.length - 1;i++){
            if(num[i] == 0){
                count++;
                continue;
            }
            if(num[i] == num[i + 1]){
                return false;
            }
            diff += num[i + 1] - num[i] - 1;
        }
        return diff <= count;
    }
}

JZ46 孩子们的游戏（约瑟夫环问题）

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1
解题思路

利用公式法： f[n] = (f[n-1] + k) % n

代码

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n < 1 || m < 1){
            return -1;
        }
        int last = 0;
        for(int i = 2;i <= n;i++){
            last = (last + m) % i;
        }
        return last;
    }
}

JZ47 求1+2+3+···+n

题目描述

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

利用递归，巧用逻辑判断作为递归终止条件

代码

public class Solution {
    public int Sum_Solution(int n) {
        int sum = n;
        boolean result = (n > 0) && ((sum += Sum_Solution(n-1)) > 0);
        return sum;
    }
}

JZ48 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
解题思路
1. 计算a和b的无进位和，和进位
2. 如果进位不为0，则说明a+b的结果等于无进位和+进位，此时，把无进位和作为a，进位作为b，继续计算
3. 如果进位等于0，说明此时a+b的结果就等于无进位和，返回无进位和即可。

代码

public class Solution {
    public int Add(int num1,int num2) {
        while (num2 != 0) {
            // 计算个位
            int temp = num1 ^ num2;
            // 计算进位（1+1）
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }
}

JZ49 把字符串转成整数

题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0
解题思路

遍历字符串，通过二进制码转成整型值

代码

public class Solution {
    public int StrToInt(String str) {
        if(str == null || str.length() == 0){
            return 0;
        }
        int tmp = (int)str.charAt(0);
        int l = 0;
        boolean flag = false;
        //判断字符串第一位是否是+/-号
        if(tmp == 43 || tmp == 45){
             l = 1;
             flag = tmp == 45 ? true : false; 
        }else if(tmp < 48 || tmp > 57){
            return 0;
        }
        int a = 1;
        int rs = 0;
        for(int i = str.length()-1;i >= l;i--){
            tmp = (int)str.charAt(i);
            if(tmp < 48 || tmp > 57){
                return 0;
            }
            //换算值
            rs += (tmp - 48)*a > Integer.MAX_VALUE ? 0 : (tmp - 48)*a;
            a *= 10;
        }
        if(l == 1 && flag){
            rs = (-1)*rs < Integer.MIN_VALUE ? 0 : (-1)*rs;
        }
        return rs;
    }
}

JZ50 数组中重复的数字

题目描述

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

从左到右遍历数组arr，对于 arr[i]，我们可以把arr[i]放到数组下标为arr[i]的位置上，即arr[arr[i]] = arr[i]。例例如 arr[0] = 4，那么我们就把arr[0]与arr[4]进行交换。假如数组中没有重复的数，那么遍历完成后的结果是 arr[i] = i。如果数组有重复的元素，那么当我们要把 arr[i] 与 arr[arr[i]] 进行交换的时候，会发现 arr[arr[i]] 的值已经为arr[i]了了，并且arr[i] != i。

代码

import java.util.*;

public class Solution {
    public int duplicate (int[] num) {
        if(num.length <= 1){
            return -1;
        }
        int i = 0;
        while(i < num.length){
            if(num[num[i]] == num[i]){
                if(num[i] == i){
                    i++;
                }else {
                    return num[i];
                }
            }else {
                int tmp = num[num[i]];
                num[num[i]] = num[i];
                num[i] = tmp;
            }
        }
        return -1;
    }
}

JZ51 构建乘积数组

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
解题思路
1. 先算出 B[i] = A[0] * …A[i-1]。
2. 接着算 B[i] = A[i+1]…A[n-1] * B[i]

代码

public class Solution {
    public int[] multiply(int[] A) {
        int len = A.length;
        int[] B = new int[len];
        B[0] = 1;
        //分两步求解,先求 B[i] = A[0]*..A[i-1];
        for(int i = 1; i < len; i++){
            B[i] = B[i-1] * A[i-1];
        }
        //再求B[i]=A[i+1]*...A[n-1];
        int tmp = A[len-1];
        for(int i = len - 2; i >= 0; i--){
            B[i] *= tmp;
            tmp *= A[i];
        }
        return B;
    }
}

JZ52 正则表达式匹配

题目描述

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

*：匹配前面的子表达式任意次。例如，zo**能匹配“z”，也能匹配“zo”以及“zoo”。

. ：匹配除“\n”和"\r"之外的任何单个字符
1. 首先判断字符串的合法性
2. 比较第一个字符是否匹配，当第一个字符相等或pattern第一个字符为.，第一个字符匹配成功，否则匹配失败，直接return
3. 判断正则表达式字符串第二位是否为*，如果是则会产生两种情况
  1. 跳过与pattern第一个字符的匹配
  2. 第一个字符是相等的，则进行对str字符串进行匹配，因为*可以替换0到多个相同字符
  如果不是*，则进行第二位的匹配

代码

import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
        //合法性判断
        if(pattern.length() <= 0){
            return str.length() <= 0;
        }
        //比较字符串第一个字符
        boolean match = (str.length() > 0 && (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.'));
        //判断pattern第二位是否为*
        if(pattern.length() > 1 && pattern.charAt(1) == '*'){
            return match(str, pattern.substring(2)) || (match && match(str.substring(1), pattern));
        } else {
            //第二个字符的匹配
            return match && match(str.substring(1), pattern.substring(1));
        }
    }
}

JZ53 表示数值的字符串

题目描述

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

根据条件进行判断：
1. 字符串长度要大于0
2. 小数点不能超过1个、有E或e后不能出现小数点
3. E/e不能超过1个、+/-只能出现再E/e的下一个
4. 不能出现其他字符

代码

import java.util.*;
public class Solution {
    public boolean isNumeric (String s) {
        char[] str = s.toCharArray();
        if (str == null || str.length <= 0){
            return false;
        }

        boolean symbol = false, decimal = false, hasE = false,hasNumber = false;
        int len = str.length;
        for (int i = 0 ; i < str.length ; i++){
            if(str[i] == '+' || str[i] == '-') {
                if (i == len-1)
                    return false;
                if (!symbol && i > 0 && str[i - 1] != 'e' && str[i - 1] != 'E')
                    return false;
                if (symbol && i > 0 && str[i - 1] != 'e' && str[i - 1] != 'E')
                    return false;
                symbol = true;
            }
            else if (str[i] == 'e' || str[i] == 'E'){
                if (i == len-1)
                    return false;
                if(hasE)
                    return false;
                if (!hasNumber)
                    return false;
                hasE = true;
            }
            else if (str[i] == '.'){
                if (decimal || hasE)
                    return false;
                if(!hasNumber) {
                    if (i == len - 1)
                        return false;
                }
                if (i == len-1)
                    continue;
                if (str[i+1] > '9' || str[i+1] <'0')
                    if(str[i+1] != 'e')
                        return false;
                decimal = true;
            }
            else if (str[i] == ' '){
                if (i == len-1 && !hasNumber)
                    return false;
            }
            else if (str[i] > '9' || str[i] < '0' )
                return false;
            else if (str[i] <= '9' || str[i] >= '0' )
                hasNumber =true;
        }
        return true;
    }
}

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

题目描述

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

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

string caseout = “”;

1.读入测试用例字符串casein

2.如果对应语言有Init()函数的话，执行Init() 函数

3.循环遍历字符串里的每一个字符ch {

Insert(ch);

caseout += FirstAppearingOnce()

}

\2. 输出caseout，进行比较。
解题思路

借助辅助空间进行判断

代码

public class Solution {
    char[] chars = new char[256];
    StringBuilder sb = new StringBuilder();
    //Insert one char from stringstream
    public void Insert(char ch){
        sb.append(ch);
        chars[ch]++;
    }
  	//return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){
        char[] str = sb.toString().toCharArray();
        for(char c : str){
            if(chars[c] == 1){
                return c;
            }
        }
        return '#';
    }
}

JZ55 环形链表的入口节点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
解题思路

双指针，利用环形链表的性质，用两个不同速度的指针来遍历链表，根据数学关系，两者相遇的路程差为n倍的环长，定义快慢两个指针，相遇后（环中相汇点）将快指针指向 pHead 然后一起走，每次往后挪一位，相遇的节点即为所求。

详细分析：相遇即 p1p2 时， p2所经过节点数为 2x,p1 所经过节点数为 x,设环中有 n 个节点,p2 比 p1 多走一圈有2x=n+x; n=x;可以看出 p1 实际走了一个环的步数，再让 p2 指向链表头部，p1 位置不变， p1,p2 每次走一步直到 p1p2; 此时 p1 指向环的入口。

代码

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null || pHead.next == null)
            return null;
        ListNode slow = pHead;
        ListNode quick = pHead;
        //快慢指针遍历链表直到相遇
        do{
            //防止链表无环引起null指针
            if(quick.next.next == null){
                return null;
            }
            quick = quick.next.next;
            slow = slow.next;
        }while(quick != slow);
        ListNode tmp = pHead;
        //找入口节点
        while(tmp != slow){
            tmp = tmp.next;
            slow = slow.next;
        }
        return tmp;
    }
}

JZ56 删除链表中的重复节点

题目描述

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

双指针，先新建一个头节点，一个指针记录当前遍历链表指针的前驱节点，一个指针遍历链表，然后向后查找值相同的节点，重复查找后删除

代码

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null || pHead.next == null)
            return pHead;
        //链接头节点，防止头节点被删
        ListNode first = new ListNode(-1);
        first.next = pHead;
        ListNode cur = pHead;
        ListNode pre = first;
        while(cur != null && cur.next != null){
            if(cur.val == cur.next.val){
                int val = cur.val;
                while(cur != null && cur.val == val){
                    cur = cur.next;
                }
                pre.next = cur;
            }else {
                pre = cur;
                cur =  cur.next;
            }
        }
        return first.next;
    }
}

JZ57 二叉树的下一个节点

题目描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
解题思路
1. 首先判断当前节点有无右孩子节点，如果有那么找右孩子的最左孩子，如果没有则进行2
2. 找第一个当前节点是父节点左孩子的节点

代码

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if(pNode == null){
            return pNode;
        }
        TreeLinkNode tmp;
        if(pNode.right != null){
            tmp = pNode.right;
            while(tmp.left != null){
                tmp = tmp.left;
            }
        }else {
            tmp = pNode.next;
            while(tmp != null && tmp.left != pNode){
                pNode = tmp;
                tmp = pNode.next;
            }
        }
        return tmp;
    }
}

JZ58 对称的二叉树

题目描述请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
解题思路

递归，判断两个镜像子树是否对称，即left.left与right.right或left.right与right.left

代码

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null) return true;
        return isSymmetrical(pRoot.left,pRoot.right);
    }
    
    private boolean isSymmetrical(TreeNode left,TreeNode right){
        if(left == null && right == null) return true;
        if(left == null || right == null) return false;
        return left.val == right.val && isSymmetrical(left.left,right.right) && isSymmetrical(left.right,right.left);
    }
}

JZ59 按之字形打印二叉树

题目描述

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

使用顺序表的辅助空间来实现，利用顺序表的头插实现逆序输出。

代码

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
    public static ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (depth % 2 == 0) {
                    tmp.add(node.val);
                } else {
                    tmp.add(0,node.val);
                }if (node.left != null) {
                    queue.add(node.left);
                }if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(tmp);
            depth++;
        }
        return res;
    }
}

JZ60 把二叉树打印成多行（BFS遍历二叉树）

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
解题思路

利用辅助空间链表或队列来存储节点，每层输出。

代码

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if(pRoot == null)
                return res;
            Queue<TreeNode> q = new LinkedList<>();
            q.add(pRoot);
            while(!q.isEmpty()){
                int size = q.size();
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = 0; i < size; i++){
                    TreeNode now = q.poll();
                    list.add(now.val);
                    if(now.left != null)
                        q.add(now.left);
                    if(now.right != null)
                        q.add(now.right);
                }
                res.add(list);
            }
            return res;
    }
}

JZ61 序列化二叉树

题目描述

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

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

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

例如，可以根据层序遍历并特定标志空结点的方案序列化，也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。

假如一棵树共有 2 个结点，其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,#,2,#,#”，按照上面第二种说法可以序列化为“{0:1,2:2}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息。

不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。
解题思路

二叉树的遍历

序列化：前序遍历二叉树存入字符串中

反序列化：根据前序遍历重建二叉树。

代码

public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val).append(",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }
    
    public int index = -1;
    TreeNode Deserialize(String str) {
        index++;
        if(index >= str.length()) return null;
        String[] ss = str.split(",");
        TreeNode root = null;
        if(!ss[index].equals("#")){
            root = new TreeNode(Integer.valueOf(ss[index]));
            root.left = Deserialize(str);
            root.right = Deserialize(str);
        }
        return root;
    }
}

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

题目描述

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点
解题思路

模拟二叉树的中序遍历，在每次打印节点时计数

代码

public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        int i = 1;
        if(pRoot == null || k <= 0) 
            return null;
        Stack<TreeNode> stack = new Stack();
        TreeNode node = pRoot;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if(i == k){
                return node;
            }else{
                i++;
            }
            node = node.right;
        }
        return null;
    }
}

JZ63 数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
1. 数组
  
  插入数时进行插入排序，size作为统计数据个数。
2. 堆
  
  维持一个大根堆一个小根堆，两个堆的元素个数差不超过1，大根堆大的值在队首，小根堆的所有元素大于大根堆的元素
  
  当元素个数为奇数时，大根堆比小根堆多一个元素，所以中位数为大根堆的堆顶
  
  当元素个数为偶数时，大根堆和小根堆元素个数相同，中位数为大根堆堆顶加小根堆堆顶的和

代码

数组

import java.util.Arrays;

public class Solution {
    private double[] arr = new double[16];
    private int size = 0;

    public void Insert(Integer num) {
        //数组扩容
        if(size == arr.length){
            arr = Arrays.copyOf(arr,arr.length << 1);
        }
        arr[size++] = num;
        //插入排序
        for(int i = size - 1;i > 0;i--){
            if(arr[i] >= arr[i - 1]){
                break;
            }else{
                arr[i] = arr[i - 1];
                arr[i - 1] = num;
            }
        }
    }

    public Double GetMedian() {
        return size % 2 == 0 ? (arr[size>>1] + arr[(size>>1)-1])/2 : arr[size/2];
    }
}

堆

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    int count = 0;
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(16, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
        
    public void Insert(Integer num) {
        count++;
        if((count & 1) == 1){
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }else {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
    }

    public Double GetMedian() {
        if(count == 0){
            return null;
        }
        
        return (count & 1) == 1 ?
                Double.valueOf(maxHeap.peek()) :
                Double.valueOf((maxHeap.peek().doubleValue() + minHeap.peek().doubleValue()) / 2);
    }
}

JZ64 滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{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. 双循环
  
  两个 for 循环，第一个 for 循环滑动窗口，第二个 for 循环滑动窗口中的
  值，寻找最大值。
2. 双端队列
  
  利用双端队列存储数量为size的依次递减的滑动窗口最大值，可能会出现只有最大值，最大值就是滑动窗口的最大值。

代码

双循环

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(num.length == 0 || size > num.length || size <= 0) return list;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i <= num.length - size;i++){
            max = num[i];
            for(int j = i;j < size + i;j++){
                max = max < num[j] ? num[j] : max;
            }
            list.add(max);
        }
        return list;
    }
}

双端队列

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> res = new ArrayList<>();
    	//辅助空间（保存下标），保存所有可能的最大值
    	Deque<Integer> deque = new ArrayDeque<>();
        //校验
        if(num == null || num.length < size || size <= 0 ) return res;
        //从左到右移动窗口 （要注意开始时窗口中元素数量不足的情况）
        for(int i = 0; i < num.length; i++){
        	//如果超出窗口范围，删除队列头元素
            if(!deque.isEmpty() && (i - deque.getFirst()) >= size){
                deque.pollFirst();
            }
            //当前元素大于队尾元素，则删除
            while(!deque.isEmpty() && num[i] > num[deque.getLast()]){
            	deque.pollLast();
            }
            //每次在队列尾部加入当前元素
            deque.addLast(i);
            //窗口中装满元素后才开始获取最大值
            if(i >= size-1){
            	res.add(num[deque.getFirst()]);//队列头元素为最大值，加入返回列表
            }
        }
        return res;
    }
}

JZ65 矩阵中的路径

题目描述

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nEiOIAxo-1631005074305)(C:\Users\胡东昇\Desktop\image-20210628102820500.png)]
解题思路

深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。

代码

import java.util.*;

public class Solution {
    
    public boolean hasPath (char[][] matrix, String word) {
        char[] words = word.toCharArray();
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0; j < matrix[0].length;j++){
                if(has(matrix,words,i,j,0))
                    return true;
            }
        }
        return false;
    }
    
    public boolean has (char[][] m, char[] word,int i,int j,int k) {
        if(i >= m.length || i < 0 ||  j >= m[0].length || j < 0 || m[i][j] != word[k])
            return false;
        if(k == word.length - 1)
            return true;
        m[i][j] = '\0';
        boolean res = has(m,word,i + 1,j,k + 1) || has(m,word,i - 1,j,k + 1) ||
            has(m,word,i,j + 1,k + 1) || has(m,word,i,j - 1,k + 1);
        m[i][j] = word[k];
        return res;
    }
}

JZ66 机器人的运动范围

题目描述

地上有一个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。请问该机器人能够达到多少个格子？

范围:

1 <= rows, cols<= 100

0 <= threshold <= 20
解题思路

DFS + 标记

BFS + 标记 + 栈/队列

代码

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] flag = new boolean[rows][cols];
        return dfs(0,0,rows,cols,threshold,flag);
    }
    
    public int dfs(int i,int j,int rows,int cols,int threshold,boolean[][] flag){
        if(i >= rows || j >= cols || threshold < sum(i,j) || flag[i][j]){
            return 0;
        }
        flag[i][j] = true;
        return 1 + dfs(i+1,j,rows,cols,threshold,flag) + dfs(i, j+1,rows,cols,threshold,flag);
    }
    
    private int sum(int i, int j) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum;
    }
}

JZ67 剪绳子

题目描述

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

基于贪心思想，对于每个子问题求解得到最优解，将子问题的最优解合并为原问题的解

代码

public class Solution {
    public int cutRope(int target) {
        int[] arr = new int[target + 1];
        arr[2] = 2;
        arr[3] = 3;
        for(int i = 4;i<=target;i++){
            //计算每个值的最优解
            arr[i] = max(i,arr);
        }
        return arr[target];
    }
    
    private int max(int n,int[] arr){
        int max = 0;
        for(int i = 2;i<n;i++){
            //消除重复计算，例如：2+3 == 3+2
            if(i > n>>1){
                return max;
            }
            //贪心思想的体现，将子问题的最优解合并为原问题的解
            int tmp = arr[i] * arr[n-i];
            //如果当前解大于最大值，则更新最大值
            if(tmp > max){
                max = tmp;
            }
        }
        return max;
    }
}

tion {

  public boolean hasPath (char[][] matrix, String word) {
      char[] words = word.toCharArray();
      for(int i = 0;i < matrix.length;i++){
          for(int j = 0; j < matrix[0].length;j++){
              if(has(matrix,words,i,j,0))
                  return true;
          }
      }
      return false;
  }
  
  public boolean has (char[][] m, char[] word,int i,int j,int k) {
      if(i >= m.length || i < 0 ||  j >= m[0].length || j < 0 || m[i][j] != word[k])
          return false;
      if(k == word.length - 1)
          return true;
      m[i][j] = '\0';
      boolean res = has(m,word,i + 1,j,k + 1) || has(m,word,i - 1,j,k + 1) ||
          has(m,word,i,j + 1,k + 1) || has(m,word,i,j - 1,k + 1);
      m[i][j] = word[k];
      return res;
  }

}


## JZ**66** 机器人的运动范围

* 题目描述

地上有一个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。请问该机器人能够达到多少个格子？

范围:

1 <= rows, cols<= 100

0 <= threshold <= 20

* 解题思路

DFS + 标记

BFS + 标记 + 栈/队列

* 代码

```java
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] flag = new boolean[rows][cols];
        return dfs(0,0,rows,cols,threshold,flag);
    }
    
    public int dfs(int i,int j,int rows,int cols,int threshold,boolean[][] flag){
        if(i >= rows || j >= cols || threshold < sum(i,j) || flag[i][j]){
            return 0;
        }
        flag[i][j] = true;
        return 1 + dfs(i+1,j,rows,cols,threshold,flag) + dfs(i, j+1,rows,cols,threshold,flag);
    }
    
    private int sum(int i, int j) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum;
    }
}

JZ67 剪绳子

题目描述

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

基于贪心思想，对于每个子问题求解得到最优解，将子问题的最优解合并为原问题的解

代码

public class Solution {
    public int cutRope(int target) {
        int[] arr = new int[target + 1];
        arr[2] = 2;
        arr[3] = 3;
        for(int i = 4;i<=target;i++){
            //计算每个值的最优解
            arr[i] = max(i,arr);
        }
        return arr[target];
    }
    
    private int max(int n,int[] arr){
        int max = 0;
        for(int i = 2;i<n;i++){
            //消除重复计算，例如：2+3 == 3+2
            if(i > n>>1){
                return max;
            }
            //贪心思想的体现，将子问题的最优解合并为原问题的解
            int tmp = arr[i] * arr[n-i];
            //如果当前解大于最大值，则更新最大值
            if(tmp > max){
                max = tmp;
            }
        }
        return max;
    }
}

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2021-09-08 10:59:23 更:2021-09-08 11:00:35

360图书馆购物三丰科技阅读网日历万年历 2024年11日历

-2024/11/26 0:38:42-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码