牛客网面试高频题top100（61~70）_牛客网算法高频面试题

面试高频算法题top100（61~70）java实现

61.删除有序链表中重复的元素（二）

import java.util.*;

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

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        while(head!=null){
            ListNode next = head.next;
            if(next==null) break;
            if(head.val==next.val){
                while(next!=null && head.val==next.val)
                    next = next.next;
                pre.next = next;
                head = next;
            }else{
                pre = head;
                head = 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

62.把字符串转换成整数

import java.util.*;


public class Solution {
    
    public int StrToInt (String s) {
        s = s.trim();
        if(s.length()<1) return 0;
        int i=0;
        int sign = 1;
        long num=0;
        if(s.charAt(i)=='+')
            i++;
        else if(s.charAt(i)=='-'){
            sign = -1;
            i++;
        }
        while(i<s.length()){
            if(Character.isDigit(s.charAt(i))){
                while(i<s.length() && Character.isDigit(s.charAt(i))){
                    num = num*10 + s.charAt(i)-'0';
                    if(sign==1 && num>=Integer.MAX_VALUE){
                        return Integer.MAX_VALUE;
                    }else if(sign==-1 && -num<=Integer.MIN_VALUE)
                        return Integer.MIN_VALUE;
                    i++;
                }
            }else
                break;
        }
        return (int)num*sign;
    }
}
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

63.反转数字

import java.util.*;


public class Solution {
    
    public int reverse (int x) {
        int num=0,temp=0;
        while(x!=0){
            num = temp*10 + x%10;
            if((num-x%10)/10!=temp)
                    return 0;
            temp = num;
            x /= 10;
        }
        return num;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

64.矩阵元素查找

已知一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        int i=n-1,j=0;
        int[] res = new int[2];
        if(n==0 || m==0) return res;
        while(i>=0 && j<m){
            if(mat[i][j]==x){
                res[0] = i;
                res[1] = j;
                break;
            }else if(mat[i][j]>x)
                i--;
            else
                j++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

65.缺失的第一个正整数

给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数

import java.util.*;


public class Solution {
    public int minNumberDisappeared (int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i:nums)
            map.put(i,1);
        int j=1;
        while(j<=nums.length+1){
            if(map.getOrDefault(j,0)>0)
                j++;
            else
                break;
        }
        return j;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

空间复杂度优化为O(1)：

import java.util.*;
public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        //遍历数组
        for(int i = 0; i < n; i++) 
            //负数全部记为n+1
            if(nums[i] <= 0) 
                nums[i] = n + 1;
        for(int i = 0; i < n; i++)
            //对于1-n中的数字
            if(Math.abs(nums[i]) <= n) 
                //这个数字的下标标记为负数
                nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]); 
        for(int i = 0; i < n; i++)
            //找到第一个元素不为负数的下标
            if(nums[i] > 0)
                return i + 1;
        return n + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

66.链表的奇偶重排

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

import java.util.*;

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

public class Solution {
    
    public ListNode oddEvenList (ListNode head) {
        if(head==null) return null;
        ListNode J = head;
        ListNode res = J;
        head = head.next;
        if(head==null) return J;
        ListNode O = head;
        ListNode temp = O;
        head = head.next;
        int count = 3;
        while(head!=null){
            if(count%2!=0){
                J.next = head;
                J = J.next;
            }else{
                O.next = head;
                O = O.next;
            }
            count ++;
            head = head.next;
        }
        J.next = temp;
        O.next = null;
        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
32
33
34
35
36
37
38
39
40

67.二叉树中的最大路径和

二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点

import java.util.*;

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

public class Solution {
    int sum = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        search(root);
        return sum;
    }
    public int search(TreeNode root){
        if(root==null) return 0;
        int left1 = Math.max(0,search(root.left));
        int right1  = Math.max(0,search(root.right));
        int temp = root.val+left1+right1;
        sum = Math.max(temp,sum);
        return Math.max(root.val+left1,root.val+right1);
    }
}
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

68.对称的二叉树

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

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null)
            return true;
       Queue<TreeNode> que = new LinkedList<>();
        que.add(pRoot);
        que.add(pRoot);
        while(!que.isEmpty()){
            TreeNode t1 = que.poll();
            TreeNode t2 = que.poll();
            if(t1==null && t2==null)
                continue;
            if(t1==null || t2==null)
                return false;
            if(t1.val!= t2.val)
                return false;
            que.add(t1.left);
            que.add(t2.right);
            que.add(t1.right);
            que.add(t2.left);
        }
        return true;
    }
}
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

69.括号生成

import java.util.*;


public class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        deal(n,0,0,"");
        return res;
    }
    public void deal(int n,int left,int right,String str){
        if(left==n && right==n) {
            res.add(str);
            return;
        }
        if(left<n)
            deal(n,left+1,right,str+'(');
        if(right<left)
            deal(n,left,right+1,str+')');
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

70.顺时针旋转矩阵

有一个nxn整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
给定一个nxn的矩阵，和矩阵的阶数n,请返回旋转后的nxn矩阵。

空间复杂度优化：

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        int[][] res = new int[n][n];
        for(int j=0;j<n;j++){
            for(int i=n-1;i>=0;i--)
                res[j][n-i-1] = mat[i][j];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12