面试经典150题(78-81)

这篇具有很好参考价值的文章主要介绍了面试经典150题(78-81)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode 150道题 计划花两个月时候刷完,今天(第三十六天)完成了4道(78-81)150:

78.(230. 二叉搜索树中第K小的元素)题目描述:

给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。

第一版(铭记!!二叉搜索树的中序遍历为递增的)

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack=new Stack();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(--k==0){
                return root.val;
            }
            root=root.right;
        }
        return -1;
    }
}

79.(98. 验证二叉搜索树)题目描述:

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

第一版(我第一反应就是递归,但是递归了好久没弄出来,就用中序遍历为递增的去判断了,算是个兜底办法)

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        Integer preNum=null;
        Stack<TreeNode> stack=new Stack();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(preNum!=null&&root.val<=preNum){
                return false;
            }
            preNum=root.val;
            root=root.right;
        }
        return true;
    }
}

第二版(看了解题,递归是真的牛,但是这个我也应该能想出来的。。但是没有)

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root,long min,long max) {
        if(root==null){
            return true;
        }
        if(root.val<=min||root.val>=max){
            return false;
        }
        return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max);
    }
}

80.(200. 岛屿数量)题目描述:

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
输入:grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出:3

第一版(这题我是真不会,看了解题,怎么说解题无敌!!)

class Solution {
    public int numIslands(char[][] grid) {
        // 卧槽解题太叼了
        int m=grid.length;
        int n=grid[0].length;
        int resNum=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    resNum++;
                    dfs(grid,i,j);
                }
            }
        }
        return resNum;
    }

    public void dfs(char[][] grid,int l,int r){
        int m=grid.length;
        int n=grid[0].length;
        if(l<0||r<0||l>=m||r>=n||grid[l][r]=='0'){
            return ;
        }
        grid[l][r]='0';
        dfs(grid,l,r-1);
        dfs(grid,l,r+1);
        dfs(grid,l-1,r);
        dfs(grid,l+1,r);
    }
}

81.(130. 被围绕的区域)题目描述:

给你一个 m x n 的矩阵 board ,由若干字符 'X''O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O''X' 填充。

第一版(有了上一题经验,在做这一题时候,确实有一点点思路,但是还是没转过来。。还是那句话解题真牛!!!)

class Solution {
    public void solve(char[][] board) {

        int m=board.length;
        int n=board[0].length;
        int[][] flag=new int[m][n];
        // 标记
        for(int i=0;i<m;i++){
           
            if(board[i][n-1]=='O'){
                dfs(flag,board,i,n-1);
            }
            
             if(board[i][0]=='O'){
                dfs(flag,board,i,0);
            }
        }
        for(int i=0;i<n;i++){
            if(board[m-1][i]=='O'){
                dfs(flag,board,m-1,i);
            }
            if(board[0][i]=='O'){
                dfs(flag,board,0,i);
            }
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'&&flag[i][j]==0){
                    board[i][j]='X';
                }
            }
        }


    }
     public void dfs(int[][] flag,char[][] grid,int l,int r){
        int m=grid.length;
        int n=grid[0].length;
        if(l<0||r<0||l>=m||r>=n||grid[l][r]=='X'||flag[l][r]==1){
            return ;
        }
        flag[l][r]=1;
        dfs(flag,grid,l,r-1);
        dfs(flag,grid,l,r+1);
        dfs(flag,grid,l-1,r);
        dfs(flag,grid,l+1,r);
    }
}

今天这图这一块真的我看了都害怕。。。是一点想法都没有。。图咋这么难!!!文章来源地址https://www.toymoban.com/news/detail-785912.html

到了这里,关于面试经典150题(78-81)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】之多指针算法经典问题

    本文为 【数据结构与算法】多指针算法经典问题 相关介绍,下边将对 链表反转 (包含 迭代反转链表 、 递归反转 、 头插法反转 ), 双指针-快慢指针 (包含 寻找单向无环链表的中点 、 判断单向链表是否有环及找环入口 ), 双指针-左右指针 (包含 两数之和 、 二分查

    2024年02月03日
    浏览(54)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(69)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 【数据结构】盘点那些经典的 [哈希面试题]【哈希切割】【位图应用】【布隆过滤器】(10)

    前言 大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《

    2024年02月04日
    浏览(53)
  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(36)
  • 头歌数据结构实训参考---十大经典排序算法

    可通过 目录 快速查阅对应排序算法

    2024年02月04日
    浏览(62)
  • 【数据结构】单链表经典算法题的巧妙解题思路

    目录 题目 1.移除链表元素 2.反转链表 3.链表的中间节点 4.合并两个有序链表 5.环形链表的约瑟夫问题 解析 题目1:创建新链表 题目2:巧用三个指针 题目3:快慢指针 题目4:哨兵位节点 题目5:环形链表   介绍完了单链表,我们这次来说几个经典的题目,本篇的题目衔接下一

    2024年04月28日
    浏览(54)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(92)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包