牛客网面试高频题top100（11~20）_牛客前100

**

牛客网面试高频题top100（11~20 java实现）

**

11.跳台阶

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

public class Solution {
    public int jumpFloor(int target) {
        int c1 = 1,c2 = 2;
        if(target<3) return target;
        int c3 = 0;
        for(int i=3;i<=target;i++){
            c3 = c1+c2;
            c1 = c2;
            c2 = c3;
        }
        return c3;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

12.链表中的节点每K个一组翻转

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

import java.util.*;

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

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while(true){
            ListNode start = head;
            for(int i=1;i<k && head!=null;i++)  head = head.next;
            if(head==null) break;
            ListNode next = head.next;
            head.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            head = next;
        }
        return dummy.next;
    }
    public ListNode reverse(ListNode node){
        ListNode pre = null;
        ListNode cur = null;
        while(node!=null){
            cur = node.next;
            node.next = pre;
            pre = node;
            node = cur;
        }
        return pre;
    }
}
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

13.连续子数组最大和

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
         int[] dp = new int[array.length];
         dp[0] = array[0];
        int max = dp[0];
         for(int i=1;i<array.length;i++){
             dp[i] = Math.max(dp[i-1]+array[i], array[i]);
             max = Math.max(max,dp[i]);
         }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

空间优化后：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
         int temp = array[0];
         int max = temp;
         for(int i=1;i<array.length;i++){
             temp = Math.max(temp+array[i], array[i]);
             max = Math.max(max,temp);
         }
         return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11

14.最长无重复子数组

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

import java.util.*;
public class Solution {
    public int maxLength (int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        int i=0,end = 0,max=0;
        while(end<arr.length){
            if(!set.contains(arr[end])){
                set.add(arr[end]);
                max = Math.max(max,end-i+1);
                end++;
            }else{
                set.remove(arr[i]);
                i++;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

15.判断链表中是否有环

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null)  return false;
        ListNode low = head;
        ListNode fast = head;
        while(low!=null ){
            if(fast==null  || fast.next==null)  break;
            low = low.next;
            fast = fast.next.next;
            if(low==fast){
                return true;
            }
        }
        return false;
    }
}
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

16.合并两个有序数组

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int t=0,j=0,k =0;
        int a[] = new int[m];
        for(int i=0;i<m;i++)
            a[i] = A[i];
        while(t<m && j<n){
            A[k++] = a[t]<=B[j]? a[t++]:B[j++];
        }
        while(t<m)
            A[k++] = a[t++];
        while(j<n)
            A[k++] = B[j++];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

17.链表中环的入口结点

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        boolean flag = false;
        while(slow!=null && fast.next!=null && fast!=null){
            slow = slow.next;
            fast = fast.next.next;
            if( fast==null) break;
            if(slow==fast){
                flag = true;
                break;
            }
        }
        if(flag==false)  return null;
        while(pHead!=slow){
            slow = slow.next;
            pHead = pHead.next;
        }
        return pHead;
            
                
    }
}
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

18.有效括号序列

给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。

import java.util.*;


public class Solution {
    public boolean isValid (String s) {
        if(s.length()==0)  return true;
        char[] cs = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<cs.length;i++){
            if(stack.empty())
                stack.push(cs[i]);
            else{
                String str = "";
                str += stack.peek();
                str += cs[i];
                if(str.equals("()") || str.equals("{}") ||str.equals("[]") )
                    stack.pop();
                else
                    stack.push(cs[i]);
            }
        }
        if(stack.empty())  return true;
        return false;
    }
    
}
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

19.删除链表的倒数第n个节点

import java.util.*;

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

public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int count = 0;
        while(head!=null){
            count += 1;
            head = head.next;
        }
        head = dummy.next;
        ListNode pre = dummy;
        int i= 0;
        while(i!=count-n){
            pre = head;
            head = head.next;
            i++;
        }
        pre.next = head.next;
        return dummy.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

20.大数加法

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

import java.util.*;


public class Solution {
   
    public String solve (String s, String t) {
        int i=s.length()-1;
        int j=t.length()-1;
        StringBuilder res = new StringBuilder();
        int more = 0;
        while(i>=0 || j>=0){
            int si = i>=0?s.charAt(i)-'0':0;
            int ti = j>=0?t.charAt(j)-'0':0;
            more += si+ti;
            res.append(more%10);
            more /= 10;
            i--;
            j--;
        }
        
        if(more>0) res.append(more);
        return res.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24