剑指offer题目--Java实现

ゝ一世哀愁。 2022-10-16 07:38 184阅读 0赞

# 一、简单 #

## 1.1 斐波那契数列–数组 ##

**描述：**

现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n ≤ 39

### ①递归 ###

**分析：**

斐波那契数列的公式：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N\*）

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

**复杂度：**

时间复杂度：O（2^n）  
 空间复杂度：O（1）

### ②优化递归 ###

递归会重复计算大量相同的数据，用数组把结果存起来

public class Solution {
        
        public int Fibonacci(int n) {
        
            int arr[] = new int[40];
            arr[0] = 0;
            arr[1] = 1;
            for(int i = 2;i <= n;i++){
        
                arr[i] = arr[i-1] + arr[i-2];
            }
            return arr[n];
        }
    }

**复杂度：**

时间复杂度：O（n）  
 空间复杂度：O（n）

## 1.2 从尾到头打印链表–链表 ##

**描述：**

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

**示例1：**

输入：\{1,2,3\}  
 返回值：\[3,2,1\]

**示例2：**

输入：\{67,0,24,58\}  
 返回值：\[58,24,0,67\]

### ①非递归 ###

listNode是链表，输入时从头到尾，输出时从尾到头，“先进后出”–栈

ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值

所以在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表

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

**复杂度：**

时间复杂度：O（n）  
 空间复杂度：O（n）

### ②递归 ###

借助系统的“栈”帮忙打印

import java.util.ArrayList;
    public class Solution {
        
        ArrayList<Integer> list = new ArrayList();
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
            if(listNode != null){
        
                printListFromTailToHead(listNode.next);
                list.add(listNode.val);
            }
            return list;
        }
    }

**复杂度：**

时间复杂度：O（n）  
 空间复杂度：O（n）

## 1.3 用两个栈实现队列–栈 ##

**描述：**

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

**示例：**

输入：\[“PSH1”,“PSH2”,“POP”,“POP”\]  
 返回值：1,2

**解析：**

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

**分析：**

栈：先进后出；队列：先进先出

当我们向模拟的队列插入数 a,b,c 时，假设插入的是 stack1，此时的栈情况为：

*  栈 stack1：\{a,b,c\}
 *  栈 stack2：\{\}

当需要弹出一个数，根据队列的"先进先出"原则，a 先进入，则 a 应该先弹出。但是此时 a 在 stack1 的最下面，将 stack1 中全部元素逐个弹出压入 stack2，现在可以正确的从 stack2 中弹出 a，此时的栈情况为：

*  栈 stack1：\{\}
 *  栈 stack2：\{c,b\}

继续弹出一个数，b 比 c 先进入"队列"，b 弹出，注意此时 b 在 stack2 的栈顶，可直接弹出，此时的栈情况为：

*  栈 stack1：\{\}
 *  栈 stack2：\{c\}

此时向模拟队列插入一个数 d，还是插入 stack1，此时的栈情况为：

*  栈 stack1：\{d\}
 *  栈 stack2：\{c\}

弹出一个数，c 比 d 先进入，c 弹出，注意此时 c 在 stack2 的栈顶，可直接弹出，此时的栈情况为：

*  栈 stack1：\{d\}
 *  栈 stack2：\{c\}

根据上述例子可得出结论：

当插入时，直接插入 stack1  
 当弹出时，当 stack2 不为空，弹出 stack2 栈顶元素，如果 stack2 为空，将 stack1 中的全部数逐个出栈入栈 stack2，再弹出 stack2 栈顶元素

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.size() <= 0){
        
                while(stack1.size() != 0){
        
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }

**复杂度：**

push时间复杂度：O（1）  
 pop空间复杂度：O（1）

## 1.4 旋转数组的最小数字–二分 ##

**描述：**

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

**示例：**

输入：\[3,4,5,1,2\]  
 返回值：1

### ①遍历数组，不断更新保存最小值变量 ###

import java.util.ArrayList;
    public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
            if(array.length == 0){
        
                return 0;
            }
            int tmp = array[0];
            for(int i = 1;i < array.length;i++){
        
                tmp = Math.min(tmp,array[i]);
            }
            return tmp;
        }
    }

时间复杂度：O（n）

### ②二分法，不断更新存在于两个子数组中的下标–待了解 ###

