leetcode 150道題 計(jì)劃花兩個(gè)月時(shí)候刷完，今天（第四十四天）完成了2道(88-89)150：

88.(22. 括號(hào)生成) 題目描述：

數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]

第一版（沒通過，我想法是 （）的全排列然后找出來符合的并且去重。。超時(shí)了）

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){
        //左邊和右邊剩余的括號(hào)數(shù)都等于 0 的時(shí)候結(jié)算。
        if(left==0&&right==0){ 
            res.add(sb.toString());
            return ;
        }
        //產(chǎn)生左分支的時(shí)候，只看當(dāng)前是否還有左括號(hào)可以使用；
        if(left>0){
            sb.append("(");
            generateCore(sb,left-1,right);
            sb.deleteCharAt(sb.length()-1);
            
        }
        //產(chǎn)生右分支的時(shí)候，還受到左分支的限制，
        //右邊剩余可以使用的括號(hào)數(shù)量一定得在嚴(yán)格大于左邊剩余的數(shù)量的時(shí)候
        if(right>0&&right>left){
            sb.append(")");
            generateCore(sb,left,right-1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

89.（79. 單詞搜索）題目描述：

給定一個(gè) m x n 二維字符網(wǎng)格 board 和一個(gè)字符串單詞 word 。如果 word 存在于網(wǎng)格中，返回 true ；否則，返回 false 。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。
輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true

第一版（沒超時(shí)，但是效率墊底，還沒來得及看解題。。）

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;
    }
}

難啊?。。≌@么難這塊。。。后面還有動(dòng)態(tài)規(guī)劃我咋辦。。

加油吧，早日跳槽?。。?/p>

-----2024.01.18 看了一下 89.（79. 單詞搜索）的解題，發(fā)現(xiàn)不需要用 String Builder 去記錄遍歷的過的字符合只需要每次去將當(dāng)前遍歷和要搜索的對(duì)比就行。改了一下效率立馬就上去。。

第二版（看了解題）

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;
    }
}

真的牛皮，今天太累了偷懶一天?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-801291.html

到了這里，關(guān)于面試經(jīng)典150題(88-89)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！