牛客网算法——名企高频面试题143题（7）

题目描述

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。 

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 完全二叉树的节点数
 * @Description TODO
 * @Date 2020/12/15 14:08
 * @Created by xjl
 */
public class 完全二叉树的节点数 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    /**
     * @description TODO 这样的方式的是的将会是时间复杂度是o(n) 不满足题目的要求
     * @param: head
     * @date: 2020/12/15 14:16
     * @return: int
     * @author: xjl
    */
    public int nodeNum(TreeNode head) {
        if (head == null) return 0;
        int l = nodeNum(head.left);
        int r = nodeNum(head.right);
        return l + r + 1;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);

        int res = nodeNum(root);
        System.out.println(res);
    }
}

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

package 名企高频面试题143;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Classname 扑克牌顺子
 * @Description TODO
 * @Date 2020/12/15 14:23
 * @Created by xjl
 */
public class 扑克牌顺子 {
    /**
     * @description TODO 使用的是排序数组 然后判断0的个数，在是否有多余0的次数
     * @param: numbers
     * @date: 2020/12/15 14:26
     * @return: boolean
     * @author: xjl
     */
    public boolean isContinuous(int[] numbers) {
        if (numbers.length == 0) return false;
        Arrays.sort(numbers);
        int num = 0;
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] == 0) {
                num++;
            } else {
                if (numbers[i + 1] == numbers[i]) {
                    return false;
                }
                if (numbers[i + 1] != numbers[i] + 1) {
                    num -= numbers[i + 1] - numbers[i] - 1;
                }
            }
        }
        return num >= 0;
    }

    @Test
    public void test() {
        boolean res = isContinuous(new int[]{0, 0, 1, 0, 1});
        System.out.println(res);
    }
}

题目描述

给定一个矩阵，矩阵内所有数均为非负整数。

求一条路径，该路径上所有数是递增的。

这个路径必须满足以下条件：

1、对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。

2、你不能走重复的单元格。即每个格子最多只能走一次。

package 复现代码;

import org.junit.Test;

import java.util.ArrayList;

/**
 * @Classname 矩阵顺时针
 * @Description TODO
 * @Date 2020/12/8 10:30
 * @Created by xjl
 */
public class 矩阵顺时针 {

    @Test
    public void test() {
        int[] arr = printMartix(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}});
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public int[] printMartix(int[][] martix) {
        //判断矩阵的安全
        int row = martix.length;
        if (row = 0 && nx < row && ny >= 0 && ny < colum && !vis[nx][ny]) {
                x = nx;
                y = ny;
            } else {
                dis = (dis + 1) % 4;
                nx = x + dx[dis];
                ny = y + dy[dis];
                x = nx;
                y = ny;
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

题目描述

现在有一个没有重复元素的整数集合S，求S的所有子集 注意： 你给出的子集中的元素必须按升序排列 给出的解集中不能出现重复的元素

package 复现代码;

/**
 * @Classname 矩阵中的最长递增路径
 * @Description TODO
 * @Date 2020/12/15 16:34
 * @Created by xjl
 */
public class 矩阵中的最长递增路径 {

    int[][] dp;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    int row, cloum;

    public int length(int[][] matrix) {
        row = matrix.length;
        if (row == 0) return 0;
        cloum = matrix[0].length;
        dp = new int[row][cloum];
        int max = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cloum; j++) {
                max = Math.max(max, dfs(matrix, i, j));
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int x, int y) {
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        //当前的状态
        dp[x][y] = 1;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < row && ny >= 0 && ny < cloum && matrix[nx][ny] > matrix[x][y]) {
                dp[x][y] = Math.max(dp[x][y], 1 + dfs(matrix, nx, ny));
            }
        }
        return dp[x][y];
    }
}

39.组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II

解数独

单词搜索

N皇后

分割回文串

二进制手表

200. 岛屿数量

package 名企高频面试题143;

/**
 * @Classname 岛屿III
 * @Description TODO
 * @Date 2020/12/16 10:40
 * @Created by xjl
 */
public class 岛屿III {
    boolean[][] vis;
    int row, cloum;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    public int solve(char[][] grid) {
        row = grid.length;
        if (row == 0) return 0;
        cloum = grid[0].length;
        vis = new boolean[row][cloum];
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cloum; j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j, vis);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int x, int y, boolean[][] vis) {
        vis[x][y]=true;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && ny >= 0 && nx < row && ny < cloum && !vis[nx][ny] && grid[nx][ny] == '1') {
                dfs(grid, nx, ny, vis);
            }
        }
    }

}