import java.util.ArrayList;
    public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
            if(array.length == 0){
        
                return 0;
            }
            int l = 0;
            int r = array.length-1;
            while(l < r-1){
        
                int mid = (l + r) >> 1;
                if(array[mid] >= array[l]){
        
                    l = mid;//说明mid所在的位置是第一个非递减子数组中
                }else if(array[mid] <= array[r]){
        
                    r = mid;//说明mid所在的位置是第二个非递减子数组中
                }
            }
            return array[r];
        }
    }

时间复杂度：O（log（n））

## 1.5 跳台阶–递归（与斐波那契数列类似） ##

**描述：**

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

**示例1：**

输入：2  
 返回值：2

**示例2：**

输入：7  
 返回值：21

**分析：**

与斐波那契数列类似，

### ①递推实现（不推荐） ###

public class Solution {
        
        public int jumpFloor(int target) {
        
            if(target == 1)
                return 1;
            if(target == 2)
                return 2;
            return jumpFloor(target-1) + jumpFloor(target-2);
        }
    }

时间复杂度：O（2^n）

### ②自底向上循环求解（面试推荐） ###

public class Solution {
        
        public int jumpFloor(int target) {
        
            int a=1,b=1;
            for(int i = 2;i <= target;i++){
        
                //求f[i]=f[i-1]+f[i-2]
                a = a+b;//这里求得的f[i]可以用于下次循环求f[i+1]
                //f[i-1]=f[i]-f[i-2]
                b = a-b;//这里求得的f[i-1]可以用于下次循环求f[i+1]
            }
            return a;
        }
    }

时间复杂度：O（n）

## 1.6 跳台阶扩展问题（变态跳台阶）–递归、动态规划 ##

**描述：**

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

**示例：**

输入：3  
 返回值：4

*  f(n)=f(n-1)+f(n-2)+…+f(1)
 *  f(n-1)=f(n-2)+…f(1)
 *  得：f(n)=2\*f(n-1)

public class Solution {
        
        public int jumpFloorII(int target) {
        
            return 1<<(target-1);
            //return (int)Math.pow(2,target-1);
        }
    }

## 1.7 合并两个排序的链表–链表 ##

**描述：**

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

**示例：**

输入：\{1,3,5\},\{2,4,6\}  
 返回值：\{1,2,3,4,5,6\}

### ①遍历两个链表，按大小顺序拼接 ###

public class Solution {
        
        public ListNode Merge(ListNode list1,ListNode list2) {
        
            ListNode list3 = new ListNode(0);
            ListNode move = list3;
            
            while(list1 != null && list2 != null){
        
                if(list1.val > list2.val){
        
                    move.next = list2;
                    list2 = list2.next;
                }else{
        
                    move.next = list1;
                    list1 = list1.next;
                }
                move = move.next;
            }
            
            if(list1 != null){
        
                move.next = list1;
            }
            if(list2 != null){
        
                move.next = list2;
            }
            return list3.next;
        }
    }

### ②递归 ###

public class Solution {
        
        public ListNode Merge(ListNode list1,ListNode list2) {
        
            if(list1 == null){
        
                return list2;
            }else if(list2 == null){
        
                return list1;
            }else{
        
                if(list1.val < list2.val){
        
                    list1.next = Merge(list1.next,list2);
                    return list1;
                }else{
        
                    list2.next = Merge(list1,list2.next);
                    return list2;
                }
            }
        }
    }

## 1.8 二叉树的镜像–树 ##

**描述：**

操作给定的二叉树，将其变换为源二叉树的镜像。  
![在这里插入图片描述][20210704111636391.png]  
**示例：**

输入：\{8,6,10,5,7,9,11\}  
 返回值：\{8,10,6,11,9,7,5\}

**先镜像当前root的左右节点，然后再递归镜像左孩子和右孩子即可**

import java.util.*;
    
    public class Solution {
        
        public TreeNode Mirror (TreeNode pRoot) {
        
            // write code here
            if(pRoot == null)
                return pRoot;
            TreeNode tmp = pRoot.left;
            pRoot.left = pRoot.right;
            pRoot.right = tmp;
            
            Mirror(pRoot.left);
            Mirror(pRoot.right);
            return pRoot;
        }
    }

## 1.9 包含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

peek()函数返回栈顶的元素，但不弹出该栈顶元素

**分析：**

使用两个栈：一个用来存所有元素，另一个用来存放加入新的元素后当前栈的最小值。

两个栈中的元素数量始终保持一致，当新的元素小于栈顶元素时，向栈顶push新来的元素；否则，向栈顶加入原栈顶元素

