Java后端开发算法基础面试题分享，你拿offer也许就差这份面试题！

Bertha 。 2022-12-05 02:16 200阅读 0赞

## 前言： ##

> Java后端技术很重要，但是技术能学成什么样不只是靠努力就行的，学这个专业的我们都知道，技术很重要，但是学这个技术，逻辑又很重要，特别是对后端来说。所以有时候很多面试时，往往会被问到逻辑问题，因为他们会需要看你的思维能力，然后评估你的学习能力、接受能力、可塑性。

# 一、算法基础 #

## 1、重建二叉树 ##

题目：

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

> 注意： 二叉树中每个节点的值都互不相同； 输入的前序遍历和中序遍历一定合法；

演示：

给定：  
前序遍历是：\[3, 9, 20, 15, 7\]  
中序遍历是：\[9, 3, 15, 20, 7\]

返回：\[3, 9, 20, null, null, 15, 7, null, null, null, null\]  
返回的二叉树如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center]

> 分析： 前序的第一个字母肯定是父节点, 然后再去中序找该节点对应的位置, 位置前是左子树, 后是右子树。以此类推。

代码：

class Solution { 
        Map<Integer,Integer> map = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            
            for(int i = 0 ; i< inorder.length; i++){ 
                map.put(inorder[i],i);
            }
            return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        }
        
        public TreeNode dfs(int [] preorder, int [] inorder, int pl, int pr, int il, int ir){ 
            if(pl > pr){ 
                return null;
            }
            TreeNode root = new TreeNode(preorder[pl]);
            int k = map.get(preorder[pl])-il;
            root.left = dfs(preorder,inorder,pl+1,pl+k,il,il+k-1);
            root.right = dfs(preorder,inorder,pl+k+1,pr,il+k+1,ir);
            return root;
        }
    }

## 2、替换空格 ##

题目：

请实现一个函数，把字符串中的每个空格替换成"%20"。

你可以假定输入字符串的长度最大是1000。 注意输出字符串的长度可能大于1000。

演示：

输入："We are happy."
    输出："We%20are%20happy."

分析：

考察对char的处理

代码：

class Solution { 
        public String replaceSpaces(StringBuffer str) { 
            char[] chars = str.toString().toCharArray();
            StringBuffer result = "";
            for(char i:chars){ 
                if(i == ' '){ 
                    result.append("%20");
                }else{ 
                    result.append(i);
                }
            }
            return result.toString();
        }
    }

## 3、二叉搜索树的后序遍历序列 ##

题目：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

演示：

输入：[4, 8, 6, 12, 16, 14, 10]
    输出：true

分析：

后序遍历的特点是根在最后, 拿这个为突破点, 因为是搜索树, 所以自然有序, 拿到不符合有序的交界节点, 则其前应为小数升序, 其后为大数升序, 不满足则返回false

代码：

class Solution { 
        public boolean verifySequenceOfBST(int [] sequence) { 
            // 迭代， 拿到最后一个元素 即根节点
            return dfs(sequence, 0 , sequence.length-1);
        }
        public boolean dfs(int [] sequence, int l, int r){ 
            if(l >= r){ return true;}
            // 拿到最后一个元素
            int root = sequence[r];
            // 遍历前面比root小的数， 拿到一个k
            int k = l;
            while( k < r && sequence[k]<root) k++;
            // 拿到k后， 遍历判断后面的数是不是都符合条件
            for(int i = k; i< r; i++){ 
                if(sequence[i]<root){ 
                    return false;
                }
            }
            return dfs(sequence, l , k-1 )&&dfs(sequence, k , r-1);
            
        }
    }

## 4、二叉树中和为某一值的路径 ##

题目：

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

演示：

给出二叉树如下所示，并给出num=22。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 1]

> 输出：\[\[5,4,12,1\],\[5,6,6,5\]\]

class Solution { 
        private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> findPath(TreeNode root, int sum) { 
            dfs(root, sum, new ArrayList<>());
            return res;
        }
        
