面试 Java 算法高频题五问五答第一期

作者：程序员小白条，个人博客

相信看了本文后，对你的面试是有一定帮助的！

⭐点赞⭐收藏⭐不迷路！⭐

1）括号生成:

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

主要思想：递归+回溯,递归函数形参(int n,int m,StringBuilder stringBuilder),先左括号再右括号

n表示左括号，m表示右括号,stringBuilder用来保存每次append后的临时字符串

if(n0&&m0) 说明左右括号都生成完毕，添加临时字符串到集合中

if(n>0) 说明应该左括号生成，append左括号，递归(n-1,m,stringBuilder)递归完成后再删除最后一个字符

if(m>n)说明右括号应该生成，先左后右，append右括号，递归(n,m-1,stringBuilder), 递归完成后再删除最后一个字符

class Solution {
      public ArrayList<String> arrayList = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        StringBuilder stringBuilder = new StringBuilder();
        backTrack(n,n,stringBuilder);
        return arrayList;
    }
    public void backTrack(int n,int m,StringBuilder stringBuilder){
        if(n==0&&m==0){
            arrayList.add(stringBuilder.toString());
            return;
        }
        if(n>0){
            stringBuilder.append("(");
            backTrack(n-1,m,stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
        // 因为先走if(n>0) 先左括号，然后左括号就会n-1,然后应该是右括号，此时m>n,因此如果要按左右的形式，此时条件应该是m>n
        if(m>n){
            stringBuilder.append(")");
            backTrack(n,m-1,stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }
}

2）单词搜索:

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” 输出：true

主要思想：深度优先搜索+递归+回溯

dfs函数传入board二维字符数组，i,j,此时的位置，String word,int index字符串该访问的位置，如果i和j此时不在范围内，或者board[i][j]!=s.charAt(index)return false; else if(index==word.length()-1) 如果已经到达最后一个字符，return true；，先将此时board[i][j] 置为任意一个不符合字母的字符，然后分别向上下左右，进行dfs递归，有一个方向成立，就是result = true, 然后将字符重置回来，board[i][j] = word[index];return result;

主函数：遍历二维字符数组，如果dfs为true,返回true,跳出所有循环返回false.

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

3）将有序数组转换为二叉搜索树:

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

主要思想：分治+递归，二叉中序遍历

功能函数build: 接受三个形参，nums数组，left左边界，right右边界,if(left>right) return null; int mid = (left+right)>>1,因为仅仅一个中序遍历确定不了具体的树，可以以中间节点的左边为分界，也可以mid=(left+right+1)>>1,以右边为分界,TreeNode treeNode= new TreeNode(nums[mid]);tree.left = build(left,mid-1),tree.right = build(mid+1,right),return treeNode;

class Solution {
   public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums,0,nums.length-1);
    }
    public TreeNode build(int [] num,int left,int right){
        if(left>right){
            return null;
        }
        int mid = (left+right)>>1;
        TreeNode treeNode = new TreeNode(num[mid]);
        treeNode.left = build(num,left,mid-1);
        treeNode.right = build(num,mid+1,right);
        return treeNode;
    }
}

4）排序链表:

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3] 输出：[1,2,3,4]

主要思想：分治+递归+合并链表

创建一个merge用于合并链表,主函数调用递归函数,传入两个链表，一个是头，一个是尾

if(head==null) return head;

if(head.next == tail) head.next = null; return head;

用快慢指针找出中间节点,while(fast!=tail&&fast.next!=tail) slow = slow.next; fast = fast.next.next;

ListNode mid = slow; 调用递归函数(head,mid) (mid,right)得到leftNode,rightNode,然后merge这两个链表即可。

5）最大子数组和:

主要思想：API函数+动态规划

class Solution {
   public int maxSubArray(int[] nums) {
        int tempMax = nums[0];
        int maxSum = nums[0];
        for(int i =1;i<nums.length;i++){
            tempMax = Math.max(nums[i],tempMax+nums[i]);
            maxSum = Math.max(tempMax,maxSum);
        }
        return maxSum;
    }
}