import java.util.Stack;
    
    public class Solution {
        
        Stack<Integer> stackAll = new Stack<Integer>();
        Stack<Integer> stackLittle = new Stack<Integer>();
        
        public void push(int node) {
        
            stackAll.push(node);
            if(stackLittle.empty()){
        
                stackLittle.push(node);
            }else{
        
                if(node <= stackLittle.peek()){
        
                    stackLittle.push(node);
                }else{
        
                    stackLittle.push(stackLittle.peek());
                }
            }
        }
        
        public void pop() {
        
            stackAll.pop();
            stackLittle.pop();
        }
        
        public int top() {
        
            return stackAll.peek();
        }
        
        public int min() {
        
            return stackLittle.peek();
        }
    }

## 1.10 数组中出现次数超过一半的数字–数组、哈希 ##

**描述：**

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组\[1,2,3,2,2,2,5,4,2\]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000

**示例1：**

输入：\[1,2,3,2,2,2,5,4,2\]  
 返回值：2

**示例2：**

输入：\[3,3,3,3,2,2,2\]  
 返回值：3

**示例3：**

输入：\[1\]  
 返回值：1

**分析：**

用preVal记录上一次访问的值，count表示当前值出现的次数，如果下一个值和当前值相同，那么count++；如果不同，count–，减到0的时候就要更换新的preVal值了，因为如果存在超过数组长度一般的值，那么最后preVal一定是该值

public class Solution {
        
        public int MoreThanHalfNum_Solution(int [] array) {
        
            if(array == null || array.length == 0)
                return 0;
            int preVal = array[0];
            int count = 1;
            for(int i = 1;i <array.length;i++){
        
                if(array[i] == preVal){
        
                    count++;
                }else{
        
                    count--;
                    if(count == 0){
        
                        preVal = array[i];
                        count = 1;
                    }
                }
            }
            //判断数字数量是否真的大于数组的一半
            int number = 0;
            for(int i = 0;i <array.length;i++){
        
                number++;
            }
            return (number > array.length/2)?preVal : 0;
        }
    }

## 1.11 连续子数组的最大和–动态规划、分治 ##

**描述：**

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

**示例：**

输入：\[1,-2,3,10,-4,7,2,-5\]  
 返回值：18

说明：输入的数组为\{1，-2,3,10，-4,7,2，-5\}，和最大的子数组为\{3,10，-4，7,2\}，因此输出为该子数组的和为18

public class Solution {
        
        public int FindGreatestSumOfSubArray(int[] array) {
        
            int max = array[0];
            for(int i = 1;i < array.length;i++){
        
                array[i] += array[i-1] > 0 ? array[i-1] : 0;
                max = Math.max(max,array[i]);
            }
            return max;
        }
    }

## 1.12 第一个只出现一次的字符位置–字符串–待了解 ##

**描述：**

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

**示例：**

输入：“google”  
 返回值：4

public class Solution {
        
        public int FirstNotRepeatingChar(String str) {
        
            if(str == null || str.length() == 0)
                return -1;
            int [] count = new int[128];
            //用一个类似于hash的东西来存储字符出现的次数
            for(int i = 0;i < str.length();i++){
        
                count[str.charAt(i)]++;
            }
            //
            for(int i = 0;i < str.length();i++){
        
                if(count[str.charAt(i)] == 1){
        
                    return i;
                }
            }
            return -1;
        }
    }

## 1.13 两个链表的第一个公共结点–链表 ##

**描述：**

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

**示例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，后台打印\{\}

public class Solution {
        
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        
            if(pHead1 == null || pHead2 == null)
                return null;
            ListNode p1 = pHead1;
            ListNode p2 = pHead2;
            while(p1 != p2){
        
                p1 = p1.next;
                p2 = p2.next;
                if(p1 != p2){
        
                    if(p1 == null)
                        p1 = pHead2;
                    if(p2 == null)
                        p2 = pHead1;
                }
            }
            return p1;
        }
    }

## 1.14 二叉树的深度–树--待了解 ##

**描述：**

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

**示例：**

