牛客网面试高频题top100（31~40）_牛客高频100详解

面试高频算法题top100（31~40）java实现

31.重建二叉树

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

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length==0) return null;
        TreeNode root = recon(pre,vin);
        return root;
        
    }
    public TreeNode recon(int [] pre,int [] vin){
        if(pre.length==0 || vin.length==0) return null;
        TreeNode root = new TreeNode(pre[0]);
        int t = 0;
        for(int i=0;i<vin.length;i++){
            if(vin[i]==pre[0]){
                t = i;
                break;
            }
        }
        root.left = recon(Arrays.copyOfRange(pre,1,t+1),Arrays.copyOfRange(vin,0,t));
        root.right = recon(Arrays.copyOfRange(pre,t+1,pre.length),Arrays.copyOfRange(vin,t+1,vin.length));
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

32.最长上升子序列（三）

给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）

import java.util.*;


public class Solution {
    public int[] LIS (int[] arr) {
        int n = arr.length;
        int[] dp =  new int[n];
        int len = 0;
        int[] res =  new int[n];
        for(int i=0;i<arr.length;i++){
            if(i==0 || arr[i]>res[len-1]){
                res[len] = arr[i];
                len ++;
                dp[i] = len;
            }else{
                int index = search(res,arr[i]);
                res[index] = arr[i];
                dp[i] = index + 1;
            }
        }
        int[] result = new int[len];
        for(int i=n-1;i>=0;i--){
            if(dp[i]==len)
                result[--len] = arr[i];
        }
        return result;
    }
    public int search(int[] res,int tar){
        int k=0;
        for(int i=0;i<res.length;i++){
            if(res[i]>=tar){
                k = i;
                break;
            }
        }
        return k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

33.求平方根

实现函数 int sqrt(int x).
计算并返回 x 的平方根（向下取整）

import java.util.*;


public class Solution {
    public int sqrt (int x) {
        int temp = 0,i=0;
        if (x==0) return 0;
        while(temp<=x){
            i++;
            temp = i;
            temp *= temp;
        }
        return i-1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

34.在旋转过的有序数组中寻找目标值

有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为[nums[k],nums[k+1],…,nums[nums.length-1],nums[0],nums[1],…,nums[k-1]]。
给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。
比如，数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4], 当给定target为10时，10的下标是2，target为3时，nums数组中不存在3，所以返回-1

import java.util.*;


public class Solution {
    public int search (int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid]==target) return mid;
            if(nums[left]<nums[mid]){
                if(nums[left]<=target && target<nums[mid])
                    right = mid-1;
                else
                    left = mid+1;
            }else{
                if(nums[mid]<target && target<=nums[right])
                    left = mid+1;
                else
                    right = mid-1;
            }
        }
        if(nums[left]==target) return left;
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

35.包含min函数的栈

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

import java.util.Stack;

public class Solution {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> stack1 = new Stack<>();
    public void push(int node) {
        stack.push(node);
        if(stack1.empty())
            stack1.push(node);
        else
            if(node<stack1.peek())
                stack1.push(node);
            else{
                int temp = stack1.peek();
                stack1.push(temp);
            }
                
    }
    
    public void pop() {
        stack.pop();
        stack1.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return stack1.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

36.买卖股票最好时机

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

import java.util.*;


public class Solution {
    public int maxProfit (int[] prices) {
        int buy = -prices[0];
        int sell = 0;
        for(int i=1;i<prices.length;i++){
            buy = Math.max(buy,-prices[i]);
            sell = Math.max(sell,buy+prices[i]);
        }
        return sell;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

37.合并K个已排序的链表

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return par(lists,0,lists.size()-1);
    }
    public ListNode par(ArrayList<ListNode> lists,int left,int right){
        if(left>right) return null;
        if(left==right) return lists.get(left);
        int mid = (left+right)/2;
        ListNode head1 = par(lists,left,mid);
        ListNode head2 = par(lists,mid+1,right);
        return merge(head1,head2);
    }
    public ListNode merge(ListNode head1,ListNode head2){
        if(head1==null || head2==null)
            return head2==null?head1:head2;
        ListNode head = null;
        if(head1.val<=head2.val){
            head = head1;
            head.next = merge(head1.next,head2);
        }else{
            head = head2;
            head.next = merge(head1,head2.next);
        }
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

38.字符串的排列

import java.util.ArrayList;
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        char[] cs = str.toCharArray();
        
        Allsort(cs,0);
        return res;
    }
    public void Allsort(char[] cs,int index){
        if(index==cs.length-1){
            String s = String.valueOf(cs);
            if(!res.contains(s))
                res.add(s);
            return;
        }
        for(int i=index;i<cs.length;i++){
            swap(cs,i,index);
            Allsort(cs,index+1);
            swap(cs,i,index);
        }
    }
    public void swap(char[] cs,int i,int j){
        if(i!=j){
            char c = cs[i];
            cs[i] = cs[j];
            cs[j] = c;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

39.接雨水问题

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

import java.util.*;


public class Solution {

    public long maxWater (int[] arr) {
        long sum=0;
        int left=0,right = arr.length-1;
        int min = 0,bucket =0;
        while(left<right){
            bucket = Math.min(arr[left],arr[right]);
            min = Math.max(min,bucket);
            sum += arr[left]<arr[right]? min-arr[left++]:min-arr[right--];
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

40.输出二叉树的右视图

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return in    t整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode root = recond(xianxu,zhongxu);
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while(!que.isEmpty()){
            int len = que.size();
            for(int i=0;i<len;i++){
                TreeNode temp = que.poll();
                if(i==len-1)
                    list.add(temp.val);
                if(temp.left!=null)
                    que.add(temp.left);
                if(temp.right!=null)
                    que.add(temp.right);
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
            
    }
    public TreeNode recond(int[] pre,int[] second){
        if(pre.length==0) return null;
        int t = 0;
        for(int i=0;i<second.length;i++){
            if(second[i]==pre[0]){
                t = i;
                break;
            }
        }
        TreeNode root = new TreeNode(pre[0]);
        root.left = recond(Arrays.copyOfRange(pre,1,t+1),Arrays.copyOfRange(second,0,t));
        root.right = recond(Arrays.copyOfRange(pre,t+1,pre.length),Arrays.copyOfRange(second,t+1,second.length));
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46