牛客刷题——剑指offer(第五期)

王同学要努力

发布于 2022-12-21 20:12:20

2440

发布于 2022-12-21 20:12:20

文章被收录于专栏：https://blog.csdn.net/xiahttps://blog.csdn.net/xia

💟💟前言 🥇作者简介：友友们大家好，我是你们的小王同学😗😗 🥈个人主页：小王同学🚗 🥉 系列专栏：牛客刷题专栏📖 📑 推荐一款非常火的面试、刷题神器👉 牛客网 今天给大家带来的刷题系列是： 剑指offer 链接：👉 剑指offer

里面有非常多的题库跟面经知识真的非常良心了！！

JZ28 对称的二叉树🍨

JZ对称的二叉树

题目描述🍨

解题思路🍨

二叉树对称的要求满足：

两棵树的根节点相同
两颗子树的左右子树分别对称
a的左子树与b的左子树的值对应相等
a的右子树的与b的右子树的值对应相等

我们可以定义一个check方法来检查两颗子树是否满足对称条件~

代码详解🍨

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
     return  cheack(pRoot,pRoot);
        
        
    }
    boolean cheack(TreeNode a,TreeNode b) {
        if(a==null && b==null) return true;
        if(a==null||b==null) return false;
        if(a.val!=b.val) return false;
        return cheack(a.left,b.right)&cheack(a.right,b.left);
        
        
    }   
}

过啦~~

JZ38 字符串的排列🍨

JZ38 字符串的排列

题目描述🍨

解题思路🍨

一道比较经典的dfs 回溯完了记得剪枝~

代码详解🍨

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> list=new ArrayList<>();
        StringBuilder sub= new StringBuilder();
        char strs[]=str.toCharArray();
        Arrays.sort(strs);
        dfs(list,sub,strs,0,new boolean[strs.length]);
        return list; 
        
    }
    
    void dfs(ArrayList<String> list,StringBuilder sub, char[]strs,int index,boolean[]vis){
        if(index==strs.length){
            list.add(sub.toString());
            return ;
            
        }
        for(int i=0;i<strs.length;i++){
            if(i>0 && strs[i-1]==strs[i]&&!vis[i-1]||vis[i])continue;
            sub.append(strs[i]);
            vis[i]=true; //用过的字符 标记为true
            dfs(list,sub,strs,index+1,vis);
            vis[i]=false;
            sub.deleteCharAt(index);
        }
        

    }
}

题目描述🍨

JZ50 第一个只出现一次的字符🍨

JZ50 第一个只出现一次的字符

解题思路🍨

1.根据字符串的api idexOf 跟lastindexOf 就是字符串第一次出现的索引跟最后一次出现的索引如果是同一个数证明出现了一次 2.还有一种办法是用一个哈希来存遍历完了次数++ 如果最后次数=1就是出现一次的字符！ 这道题可以两种方法来做

代码详解🍨

方法1：

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int len=str.length();
        for(int i=0;i<len;i++){
            char ch=str.charAt(i);
            if(str.lastIndexOf(ch)==str.indexOf(ch))
            {
                return i;
            }
        }
        return -1;
        
        
    }
}

方法2：

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int len=str.length();
        int map[]=new int[256];
        for(int i=0;i<len;i++){
            map[str.charAt(i)]++;
        }
        for(int i=0;i<len;i++){
            if( map[str.charAt(i)]==1){
                return i;
            }
        }
        
        return -1;
        
    }
}