输入：\{1,2,3,4,5,\#,6,\#,\#,7\}  
 返回值：4

### ①递归 ###

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

## 1.15 平衡二叉树–树、dfs–待了解 ##

**描述：**

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

注：我们约定空树是平衡二叉树。

**示例：**

输入：\{1,2,3,4,5,6,7\}  
 返回值：true

public class Solution {
        
        public boolean IsBalanced_Solution(TreeNode root) {
        
            return depth(root) != -1;
        }
        public int depth(TreeNode root){
        
            if(root == null)
                return 0;
            int left = depth(root.left);
            if(left == -1)
                return -1;//如果发现子树不平衡之后就没必要进行下面高度的求解
            
            int right = depth(root.right);
            if(right == -1)
                return -1;
            
            if(left - right < (-1) || left - right > 1)
                return -1;
            else
                return 1+(left > right?left : right);
        }
    }

## 1.16 扑克牌顺子–模拟–待了解 ##

**描述：**

现在有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\]

**示例1：**

输入：\[6,0,2,0,4\]  
 返回值：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.TreeSet;
    public class Solution {
        
        public boolean IsContinuous(int [] numbers) {
        
            if(numbers.length < 5 || numbers.length > 5)
                return false;
            int num = 0;
            TreeSet<Integer> set = new TreeSet<>();
            for(int i = 0;i < numbers.length;i++){
        
                if(numbers[i] == 0){
        
                    num++;
                }else{
        
                    set.add(numbers[i]);
                }
            }
            if((num + set.size() != 5)){
        
                return false;
            }
            if((set.last() - set.first()) < 5){
        
                return true;
            }
            return false;
        }
    }

## 1.17 不用加减乘除做加法 ##

**描述：**

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

**示例：**

输入：1,2  
 返回值：3

### 位运算 ###

**一位加法：**  
![在这里插入图片描述][20210707182907185.png]  
![在这里插入图片描述][20210707182917952.png]  
**“<<”表示向左移动一位，也就是进位**

**（x & y）<< 1**

两个表达式：

*  执行加法 x ^ y
 *  进位操作 ( x & y ) << 1

**二位加法：**  
![在这里插入图片描述][20210707183357587.png]

public class Solution {
        
        public int Add(int num1,int num2) {
        
            int res1 = 0;
            int res2 = 0;
            do{
        
                res1 = num1 ^ num2;//不带进位的加法
                res2 = (num1 & num2) << 1;//进位
                num1 = res1;
                num2 = res2;
            }while(res2 != 0);
            return res1;//进位不为0则继续执行加法处理进位
        }
    }

**复杂度：**

时间复杂度：O（1）//最高执行32次，int大小32位  
 空间复杂度：O（1）

## 1.18 数组中重复的数字–数组 ##

**描述：**

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

**示例：**

输入：\[2,3,1,0,2,5,3\]  
 返回值：2

说明：2或3都是对的

**重复性问题需要想到set，遍历数组依次加入集合，若集合中存在该元素则直接返回该元素，否则将该元素加入集合**

import java.util.*;
    
    public class Solution {
        
        public int duplicate (int[] numbers) {
        
            // write code here
            Set<Integer> set = new HashSet<Integer>();
            for(int i : numbers){
        
                if(set.contains(i)){
        
                    return i;
                }else{
        
                    set.add(i);
                }
            }
            return -1;
        }
    }

## 1.19 构建乘积数组–数组 ##

**描述：**

给定一个数组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,2,3,4,5\]  
 返回值：\[120,60,40,30,24\]

**分析：**

数组 B\[i\] = A\[0\]A\[1\]…A\[i-1\]A\[i+1\]…A\[n-1\]，即除去 A\[i\] 的所有值相乘

可以将 A\[i\] 设为1，再用 for 循环将 A 中所有值相乘  
 临时变量 temp 先存储 A\[i\] 的值，然后再赋回来。

import java.util.ArrayList;
    public class Solution {
        
        public int[] multiply(int[] A) {
        
            int[] B = new int[A.length];
            int tmp = 0;
            for(int i = 0;i < A.length;i++){
        
                tmp = A[i];
                A[i] = 1;
                B[i] = 1;
                for(int j = 0;j < A.length;j++){
        
                    B[i] *= A[j];
                }
                A[i] = tmp;
            }
            return B;
        }
    }

## 1.20 二叉搜索树的第k个结点–树 ##

**描述：**

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

**示例：**

输入：\{5,3,7,2,4,6,8\},3  
 返回值：4

说明：按结点数值大小顺序第三小结点的值为4

**非递归实现：二叉搜索树的第k个结点 中序遍历**