        private void dfs(TreeNode root, int sum, List path){ 
            if(root == null){ 
                return;
            }
            path.add(root.val);
            sum -= root.val;
            if(sum == 0 && root.left == null && root.right == null){ 
                res.add(new ArrayList<>(path));
            }else{ 
                dfs(root.left, sum, path);
                dfs(root.right, sum, path);
            }
            path.remove( path.size() -1);
        }
    }

## 5、 斐波那契数列 ##

题目：

输入一个整数 n ，求斐波那契数列的第 n 项。

假定从0开始，第0项为0。(n<=39)

演示：

输入整数 n=5
    返回 5

分析：  
最基础的做法就是用递归， 进阶做法用动态规划

代码：

class Solution { 
        public int Fibonacci(int n) { 
             // 如果是 1 和 2 则直接返回
             if(n == 1 || n == 2){ 
                 return 1;
             }
             // 否则的话动态规划
             n -= 2;
             
             int a = 1;
             int b = 1;
             int c = 0;
             while(n > 0){ 
                c = a + b;
                a = b;
                b = c;
                n--;
             }
             return c;
        }
    }

## 6、 跳台阶 ##

题目：

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

代码：

public class Solution { 
        public int JumpFloor(int n) { 
             // 如果是 1 和 2 则直接返回
             if(n <= 2){ 
                 return n;
             }
             // 否则的话动态规划
             n -= 2;
             
             int a = 1;
             int b = 2;
             int c = 0;
             while(n > 0){ 
                c = a + b;
                a = b;
                b = c;
                n--;
             }
             return c;
        }
    }

## 7、栈的压入、弹出序列 ##

题目：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

演示：

输入：
    [1,2,3,4,5]
    [4,5,3,2,1]
    输出：true

分析：

用一个真实的栈来辅助, 当pop的值和弹出序列的某个数相等&&栈不为空, 则弹出这个数。最后看栈是否为空, 如果不是正确的压入弹出顺序, 栈是空不了的。

代码：

class Solution { 
        public boolean isPopOrder(int [] pushV,int [] popV) { 
            // 如果两个数组为空， 直接返回true， 两个数组长度不等， 返回false
            if(pushV == null && popV == null){ 
                return true;
            }
            if(pushV.length != popV.length){ 
                return false;
            }
            // 新建一个栈， 将push一个一个放入， 并判断
            // 如果元素与popV的top元素相等， 则弹出popV， 否则继续在stack里放元素
            // 如果顺序正确的话， PopV应该会为空值
            Stack<Integer> stack = new Stack<>();
            int index = 0;
            for(int i = 0; i< popV.length; i++){ 
                stack.push(pushV[i]);
                while(!stack.isEmpty() && stack.peek() == popV[index]){ 
                    stack.pop();
                    index++;
                }
            }
            return stack.isEmpty();
        }
    }

## 8、二叉搜索树的后序遍历序列 ##

题目：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

演示：

输入：\[4, 8, 6, 12, 16, 14, 10\]  
输出：true

分析：

代码：

## 9、二叉树的镜像 ##

题目：

输入一个二叉树，将它变换为它的镜像。

演示：

输入树：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 2]

> \[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null\]

输出树：  
递归思想, 交换当前节点的左右子节点, 然后遍历整个树  
代码：

class Solution { 
        public void mirror(TreeNode root) { 
            if(root == null){ 
                return ;
            }
            // swap(left,right)
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            
            mirror(root.left);
            mirror(root.right);
            
        }
    }

## 结语： ##

当然，不是说光有算法基础就能面试成功的，Java还有很多知识点，碰到什么问题都是可能的，所以我这里整理有海量的2020年最新的Java面试资料以及Java后端各方面的学习资料。如果有需要的可以[点击进入][Link 1]暗号：cszq，免费拿。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 4]

> 最后祝各位小伙伴都能面试顺利哦！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/356a4ef379384466b21af9cd6dced8c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/90c5937a920c455d8dc1ac74557dad68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/fecec48f809e427f962c2caf40d01028.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=Wqu4GEw7
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/20e6ee7c3b5d487e824e5bb4085e51b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjcwNjY3_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/cac93a1cb2d54c8cab983da4ba1e0602.png