牛客网面试高频题top100（41~50）_输入一个01矩阵,1代表是草地

面试高频算法题top100（41~50）java实现

41.岛屿数量

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3(注：存储的01数据其实是字符’0’,‘1’)

import java.util.*;


public class Solution {
   
    public int solve (char[][] grid) {
        int sum = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    search(grid,i,j);
                    sum += 1;
                }
            }
        }
        
        return sum;
    }
    public void search(char[][] grid,int i,int j){
        if(i>=0 && i<grid.length && j>=0 && j<grid[0].length){
            if(grid[i][j]=='0') return;
            if(grid[i][j]=='1'){
                grid[i][j] = '0';
                search(grid,i+1,j);
                search(grid,i-1,j);
                search(grid,i,j+1);
                search(grid,i,j-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
26
27
28
29
30
31

42.二叉树的最大深度

求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。

import java.util.*;

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

public class Solution {
    public int maxDepth (TreeNode root) {
        if(root==null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

43.判断是否为回文字符串

给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。

import java.util.*;


public class Solution {
    public boolean judge (String str) {
        int len = str.length()-1;
        for(int i=0,j=len;i<=j;i++,j--){
            if(str.charAt(i)!=(str.charAt(j)))   return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

44.单链表的排序

给定一个节点数为n的无序单链表，对其按升序排序。

import java.util.*;

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

public class Solution {
    public ListNode sortInList (ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        Collections.sort(list);
        ListNode phead = new ListNode(-1);
        ListNode dummy = phead;
        for(int i:list){
            ListNode temp = new ListNode(i);
            phead.next = temp;
            phead = phead.next;
        }
        phead.next = null;
        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

45.判断是不是平衡二叉树

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null) return true;
        boolean b1 = IsBalanced_Solution(root.left);
        boolean b2 = IsBalanced_Solution(root.right);
        return b1 && b2 && Math.abs(height(root.left)-height(root.right))<2;
    }
    public int height(TreeNode root){
        if(root==null) return 0;
        return Math.max(height(root.left),height(root.right))+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

46.数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int time = 1;
        int tar = array[0];
        for(int i=1;i<array.length;i++){
            if(array[i]==tar)
                time ++;
            else{
                if(time!=0)
                    time--;
                else{
                    tar = array[i];
                    time = 1;
                }
            }
        }
        //再次验证
        int count = 0;
        for(int i:array){
            if(i==tar)
                count++;
        }
        if(count>array.length/2) return tar;
        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
26

47.矩阵的最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

import java.util.*;


public class Solution {
    public int minPathSum (int[][] matrix) {
        int hang= matrix.length,lie=matrix[0].length;
        int[][] dp = new int[hang][lie];
        dp[0][0] = matrix[0][0];
        for(int i=1;i<hang;i++)
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        for(int j=1;j<lie;j++)
            dp[0][j] = dp[0][j-1] + matrix[0][j];
        for(int i=1;i<hang;i++){
            for(int j=1;j<lie;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j];
            }
        }
        return dp[hang-1][lie-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

48.表达式求值

请写一个整数计算器，支持加减乘三种运算和括号。

import java.util.*;
public class Solution {
    public int solve (String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        char[] cs = s.toCharArray();
        Stack<Character> stack_fu = new Stack<>();
        Stack<Integer> stack_num = new Stack<>();
        stack_num.push(0);
        String str = "";
        for(int i=0;i<cs.length;i++){
            if(Character.isDigit(cs[i])){
                int u=0;
                int j=i;
                while(j<cs.length && Character.isDigit(cs[j]))
                    u = u*10 + cs[j++]-'0';
                stack_num.push(u);
                i = j-1;
            }else{
                if(cs[i]=='(' )
                    stack_fu.push(cs[i]);
                else if(cs[i]==')'){
                    while(!stack_fu.empty() && stack_fu.peek()!='('){
                        deal(stack_fu,stack_num);
                    }
                    stack_fu.pop();
                }else{
                    while(!stack_fu.empty() && stack_fu.peek()!='('){
                        if(map.get(cs[i])<=map.get(stack_fu.peek()))
                            deal(stack_fu,stack_num);
                        else
                            break;
                    }
                   
                    stack_fu.push(cs[i]);
                }
            }
        }
        while(!stack_fu.empty())
            deal(stack_fu,stack_num);
        return stack_num.pop();
    }
    public void deal(Stack<Character> stack_fu,Stack<Integer> stack_num){
        int num2 = stack_num.pop();
        int num1 = stack_num.pop();
        char c = stack_fu.pop();
        if(c=='+')
            stack_num.push(num1+num2);
        else if(c=='-')
            stack_num.push(num1-num2);
        else
            stack_num.push(num1*num2);
        
    }
}
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

49.字符串出现次数的TopK问题

给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
比如"ah1x"小于"ahb"，“231”<”32“

import java.util.*;
public class Solution {
    public String[][] topKstrings (String[] strings, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        ArrayList<String> map_key = new ArrayList<>();
        for(String s:strings)
            map.put(s,map.getOrDefault(s,0)+1);
        for(String kk:map.keySet())
            map_key.add(kk);
        Collections.sort(map_key,new Comparator<String>(){
            @Override
            public int compare(String s1,String s2){
                return map.get(s1)==map.get(s2)?s1.compareTo(s2):map.get(s2)-map.get(s1);
            
            }
        });
        String[][] res = new String[k][2];
        int count = 0;
        for(String kk:map_key){
            if(count<k){
                res[count][0] = kk;
                res[count][1] = String.valueOf(map.get(kk));
                count ++;
            }else
                break;
        }
        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

50.进制转换

给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。当 N 大于 10 以后， 应在结果中使用大写字母表示大于 10 的一位，如 ‘A’ 表示此位为 10 ， ‘B’ 表示此位为 11 。若 M 为负数，应在结果中保留负号。

import java.util.*;
public class Solution {
    public String solve (int M, int N) {
        StringBuilder str = new StringBuilder();
        String tar = "0123456789ABCDEF";
        int M1 = Math.abs(M);
        while(M1!=0){
            str.append(tar.charAt(M1%N));
            M1 /= N;
        }
        if(M<0) str.append('-');
        return str.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14