面试经典150题(88-89)

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

leetcode 150道题 计划花两个月时候刷完,今天(第四十四天)完成了2道(88-89)150:

88.(22. 括号生成) 题目描述:

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

第一版(没通过,我想法是 ()的全排列然后找出来符合的并且去重。。超时了)

class Solution {
    List<String> res=new ArrayList();
    Set<String> set=new HashSet();
    public List<String> generateParenthesis(int n) {
        if(n<1){
            return res;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<n;i++){
            sb.append("()");
        }
        boolean[] used=new boolean[n*2];
        generateCore(sb.toString(),new StringBuilder(),used);
        return res;
    }
    public void generateCore(String str,StringBuilder sb,boolean[] used){
        if(sb.length()==str.length()){ 
            if(check(sb.toString())&&set.add(sb.toString())){
                res.add(sb.toString()); 
            }
            return ;
        }
        for(int i=0;i<str.length();i++){
            if(used[i]){
                continue;
            }
            sb.append(str.charAt(i));
            used[i]=true;
            generateCore(str,sb,used);
            used[i]=false;
            sb.deleteCharAt(sb.length()-1);
        }
    }

    public boolean check(String str){
        Stack<Character> stack=new Stack();
        for(char ch:str.toCharArray()){
            if(ch=='('){
                stack.push(ch);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

第二版(看了解题)

class Solution {
    List<String> res=new ArrayList();
    public List<String> generateParenthesis(int n) {
        if(n<1){
            return res;
        }
        generateCore(new StringBuilder(),n,n);
        return res;
    }
    public void generateCore(StringBuilder sb,int left,int right){
        //左边和右边剩余的括号数都等于 0 的时候结算。
        if(left==0&&right==0){ 
            res.add(sb.toString());
            return ;
        }
        //产生左分支的时候,只看当前是否还有左括号可以使用;
        if(left>0){
            sb.append("(");
            generateCore(sb,left-1,right);
            sb.deleteCharAt(sb.length()-1);
            
        }
        //产生右分支的时候,还受到左分支的限制,
        //右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候
        if(right>0&&right>left){
            sb.append(")");
            generateCore(sb,left,right-1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

89.(79. 单词搜索)题目描述:

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

第一版(没超时,但是效率垫底,还没来得及看解题。。)

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if(board[i][j]==word.charAt(0)){
                    boolean[][] used=new boolean[board.length][board[0].length];
                    if(dfs(board,word,i,j,new StringBuilder(),used))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, String word,int mIndex,int nIndex,StringBuilder sb,boolean[][] used) {
        int m=board.length;
        int n=board[0].length;
        if(mIndex<0||mIndex>=m){
            return false;
        }
        if(nIndex<0||nIndex>=n){
            return false;
        }
        if(used[mIndex][nIndex]){
            return false;
        }
        sb.append(board[mIndex][nIndex]);
        used[mIndex][nIndex]=true;
        if(sb.length()>word.length()){
            sb.deleteCharAt(sb.length()-1);
            used[mIndex][nIndex]=false;
            return false;
        }else if(sb.length()==word.length()){
            if(word.equals(sb.toString())){
                sb.deleteCharAt(sb.length()-1);
                used[mIndex][nIndex]=false;
                return true;
            }else{
                sb.deleteCharAt(sb.length()-1);
                used[mIndex][nIndex]=false;
                return false;
            }
        }else{
            if(!word.substring(0,sb.length()).equals(sb.toString())){
                sb.deleteCharAt(sb.length()-1);
                used[mIndex][nIndex]=false;
                return false;
            }
        }
        
        boolean flag=dfs(board, word, mIndex + 1, nIndex, sb, used) ||
                dfs(board, word, mIndex - 1, nIndex, sb, used) ||
                dfs(board, word, mIndex, nIndex + 1, sb, used) ||
                dfs(board, word, mIndex, nIndex - 1, sb, used);
        if(!flag){
            sb.deleteCharAt(sb.length()-1);
            used[mIndex][nIndex]=false;
        }
        return flag;
    }
}

难啊!!!咋这么难这块。。。后面还有动态规划我咋办。。

加油吧,早日跳槽!!!

-----2024.01.18 看了一下 89.(79. 单词搜索)的解题,发现不需要用 String Builder 去记录遍历的过的字符合只需要每次去将当前遍历和要搜索的对比就行。改了一下效率立马就上去。。

第二版(看了解题)

class Solution {
    public boolean exist(char[][] board, String word) {
         boolean[][] used=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if(board[i][j]==word.charAt(0)){
                    if(dfs(board,word,i,j,0,used))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board, String word,int mIndex,int nIndex,int index,boolean[][] used) {
        if(index>=word.length()){
            return true;
        }
        int m=board.length;
        int n=board[0].length;
        if(mIndex<0||mIndex>=m){
            return false;
        }
        if(nIndex<0||nIndex>=n){
            return false;
        }
        if(used[mIndex][nIndex]){
            return false;
        }
      
        if(board[mIndex][nIndex]!=word.charAt(index))
        {
            return false;
        }
        used[mIndex][nIndex]=true;
        boolean flag=dfs(board, word, mIndex + 1, nIndex, index+1, used)||
        dfs(board, word, mIndex - 1, nIndex, index+1, used)||
        dfs(board, word, mIndex, nIndex + 1, index+1, used)||
        dfs(board, word, mIndex, nIndex - 1, index+1, used);
        if(flag){
            return flag;
        }
        used[mIndex][nIndex]=false;
        return flag;
    }
}

真的牛皮,今天太累了偷懒一天!!!文章来源地址https://www.toymoban.com/news/detail-801291.html

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

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

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

相关文章

  • 经典面试题:玩家进游戏场地分配号码、判断括号是否闭合、提取回文串字符的分析和 php 程序实现 - 经典数据结构面试

        给定一长串字母和符号,里面有三种括号包括([{}])这些,需要判断这三种括号必须是配对的。即这三类括号要么不出现,要出现必须是先出现左边的括号,然后出现右边的,中间括号可以嵌套。     定义一个字符对应关系数组,初始化一个数组栈。所以进入的左边符号入

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

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

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

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

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

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

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

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

    2024年02月13日
    浏览(83)
  • 【数据结构与算法】之多指针算法经典问题

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

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

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

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

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

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

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

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

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

    2024年04月28日
    浏览(63)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包