import java.util.Stack;
    public class Solution {
        
        TreeNode KthNode(TreeNode pRoot, int k) {
        
            if(pRoot == null || k <= 0){
        
                return null;
            }
            Stack<TreeNode> stack = new Stack<>();//建立栈
            TreeNode cur = pRoot;
            //while部分为中序遍历
            while(!stack .isEmpty() || cur != null){
        
                if(cur != null){
        
                    stack.push((cur));//当前结点不为null，应该寻找左孩子
                    cur = cur.left;
                }else{
        
                    cur = stack.pop();//当前结点null则弹出栈内元素，相当于按顺序输出最小值
                    if(--k == 0){
        
                        return cur;
                    }
                    cur = cur.right;
                }
            }
                        return null;
        }
    }

## 1.21 按之字形顺序打印二叉树–栈、树 ##

**描述：**

给定一个二叉树，返回该二叉树的之字形层序遍历，（**第一层从左向右，下一层从右向左，一直这样交替**）  
例如：  
 给定的二叉树是\{1,2,3,\#,\#,4,5\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70]  
该二叉树之字形层序遍历的结果是  
\[  
\[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\]\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70 1]

import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
            if(pRoot == null)
                return result;
            Stack<TreeNode> tmp = new Stack<>();
            Stack<TreeNode> tmp1 = new Stack<>();
            tmp.add(pRoot);
            
            while(tmp.size() >0 || tmp1.size() > 0){
        
                ArrayList<Integer> flood = new ArrayList<>();
                
                if(tmp.size() > 0){
        
                    int size = tmp.size();
                    for(int i = 0;i < size;i++){
        
                        TreeNode pop = tmp.pop();
                        flood.add(pop.val);
                        if(pop.left != null){
        
                            tmp1.add(pop.left);
                        }
                        if(pop.right != null){
        
                            tmp1.add(pop.right);
                        }
                    }
                    result.add(flood);
                    continue;
                }
                
                if(tmp1.size() > 0){
        
                    int size = tmp1.size();
                    for(int i = 0;i < size;i++){
        
                        TreeNode pop = tmp1.pop();
                        flood.add(pop.val);
                        if(pop.right != null){
        
                            tmp.add(pop.right);
                        }
                        if(pop.left != null){
        
                            tmp.add(pop.left);
                        }
                    }
                    result.add(flood);
                    continue;
                }
            }
            return result;
        }
    }

# 二、中等 #

## 2.1 剪绳子–数学 ##

**描述：**

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

**输入描述：**

输入一个数n，意义见题面。（2 <= n <= 60）

**返回值描述：**

输出答案

**示例：**

输入：8  
 返回值：18

public class Solution {
        
        /**
        * 解题思路，找出最优解的规律
        * 当target等于1，2，3的时候，结果是固定的
        * 当target大于3的时候，可以看以下数据
        * target=4, 最优解：2 2
        * target=5, 最优解：3 2
        * target=6, 最优解：3 3
        * target=7, 最优解：3 2 2
        * target=8, 最优解：3 3 2
        * target=9, 最优解：3 3 3
        * target=10,最优解：3 3 2 2
        * target=11,最优解：3 3 3 2
        * target=12,最优解：3 3 3 3
        * target=13,最优解：3 3 3 2 2
        * target=14,最优解：3 3 3 3 2
        * target=15,最优解：3 3 3 3 3
        *
        * 所以不难发现3和2的个数规律
        */
        public int cutRope(int target) {
        
            if(target <= 0)
                return 0;
            if(target == 1 || target == 2)
                return 1;
            if(target == 3)
                return 2;
            int m = target % 3;
            switch(m){
        
                case 0:
                    return (int)Math.pow(3,target/3);
                case 1:
                    return (int)Math.pow(3,target/3 - 1)*4;
                case 2:
                    return (int)Math.pow(3,target/3)*2;
            }
            return 0;
        }
    }

pow函数：输出第一个参数的第二个参数次方

## 2.2 二维数组中的查找–数组 ##

**描述：**

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。  
\[  
  \[1,2,8,9\],  
  \[2,4,9,12\],  
  \[4,7,10,13\],  
  \[6,8,11,15\]  
\]

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

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

**示例2：**  
 输入：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) {
        
            for(int i = 0;i < array.length;i++){
        
                for(int j = 0;j < array[0].length;j++){
        
                    if(array[i][j] == target){
        
                        return true;
                    }
                }
            }
            return false;
        }
    }

注：j < array\[0\].length是array\[0\],不是array\[i\]

**复杂度：**

