当前位置:   article > 正文

牛客网面试高频题top100(1~10)_牛客网100题

牛客网100题

*牛客网面试高频题top100(1~10 java实现)

1.反转链表

描述:
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

public class Solution {
    public ListNode ReverseList(ListNode head) {
    if(head==null) return null;
        ListNode pre = null;
        while(head!=null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

2.排序(快排

描述:
给定一个长度为 n 的数组,请你编写一个函数,返回该数组按升序排序后的结果。

import java.util.*;
public class Solution {
    public int[] MySort (int[] arr) {
        if(arr.length==0) return arr;
        QuickSort(arr,0,arr.length-1);
        return arr;
    }
    public void QuickSort(int[] arr,int L,int r){
        if(L<r){
            int par = partition(arr,L,r);
            QuickSort(arr,L,par);
            QuickSort(arr,par+1,r);
        }
    }
    public int partition(int[] arr,int L,int r){
        int temp = new Random().nextInt(r-L+1)+L;
        swap(arr,L,temp);
        int key = arr[L];
        while(L<r){
            while(L<r && arr[r]>=key)   r--;
            arr[L] = arr[r];
            while(L<r && arr[L]<=key)   L++;
            arr[r] = arr[L];
        }
         arr[L] = key;
        return L;
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
  • 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

归并排序实现:

import java.util.*;


public class Solution {
   
    public int[] MySort (int[] arr) {
        if(arr.length==0) return arr;
        sort(arr,0,arr.length-1);
        return arr;
    }
    // 归并排序
    public void sort(int[] arr,int left,int right){
        if(left>=right) return;
        int mid = left +(right-left)/2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        merger(arr,left,mid,right);
    }
    public void merger(int[] arr,int left,int mid,int right){
        int[] res = new int[right-left+1];
        int k= 0, i=left, j=mid+1;
        while(i<=mid && j<=right){
           res[k++] = arr[i]<arr[j]?arr[i++]:arr[j++];
        }
        while(i<=mid){
            res[k++] = arr[i++];
        }
        while(j<=right){
            res[k++] = arr[j++];
        }
        for(int t=left;t<=right;t++)
            arr[t] = res[t-left];
    }
}
  • 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

3.设计LRU缓存结构

描述:
设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能:

  1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  2. get(key):如果关键字 key 存在于缓存中,则返回key对应的value值,否则返回 -1 。
  3. set(key, value):将记录(key, value)插入该结构,如果关键字 key 已经存在,则变更其数据值 value,如果不存在,则向缓存中插入该组 key-value ,如果key-value的数量超过capacity,弹出最久未使用的key-value
import java.util.*;
public class Solution {
    int cap;
    HashMap<Integer,Node> map;
    Node head,tail;
    class Node{
        int k,v;
        Node pre=null;
        Node next = null;
        Node(int k,int v){
            this.k = k;
            this.v = v;
        }
    }
    public Solution(int capacity) {
         this.cap = capacity;
         map = new HashMap<>();
    }

    public int get(int key) {
         if(!map.containsKey(key)) return -1;
         update(key);
         return map.get(key).v;
    }

    public void set(int key, int value) {
         if(map.containsKey(key)){
             map.get(key).v = value;
             update(key);
             return;
         }else{
             if(map.size()==cap){
                 map.remove(tail.k);
                 tail = tail.pre;
                 tail.next = null;
             }
             Node t = new Node(key,value);
             if(head==null){
                 head = t;
                 tail = t;
             }else{
                 t.next = head;
                 head.pre = t;
                 head = t;
             }
             map.put(key,t);
         }
    }
    public void update(int key){
        Node t = map.get(key);
        if(t!=head){
            if(t==tail){
                tail = tail.pre;
                tail.next = null;
            }else{
                t.pre.next = t.next;
                t.next.pre = t.pre;
            }
            t.next = head;
            head.pre = t;
            head = t;
        }
    }
}
  • 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
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

4.实现二叉树的先序、中序、后序

描述:
给定一棵二叉树,分别按照二叉树先序,中序和后序打印所有的节点。
要求:空间复杂度 O(n),时间复杂度 O(n)

import java.util.*;
public class Solution {
    ArrayList<Integer> list1 = new ArrayList<>();
    ArrayList<Integer> list2 = new ArrayList<>();
    ArrayList<Integer> list3 = new ArrayList<>();
    public int[][] threeOrders (TreeNode root) {
        search(root);
        int[][] res = new int[3][list1.size()];
        for(int i=0;i<list1.size();i++){
            res[0][i] = list1.get(i);
            res[1][i] = list2.get(i);
            res[2][i] = list3.get(i);
        }
        return res;
    }
    public void search(TreeNode root){
        if (root==null)  return ;
        list1.add(root.val);
        search(root.left);
        list2.add(root.val);
        search(root.right);
        list3.add(root.val);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

5.最小的K个数

描述:
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(input);
        for(int i=0;i<k;i++)
            list.add(input[i]);
        return list;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

6.求二叉树的层序遍历

描述:
给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while(!que.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int len = que.size();
            for(int i=0;i<len;i++){
                TreeNode temp = que.poll();
                list.add(temp.val);
                if(temp.left!=null)
                    que.add(temp.left);
                if(temp.right!=null)
                    que.add(temp.right);
            }
            res.add(list);
        }
       return res; 
    }
}
  • 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

7.寻找第K大

描述
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        
        Arrays.sort(a);
        return a[n-K];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

快排思路:

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return QuickSort(a,0,n-1,K);
    }
    public int QuickSort(int[] arr, int L,int R, int K){
        int p = partition(arr,L,R);
        if(p==arr.length-K)  return arr[p];
        else if(p>arr.length-K) return QuickSort(arr,L,p-1,K);
        else
            return QuickSort(arr,p+1,R,K);
    }
    public int partition(int[] arr, int L,int R){
        int key = arr[L];
        while(L<R){
            while(L<R && arr[R]>=key)  R--;
            arr[L] = arr[R];
            while(L<R && arr[L]<=key) L++;
            arr[R] = arr[L];
        }
        arr[L] = key;
        return L;
    }
}
  • 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

8.两数之和

给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到

import java.util.*;


public class Solution {
    public int[] twoSum (int[] numbers, int target) {
        int[] res = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<numbers.length;i++){
            if(!map.containsKey(target-numbers[i]))
                map.put(numbers[i],i+1);
            else{
                res[0] = map.get(target-numbers[i]);
                res[1] = i+1;
            }
                
        }
        return res;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

9.合并两个排序的链表

输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list2==null || list1==null)  
            return list2==null?list1:list2;
        
        ListNode temp = new ListNode(-10002);
        ListNode head = temp;
        while(list2!=null && list1!=null){
            if(list1.val<=list2.val){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1==null?list2:list1;
        return head.next;
    }
}
  • 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

10.用两个栈实现队列

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

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.empty()){
            while(!stack1.empty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/937414
推荐阅读
相关标签
  

闽ICP备14008679号