时间复杂度：O（n^2）  
 空间复杂度：O（1）

### ②从左下找 ###

**分析：**

利用该二维数组的性质：

每一行都按照从左到右递增的顺序排序，  
 每一列都按照从上到下递增的顺序排序

改变个说法，即对于左下角的值 m，m 是该行最小的数，是该列最大的数  
每次将 m 和目标值 target 比较：

1)当 m < target，由于 m 已经是该行最大的元素，想要更大只有从列考虑，取值右移一位  
 2)当 m > target，由于 m 已经是该列最小的元素，想要更小只有从行考虑，取值上移一位  
 3)当 m = target，找到该值，返回 true

用某行最小或某列最大与 target 比较，每次可剔除一整行或一整列

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

**复杂度：**

时间复杂度：O（行高 + 列宽）  
 空间复杂度：O（1）

## 2.3 重建二叉树–数组、树、dfs ##

**描述：**

给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。  
 例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建出如下图所示。  
![在这里插入图片描述][20210719140842744.png]  
提示:

1.0 <= pre.length <= 2000  
 2.vin.length == pre.length  
 3.0 <= pre\[i\], vin\[i\] <= 10000  
 4.pre 和 vin 均无重复元素  
 5.vin出现的元素均出现在 pre里  
 6.只需要返回根结点，系统会自动输出整颗树做答案对比

**示例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.根据前序序列第一个结点确定根结点
 *  2.根据根结点在中序序列中的位置分割出左右两个子序列
 *  3.对左子树和右子树分别递归使用同样的方法继续分解

例如：

前序序列\{1,2,4,7,3,5,6,8\} = pre  
 中序序列\{4,7,2,1,5,3,8,6\} = in

*  根据当前前序序列的第一个结点确定根结点，为 1
 *  找到 1 在中序遍历序列中的位置，为 in\[3\]
 *  切割左右子树，则 in\[3\]前面的为左子树， in\[3\] 后面的为右子树
 *  则切割后的左子树前序序列为：\{2,4,7\}，切割后的左子树中序序列为：\{4,7,2\}；切割后的右子树前序序列为：\{3,5,6,8\}，切割后的右子树中序序列为：\{5,3,8,6\}
 *  对子树分别使用同样的方法分解

import java.util.Arrays;
    public class Solution {
        
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        
            if(pre.length == 0 || in.length == 0){
        
                return null;
            }
            TreeNode root = new TreeNode(pre[0]);
            //在中序中找到前序的根
            for(int i = 0;i < in.length;i++){
        
                if(in[i] == pre[0]){
        
                    //左子树，注意copyOfRange函数，左闭右开
                    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                    //右子树，注意copyOfRange函数，左闭右开
                    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
                    break;
                }
            }
            return root;
        }
    }

复杂度：

时间复杂度：O（n）  
 空间复杂度：O（n）

## 2.4 矩形覆盖–递归、动态规划 ##

**描述：**

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

比如n=3时，2\*3的矩形块有3种不同的覆盖方法(从同一个方向看)：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70 2]  
**输入描述：**

2\*1的小矩形的总个数n

**返回值描述：**

覆盖一个2\*n的大矩形总共有多少种不同的方法(从同一个方向看)

**示例1：**

输入：0  
 返回值：0

**示例2：**

输入：1  
 返回值：1

**示例3：**

输入：4  
 返回值：5

### ①简单的递归 ###

n = 1 时

只能横着覆盖，一种

n = 2 时

可以横着和竖着覆盖，两种

n = 3 时

第三级横着覆盖，用了一级，剩下 n = 2，有两种覆盖方法  
 第三季竖着覆盖，用了两级，剩下 n = 1，有一种覆盖方法  
 总共有 3 种

n = 4 的时候

第 4 级横着覆盖，用了一级，剩下 n = 3，有三种覆盖方法  
 第 4 级竖着覆盖，用了两级，剩下 n = 2，有两种覆盖方法  
 总共有 5 种方法

n = n 的时候

第 n 级横着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法  
 第 n 级竖着覆盖，用了两级，剩下 n = n - 2，所以关注第 n - 2 种有几种覆盖方法  
 总和为两种情况的总和

从 n = 1 到 n = 4 的示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70 3]  
 所以回答上面的问题，涂掉最后一级矩阵的时候，可以选择使用横向完成，也可以使用竖向完成，横向涂剩下 n - 1 阶，竖向涂剩下 n - 2 阶

关注 n - 1 与 n - 2 时的涂法有几种，这就是斐波那契数列

public class Solution {
        
        public int rectCover(int target) {
        
            if(target <= 0){
        
                return 0;
            }
            if(target == 1){
        
                return 1;
            }
            if(target == 2){
        
                return 2;
            }
            return rectCover(target-1) + rectCover(target-2);
        }
    }

### ②迭代 ###

public class Solution {
        
        public int rectCover(int target) {
        
            if(target <= 2){
        
                return target;
            }
            int pre1 = 2;//n最后使用一块，剩下n-1块的写法
            int pre2 = 1;//n最后使用两块，剩下n-2块的写法
            for(int i = 3;i <= target;i++){
        
                int tmp = pre1 + pre2;
                pre2 = pre1;
                pre1 = tmp;
            }
            return pre1;//相对于n+1块来说，第n种的方法
        }
    }

## 2.5 二进制中1的个数–数学 ##

**描述：**

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

**示例1：**

输入：10  
 返回值：2

如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。

举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

public class Solution {
        
        public int NumberOf1(int n) {
        
            int count = 0;
            while(n != 0){
        
                count++;
                n = n&(n-1);
            }
            return count;
        }
    }

## 2.6 数值的整数次方–数学 ##

**描述：**

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

保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数

**示例1：**

输入：2.00000,3  
 返回值：8.00000

**示例2：**

输入：2.10000,3  
 返回值：9.26100

**示例3：**

输入：2.00000,-2  
 返回值：0.25000

说明：2的-2次方等于1/4=0.25

public class Solution {
        
        public double Power(double base, int exponent) {
        
            if(base == 0.0)
                return 0.0;
            double result = 1.0;
            int e = exponent > 0 ? exponent : -exponent;
            
            for(int i = 1;i <= e;i++){
        
                result *= base;
            }
            return exponent >0 ? result : 1/result;
      }
    }

## 2.7 调整数组顺序使奇数位于偶数前面–数组 ##

**描述：**

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

**示例1：**

输入：\[1，2，3，4\]  
 返回值：\[1，3，2，4\]

**示例2：**

输入：\[2，4，6，5，7\]  
 返回值：\[5,7，2,4，6\]

import java.util.*;
    public class Solution {
        
        public int[] reOrderArray (int[] array) {
        
            // write code here
            if(array == null || array.length == 0)
                return array;
            int tmp = 0;
            int j = 0;//记录已为奇数的位置
            for(int i = 0;i < array.length;i++){
        
                tmp = array[i];
                if(array[i]%2 == 0){
        
                    continue;
                }else{
        
                    int k = i;
                    while(k > j){
        
                        array[k] = array[k-1];//数组整体后移一位
                        k--;
                    }
                    array[k] = tmp;
                    j++;
                }
            }
            return array;
        }
    }

# 三、较难 #

## 3.1 替换空格 ##

**描述：**

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

**示例：**  
 输入：“We Are Happy”  
 返回值：“We%20Are%20Happy”

### ①String.replaceAll() ###

### ②Spring.split() ###

import java.util.*;
    
    
    public class Solution {
        
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param s string字符串 
         * @return string字符串
         */
        public String replaceSpace (String s) {
        
             StringBuilder sb = new StringBuilder();
        if (s == null || "".equals(s))
            return s;
        String[] strs = s.split("");
        for (String str : strs) {
        
            if (" ".equals(str))
                sb.append("%20");
            else
            sb.append(str);
        }
        return sb.toString();
        }
    }

[20210704111636391.png]: /images/20221014/8b1cbd2fae3247d3b3d09295e5370ece.png
[20210707182907185.png]: /images/20221014/04c761396fa44edebe750975f388871a.png
[20210707182917952.png]: /images/20221014/787fcc13bd674bcda86a918786d31de8.png
[20210707183357587.png]: /images/20221014/b58972dcb0de42aa9ca5f7e0ab9c6fc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70]: /images/20221014/bc11f11ad1564fc89f441634fa662d2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70 1]: /images/20221014/2377b0b48f6b4e579e17c8612870144e.png
[20210719140842744.png]: /images/20221014/fcb6ec0daed448468bc890aa639c316d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70 2]: /images/20221014/8e517e5bf9244d6390ce3c298c6532f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDExNjA5OA_size_16_color_FFFFFF_t_70 3]: /images/20221014/2691e6238a314600bc72a9554840630d.png